0
0

数据结构之带头双向循环链表

前言：前面我们实现了顺序表和单链表，这次来实现一个结构更复杂的链表-----带头双向循环链表。不要被它的名字吓到哦，只是结构复杂而已，它的结构更有利于代码的实现。

1 双向循环链表的介绍

有了单链表的基础，要实现这个双向循环带头链表其实并不难。下面我们先来了解一下什么是双向循环带头链表。

在这里插入图片描述

这就是双向循环带头链表的结构图，可以很清晰的看到，这个链表需要两个指针，一个指向后继结点，一个指向前驱节点，其次还需要一个头结点。只是这个头结点并不需要存储有效数据。

2 双向循环链表的实现

2.1 双向循环带头链表的定义

//存储的数据类型typedefint LDataType;//链表的定义typedefstructListNode{
    LDataType val;structListNode* next;//指向后继节点structListNode* prev;//指向前驱节点}LTNode;

2.2 双向循环带头链表的接口

//初始化双向循环带头链表‘
LTNode*ListInit();//打印voidListPrint(plist);//尾插voidListPushBack(LTNode* phead, LDataType x);//尾删voidListPopBack(LTNode* phead);//头插voidListPushFront(LTNode* phead, LDataType x);//头删voidListPopFront(LTNode* phead);//查找
LTNode*ListFind(LTNode* phead, LDataType x);//pos位置之前插入voidListInsert(LTNode* pos, LDataType x);//删除pos位置voidListErase(LTNode* pos);//销毁链表voidListDestroy(LTNode* phead);

2.2.1 初始化链表

//初始化双向循环带头链表
LTNode*ListInit(){//哨兵位头结点
    LTNode* phead =(LTNode*)malloc(sizeof(LTNode));if(phead ==NULL){printf("malloc fail\n");exit(-1);}
    phead->next = phead;
    phead->prev = phead;return phead;}

在这里插入图片描述

2.2.2 创建新节点

//创建新节点
LTNode*BuyListNode(LDataType x){
    LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){printf("malloc fail\n");exit(-1);}
    newnode->val = x;
    newnode->prev=newnode->next=NULL;return newnode;}

2.2.3 链表尾插

//尾插voidListPushBack(LTNode* phead, LDataType x){assert(phead);
    LTNode* tail = phead->prev;/*LTNode* newnode = (LTNode*)malloc(sizeof(LDataType));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->val = x;*/
    LTNode* newnode =BuyListNode(x);
    newnode->next = phead;
    phead->prev = newnode;
    newnode->prev = tail;
    tail->next = newnode;}

在这里插入图片描述

通过phead->prev就可以找到链表的尾节点，增加的节点newnode->prev
应该链接链表尾节点，链表的尾节点链接newnode,newnode->next应
该链接链表的头结点，链表的头结点的prev保存newnode的地址，使
newnode成为链表新的尾节点。

2.2.4 链表头插

//头插voidListPushFront(LTNode* phead, LDataType x){assert(phead);
    LTNode* newnode =BuyListNode(x);
    LTNode* pheadNext = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    pheadNext->prev = newnode;
    newnode->next = pheadNext;}

在这里插入图片描述

先创建一个指针指向头结点的后继结点，再让newnode->next保存该
节点的地址，该节点的prev保存newnode的地址，phead->next保存
newnode的地址，newnode->prev保存头结点的地址。

2.2.5 链表尾删

//尾删voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    tailPrev->next = phead;
    phead->prev = tailPrev;free(tail);}

在这里插入图片描述

通过phead->prev找到链表尾节点，再通过尾节点的prev找到尾节点
的前驱节点，让该前驱节点的next指向phead,phead->prev指向该前
驱节点，最后释放尾节点。

2.2.6 链表头删

//头删voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* head = phead->next;
    LTNode* next = head->next;
    next->prev = phead;
    phead->next = next;free(head);}

在这里插入图片描述

首先通过phead->next找到链表头结点的后继结点，再通过该后继结点找到下一个节点，使该节点的prev保存头结点的地址，头结点的next保存该节点的地址，最后释放该后继结点。

2.2.7 链表的查找

//查找
LTNode*ListFind(LTNode* phead, LDataType x){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){if(cur->val == x){return cur;}else{
            cur = cur->next;}}returnNULL;}

从头结点的后继结点开始遍历查找，找到了就返回该节点的地址，找不到返回NULL（当再一次遍历到头结点时，说明未找到）。

2.2.8 从pos位置之前插入

//pos位置之前插入voidListInsert(LTNode* pos, LDataType x){assert(pos !=NULL);
    LTNode* newnode =BuyListNode(x);
    LTNode* posPrev = pos->prev;
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;}

在这里插入图片描述

首先找到pos位置的前驱节点，再让newnode->prev指向该前驱节
点，该前驱节点的next指向newnode,pos->prev指newnode,
newnode->next指向pos。

2.2.9 删除pos位置

//删除pos位置voidListErase(LTNode* pos){assert(pos !=NULL);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;free(pos);}

在这里插入图片描述

找到pos位置的前驱节点和后继结点，让该前驱节点的next指向该后
继结点，该后继结点的prev指向该前驱节点。

