[数据结构]—带头双向循环链表——超详解

news/2025/2/20 18:48:14/

💓作者简介🎉：在校大二迷茫大学生

💖个人主页🎉：小李很执着

💗系列专栏🎉：数据结构

每日分享✨：旅行是为了迷路，迷路是为了遇上美好❣️❣️❣️

目录

💓1.总体布局

 💓2.详细解读

❣️1.创建双向链表节点

❣️2.初始化双向循环链表

❣️3.打印双向循环链表

❣️4.循环双向链表尾插

❣️5.双向循环链表中删除尾节点

❣️6.双向链表的头插操作

❣️7.双向链表的头部删除操作

❣️8.循环链表中查找指定值节点

❣️9.该函双向链表中指定节点pos的前面插入一个新的节点

❣️10.双向链表中删除某个节

❣️11.销毁一个循环双向链表

💓3.部分代码进阶

❣️1.根据2—9：void LTInsert(LTNode* pos, LTDataType x)

❣️2.根据2—10void LTErase(LTNode* pos)

💓4.整体代码

❣️1.List.h

❣️2.List.c

❣️3.Test.c

💓1.总体布局

1.创建双向链表节点

LTNode* CreateLTNode(LTDataType x)；

2.初始化双向循环链表

LTNode* LTInit();

3.打印双向循环链表
void LTPrint(LTNode* phead);

4.循环双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x);

5.双向循环链表中删除尾节点
void LTPopBack(LTNode* phead);

6.双向链表的头插操作

void LTPushFront(LTNode* phead, LTDataType x);

7.双向链表的头部删除操作
void LTPopFront(LTNode* phead);

8.循环链表中查找指定值节点

LTNode* LTFind(LTNode* phead, LTDataType x);

9.该函双向链表中指定节点pos的前面插入一个新的节点
void LTInsert(LTNode* pos, LTDataType x);

10.双向链表中删除某个节
void LTErase(LTNode* pos);

11.销毁一个循环双向链表

void LTDestroy(LTNode * phead); 

 💓2.详细解读

❣️1.创建双向链表节点

函数输入参数为节点的值x，函数返回一个指向节点的指针。

函数内部实现：

  1. 使用malloc函数为新节点分配内存空间，分配的大小为一个LTNode结构体的大小。

  2. 判断内存分配是否成功，如果分配失败，则输出错误信息并退出程序。

  3. 对新节点进行初始化，将节点的值设置为x，next指针和prev指针设置为NULL。

  4. 返回指向新节点的指针。

LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

❣️2.初始化双向循环链表

链表中的每个节点都是LTNode类型的结构体，其中包含一个指向前一个节点的指针prev和一个指向后一个节点的指针next。该函数首先创建一个值为-1的头节点，并将头节点的前一个节点和后一个节点都指向头节点本身，以形成一个空的双向循环链表。最后返回头节点的指针。

