前言
在实际生活中最常用的就是这两种链表。无头单向非循环链表。和带头双向循环链表。
无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。
1. 创建结构体
注意:typedef起作用是在第7行哦。所以第5,6还需要写struct listnode类型。
typedef int lndatatype; typedef struct listnode { struct listnode* prev; struct listnode* next; lndatatype val; }ln;
2.malloc新节点
注意:需判断新开辟的节点是否为空。
//申请一个新节点 ln* buynewnode(lndatatype x) { ln* newnode = (ln*)malloc(sizeof(ln)); if (newnode == null) { printf("malloc fail"); exit(-1); } newnode->next = null; newnode->prev = null; newnode->val = x; return newnode; }
3.创建哨兵位节点
注意:这里因为需要改变plist指针的内容,也就是改变plist指针的指向,所以需要传递plist的地址。
一句话就是:需要改变谁的内容,就传谁的地址。
这里有一点非常巧非常妙,就是phead的后继和前驱都是指向自己(phead),这里是模仿c++stl库里的哨兵位节点。
只能佩服想出来这些东西的大神。这样设计哨兵位节点的话,后续尾插,尾删,都特别的巧妙。
test.c
ln* plist = null; listnodeinit(&plist);
list.h
//初始化节点 void listnodeinit(ln** pphead) { ln* newnode = buynewnode(0); *pphead = newnode; (*pphead)->next = *pphead; (*pphead)->prev = *pphead; }
4.尾插
注意:需要断言的原因是因为,即使链表没有一个节点,那链表至少还有个头,所以phead肯定不为空。
这里没有传地址的原因是因为,你不需要改变plist的指向,你改变的是plist指向的结构体里面的值。
多个节点尾插的情况如图。
一个节点的尾插。
//尾插 void listnodepushback(ln* phead, lndatatype x) { assert(phead); ln* newnode = buynewnode(x); ln* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
5.打印
注意:因为带个头,所以cur从第二个位置开始。
//打印 void listnodeprint(ln* phead) { ln* cur = phead->next; while (cur != phead) { printf("%d ", cur->val); cur = cur->next; } printf("n"); }
6.尾删
注意不能删掉头结点,free掉头结点的话会造成野指针,再次访问时会造成非法访问。
所以要用assert断言不为首节点。
//尾删 void listnodepopback(ln* phead) { assert(phead); assert(phead->next != phead); ln* tail = phead->prev; ln* tailprev = tail->prev; free(tail); tail = null; phead->prev = tailprev; tailprev->next = phead; }
7.头插
最好用next记录下一个节点。这样方便,思路清晰
//头插 void listnodepushfront(ln* phead, lndatatype x) { assert(phead); ln* newnode = buynewnode(x); ln* next = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; }
8.在指定位置pos的前面进行插入
一般情况
只有一个节点时。
两种情况都适用以下代码。
//指定位置前插入,极限是头插 void listnodeinsert(ln* pos, lndatatype x) { if (pos == null) { printf("没有找到这个数n"); return; } ln* newnode = buynewnode(x); ln* tailprev = pos->prev; tailprev->next = newnode; newnode->prev = tailprev; newnode->next = pos; pos->prev = newnode; }
9. 删除指定位置pos节点
正常情况
极限尾删
两种情况都适用以下代码。
//指定位置删除 void listnodeerease(ln* phead, ln* pos) { if (pos == phead || pos == null) { printf("pos指向头,或为空n"); return; } ln* posprev = pos->prev; ln* posnext = pos->next; posprev->next = posnext; posnext->prev = posprev; free(pos); pos = null; }
10.销毁链表
注意:这里相当于malloc用完之后的free。否则会造成内存泄漏。
cur可以置空,但用处不大,因为cur是形参,形参是实参的一份临时拷贝,形参置空并不能改变实参。外部的实参还是依旧能非法访问到cur所指向的空间。
//链表销毁 void listnodedestroy(ln* phead) { assert(phead); ln* cur = phead->next; ln* next = cur->next; while (cur != phead) { next = cur->next; free(cur); cur = null; cur = next; } free(phead); phead = null; }
到此这篇关于c语言实现带头双向循环链表的文章就介绍到这了,更多相关c语言 带头双向循环链表内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>!
需要了解更多c/c++开发分享C语言实现带头双向循环链表,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/1073981.html