如何用7.2 CC++技术实现动态链表功能？

本文共计1781个文字，预计阅读时间需要8分钟。

动态链表是一种常用的动态数据结构，可以在运行时动态地申请内存来存储数据，相较于静态数组和静态链表，更具灵活性和高效性。在动态链表中，数据元素被组织成一条链表，每个元素包含数据和指向下一个元素的指针。这使得动态链表可以快速地插入和删除元素。

动态链表是一种常用的动态数据结构，可以在运行时动态地申请内存空间来存储数据，相比于静态数组和静态链表，更加灵活和高效。在动态链表中，数据元素被组织成一条链表，每个元素包含了指向下一个元素的指针，这样就可以通过指针将所有元素串联起来。

使用动态链表存储数据时，不需要预先申请内存空间，而是在需要的时候才向内存申请。当需要添加新的元素时，可以使用malloc函数动态地申请内存空间，然后将新的元素插入到链表中；当需要删除元素时，可以使用free函数释放元素占用的内存空间，然后将链表中的指针重新连接。

动态链表的优点在于可以随时插入或删除元素，而且不会浪费内存空间。但是它也有缺点，比如访问链表中的任何一个元素都需要遍历整个链表，时间复杂度较高，不适合随机访问操作。同时，动态链表还需要额外的指针来存储元素之间的关系，相比于静态数组来说，存储空间的开销会更大。

读者需自行创建头文件linklist.h并拷贝如下动态链表代码实现；

#include <stdio.h> #include <string.h> #include <stdlib.h> typedef void * LinkList; typedef void(*FOREACH)(void *); typedef int(*COMPARE)(void *, void *); // 链表节点数据类型 struct LinkNode { void *data; struct LinkNode *next; }; // 链表数据类型 struct LList { struct LinkNode header; int size; }; // 初始化链表 LinkList InitLinkList() { struct LList *list = malloc(sizeof(struct LList)); if (NULL == list) return NULL; list->header.data = NULL; list->header.next = NULL; list->size = 0; return list; } // 向节点插入数据 void InsertLinkList(LinkList list, int pos, void *data) { // 如果传入链表为空,或者插入数据为空则直接返回 if (NULL == list || NULL == data) { return; } struct LList * mylist = (struct LList *)list; // 如果插入位置小于0或者是插入位置大于链表的结束 if (pos < 0 || pos > mylist->size) { pos = mylist->size; } // 插入前先查找插入位置 struct LinkNode *pCurrent = &(mylist->header); for (int i = 0; i < pos; ++i) { pCurrent = pCurrent->next; } // 创建新节点,并初始化数据 struct LinkNode *newnode = malloc(sizeof(struct LinkNode)); newnode->data = data; newnode->next = NULL; // 将创建的新节点插入到链表中 newnode->next = pCurrent->next; pCurrent->next = newnode; mylist->size++; } // 遍历链表,传入myforeach回调函数,自定制输出 void ForeachLinkList(LinkList list, FOREACH myforeach) { if (NULL == list || NULL == myforeach) { return; } // 获得链表头指针 struct LList * mylist = (struct LList *)list; // 指向下一个链表结构 struct LinkNode *pCurrent = mylist->header.next; while (pCurrent != NULL) { myforeach(pCurrent->data); pCurrent = pCurrent->next; } } // 按照位置删除链表中的节点 void RemoveByPosLinkList(LinkList list, int pos) { if (NULL == list || NULL == pos) { return; } struct LList *mylist = (struct LList *)list; // 插入位置小于0,或者插入位置大于最后一个元素 if (pos < 0 || pos > mylist->size - 1) { return; } // 通过遍历指针寻找待插入元素的位置 struct LinkNode *pCurrent = &(mylist->header); for (int i = 0; i < pos; ++i) pCurrent = pCurrent->next; // 先保存待删除结点 struct LinkNode *pDel = pCurrent->next; // 重新建立待删除结点的前驱和后继结点关系 pCurrent->next = pDel->next; // 释放删除节点内存 free(pDel); pDel = NULL; mylist->size--; } // 按照值删除链表中的节点 void RemoveByValLinkList(LinkList list, void *data, COMPARE compare) { if (NULL == list || NULL == data || NULL == compare) { return; } struct LList *mylist = (struct LList *)list; // 辅助指针变量pPrev指向上一个元素pCurrent指向当前元素 struct LinkNode *pPrev = &(mylist->header); struct LinkNode *pCurrent = pPrev->next; while (pCurrent != NULL) { if (compare(pCurrent->data, data)) { // 找到了 pPrev->next = pCurrent->next; // 释放删除节点内存 free(pCurrent); pCurrent = NULL; mylist->size--; break; } pPrev = pCurrent; pCurrent = pCurrent->next; } } // 清空链表 void ClearLinkList(LinkList list) { if (NULL == list) { return; } struct LList *mylist = (struct LList *)list; // 辅助指针变量 struct LinkNode *pCurrent = mylist->header.next; while (pCurrent != NULL) { // 先缓存下一个节点的地址 struct LinkNode *pNext = pCurrent->next; // 释放当前结点内存 free(pCurrent); pCurrent = pNext; } mylist->header.next = NULL; mylist->size = 0; } // 获取链表当前大小 int SizeLinkList(LinkList list) { if (NULL == list) { return -1; } struct LList *mylist = (struct LList *)list; return mylist->size; } // 销毁链表 void DestroyLinkList(LinkList list) { if (NULL == list) { return; } // 清空链表 ClearLinkList(list); free(list); list = NULL; }