2.2.10 链表的打印

//打印voidListPrint(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->val);
        cur = cur->next;}printf("\n");}

从头结点的后继结点开始遍历链表，当节点不是头结点时就打印该节点的值。

2.2.11 销毁链表

//销毁链表voidListDestroy(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){
        LTNode* tmp = cur;
        cur = cur->next;free(tmp);
        tmp =NULL;}
    cur =NULL;
    phead =NULL;}

从头结点的后继结点开始销毁，先记录该后继结点的下一个节点，再销毁该后继结点。重复上述操作，直到再一次回到头结点的位置，此时销毁该头结点。

3 完整代码的实现

List.h文件

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint LDataType;typedefstructListNode{
    LDataType val;structListNode* next;structListNode* prev;}LTNode;//初始化双向循环带头链表‘
LTNode*ListInit();//打印voidListPrint(plist);//尾插voidListPushBack(LTNode* phead, LDataType x);//尾删voidListPopBack(LTNode* phead);//头插voidListPushFront(LTNode* phead, LDataType x);//头删voidListPopFront(LTNode* phead);//查找
LTNode*ListFind(LTNode* phead, LDataType x);//pos位置之前插入voidListInsert(LTNode* pos, LDataType x);//删除pos位置voidListErase(LTNode* pos);//销毁链表voidListDestroy(LTNode* phead);

List.c文件

#define_CRT_SECURE_NO_WARNINGS#include"List.h"//初始化双向循环带头链表
LTNode*ListInit(){//哨兵位头结点
    LTNode* phead =(LTNode*)malloc(sizeof(LTNode));if(phead ==NULL){printf("malloc fail\n");exit(-1);}
    phead->next = phead;
    phead->prev = phead;return phead;}//打印voidListPrint(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->val);
        cur = cur->next;}printf("\n");}//销毁链表voidListDestroy(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){
        LTNode* tmp = cur;
        cur = cur->next;free(tmp);
        tmp =NULL;}
    cur =NULL;
    phead =NULL;}//创建新节点
LTNode*BuyListNode(LDataType x){
    LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){printf("malloc fail\n");exit(-1);}
    newnode->val = x;//newnode->prev = newnode->next = NULL;return newnode;}//尾插voidListPushBack(LTNode* phead, LDataType x){assert(phead);
    LTNode* tail = phead->prev;/*LTNode* newnode = (LTNode*)malloc(sizeof(LDataType));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->val = x;*/
    LTNode* newnode =BuyListNode(x);
    newnode->next = phead;
    phead->prev = newnode;
    newnode->prev = tail;
    tail->next = newnode;}//尾删voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;//free(tail);
    tailPrev->next = phead;
    phead->prev = tailPrev;free(tail);}//头插voidListPushFront(LTNode* phead, LDataType x){assert(phead);
    LTNode* newnode =BuyListNode(x);
    LTNode* pheadNext = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    pheadNext->prev = newnode;
    newnode->next = pheadNext;}//头删voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* head = phead->next;
    LTNode* next = head->next;
    next->prev = phead;
    phead->next = next;free(head);}//查找
LTNode*ListFind(LTNode* phead, LDataType x){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){if(cur->val == x){return cur;}else{
            cur = cur->next;}}returnNULL;}//pos位置之前插入voidListInsert(LTNode* pos, LDataType x){assert(pos !=NULL);
    LTNode* newnode =BuyListNode(x);
    LTNode* posPrev = pos->prev;
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;}//删除pos位置voidListErase(LTNode* pos){assert(pos !=NULL);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;free(pos);}

test.c文件

#define_CRT_SECURE_NO_WARNINGS#include"List.h"voidListTest1(){
    LTNode* plist =ListInit();ListPushBack(plist,1);ListPushBack(plist,2);ListPushBack(plist,3);ListPushBack(plist,4);ListPushBack(plist,5);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPrint(plist);ListPushFront(plist,6);ListPushFront(plist,7);ListPushFront(plist,8);ListPushFront(plist,9);ListPushFront(plist,10);ListPrint(plist);ListPopFront(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist);

    LTNode* pos =ListFind(plist,2);if(NULL!= pos){printf("找到了\n");}else{printf("找不到\n");}ListInsert(pos,10);ListPrint(plist);

    pos =ListFind(plist,1);ListErase(pos);ListPrint(plist);ListDestroy(plist);
    plist =NULL;//ListPrint(plist);}intmain(){ListTest1();return0;}

4 顺序表与链表的对比

在这里插入图片描述

标签： 数据结构 笔记 链表
本文转载自: https://blog.csdn.net/2402_84532723/article/details/143655422
版权归原作者 CodePracticer 所有， 如有侵权，请联系我们删除。
登录后发布评论

“数据结构之带头双向循环链表”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

生产力工具｜vscode for mac的安装python库和使用虚拟环境（一）

JumpServer （开源堡垒机）

基于Hadoop的短视频数据分析的设计与实现

【面试题】Hive 查询：如何查找用户连续三天登录的记录

Spark环境搭建

前端数据可视化常用工具大盘点

用exceljs和file-saver插件实现纯前端表格导出Excel（支持样式配置，多级表头）

文章导航