Created
May 11, 2018 03:18
-
-
Save hyperion0201/1b44c8e64266ea49a5179ab087a64125 to your computer and use it in GitHub Desktop.
24 core functions about single linked list C++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include "SingleLinkedList.h" | |
| int CompareData(Data info1, Data info2) { | |
| if (info1.x == info2.x) return 0; | |
| else if (info1.x > info2.x) return 1; | |
| return -1; | |
| } | |
| void InitList(List& l) { | |
| l.pHead = l.pTail = NULL; | |
| } | |
| bool isEmptyList(List l) { | |
| if (l.pHead == NULL) return true; | |
| return false; | |
| } | |
| void PrintList(List l, const char* str) { | |
| Node* p = l.pHead; | |
| printf("%s:\t", str); | |
| while (p!=NULL) | |
| { | |
| printf("%d\t", p->info.x); | |
| p = p->pNext; | |
| } | |
| printf("\n"); | |
| } | |
| Node* CreateNode(Data info) { | |
| Node* p = new Node; | |
| if (p != NULL) { | |
| p->info = info; | |
| p->pNext = NULL; | |
| } | |
| else | |
| return p; | |
| } | |
| Node* getPointer(List l, Data info) { | |
| for (Node* p = l.pHead; p != NULL; p = p->pNext) | |
| { | |
| if (p->info.x == info.x) | |
| { | |
| return p; | |
| } | |
| } | |
| return NULL; | |
| } | |
| Node* getIndexPointer(List l, int index) { | |
| Node* p = l.pHead; | |
| int i = 0; | |
| while (p!=NULL && i<index) | |
| { | |
| p = p->pNext; | |
| i++; | |
| } | |
| return p; | |
| } | |
| int getNodeIndex(List l, Node* pNode) { | |
| if (isEmptyList(l) == true) return -1; | |
| Node* p = l.pHead; | |
| int i = 0; | |
| while (p!=NULL) | |
| { | |
| i++; | |
| p = p->pNext; | |
| if (p == pNode) return i; | |
| } | |
| return -1; | |
| } | |
| Node* getPreNode(List l, Node* pNode) { | |
| Node* p = l.pHead; | |
| while (p!=NULL && p->pNext!=pNode) | |
| { | |
| p = p->pNext; | |
| } | |
| return p; | |
| } | |
| void AddHead(List& l, Node* newNode) { | |
| if (isEmptyList(l) == true) { | |
| l.pHead = l.pTail = newNode; | |
| } | |
| else { | |
| newNode->pNext = l.pHead; | |
| l.pHead = newNode; | |
| } | |
| } | |
| Node* AddHead(List &l, Data info) { | |
| Node* newNode = CreateNode(info); | |
| if (newNode!=NULL) AddHead(l, newNode); | |
| return newNode; | |
| } | |
| void AddTail(List& l, Node* newNode) { | |
| if (isEmptyList(l) == true) { | |
| l.pHead = l.pTail = newNode; | |
| } | |
| l.pTail->pNext = newNode; | |
| l.pTail = newNode; | |
| } | |
| Node* AddTail(List& l, Data info) { | |
| Node* newNode = CreateNode(info); | |
| if (newNode != NULL) { | |
| AddTail(l, newNode); | |
| } | |
| return newNode; | |
| } | |
| void AddAfter(List& l, Node* q, Node* newNode) { | |
| if (q != NULL) | |
| { | |
| newNode->pNext = q->pNext; | |
| q->pNext = newNode; | |
| if (newNode->pNext == NULL) l.pTail = newNode; | |
| } | |
| } | |
| Node* AddAfter(List& l, Node* q, Data info) { | |
| Node* p = CreateNode(info); | |
| if (p != NULL) AddAfter(l, q, p); | |
| return p; | |
| } | |
| void AddBefore(List& l, Node* q, Node* newNode) { | |
| if (q != NULL) { | |
| if (q == l.pHead) AddHead(l, newNode); | |
| else | |
| { | |
| Node* pre = getPreNode(l, q); | |
| AddAfter(l, pre, newNode); // add newNode after pre node, mean pre-newNode-q | |
| } | |
| } | |
| } | |
| Node* AddBefore(List& l, Node* q, Data info) { | |
| Node* newNode = CreateNode(info); | |
| if (newNode != NULL) | |
| { | |
| AddBefore(l, q, newNode); | |
| } | |
| return newNode; | |
| } | |
| void AddAscendingList(List& l, Node* newNode) { | |
| Node* p = l.pHead; | |
| Node* q = NULL; | |
| while (p!=NULL && p->info.x<newNode->info.x) | |
| { | |
| q = p; | |
| p = p->pNext; | |
| } | |
| if (q != NULL) AddAfter(l, q, newNode); | |
| else AddHead(l, newNode); | |
| } | |
| Node* AddAscendingList(List& l, Data info) { | |
| Node* newNode = CreateNode(info); | |
| if (newNode != NULL) | |
| { | |
| AddAscendingList(l, newNode); | |
| } | |
| return newNode; | |
| } | |
| Node* RemoveHead(List& l) { | |
| Node* p = NULL; | |
| if (isEmptyList(l) == false) // co head | |
| { | |
| p = l.pHead; | |
| l.pHead = l.pHead->pNext; | |
| if (l.pHead == NULL) l.pTail = l.pHead; | |
| } | |
| return p; | |
| } | |
| Node* RemoveTail(List& l) { | |
| Node* p = NULL; | |
| if (isEmptyList(l) == false) // co tail | |
| { | |
| if (l.pHead == l.pTail)// co 1 nut | |
| { | |
| p = RemoveHead(l); | |
| } | |
| else { | |
| Node* tmp = getPreNode(l, l.pTail); | |
| p = RemoveAfter(l, tmp); | |
| } | |
| } | |
| return p; | |
| } | |
| Node* RemoveAfter(List& l, Node* q) { | |
| Node*p = NULL; | |
| if (q != NULL) | |
| { | |
| if (q != l.pTail) { | |
| p = q->pNext; | |
| q->pNext = p->pNext; | |
| //free(p); | |
| if (l.pHead == NULL) l.pTail = l.pHead; | |
| } | |
| } | |
| return p; | |
| } | |
| Node* RemoveNode(List& l, Data info) { | |
| Node* q = getPointer(l, info); | |
| Node* p = NULL; | |
| if (q != NULL) { | |
| if (q == l.pHead) p = RemoveHead(l); | |
| else { | |
| Node* tmp = getPreNode(l, q); | |
| if (tmp!=NULL)//find pre node before q | |
| p = RemoveAfter(l, tmp); | |
| } | |
| } | |
| return p; | |
| } | |
| void DeleteAll(List& l) | |
| { | |
| while (isEmptyList(l)==false) | |
| { | |
| Node* p = RemoveHead(l); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment