🌹作者:云小逸
📝个人主页:云小逸的主页
📝码云:云小逸 (YunXiaoYi003) - Gitee.com
🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前,其次就是现在!学会自己和解,与过去和解,努力爱自己。==希望春天来之前,我们一起面朝大海,春暖花开!==🤟
👏专栏:C语言初阶👏
文章目录
前言
今天我们来聊一聊:数据结构中链表的双向循环带头链表,对于第一次听到双向循环带头链表的同学,可能会认为双向循环带头链表是十分复杂的,的确双向循环带头链表的结构是有点复杂,但是它的操作是非常简单的,非常便于操作,那么现在就由云小逸带你了解认识学习双向循环带头链表。
——————————————————————————————
首先先写上几句话:献给坚持创作的我和点开这篇文章希望进步的你
1.世人慌慌张张,不过是图碎银几两。偏偏这碎银几两,能解世间惆怅,可让父母安康,可护幼子成长,但这碎银几两,也断了儿时念想,让少年染上沧桑,压弯了脊梁
2.暂时抛去心灵深处的空洞与匮乏,沏一杯淡淡的茶,斜阳层层,叠叠的洒在桌面上,有那么一瞬间,好像忘记了曾经的阴霾和受过的伤。林徽因说过:“温柔要有,但不是妥协,我们要在不慌不忙中安静的坚强。″
1.链表的分类:
- 单向、双向
- 带头、不带头
- 循环、非循环今天我们就来讲一讲链表中看似结构复杂的双向循环带头链表:
2.双向链表的初始化:
方法一:传双指针
voidListNodeInit(ListNode** pphead){*pphead =ListNodeBuy(0);//ListNodeBuy(0)是建立一个存储0的地址的函数,后面会写上这个函数(* pphead)->next =*pphead;(*pphead)->prev =*pphead;}
方法二:返回值法
ListNode*ListNodeInit(){
ListNode* phead =ListNodeBuy(0);
phead->next = phead;
phead->prev = phead;return phead;}
再加上主函数上写:
ListNode* phead=ListNodeInit();
即可完成双向链表的初始化。
PS:双向循环带头链表为空时,即是只有头指针时,head->next和head->prev均指向自己(head)
3.双向链表的打印
(1)运行代码:
voidListPrint(ListNode* phead){assert(phead);
ListNode* cur = phead->next;while(cur != phead){printf("%d ", cur->data);
cur = cur->next;}printf("\n");}
这里要记得双向循环带头链表打印时的终止条件是:当cur遍历回到了phead!
(2)运行结果:
4.双向链表的尾插:
(1)运行代码:
由于插入时要创建一个变量newnode,需向内存申请空间存储变量,且变量的值为插入的值,又因为每次插入都需要这一步,故将这一步写成一个函数,便于使用该函数为:
ListNode*ListNodeBuy(LTDataType x){
ListNode* newnode =(ListNode*)malloc(sizeof(ListNode));
newnode->next =NULL;
newnode->prev =NULL;
newnode->data=x;return newnode;}
尾插函数:
voidListNodePushBack(ListNode* phead, LTDataType x){assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode =ListNodeBuy(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;}
(2)运行结果:
5.双向链表的尾删
(1)运行代码:
voidListNodePopBack(ListNode* phead){assert(phead);//这是调用断言函数,该表达式的意思为判断phead是否为NULLassert(phead->next != phead);//这是判断该链表是否为空链表,若为空链表,则会报错
ListNode* tail = phead->prev;
ListNode* tail_prev = tail->prev;
tail_prev->next = phead;
phead->prev = tail_prev;free(tail);
tail =NULL;}
assert(phead);//这是调用断言函数,该表达式的意思为判断phead是否为NULL
assert(phead->next != phead);//这是判断该链表是否为空链表,若为空链表,则会报错
(2)运行结果:
6.双向链表的头插:
(1)运行代码:
voidListNodePushFront(ListNode* phead, LTDataType x){assert(phead);
ListNode* first = phead->next;
ListNode* newnode =ListNodeBuy(x);
phead->next = newnode;
newnode->next = first;
newnode->prev = phead;
first->prev = newnode;}
注:头插是是将newnode插在phead和first(头结点后的第一个结点)
(2)运行结果:
7.双向链表的头删:
(1)运行代码:
voidListNodePopFront(ListNode* phead){assert(phead);//这是调用断言函数,该表达式的意思为判断phead是否为NULLassert(phead->next != phead);//这是判断该链表是否为空链表,若为空链表,则会报错
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;free(first);
first =NULL;}
(2)运行结果:
8.双向链表的查找
(1)运行代码:
ListNode*ListNodeFind(ListNode* phead, LTDataType x){assert(phead);
ListNode* cur = phead->next;while(cur != phead){if(cur->data == x)return cur;
cur = cur->next;}returnNULL;}
查找后返回的是结点的指针,可以用pos->data=某个数进而修改这个点的值!!!
(2)运行结果:
9.双向链表的中间插入:
(1)运行代码:
插入在指定位置的前面
voidListNodeInsert(ListNode* pos, LTDataType x){assert(pos);
ListNode* pos_prev = pos->prev;
ListNode* newnode =ListNodeBuy(x);
newnode->next = pos;
pos->prev = newnode;
pos_prev->next = newnode;
newnode->prev = pos_prev;}
(2)运行结果:
10.双向链表的中间删除:
(1)运行代码:
voidListNodeErase(ListNode* pos){assert(pos);
ListNode* pos_prev = pos->prev;
ListNode* next = pos->next;free(pos);
pos =NULL;
pos_prev->next = next;
next->prev = pos_prev;}
(2)运行结果:
11.双向链表的销毁:
每一次用完链表后销毁是很有必要的,如果不销毁,将会导致内存的泄露,短时间内可能没用什么,且很难被发现,但时间长了,必将导致程序的崩溃,最终将导致时间和金钱的浪费!!!
这里介绍两种销毁:
方法一:销毁全部,不保留头结点:
voidListNodeDestroy(ListNode* phead){assert(phead);
ListNode* cur = phead;while(cur != phead){
ListNode* next = cur->next;free(cur);
cur =NULL;
cur = next;}free(phead);
phead=NULL;}
方法二:保留头结点:
voidListNodeDestroy(ListNode* phead){assert(phead);
ListNode* cur = phead;while(cur != phead){
ListNode* next = cur->next;free(cur);
cur =NULL;
cur = next;}}
具体选择哪一种,需要看实际需要!!!
12.完整代码:
(1)List.h文件:
#define_CRT_SECURE_NO_WARNINGS1#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint LTDataType;typedefstructListNode{structListNode* prev;
LTDataType data;structListNode* next;}ListNode;
ListNode*ListNodeBuy(LTDataType x);voidListNodeInit(ListNode** pphead);voidListPrint(ListNode* phead);voidListNodePushBack(ListNode* phead, LTDataType x);voidListNodePopBack(ListNode* phead);voidListNodePushFront(ListNode* phead, LTDataType x);voidListNodePopFront(ListNode* phead);
ListNode*ListNodeFind(ListNode* phead, LTDataType x);voidListNodeInsert(ListNode* pos, LTDataType x);voidListNodeErase(ListNode* pos);voidListNodeDestroy(ListNode* phead);
(2)List.c文件:
#include"List.h"#define_CRT_SECURE_NO_WARNINGS1
ListNode*ListNodeBuy(LTDataType x){
ListNode* newnode =(ListNode*)malloc(sizeof(ListNode));
newnode->next =NULL;
newnode->prev =NULL;
newnode->data=x;return newnode;}voidListNodeInit(ListNode** pphead){*pphead =ListNodeBuy(0);(* pphead)->next =*pphead;(*pphead)->prev =*pphead;}
ListNode*ListNodeInit(){
ListNode* phead =ListNodeBuy(0);
phead->next = phead;
phead->prev = phead;return phead;}voidListPrint(ListNode* phead){assert(phead);
ListNode* cur = phead->next;while(cur != phead){printf("%d ", cur->data);
cur = cur->next;}printf("\n");}voidListNodePushBack(ListNode* phead, LTDataType x){assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode =ListNodeBuy(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;}voidListNodePopBack(ListNode* phead){assert(phead);assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* tail_prev = tail->prev;
tail_prev->next = phead;
phead->prev = tail_prev;free(tail);
tail =NULL;}voidListNodePushFront(ListNode* phead, LTDataType x){assert(phead);
ListNode* first = phead->next;
ListNode* newnode =ListNodeBuy(x);
phead->next = newnode;
newnode->next = first;
newnode->prev = phead;
first->prev = newnode;}voidListNodePopFront(ListNode* phead){assert(phead);assert(phead->next != phead);
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;free(first);
first =NULL;}
ListNode*ListNodeFind(ListNode* phead, LTDataType x){assert(phead);
ListNode* cur = phead->next;while(cur != phead){if(cur->data == x)return cur;
cur = cur->next;}returnNULL;}voidListNodeInsert(ListNode* pos, LTDataType x){assert(pos);
ListNode* pos_prev = pos->prev;
ListNode* newnode =ListNodeBuy(x);
newnode->next = pos;
pos->prev = newnode;
pos_prev->next = newnode;
newnode->prev = pos_prev;}voidListNodeErase(ListNode* pos){assert(pos);
ListNode* pos_prev = pos->prev;
ListNode* next = pos->next;free(pos);
pos =NULL;
pos_prev->next = next;
next->prev = pos_prev;}voidListNodeDestroy(ListNode* phead){assert(phead);
ListNode* cur = phead;while(cur != phead){
ListNode* next = cur->next;free(cur);
cur =NULL;
cur = next;}}
(3)test.c文件:
#include"List.h"#define_CRT_SECURE_NO_WARNINGS1intmain(void){
ListNode* phead =NULL;ListNodeInit(&phead);/*ListNodePushBack(phead, 1);
ListNodePushBack(phead, 2);
ListNodePushBack(phead, 3);
ListNodePushBack(phead, 4);
ListNodePushBack(phead, 5);
ListNodePushBack(phead, 6);
ListPrint(phead);
ListNodePopBack(phead, 1);
ListNodePopBack(phead, 2);
ListNodePopBack(phead, 3);
ListNodePopBack(phead, 4);
ListNodePopBack(phead, 5);
ListPrint(phead);*/ListNodePushFront(phead,1);ListNodePushFront(phead,2);ListNodePushFront(phead,3);ListNodePushFront(phead,4);ListNodePushFront(phead,5);ListNodePushFront(phead,6);ListPrint(phead);/*ListNodePopFront(phead, 1);
ListNodePopFront(phead, 2);
ListNodePopFront(phead, 3);
ListNodePopFront(phead, 4);
ListNodePopFront(phead, 5);
ListPrint(phead);*/
ListNode* pos =ListNodeFind(phead,3);
pos->data =300;ListPrint(phead);ListNodeInsert(pos,1);ListPrint(phead);ListNodeErase(pos);ListPrint(phead);ListNodeDestroy(phead);return0;}
最后
十分感谢你可以耐着性子把它读完和我可以坚持写到这里,送几句话,对你,也对我:
1.也许你要早上七点起床,晚上十二点睡觉,日复一日,踽踽独行。但只要笃定而努力地活着,即使生不逢时,你人生最坏的结果,也只是大器晚成。
2.这个世界根本不存在“不会”这回事。当你失去所有依靠的时候,你自然就什么都会了。
3.当你足够优秀时,你周围的一切自然都会好起来。
4.人一旦堕落,哪怕是短暂的几年,上帝就会以最快的速度,收走你的天赋和力量。5.你所做的事情,也许暂时看不到成果,但不要灰心或焦虑,你不是没有成长,而是在扎根。
最后如果觉得我写的还不错,请不要忘记点赞✌,收藏✌,加关注✌哦(。・ω・。)
愿我们一起加油,奔向更美好的未来,愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油,为自己点赞!
版权归原作者 云小逸 所有, 如有侵权,请联系我们删除。