LTNode* LTInit()
{LTNode* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

❣️3.打印双向循环链表

其参数为双向循环链表的头结点指针，函数内部会从头结点开始遍历链表，并依次打印每个节点的值，直到遍历到头结点为止。最终输出的内容是形如“哨兵位<=>x<=>y<=>z<=>哨兵位”的字符串，其中x、y、z分别表示链表中的元素值。

void LTPrint(LTNode* phead)
{assert(phead);printf("哨兵位<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->val);cur = cur->next;}printf("\n");
}

❣️4.循环双向链表尾插

将一个元素x插入到链表的最后一个节点的后面。

函数接收两个参数，一个是指向链表头结点的指针phead，另一个是要插入到链表尾部的元素x。

首先使用assert函数检查参数phead是否为NULL，如果是则直接终止程序。

接着定义两个指针tail和newnode，tail指向链表的最后一个节点，newnode是要插入到链表尾部的新节点。

然后将新节点插入到链表尾部。具体步骤如下：

  1. 让tail节点的next指针指向newnode节点，即tail->next = newnode。

  2. 让newnode节点的prev指针指向tail节点，即newnode->prev = tail。

  3. 让newnode节点的next指针指向链表头节点phead，即newnode->next = phead。

  4. 让phead节点的prev指针指向newnode节点，即phead->prev = newnode。

这样就完成了在链表尾部插入新节点的操作。

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = CreateLTNode(x);// phead               tail  newnodetail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

❣️5.双向循环链表中删除尾节点

具体分析如下：

  1. 首先使用assert函数来判断phead是否为空，如果为空则程序立即终止。

  2. 由于是双向循环链表，在删除尾节点之前需要判断链表中是否存在节点。使用assert函数来判断phead的next指针是否指向phead本身，如果是则链表为空，程序立即终止。

  3. 设置指针tail指向链表的尾节点，并使用tailPrev指针来记录尾节点的前一个节点。

  4. 释放tail指向的节点，即删除尾节点。

  5. 将tailPrev节点的next指针指向phead节点，即将链表尾节点删除后，将尾节点的前一个节点的next指针指向头节点。

  6. 将phead节点的prev指针指向tailPrev节点，即将链表尾节点删除后，将头节点的prev指针指向链表的倒数第二个节点，以保证链表仍然是双向循环的。

注意，该函数的前提条件是链表中至少存在一个节点，否则会因为assert函数判断失败而终止程序。在使用该函数时需要注意链表的状态。

void LTPopBack(LTNode* phead)
{assert(phead);// 空assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;}

❣️6.双向链表的头插操作

将一个新节点插入到链表的第一个位置。

输入参数：

  • phead：头结点指针，其中包含链表的头指针和尾指针；
  • x：要插入的节点的值。

函数流程：

  1. 创建新节点，其数据域为x；
  2. 获取原链表中第一个节点的指针first；
  3. 将新节点插入到头结点之后的位置，使得新节点为原链表的第一个节点，first成为新节点的后继节点；
  4. 将原第一个节点的prev指针指向新节点，完成头插操作。

注意事项：

  • 函数中使用了assert宏，用于判断头结点是否存在；
  • 操作需要改变多个节点的指针，需要仔细考虑顺序和细节。
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = CreateLTNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

❣️7.双向链表的头部删除操作

1. 首先使用assert函数判断传入的链表头结点指针phead是否为空，如果为空则终止程序运行。

2. 再通过assert函数判断链表是否为空，即头结点的下一个结点是否还是头结点自身，如果是则说明链表为空，同样终止程序运行。

3. 取出链表头结点的下一个结点first，以及第二个结点second。

4. 将头结点的下一个结点指向第二个结点，同时将第二个结点的前一个结点指向头结点，完成删除操作。

5. 最后使用free函数释放被删除的结点first的内存空间，并将first指针置为空。

void LTPopFront(LTNode* phead)
{assert(phead);// 空assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;}

❣️8.循环链表中查找指定值节点

参数说明：

  • phead：指向循环链表头节点的指针。
  • x：需要查找的值。

函数实现步骤：

  1. 首先，断言链表头节点不为空。
  2. 定义一个指针 cur，指向链表的第一个节点。
  3. 遍历链表，如果找到了值为 x 的节点，直接返回该节点指针。
  4. 如果遍历完整个链表都没有找到值为 x 的节点，就返回 NULL 指针，表示没有找到。

需要注意的是，该函数是针对循环链表的查找实现，因此需要判断 cur 指针是否回到了头节点 phead，如果回到了头节点，则表示遍历完整个链表，需要退出循环。

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}

❣️9.该函双向链表中指定节点pos的前面插入一个新的节点

节点的值为x。函数实现需要注意以下几点：

  1. 首先需要判断pos节点是否存在，若不存在则直接返回。

  2. 创建一个新节点newnode，并将其值赋为x。

  3. 获取pos节点的前一个节点posPrev，posPrev节点和newnode节点之间需要插入新的节点。

  4. 将posPrev节点的next指针指向newnode节点，将newnode节点的prev指针指向posPrev节点，将newnode节点的next指针指向pos节点，将pos节点的prev指针指向newnode节点。

  5. 确保插入操作顺利完成后，函数返回。

// 在pos前面的插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = CreateLTNode(x);// posprev newnode posposPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

❣️10.双向链表中删除某个节

输入参数是要删除的节点指针pos。

首先通过断言语句assert(pos)来检查输入参数是否为空。

然后通过pos指针找到它的前驱节点posPrev和后继节点posNext，将它们之间的连接断开，即将posPrev的next指针指向posNext，将posNext的prev指针指向posPrev。

最后通过free函数释放pos指向的内存空间，完成删除操作。

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

❣️11.销毁一个循环双向链表

参数phead是链表的头指针，其指向一个LTNode类型的结构体，该结构体中有两个指针，分别指向链表的头节点和尾节点。

首先，函数中使用了断言assert(phead)，判断参数phead是否为空指针，如果是，程序会终止运行，有助于在调用函数时发现错误。

然后，定义一个指针cur指向链表第一个节点，然后使用while循环遍历除了头节点之外的所有节点，直到遍历完所有节点为止。

在循环中，使用一个指针next指向当前节点的下一个节点，然后释放当前节点的内存空间，最后将cur指向下一个节点。

循环结束后，释放链表头节点的内存空间，销毁整个链表。

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

💓3.部分代码进阶

❣️1.根据2—9：void LTInsert(LTNode* pos, LTDataType x)

 1.循环双向链表尾插操作

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead, x);
}

2. 双向链表的头插操作

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead->next, x);
}

