结构体实现单链表(C语言) |
您所在的位置:网站首页 › c语言是干啥的啊 › 结构体实现单链表(C语言) |
结构体实现单链表(C语言)
什么是链表链表的存储方式逻辑结构物理结构
链表的代码实现链表结构体变量的创建链表的尾插和尾删尾插步步实现
整体代码尾删
头删和头插头插步步实现整体代码
头删
为什么要有链表
什么是链表
我们知道顺序表在内存中是连续存放的一种线性表,这次的主角链表则是不同于顺序表。 链表是一种是通过链表中的指针链接次序实现的在物理存储单元上非连续、非顺序的存储结构 现在看来这个定义可能有点抽象,现在就让我们来解析一下链表的存储方式。 链表的存储方式 逻辑结构在了解链表的逻辑结构前,我们先看一下顺序表的逻辑结构 我们知道链表是通过每个元素的指针进行链接 这里通过我们前面的物理结构,我们就可以知道链表有两个必要成分 1:需要存储的数据 2:下一个结点的地址 所以 type data是存储的数据 next则是下一个节点的地址 typedef int type是为了方便改变链表存储数据类型而进行改名 链表的尾插和尾删尾部算法算是这个博客中最难的部分了 尾插 步步实现首先我们要设置传输的参数,首先链表通过指针相互链接,所以我们在传参时只需要将头部指针进行传输,就可以实现整个链表的遍历 所以需要实现尾插时需要传入两个参数 1:头部指针的地址 2:需要插入的数据 为什么这里传入的时头部指针的地址,而不是头部指针 且慢慢看文章,后面会进行详细讲解 void Lilpushback(link_list** pphead, type x)看到这个,首先就想到我们应该向内存中申请一块内存,用来存放新节点。 link_list* test = (link_list*)malloc(sizeof(link_list)); if (test == NULL) { printf("malloc fail"); return; } test->data = x; test->next = NULL;经过这个操作后,现在变成了 上述代码中 while (ptail->next != NULL)是为了遍历链表,找到链表的最后一个节点。 ptail=ptail->next推动ptail不断指向下一个结构体,实现前进 尾删其实和尾插大差不差了。 void Lilpopback(link_list** pphead) { assert(phead); assert(*phead); link_list* cur = *phead; if (cur->next == NULL) { free(cur); *phead = NULL; } else { while (cur->next->next != NULL) { cur = cur->next; } free(cur->next); cur->next = NULL; } }对phead和*phead进行assert 因为空链表不能进行删除,首先要保证链表头节点不为空才行(*pphead),同时防止用户误传空指针pphead if (cur->next == NULL) { free(cur); *phead = NULL; }这个部分是为了应对只有一个节点的链表情况 将节点对应空间释放 并且将头节点(*pphead)置为空。 else { while (cur->next->next != NULL) { cur = cur->next; } free(cur->next); cur->next = NULL; },这里使用cur->next->next != NULL,是为了寻找要删除的目标节点的上一个节点。 因为删除具有两部分 1:free目标的内存 2:将上个节点的next置空 因此我们要寻找的是要删除节点的上个节点,并非是要删除的节点,这样可以同时实现两个目标。 头删和头插 头插 步步实现
这个算是链表中插入都要用到的代码了,向内存中申请一块空间,并且检查是否开辟成功。 头删可以这四个中算是最简单的部分 void Lilpopfront(link_list** pphead) { assert(pphead); assert(*pphead); link_list* ptr =*pphead; *pphead=ptr->next; free(ptr); }首先空链表不能进行删除,和尾删一样,所以先进行 1:pphead和*pphead进行断言,防止用户传错。 2:将头部节点进行改变至下个节点 3:将旧头部节点进行free 为什么要有链表在我们对顺序表的了解中 我们发现顺序表的特点: 1:尾插尾删很方便 2:头插头删需要遍历数据,不方便 3:长度固定,有时需要扩容 而相对与顺序表 链表的特点: 1:头插头删很方便 2:尾删尾插需要遍历数据,不方便 3:长度不固定,随时随地扩容和删除 这里我们发现这两个表的优缺点是相辅相成。 每个事物存在总有它的长处。 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |