Link table operation

#include "stdafx.h" #include using namespace std; struct student {int data; struct student * next;}; // the linked list; two nodes which have the equal data struct student * CreateList (int count) {struct student * head = new struct student (); head-> next = NULL; struct student * pTemp = NULL; struct student * pCurrent = NULL; pCurrent = Head; for (int i = 0; i data = i; pcurrent-> next = Ptemp; pcurrent = pcurrent-> next;} pcurrent-> next = NULL; return head;} ​​// The linked list has a head node which has not data struct student * CreateRandomList (int count) {struct student * head = new struct student (); head-> next = NULL; struct student * ptemp = null; struct student * pcurrent = null; pcurrent = head; for (int i = 0; i data = rand (); pCurrent-> next = pTemp; pCurrent = pCurrent-> next;} pCurrent-> next = NULL; return head;} ​​void Print (struct student * head) {struct student * pTemp = head-> next; while (pTemp =! NULL) {cout << PTEMP-> Data << '/ t'; ptemp = ptemp-> next;} cout << endl;} // delete the node which data = para (data) Struct Student * Dellist (Struct Student * head, int data) {structure * pcurrent = head; struct student * Ptemp; // Assume &&

Calculate from left to right, // else there is error on pcurrent-> next-> data if pcurrent-> next is null while (pcurrent-> next! = null && pcurrent-> next-> data! = data) {pcurrent = Pcurrent-> next;}} (! Pcurrent-> next) {cout << "not all!";} Else {ptemp = pcurrent-> next; pcurrent-> next = ptemp-> next; delete ptemp; ptemp = NULL;} return head;} ​​struct student * InsList (struct student * head, int data) {struct student * pCurrent = head; // Assume && calculate from left to right, // else there is error on pCurrent-> next- > data if pcurrent-> Next is null while (pcurrent-> next! = null && pcurrent-> next-> data <= data) {pcurrent = pcurrent-> next;} strunt student * stu = new struct student (); stu-> data = data; stu-> next = pCurrent-> next; pCurrent-> next = stu; return head;} ​​struct student * RevList (struct student * head) {struct student * pPrev; struct student * pNext; struct student * pCurrent; pCurrent = head-> next; pPrev = NULL; while (! pCurrent-> next = NULL) {pNext = pCurrent-> next; pCurrent-> next = pPrev; pPrev = pCurrent; pCurrent = pNext;} pCurrent -> Next = pprev; head-> next = pcurrent; return head;} ​​// Revert Partial List // EX: 0, 1, 2, 3, 4, OFFSET = 3, and Then Output: 3, 2, 1, 0, 4 Struct Student * RevpartList (strunt news * off, struct student * offset) {strunt news * pprev; struct student * pnext;

