这门课太难了.
记录学习经历.
#include#include struct Node { int data; struct Node* next; }; struct Node* createList() { struct Node* list = (struct Node*)malloc(sizeof(struct Node)); if (list == NULL) return NULL; list->next = NULL; return list; } struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) return NULL; newNode->data = data; newNode->next = NULL; return newNode; } void insertNode(struct Node* list, int data) { struct Node* newNode = createNode(data); newNode->next = list->next; list->next = newNode; } void printList(struct Node* list) { struct Node* pMove = list->next; while (pMove != NULL) { printf("%dt", pMove->data); pMove = pMove->next; } printf("n"); } int main() { struct Node* list = createList(); for (int i = 0; i < 3; i++) { insertNode(list, i); } printList(list); return 0; }
无头链表第一种写法:
#include#include struct Node { int data; struct Node* next; }; struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) return NULL; newNode->data = data; newNode->next = NULL; return newNode; } //再封装的写法 struct list { struct Node* headNode; //指向表头的指针 int listSize; //万金油 }; //描述最初状态 struct list* createList() { struct list* myList = (struct list*)malloc(sizeof(struct list)); if (myList == NULL) return NULL; myList->headNode = NULL; myList->listSize = 0; return myList; } //表头法 void insertNode(struct list* myList, int data) { struct Node* newNode = createNode(data); newNode->next = myList->headNode; myList->headNode = newNode; myList->listSize++; } //指定位置插入 void insertNodeAppoin(struct list* myList, int data, int posData) { //指定插入极有可能变成表头插入 struct Node* posNode = myList->headNode; struct Node* preNode = NULL; while (posNode != NULL && posNode->data != posData) { preNode = posNode; posNode = preNode->next; } if (posNode == NULL) { printf("未找到指定位置，无法插入!n"); } else if (preNode == NULL) //第一个 { insertNode(myList, data); } else { struct Node* newNode = createNode(data); preNode->next = newNode; newNode->next = posNode; myList->listSize++; } } //删除! 表头法删除不一样! void deleteHead(struct list* myList) { if (myList == NULL || myList->headNode == NULL) { printf("error list is NULLn"); return; } struct Node* nextNode = myList->headNode->next; free(myList->headNode); myList->headNode = nextNode; myList->listSize--; } //指定未删除也需要考虑是否删除表头 //表尾删除 void printList(struct list* myList) { struct Node* pMove = myList->headNode; while (pMove != NULL) { printf("%dt", pMove->data); pMove = pMove->next; } printf("n"); } int main() { struct list* myList = createList(); for (int i = 0; i < 3; i++) { insertNode(myList, i); } printList(myList); insertNodeAppoin(myList, -100, 2); insertNodeAppoin(myList, -100, 100); insertNodeAppoin(myList, -100, 1); printList(myList); deleteHead(myList); printList(myList); return 0; }
无头链表第二种写法:
#include#include struct Node { int data; struct Node* next; }; struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) { return NULL; } newNode->data = data; newNode->next = NULL; return newNode; } void insertNodeByFront(struct Node** list, int data) { struct Node* newNode = createNode(data); newNode->next = *list; *list = newNode; } void insertNodeByAppoin(struct Node** list, int data, int posData) { struct Node* posNode = *list; struct Node* preNode = NULL; while (posNode != NULL && posNode->data != posData) { preNode = posNode; posNode = preNode->next; } if (posNode == NULL) { printf("error!n"); } else if (preNode == NULL) { insertNodeByFront(list, data); } else { struct Node* newNode = createNode(data); preNode->next = newNode; newNode->next = posNode; } } void printList(struct Node* list) { struct Node* pMove = list; while (pMove != NULL) { printf("%dt", pMove->data); pMove = pMove->next; } printf("n"); } int main() { struct Node* list = createNode(1); //无头链表 for (int i = 0; i < 3; i++) insertNodeByFront(&list, i); printList(list); insertNodeByAppoin(&list, -100, 2); insertNodeByAppoin(&list, 101, 1); printList(list); return 0; }
单链表之间的操作:
#include#include struct Node { int data; struct Node* next; }; struct Node* createList() { struct Node* list = (struct Node*)malloc(sizeof(struct Node)); if (list == NULL) return NULL; list->next = NULL; return list; } struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) return NULL; newNode->data = data; newNode->next = NULL; return newNode; } void insertNode(struct Node* list, int data) { struct Node* newNode = createNode(data); newNode->next = list->next; list->next = newNode; } void printList(struct Node* list) { struct Node* pMove = list->next; while (pMove != NULL) { printf("%dt", pMove->data); pMove = pMove->next; } printf("n"); } // 1.找两个链表中的相同元素组成第三个链表 void intersection(struct Node* listOne, struct Node* listTwo, struct Node* listThree) { for (struct Node* pFirst = listOne->next; pFirst != NULL; pFirst = pFirst->next) { for (struct Node* pSecond = listTwo->next; pSecond != NULL; pSecond = pSecond->next) { if (pFirst->data == pSecond->data) { insertNode(listThree, pFirst->data); } } } } void freeList(struct Node** list) { if (list == NULL) return; struct Node* nextNode = NULL; while ((*list) != NULL) { nextNode = (*list)->next; free(*list); *list = nextNode; } } // 2.反转链表 // 2.1 最简单 遍历逆序插入 void reverseFirstWay(struct Node** list) { struct Node* tempList = createList(); struct Node* pMove = (*list)->next; while (pMove != NULL) { insertNode(tempList, pMove->data); pMove = pMove->next; } //释放原来的链表 freeList(list); *list = tempList; } void reverseSecondWay(struct Node** list) { struct Node* preNode = NULL; struct Node* curNode = (*list)->next; struct Node* nextNode = (*list)->next; while (curNode != NULL) { nextNode = curNode->next; curNode->next = preNode; preNode = curNode; curNode = nextNode; } (*list)->next = preNode; } int main() { struct Node* list = createList(); struct Node* list2 = createList(); struct Node* list3 = createList(); struct Node* test = createList(); struct Node* test2 = createList(); for (int i = 0; i < 3; i++) { insertNode(list, i); insertNode(list2, i); insertNode(test, i); insertNode(test2, i); } insertNode(list2, 100); intersection(list, list2, list3); printList(list3); reverseFirstWay(&test); printList(test); printf("反转前:"); printList(test2); reverseSecondWay(&test2); printf("反转后:"); printList(test2); return 0; }
有序链表:
#include#include struct data { int index; //构建序号 int second; }; struct Node { struct data myData; struct Node* next; }; struct Node* createList() { struct Node* list = (struct Node*)malloc(sizeof(struct Node)); if (list == NULL) return NULL; list->next = NULL; return list; } struct Node* createNode(struct data myData) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) return NULL; newNode->next = NULL; newNode->myData = myData; return newNode; } void insertByIndex(struct Node* list, struct data myData) { struct Node* newNode = createNode(myData); struct Node* preNode = list; struct Node* posNode = list->next; while (posNode != NULL && posNode->myData.index < myData.index) { preNode = posNode; posNode = preNode->next; } if (posNode == NULL) { preNode->next = newNode; } else { preNode->next = newNode; newNode->next = posNode; } } void printList(struct Node* list) { struct Node* pMove = list->next; while (pMove != NULL) { printf("%d:%dn", pMove->myData.index, pMove->myData.second); pMove = pMove->next; } } int main() { struct data array[5] = {1, 2, 6, 3, 4, 5, 6, 7, 8, 3}; struct Node* list = createList(); for (int i = 0; i < 5; i++) { insertByIndex(list, array[i]); } printList(list); return 0; }