如下代码则是使用方法，通过调用链表操作库实现了对链表的创建、插入、删除、遍历等操作。在代码中定义了一个结构体Student，包含姓名和年龄两个字段。同时还定义了回调函数myPrint和myComapre，分别用于遍历链表时的数据输出和链表成员比较。

代码通过调用链表操作库实现对链表的操作，具体操作包括：

• 初始化链表 InitLinkList
• 插入链表元素 InsertLinkList
• 删除链表元素 RemoveByPosLinkList 和 RemoveByValLinkList
• 遍历链表元素 ForeachLinkList
• 清空链表 ClearLinkList
• 销毁链表 DestroyLinkList

其中，回调函数 myPrint 用于输出链表中的每个成员，回调函数 myCompare 用于比较链表中的成员是否相同。在代码中，还输出了链表的大小，即元素个数。

#include "LinkList.h" struct Student { char name[64]; int age; }; // 通过自定义回调函数实现输出个性化数据 void myPrint(void *data) { struct Student *stu = (struct Student *)data; printf("姓名: %s 年龄: %d \n", stu->name, stu->age); } // 链表对比方法 int myComapre(void *d1, void *d2) { struct Student *p1 = (struct Student *)d1; struct Student *p2 = (struct Student *)d2; if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age) { return 1; } return 0; } int main(int argc, char *argv[]) { // 创建链表首个节点 LinkList list = InitLinkList(); // 创建要插入的数据 struct Student stu1 = { "admin", 10 }; struct Student stu2 = { "guest", 20 }; struct Student stu3 = { "blib", 30 }; // 插入测试数据 InsertLinkList(list, 0, &stu1); InsertLinkList(list, 1, &stu2); InsertLinkList(list, 2, &stu3); printf("当前链表大小: %d \n", SizeLinkList(list)); // 输出链表元素 ForeachLinkList(list, myPrint); // 删除下标为2的元素 RemoveByPosLinkList(list, 2); printf("当前链表大小: %d \n", SizeLinkList(list)); // 删除pDel的链表成员 struct Student pDel = { "admin", 10 }; RemoveByValLinkList(list, &pDel, myComapre); ForeachLinkList(list, myPrint); // 清空链表 ClearLinkList(list); // 销毁链表 DestroyLinkList(list); system("pause"); return EXIT_SUCCESS; }

本文作者： 王瑞 本文链接： www.lyshark.com/post/161cb96e.html 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！