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

🕗 发布于 2024-11-10 18:16 数据结构 笔记链表

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

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 顺序表与链表的对比

在这里插入图片描述

原文地址：https://blog.csdn.net/2402_84532723/article/details/143655422

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：逐梦代码深林：Linux编译之舞，链接之诗——自举、动静态库的浪漫旅程
下一篇：Python数据分析案例64——杭帮菜美食探索数据分析可视化

如何构建安全可靠的 HarmonyOS 应用
本文将深入探讨 HarmonyOS App 的安全编码规范与最佳实践，帮助开发者在代码编写中避免常见的安全漏洞，如 SQL 注入、XSS攻击等。我们将提供具体的编码示例，并结合ArkUI和ArkTS实
阅读更多2024-11-16
js像循环数组那样循环一个数字，Array.from()
js像循环数组那样循环一个数字，Array.from()
阅读更多2024-11-16
【C++笔记】vector使用详解及模拟实现
vector的文档使用STL的三个境界：能用、明理、能扩展，下面学习vector，我们也按照这个境界去学习。vector是可以改变大小的数组序列容器，也就是数据结构的顺序表。构造函数声明接口说明vec
阅读更多2024-11-16
Java线程池：ThreadPoolExecutor原理解析
本文介绍了线程池的基本概念、主要参数、工作流程，以及 execute() 方法的源码分析，此外，还讨论了在实际应用中可能遇到的陷阱和问题。
阅读更多2024-11-16
1.两数之和-力扣（LeetCode）
1.两数之和-力扣（LeetCode）
阅读更多2024-11-16
Xss挑战（跨脚本攻击）
这里将script，on，src，data，href，进行了过滤，并且在尝试的时候关键字双写不能用了，那么这里直接选择不去闭合标签，直接使用伪协议，但是发现javascript也被拆开了，这里可以对伪
阅读更多2024-11-16
《Python 网络爬虫》
本文介绍了 Python 网络爬虫的基本概念、技术原理、常用工具以及实战案例，希望能够帮助读者快速掌握 Python 网络爬虫技术。在实际应用中，需要根据具体的需求选择合适的工具和方法，并注意遵守法律
阅读更多2024-11-16
UEFI学习（五）——启动框架
https://www.zhihu.com/question/36313402/answer/2398532123UEFI（统一可扩展固件接口）在启动过程主要有以下几个阶段：
阅读更多2024-11-16
【洛谷】T539820 202411A Giants
C++ LGR-207-Div.4】洛谷入门赛 #29 第一题
阅读更多2024-11-16
Python 正则表达式进阶用法：量词与范围
匹配前面的字符零次或多次，相当于“任意多次”。：匹配前面的字符一次或多次，相当于“至少一次”。?：匹配前面的字符零次或一次，相当于“可有可无”。{n}：匹配前面的字符n次。{n,}：匹配前面的字符至少
阅读更多2024-11-16

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

1 双向循环链表的介绍

2 双向循环链表的实现

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

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

2.2.1 初始化链表

2.2.2 创建新节点

2.2.3 链表尾插

2.2.4 链表头插

2.2.5 链表尾删

2.2.6 链表头删

2.2.7 链表的查找

2.2.8 从pos位置之前插入

2.2.9 删除pos位置

2.2.10 链表的打印

2.2.11 销毁链表

3 完整代码的实现

4 顺序表与链表的对比

相关文章