本文最后更新于 564 天前,其中的信息可能已经有所发展或是发生改变。
之前一直写的都是Java/C#,初学几天C语言,先来实现一个简单的链表试试。
| typedef struct LinkedListNodeStruct { |
| struct LinkedListNodeStruct *next, *pre; |
| int value; |
| } LinkedListNode; |
| |
| typedef struct LinkedListStruct { |
| LinkedListNode *header, *tail; |
| int size; |
| } LinkedList; |
| LinkedList * LinkedList_Create(); |
| |
| void LinkedList_Recycle(LinkedList *linkedList); |
| |
| int LinkedList_Length(LinkedList *linkedList); |
| |
| LinkedListNode * LinkedList_BuildNode(int value); |
| |
| void LinedList_Add(LinkedList *linkedList, LinkedListNode *node); |
| |
| void LinkedList_Insert(LinkedList *linkedList, LinkedListNode *node, int index); |
| |
| LinkedListNode * LinedList_Get(LinkedList *linkedList, int index); |
| |
| LinkedListNode * LinkedList_GetFromHead(LinkedList *linkedList, int targetIndex); |
| |
| LinkedListNode * LinkedList_GetFromTail(LinkedList *linkedList, int targetIndex); |
| |
| void LinkedList_Remove(LinkedList *linkedList, int index); |
引入库文件
| #include "linkedlist.h" |
| #include "stdio.h" |
| #include "memory.h" |
| #include "stdlib.h" |
先来定义两个用于检查链表空和索引越界的函数。
| static bool autoCheckAvailable(LinkedList *linkedList, bool isAutoExit); |
| static bool autoCheckIndex(LinkedList *linkedList, int index, bool isAutoExit); |
| |
| static bool autoCheckAvailable(LinkedList *linkedList, bool isAutoExit) { |
| if (linkedList == nullptr) { |
| |
| throwNullPointerException(); |
| if (isAutoExit) exit(-1); |
| return false; |
| } |
| return true; |
| } |
| |
| static bool autoCheckIndex(LinkedList *linkedList, int index, bool isAutoExit) { |
| if (index >= linkedList->size || index < 0) { |
| |
| throwIndexOutOfBoundsException(); |
| if (isAutoExit) exit(-1); |
| return false; |
| } |
| return true; |
| } |
| LinkedList * LinkedList_Create() { |
| LinkedList *list = malloc(sizeof (LinkedList)); |
| memset(list, 0, sizeof (LinkedList)); |
| list->size = 0; |
| list->header = nullptr; |
| list->tail = nullptr; |
| return list; |
| } |
| void LinkedList_Recycle(LinkedList *linkedList) { |
| if (linkedList != nullptr) { |
| free(linkedList); |
| linkedList = nullptr; |
| } |
| } |
| LinkedListNode * LinkedList_BuildNode(int value) { |
| LinkedListNode *node = malloc(sizeof (LinkedListNode)); |
| node->value = value; |
| return node; |
| } |
| void LinedList_Add(LinkedList *linkedList, LinkedListNode *newNode) { |
| bool checkResult = autoCheckAvailable(linkedList, false); |
| if (!checkResult) { |
| return; |
| } |
| |
| if (linkedList->size == 0) { |
| linkedList->header = newNode; |
| linkedList->tail = newNode; |
| } else { |
| newNode->next = nullptr; |
| newNode->pre = linkedList->tail; |
| |
| linkedList->tail->next = newNode; |
| |
| linkedList->tail = newNode; |
| } |
| |
| linkedList->size++; |
| } |
| void LinkedList_Insert(LinkedList *linkedList, LinkedListNode *node, int index) { |
| bool checkResult = autoCheckAvailable(linkedList, false); |
| if (!checkResult) { |
| return; |
| } |
| |
| LinkedListNode *target = LinedList_Get(linkedList, index); |
| LinkedListNode *preNode = target->pre; |
| |
| node->next = target; |
| target->pre = node; |
| if (index == 0) { |
| linkedList->header = node; |
| } else { |
| preNode->next = node; |
| node->pre = preNode; |
| } |
| |
| linkedList->size++; |
| } |
由于双向链表既可以从头部开始遍历也可以从尾部开始遍历,所以双向链表具有插入慢、读取快的特性,但假设链表长度为10,需要获取下标为8的节点,显然从尾部开始向前遍历速度最快,所以可以根据下标来决定从哪个方向开始遍历。
以下是具体实现
| LinkedListNode * LinkedList_GetFromHead(LinkedList *linkedList, int targetIndex) { |
| LinkedListNode *cursor = linkedList->header; |
| for (int i = 0; i < targetIndex; i++) { |
| cursor = cursor->next; |
| } |
| return cursor; |
| } |
| |
| LinkedListNode * LinkedList_GetFromTail(LinkedList *linkedList, int targetIndex) { |
| LinkedListNode *cursor = linkedList->tail; |
| for (int i = linkedList->size; i > targetIndex + 1; i--) { |
| cursor = cursor->pre; |
| } |
| return cursor; |
| } |
所以整合一下就是这样
| LinkedListNode * LinedList_Get(LinkedList *linkedList, int index) { |
| bool checkResult = autoCheckAvailable(linkedList, false) && autoCheckIndex(linkedList, index, false); |
| if (!checkResult) { |
| return nullptr; |
| } |
| return index + 1 <= linkedList->size / 2 ? LinkedList_GetFromHead(linkedList, index) : LinkedList_GetFromTail(linkedList, index); |
| } |
| void LinkedList_Remove(LinkedList *linkedList, int index) { |
| bool checkResult = autoCheckAvailable(linkedList, false) && autoCheckIndex(linkedList, index, false); |
| if (!checkResult) { |
| return; |
| } |
| |
| LinkedListNode *target = LinedList_Get(linkedList, index); |
| LinkedListNode *preNode = target->pre; |
| LinkedListNode *nextNode = target->next; |
| |
| if (index == 0) { |
| linkedList->header = nextNode; |
| } else if (index + 1 == linkedList->size) { |
| linkedList->tail = preNode; |
| } else { |
| preNode->next = nextNode; |
| nextNode->pre = preNode; |
| } |
| |
| free(target); |
| target = nullptr; |
| |
| linkedList->size--; |
| } |
写一个测试函数来试试
| void LinkedList_UnitTest() { |
| printf(">>> Now start unit test of LinkedList\n"); |
| |
| LinkedList *testList = LinkedList_Create(); |
| LinedList_Add(testList, LinkedList_BuildNode(114)); |
| LinedList_Add(testList, LinkedList_BuildNode(514)); |
| LinedList_Add(testList, LinkedList_BuildNode(191)); |
| LinedList_Add(testList, LinkedList_BuildNode(981)); |
| LinedList_Add(testList, LinkedList_BuildNode(189)); |
| |
| printf(">>> List content\n"); |
| LinkedListNode *cursor = testList->header; |
| for (int i = 0; i < testList->size; i++) { |
| printf("%d\n", cursor->value); |
| cursor = cursor->next; |
| } |
| |
| printf(">>> || Fx: Get\n"); |
| printf("%d\n", LinedList_Get(testList, 0)->value); |
| printf("%d\n", LinedList_Get(testList, 1)->value); |
| printf("%d\n", LinedList_Get(testList, 2)->value); |
| printf("%d\n", LinedList_Get(testList, 3)->value); |
| printf("%d\n", LinedList_Get(testList, 4)->value); |
| |
| printf(">>> || Fx: Remove Head\n"); |
| LinkedList_Remove(testList, 0); |
| printf("%d\n", LinedList_Get(testList, 0)->value); |
| |
| printf(">>> || Fx: Remove Tail\n"); |
| LinkedList_Remove(testList, 3); |
| printf("%d\n", LinedList_Get(testList, 2)->value); |
| |
| printf(">>> || Fx: Insert\n"); |
| LinkedList_Insert(testList, LinkedList_BuildNode(2333), 1); |
| printf("%d\n", LinedList_Get(testList, 1)->value); |
| |
| LinkedList_Recycle(testList); |
| printf(">>> Unit test of LinkedList now ended\n"); |
| } |
运行结果为
| >>> Now start unit test of LinkedList |
| >>> List content |
| 114 |
| 514 |
| 191 |
| 981 |
| 189 |
| >>> || Fx: Get |
| 114 |
| 514 |
| 191 |
| 981 |
| 189 |
| >>> || Fx: Remove Head |
| 514 |
| >>> || Fx: Remove Tail |
| 981 |
| >>> || Fx: Insert |
| 2333 |
| >>> Unit test of LinkedList now ended |
最后欢迎各位大佬指正