当前位置： 首页 > news >正文

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

news 2024/11/15 0:17:06

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

1 双向循环链表的介绍

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

在这里插入图片描述

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

2 双向循环链表的实现

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

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

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

//初始化双向循环带头链表‘
LTNode* ListInit();//打印
void ListPrint(plist);//尾插
void ListPushBack(LTNode* phead, LDataType x);//尾删
void ListPopBack(LTNode* phead);//头插
void ListPushFront(LTNode* phead, LDataType x);//头删
void ListPopFront(LTNode* phead);//查找
LTNode* ListFind(LTNode* phead, LDataType x);//pos位置之前插入
void ListInsert(LTNode* pos, LDataType x);//删除pos位置
void ListErase(LTNode* pos);//销毁链表
void ListDestroy(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 链表尾插

//尾插
void ListPushBack(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 链表头插

//头插
void ListPushFront(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 链表尾删

//尾删
void ListPopBack(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 链表头删

//头删
void ListPopFront(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;}}return NULL;
}

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

2.2.8 从pos位置之前插入

//pos位置之前插入
void ListInsert(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位置
void ListErase(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 链表的打印

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

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

2.2.11 销毁链表

//销毁链表
void ListDestroy(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文件

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LDataType;typedef struct ListNode
{LDataType val;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化双向循环带头链表‘
LTNode* ListInit();//打印
void ListPrint(plist);//尾插
void ListPushBack(LTNode* phead, LDataType x);//尾删
void ListPopBack(LTNode* phead);//头插
void ListPushFront(LTNode* phead, LDataType x);//头删
void ListPopFront(LTNode* phead);//查找
LTNode* ListFind(LTNode* phead, LDataType x);//pos位置之前插入
void ListInsert(LTNode* pos, LDataType x);//删除pos位置
void ListErase(LTNode* pos);//销毁链表
void ListDestroy(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;
}//打印
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->val);cur = cur->next;}printf("\n");
}//销毁链表
void ListDestroy(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;
}//尾插
void ListPushBack(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;
}//尾删
void ListPopBack(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);
}//头插
void ListPushFront(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;
}//头删
void ListPopFront(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;}}return NULL;
}//pos位置之前插入
void ListInsert(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位置
void ListErase(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"void ListTest1()
{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);}
int main()
{ListTest1();return 0;
}

4 顺序表与链表的对比

在这里插入图片描述


http://www.mrgr.cn/news/69740.html

相关文章：

  • 标准C++ 字符串
  • 658. 找到 K 个最接近的元素
  • Java——异常处理
  • 论文阅读《BEVFormer v2》
  • 【疑难杂症】电脑休眠后无法开机，进入 steamVR 时电脑突然黑屏关机
  • 《TCP/IP网络编程》学习笔记 | Chapter 9：套接字的多种可选项
  • Web前端效果展示：腺体超声图像分割
  • 2024年下半年软件设计师上午真题【回忆】
  • 常用的c++新特性--＞day03
  • ORB-SLAM2源码学习：ORBextractor.cc：ORBextractor特征提取器③
  • pg_dump -Fc 导出的自定义格式数据库文件 相关操作
  • Unity性能优化-具体操作
  • [docker] container 通信 -- bridge
  • Java 8 特性
  • ROS1 Nodelets 与 ROS2 rclcpp_components 多节点运行以及功能插件
  • 手把手教你写Unity3D飞机大战(6)玩家子弹射击之瞄准程序（射线检测）
  • 平衡二叉树
  • 【含文档】基于ssm+jsp的旅游网站（含源码+数据库+lw）
  • 【数据结构实战】从零开始打造你的专属链表
  • FPGA 第5讲 点亮你的LED灯
  • AI重塑软件开发流程
  • A025-基于SpringBoot的售楼管理系统的设计与实现
  • 【网络安全】Nginx功能快速入门
  • 05_docker 安装常用软件
  • 【GPTs】EmojiAI：轻松生成趣味表情翻译
  • Linux服务器进程的控制与进程之间的关系