struct student * pCurrent; pCurrent = head-> next; pPrev = offset-> next; while (pCurrent = offset!) {pNext = pCurrent-> next; pCurrent-> next = pPrev; pPrev = pCurrent; pCurrent = pNext;} pCurrent-> next = pPrev; head-> next = pCurrent; return head;} ​​struct student * SwapList (struct student * head, struct student * node1, struct student * node2) {struct student * pPrev1; struct student * pPrev2; struct student * pNode1; struct student * pNext2; struct student * pCurrent = head; int find = 0; while (! pCurrent-> next = NULL) {// Ensure pPrev1 is before pPrev2 if ((pCurrent-> next-> data = = NODE1-> DATA) || (pcurrent-> new-> data == node2-> data) {if (find == 0) {pprev1 = pcurrent; pnode1 = pcurrent-> next; find ;} else {pprev2 = Pcurrent; pnext2 = pcurrent-> next-> next; Find ;}}} f (find == 2) {Break;} pcurrent = pcurrent-> next;} if (find! = 2) {cout << "The input data aren't right << endl; return head; } If (pnode1 == pprev2) {// 2 nodes adjoin and node1 before node2 // swap from the first // before: 0-> 1 (pprev1) -> 2 (pnode1) -> 3-> 4 (PNEXT2) // after: 0-> 1 (pPREV1) -> 3-> 2 (pnode1) -> 4 (pnext2) pprev1-> next = pnode1-> next; pnode1->

Next-> next = pnode1; pnode1-> next = pnext2;} else {// 2 nodes aren't ad' / // swap from the first // before: 0-> 1 (pprev1) -> 2 (pnode1) -> 3-> 4-> 5 (PPREV2) -> 6-> 7 (pnext2) -> 8 // after: 0-> 1 (pprev1) -> 6-> 3-> 4-> 5 (pprev2) -> 2 (PNODE1) -> 7 (PNEXT2) -> 8 pprev1-> next = pprev2-> next; pprev2-> next-> next = pnode1-> next; pprev2-> next = pnode1; pnode1-> next = pNEXT2; Return Head;} ​​// Para: Head-> 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9 // Return: Head-> 2-> 1-> 4-> 3-> 6-> 5-> 8-> 7-> 9 struct student * SwapOddAndEvenNodes (struct student * head) {struct student * pPrev1; struct student * pNode1; struct student * pNext2; struct student * pCurrent = Head; while (pcurrent-> next-> next! = null) {// set the point1 = pcurrent-> next; pnext2 = pcurrent-> next-> next-> next; // swap odd and Even nodes pprev1-> next = pnode1-> next; pnode1-> next-> next = pnode1; pno de1-> next = pNext2; // Reset the pCurrent pCurrent = pCurrent-> next-> next;} return head;} ​​// Bubble sort void SortList (struct student * head) {struct student * p; struct student * pPrev; Struct student * pcur; struct student * pnext; // Because We can't get the total nodes, // We will compare all nodes in one time sort for (p = head-> next; p; p = p-> next ) {Bool exchange = false; for (pprev = head, pcur = pprev->

Next, pnext = pcur-> next; pnext;) {if (pcur-> data> pnext-> data) {pprev-> next = pnext; pcur-> next = pNext-> next; pnext-> next = pcur; Exchanged = true;} else {pcur = pcur-> next;} pprev = pprev-> next; pnext = pcur-> next;}}}}} // just combine Two lists struct student * Combinelist (Struct Student * Head2) {strunt news * p; for (p = head1; p-> next; p = p-> next); p-> next = head2-> next; return head1; RETURN HEAD1; } // good method /// 1. Sort the two list seperatly, and the time complexity: N (n-1) / 2 // 2. Merge the two list, and the time complexity: n n // so the time Complexity Totally: N (N-1) / 2 * 2 N N = N ^ 2 N // Bad Mehtod //// Bad Mehtod // Merge The Two List, And The Time Complexity: N N // 2. Sort The Two List seperatly, and the time Complexity: 2N (2N-1) / 2 // SO The Time Complexity Totally: 2N (2N-1) / 2 * 2 N N = 2N ^ 2 N // ITS Time Complexity Is More Than Above Method Struct Student * MergeList (struct student * head1, struct student * head2) {// Use head1 as head struct student * head = head1; struct student * p = head; // Skip the head which has not data struct student * p1 = head1 -> Next; Struct Student * p2 = head2-> next; while (p1 && p2) {if (p1-> data <= p2-> data) {p-> next = p1; p = p1; p1 = p1- > NEXT;

} Else {p-> next = p2; p = p2; p2 = p2-> next;}} P-> next = p1? P1: p2; // clean the head2 delete (head2); return head;} ​​void main () {struct student * head; struct student * head1; struct student * head2; struct student * stu; struct student * pNode1; struct student * pNode2; int data; head = CreateList (10); Print (head); char ch Do {cout << "please input what will you do." << endl; cout << "d for delete one node" << Endl; cout << "i for insert one node" << endl; cout << "R for reverse the link" << endl; cout << "p for partial reverse the link" << Endl; cout << "s for swip two nodes << endl; cout <<" o for swip even and odd Nodes << endl; cout << "M for merge two links << Endl; cout <<" q for quit "<< Endl; CIN >> CH; switch (ch) {case 'd': case 'd ': COUT << "Which one delete:"; cin >> data; head = d Ellist (head, data); cout << "Print the current link" << Endl; Print (HEAD); Break; Case 'i': Case 'i': cout << "please input insert node - data:" Cin >> Data; Head = InSlist (Head, Data); COUT << "Print The Current Link" << Endl; Print (HEAD); Break; Case 'R': Case 'R'

: Cout << "Reverse the link" << Endl; Head = revlist (head); Print (Head); Break; Case 'P': Case 'P': COUT << "Please Input The Revert Node Offset:"; Cin >> data; stu = head-> next; for (int i = 0; i next;} head = revpartList (Head, STU); Print (head); Break; Case 's': case 's': cout << "swap 2 node. please input 2 node - data:" << Endl; pnode1 = new struct student (); pnode2 = new strunt student (); cin >> Pnode1-> data; cin >> pnode2-> data; head = swaplist (head, pnode1, pnode2); cout << "Print the current link" << endl; print (head); break; case 'o': CASE 'o': cout << "swap odd and even nod" << Endl; Head = swapoddandevennodes (head); cout << "Print The Current Link" << Endl; Print (HEAD); Break; Case 'M': Case 'm': Head1 = Createrandomlist (5); Print (Head1); Head2 = CreateRandomlist (5); Print (Head2); cout << "sort The list head1 "<< Endl; Sortlist (HEAD1); Print (Head1); cout <<" sort the list head2 "<< endl; sortlist (head2); print <<"