作者:云小逸
个人主页:云小扬的主页
码云:云小扬 (YunXiaoYang003) – Gitee.com
motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前,其次就是现在!学会自己和解,与过去和解,努力爱自己。希望春天来之前,我们一起面朝大海,春暖花开!
专栏:C语言初阶专栏:C语言进阶专栏:数据结构和算法
专栏:C++初阶—专栏:C++进阶–专栏:Linux学习
文章目录
- 前言
- 1.链表的分类:
- 2.双向链表的初始化:
- 方法一:传==双指针==
- 方法二:==返回值==法
- 3.双向链表的打印
- (1)运行代码:
- (2)运行结果:
- 4.双向链表的尾插:
- (1)运行代码:
- (2)运行结果:
- 5.双向链表的尾删
- (1)运行代码:
- (2)运行结果:
- 6.双向链表的头插:
- (1)运行代码:
- (2)运行结果:
- 7.双向链表的头删:
- (1)运行代码:
- (2)运行结果:
- 8.双向链表的查找
- (1)运行代码:
- (2)运行结果:
- 9.双向链表的中间插入:
- (1)运行代码:
- (2)运行结果:
- 10.双向链表的中间删除:
- (1)运行代码:
- (2)运行结果:
- 11.双向链表的销毁:
- 12.完整代码:
- (1)List.h文件:
- (2)List.c文件:
- (3)test.c文件:
- 最后
-
前言
今天我们来聊一聊:数据结构中链表的双向循环带头链表,对于第一次听到双向循环带头链表的同学,可能会认为双向循环带头链表是十分复杂的,的确双向循环带头链表的结构是有点复杂,但是它的操作是非常简单的,非常便于操作,那么现在就由云小逸带你了解认识学习双向循环带头链表。
——————————————————————————————
1.链表的分类:
- 单向、双向
- 带头、不带头
- 循环、非循环
今天我们就来讲一讲链表中看似结构复杂的双向循环带头链表:
2.双向链表的初始化:
方法一:传双指针
void ListNodeInit(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)运行代码:
void ListPrint(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;}
尾插函数:
void ListNodePushBack(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)运行代码:
void ListNodePopBack(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)运行代码:
void ListNodePushFront(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)运行代码:
void ListNodePopFront(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;}return NULL;}
查找后返回的是结点的指针,可以用pos->data=某个数进而修改这个点的值!!!
(2)运行结果:
9.双向链表的中间插入:
(1)运行代码:
插入在指定位置的前面
void ListNodeInsert(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)运行代码:
void ListNodeErase(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.双向链表的销毁:
每一次用完链表后销毁是很有必要的,如果不销毁,将会导致内存的泄露,短时间内可能没用什么,且很难被发现,但时间长了,必将导致程序的崩溃,最终将导致时间和金钱的浪费!!!
这里介绍两种销毁:
方法一:销毁全部,不保留头结点:
void ListNodeDestroy(ListNode* phead){assert(phead);ListNode* cur = phead;while (cur != phead){ListNode* next = cur->next;free(cur);cur = NULL;cur = next;}free(phead);phead=NULL;}
方法二:保留头结点:
void ListNodeDestroy(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_WARNINGS 1#pragma once#include#include#includetypedef int LTDataType;typedef struct ListNode{struct ListNode* prev;LTDataTypedata;struct ListNode* next;}ListNode;ListNode* ListNodeBuy(LTDataType x);void ListNodeInit(ListNode** pphead);void ListPrint(ListNode* phead);void ListNodePushBack(ListNode* phead, LTDataType x);void ListNodePopBack(ListNode* phead);void ListNodePushFront(ListNode* phead, LTDataType x);void ListNodePopFront(ListNode* phead);ListNode* ListNodeFind(ListNode* phead, LTDataType x);void ListNodeInsert(ListNode* pos, LTDataType x);void ListNodeErase(ListNode* pos);void ListNodeDestroy(ListNode* phead);
(2)List.c文件:
#include"List.h"#define _CRT_SECURE_NO_WARNINGS 1ListNode* ListNodeBuy(LTDataType x){ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->next = NULL;newnode->prev = NULL;newnode->data=x;return newnode;}void ListNodeInit(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;}void ListPrint(ListNode* phead){assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}void ListNodePushBack(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;}void ListNodePopBack(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;}void ListNodePushFront(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;}void ListNodePopFront(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;}return NULL;}void ListNodeInsert(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;}void ListNodeErase(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;}void ListNodeDestroy(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_WARNINGS 1int main(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);return 0;}
最后
十分感谢你可以耐着性子把它读完和我可以坚持写到这里,送几句话,对你,也对我:
1.也许你要早上七点起床,晚上十二点睡觉,日复一日,踽踽独行。但只要笃定而努力地活着,即使生不逢时,你人生最坏的结果,也只是大器晚成。
2.这个世界根本不存在“不会”这回事。当你失去所有依靠的时候,你自然就什么都会了。
3.当你足够优秀时,你周围的一切自然都会好起来。
4.人一旦堕落,哪怕是短暂的几年,上帝就会以最快的速度,收走你的天赋和力量。5.你所做的事情,也许暂时看不到成果,但不要灰心或焦虑,你不是没有成长,而是在扎根。
最后如果觉得我写的还不错,请不要忘记点赞✌,收藏✌,加关注✌哦(。・ω・。)
愿我们一起加油,奔向更美好的未来,愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油,为自己点赞!