❣️2.根据2—10void LTErase(LTNode* pos)

1.双向循环链表中删除尾节点

void LTPopBack(LTNode* phead)
{assert(phead);LTErase(phead->prev);
}

2. 双向链表的头部删除操作

void LTPopFront(LTNode* phead)
{assert(phead);// 空assert(phead->next != phead);LTErase(phead->next);
}

💓4.整体代码

❣️1.List.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType val;
}LTNode;LTNode* CreateLTNode(LTDataType x);
LTNode* LTInit();
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);void LTInsert(LTNode* pos, LTDataType x);void LTErase(LTNode* pos);void LTDestroy(LTNode * phead);

❣️2.List.c

#include"List.h"LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}LTNode* LTInit()
{LTNode* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTPrint(LTNode* phead)
{assert(phead);printf("哨兵位<=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->val);cur = cur->next;}printf("\n");
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//LTNode* tail = phead->prev;//LTNode* newnode = CreateLTNode(x);phead               tail  newnode//tail->next = newnode;//newnode->prev = tail;//newnode->next = phead;//phead->prev = newnode;LTInsert(phead, x);
}void LTPopBack(LTNode* phead)
{assert(phead);// 空assert(phead->next != phead);/*LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;*/LTErase(phead->prev);
}//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = CreateLTNode(x);
//
//	newnode->next = phead->next;
//	phead->next->prev = newnode;
//
//	phead->next = newnode;
//	newnode->prev = phead;
//
//}void LTPushFront(LTNode* phead, LTDataType x)
{/*assert(phead);LTNode* newnode = CreateLTNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;*/LTInsert(phead->next, x);
}void LTPopFront(LTNode* phead)
{assert(phead);// 空assert(phead->next != phead);/*LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;*/LTErase(phead->next);
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}// 在pos前面的插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = CreateLTNode(x);// posprev newnode posposPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}// 删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posNext = pos->next;LTNode* posPrev = pos->prev;posPrev->next = posNext;posNext->prev = posPrev;free(pos);//pos = NULL;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);//phead = NULL;
}

❣️3.Test.c

#include "List.h"void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 5);LTPushBack(plist, 4);LTPrint(plist);LTPushFront(plist, 10);LTPrint(plist);
}void TestList2()
{LTNode* plist = LTInit();LTPushFront(plist, 10);LTPushFront(plist, 20);LTPushFront(plist, 30);LTPushFront(plist, 40);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);
}void TestList3()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 5);LTPushBack(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){pos->val *= 10;}LTPrint(plist);LTInsert(pos, 30000);LTPrint(plist);LTInsert(plist, -1);LTPrint(plist);LTInsert(plist, -2);LTPrint(plist);
}void TestList4()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 5);LTPushBack(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTErase(pos);pos = NULL;}LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{TestList4();return 0;
}


