作者:云小逸
个人主页:云小扬的主页
码云:云小扬 (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.链表的分类:

  1. 单向、双向
  2. 带头、不带头
  3. 循环、非循环

    今天我们就来讲一讲链表中看似结构复杂的双向循环带头链表

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->nexthead->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插在pheadfirst(头结点后的第一个结点)

(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.你所做的事情,也许暂时看不到成果,但不要灰心或焦虑,你不是没有成长,而是在扎根。

最后如果觉得我写的还不错,请不要忘记点赞✌,收藏✌,加关注✌哦(。・ω・。)

愿我们一起加油,奔向更美好的未来,愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油,为自己点赞!