动态链表是一种常用的动态数据结构,可以在运行时动态地申请内存空间来存储数据,相比于静态数组和静态链表,更加灵活和高效。在动态链表中,数据元素被组织成一条链表,每个元素包含了指向下一个元素的指针,这样就可以通过指针将所有元素串联起来。
使用动态链表存储数据时,不需要预先申请内存空间,而是在需要的时候才向内存申请。当需要添加新的元素时,可以使用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; 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++; }
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; 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;
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);
RemoveByPosLinkList(list, 2); printf("当前链表大小: %d \n", SizeLinkList(list));
struct Student pDel = { "admin", 10 }; RemoveByValLinkList(list, &pDel, myComapre); ForeachLinkList(list, myPrint);
ClearLinkList(list);
DestroyLinkList(list);
system("pause"); return EXIT_SUCCESS; }
|