动态链表是一种常用的动态数据结构，可以在运行时动态地申请内存空间来存储数据，相比于静态数组和静态链表，更加灵活和高效。在动态链表中，数据元素被组织成一条链表，每个元素包含了指向下一个元素的指针，这样就可以通过指针将所有元素串联起来。
使用动态链表存储数据时，不需要预先申请内存空间，而是在需要的时候才向内存申请。当需要添加新的元素时，可以使用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;
}本文作者： 王瑞
本文链接： https://www.lyshark.com/post/161cb96e.html
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