http://www.ppmy.cn/news/1218651.html

相关文章

深圳市第十三届职工技术创新运动会暨2023深圳技能大赛火热报名中

深圳市第十三届职工技术创新运动会暨2023深圳技能大赛火热报名中

阅读更多...
Mysql 提升索引效率优化的八种方法

Mysql 提升索引效率优化的八种方法

目录 1. 选择唯一性索引 2. 为经常需要排序、分组和联合操作的字段建立索引 3. 为常作为查询条件的字段建立索引 4. 限制索引的数目 5. 尽量使用数据量少的索引 6. 数据量小的表最好不要使用索引 7. 尽量使用前缀来索引 8. 删除不再使用或者很少使用的索引 总结 索引的…
阅读更多...
conda创建新环境时404问题 linux

conda创建新环境时404问题 linux

vi ~/.condarc若不存在该路径&#xff0c;则新建 然后在里边配置国内源&#xff1a; channels:- defaults show_channel_urls: true default_channels:- https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/main- https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/r- ht…
阅读更多...
IO学习系列之缓冲区

IO学习系列之缓冲区

缓冲区&#xff08;本文特指标准IO的缓冲区&#xff09;&#xff1a;缓冲区的类型&#xff1a;一、行缓冲&#xff1a;和终端相关的缓冲区&#xff1b;例如&#xff1a;标准输入&#xff08;stdin&#xff09;、标准输出&#xff08;stdout&#xff09;&#xff1b;内存空间的大…
阅读更多...
NovelD: A Simple yet Effective Exploration Criterion论文笔记

NovelD: A Simple yet Effective Exploration Criterion论文笔记

NovelD:一种简单而有效的探索准则 1、Motivation 针对稀疏奖励环境下的智能体探索问题&#xff0c;许多工作中采用各种内在奖励(Intrinsic Reward)设计来指导困难探索环境中的探索 &#xff0c;例如&#xff1a; ICM&#xff1a;基于前向动力学模型的好奇心驱动探索RND&…
阅读更多...
【React】Antd 组件基本使用

【React】Antd 组件基本使用

Antd 组件基本使用 第一步 安装并引入 antd 包 使用命令下载这个组件库 yarn add antd在我们需要使用的文件下引入&#xff0c;我这里是在 App.jsx 内引入 import { Button } from antd现在我们可以在 App 中使用 Button 组件 <div>App..<Button type"prima…
阅读更多...
正则表达式：验证中英文长度限制16个字符(8个中文)，支持中文字母数字或者下划线

正则表达式：验证中英文长度限制16个字符(8个中文)，支持中文字母数字或者下划线

1.中文字母数字或者下划线 2.长度限制16个字符(8个中文) html: <input class"form-control text" maxlength"17" name"name" placeholder"输入16个字符以内的备注名称" type"text" v-model.trim"remarkName" …
阅读更多...
交换机Vlan和端口配置（H3C）

交换机Vlan和端口配置（H3C）

交换机Vlan配置&#xff08;H3C&#xff09; 配置VLAN配置VLAN接口的IP地址开启ARP网关保护功能&#xff0c;配置被保护的网关IP地址 配置VLAN Vlan物理端口3GigabitEthernet 1/0/1 ~ GigabitEthernet 1/0/14 &#xff1b;GigabitEthernet 2/0/1 ~ GigabitEthernet 2/0/1450Gi…
阅读更多...
最新文章

Copyright @ 2022~2023