带头+双向+循环链表的实现

目录

  • 1. 链表
    • 1.1 带头双向循环链表
  • 2. 链表的实现
    • 2.1 结构体
    • 2.2 初始化
    • 2.3 打印
    • 2.4 判断空不能删
    • 2.5 尾插
    • 2.6 头插
    • 2.7 尾删
    • 2.8 头删
    • 2.9 查找
    • 2.10 在pos之前插入
    • 2.11 删除pos位置的值
    • 2. 12 销毁
    • 2.13 创建节点
  • 3. test主函数
  • 4. List.c文件
  • 5. List.h文件

1. 链表

1.1 带头双向循环链表

在这里插入图片描述
双向带头循环链表（Doubly Linked Circular List）是一种特殊的链表结构，其中每个节点都包含两个指针：一个指向前一个节点（prev），另一个指向后一个节点（next）。与普通双向链表不同，双向带头循环链表的第一个节点（通常称为头节点）的 prev 指针指向链表的最后一个节点，而最后一个节点的 next 指针则指向头节点，形成一个闭环。头节点不存储数据，只用于方便操作。

以下是双向带头循环链表的一些主要特点：

  • 循环性：链表的最后一个节点的 next 指针指向头节点，头节点的 prev 指针指向最后一个节点，形成一个闭环。
  • 带头节点：链表包含一个不存储数据的头节点，其 prev 指针指向最后一个节点，next 指针指向第一个数据节点。头节点的存在可以简化一些操作，如插入和删除节点。
  • 双向性：每个节点都有两个指针，一个指向前一个节点，另一个指向后一个节点。这使得在链表中向前和向后遍历都非常容易。

双向带头循环链表的基本操作包括：

  • 初始化：创建一个头节点，并设置其 prev 和 next 指针都指向自己。
  • 插入节点：在指定位置插入新节点，并更新相邻节点的指针。
  • 删除节点：删除指定节点，并更新相邻节点的指针。
  • 遍历：从头节点开始，可以向前或向后遍历整个链表。
    这种链表结构常用于需要频繁在链表中进行插入和删除操作的场景，因为双向结构使得查找和更新节点的前后指针都非常高效。而循环性则避免了处理边界条件的复杂性。头节点的存在进一步简化了这些操作。

2. 链表的实现

2.1 结构体

首先要先把结构体定义出来，因为是带头双向循环链表，所以要有两个指针域一个指向头，一个指向尾，还要有一个数据域。

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;//头指针struct ListNode* next;//尾指针LTDataType data;//数据域
}LTNode;

2.2 初始化

初始化链表，防止都是随机值。

//初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}

2.3 打印

这个就得注意点了，只能是cur != phead不能是cur->next != phead，这样的话链表的最后一个就不能打印出来，少了一个。

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

2.4 判断空不能删

当只有头节点的时候再删就出问题了。

//判断空不能删
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

2.5 尾插

只有找到phead->prev就是尾，所以实现起来也比较简单，只要改变4个指针的指向就可以了。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;phead->prev = newnode;newnode->next = phead;newnode->prev = newnode;*/LTInsert(phead->prev, x);
}

测试代码：

//尾插测试
void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.6 头插

因为是带哨兵位的，要找到phead->next这就是我们要头插的位置。

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* tail = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = tail;tail->prev = newnode;*/LTInsert(phead->next, x);
}

测试代码：

//头插测试
void TestList2()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.7 尾删

跟尾插是一样的，改4个指针的指向，再free掉。

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));/*LTNode* cur = phead->prev;LTNode* tail = cur->prev;free(cur);tail->next = phead;phead->prev = tail;*/LTErase(phead->next);
}

测试代码：

//尾删测试
void TestList3()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.8 头删

哨兵位的next就是当前的头，改指针的指向。

//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));/*LTNode* next = phead->next;LTNode* tail = next->next;free(next);phead->next = tail;tail->prev = phead;*/LTErase(phead->prev);
}

测试代码：

//头删测试
void TestList4()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.9 查找

尽量不要动头指针，最好是用一个指针记录下来，不然找不到头指针，再去遍历。

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

2.10 在pos之前插入

//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

3之前插入40测试代码：

void TestList8()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTInsert(pos, 30);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.11 删除pos位置的值

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

删除3位置测试代码：

void TestList9()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTErase(pos);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2. 12 销毁

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

2.13 创建节点

写一个函数创建节点，不然每次要创建节点的时候都得写一个，现在直接调用就可以。

//创建节点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("BuyLTNode");return NULL;}newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}

3. test主函数

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"//尾插测试
void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTDestroy(plist);plist = NULL;
}//头插测试
void TestList2()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTDestroy(plist);plist = NULL;
}//尾删测试
void TestList3()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;
}//头删测试
void TestList4()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;
}void TestList8()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTInsert(pos, 30);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}void TestList9()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTErase(pos);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{TestList9();return 0;
}

4. List.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"//声明
LTNode* BuyLTNode(LTDataType x);//初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}//打印
void LTPrint(LTNode* phead)
{assert(phead);printf("哨兵位<==>");LTNode* cur = phead->next;while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}//判断空不能删
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//创建节点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("BuyLTNode");return NULL;}newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;phead->prev = newnode;newnode->next = phead;newnode->prev = newnode;*/LTInsert(phead, x);
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* tail = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = tail;tail->prev = newnode;*/LTInsert(phead->next, x);
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));/*LTNode* cur = phead->prev;LTNode* tail = cur->prev;free(cur);tail->next = phead;phead->prev = tail;*/LTErase(phead->next);
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));/*LTNode* next = phead->next;LTNode* tail = next->next;free(next);phead->next = tail;tail->prev = phead;*/LTErase(phead->prev);
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}//删除pos位置的值		
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

5. List.h文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;//初始化
LTNode* LTInit();//打印
void LTPrint(LTNode* phead);//判断空不能删
bool LTEmpty(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置的值		
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode* phead);

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/349561.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

AI大模型探索之路-实战篇：智能化IT领域搜索引擎之知乎网站数据获取（初步实践）

AI大模型探索之路-实战篇：智能化IT领域搜索引擎之知乎网站数据获取（初步实践）

系列篇章&#x1f4a5; No.文章1AI大模型探索之路-实战篇&#xff1a;智能化IT领域搜索引擎的构建与初步实践2AI大模型探索之路-实战篇&#xff1a;智能化IT领域搜索引擎之GLM-4大模型技术的实践探索3AI大模型探索之路-实战篇&#xff1a;智能化IT领域搜索引擎之知乎网站数据获…
阅读更多...
Unity：Text-TextMeshPro 不显示中文

Unity：Text-TextMeshPro 不显示中文

共计四步&#xff1a; 一、去C盘复制一份字体&#xff1a; C:\Windows\Fonts二、粘贴到你的项目里&#xff08;任意文件位置&#xff09;&#xff0c;得到“MSYH”&#xff1a; 三、右键字体文件&#xff0c;依次点击create–>TextMeshPro–>FontAsset&#xff1a; …
阅读更多...
数据预处理——调整方差、标准化、归一化（Matlab、python）

数据预处理——调整方差、标准化、归一化（Matlab、python）

对数据的预处理&#xff1a; (a)、调整数据的方差&#xff1b; (b)、标准化&#xff1a;将数据标准化为具有零均值和单位方差&#xff1b;&#xff08;均值方差归一化(Standardization)&#xff09; (c)、最值归一化&#xff0c;也称为离差标准化&#xff0c;是对原始数据的…
阅读更多...
0. 云原生之基于乌班图远程开发

0. 云原生之基于乌班图远程开发

云原生专栏大纲 文章目录 安装乌班图配置静态IP重置root密码开启root远程登录开启远程SSH访问安装docker安装docker-compose安装Edge浏览器安装搜狗输入法安装TeamViewer安装虚拟显示器安装JDK安装maven安装vscodevscode插件安装VSCode配置maven、git、jdk、自动报错vscode快捷…
阅读更多...
C++面向对象：多态性

C++面向对象：多态性

多态性 1.概念 多态性是面向对象的程序设计的一个重要特征。在面向对象的方法中一般是这样表述多态的&#xff1a;向不同的对象发送同一个信息&#xff0c;不同的对象在接收时会产生不同的行为。也就是说&#xff0c;每个对象用自己的方式去响应共同的消息。 2.典例 下面这…
阅读更多...
MPLS提高网络服务质量的原理

MPLS提高网络服务质量的原理

MPLS&#xff08;Multiprotocol Label Switching&#xff0c;多协议标签交换&#xff09;是一种网络技术&#xff0c;它能够提高网络的服务质量&#xff08;Quality of Service&#xff0c;QoS&#xff09;以及整体性能。MPLS通过以下几种方式来提升网络服务质量&#xff1a;标…
阅读更多...
Unity引擎在UI上渲染粒子播放

Unity引擎在UI上渲染粒子播放

大家好&#xff0c;我是阿赵。   在UI上面显示粒子特效&#xff0c;如果把粒子系统直接拖到Canvas里面&#xff0c;会存在很多问题&#xff0c;比如层级问题、裁剪问题等。这里分享一种用MaskableGraphic和UIVertex来显示粒子特效的方法。 一、 MaskableGraphic和UIVertex简…
阅读更多...
r语言数据分析案例25-基于向量自回归模型的标准普尔 500 指数长期预测与机制分析

r语言数据分析案例25-基于向量自回归模型的标准普尔 500 指数长期预测与机制分析

一、背景介绍 2007 年的全球经济危机深刻改变了世界经济格局&#xff0c;引发了一系列连锁反应&#xff0c;波及各大洲。经济增长停滞不前&#xff0c;甚至在某些情况下出现负增长&#xff0c;给出口导向型发展中国家带来了不确定性。实体经济受到的冲击尤为严重&#xff0c;生…
阅读更多...
[qt] qt程序打包以及docker镜像打包

[qt] qt程序打包以及docker镜像打包

目录 一 环境准备: 1.1 qt环境 1.2 linuxdeplouqt打包工具 二 qt包发布: 2.1 搜索链接库 2.2 应用程序APP打包 2.3 发布 三 docker镜像包发布 3.1 环境准备 3.2 镜像生产脚本 3.3 加载镜像并运行docker容器 四 补充 4.1 时间不同步问题解决 一 环境准备: qt环境l…
阅读更多...
2024-06-07 Unity 编辑器开发之编辑器拓展8 —— Scene 窗口拓展

2024-06-07 Unity 编辑器开发之编辑器拓展8 —— Scene 窗口拓展

文章目录 1 Handles 类1.1 Scene 响应函数1.2 自定义窗口中监听 Scene1.3 Handles 常用 API2.2.1 颜色控制2.2.2 文本2.2.3 线段2.2.4 虚线2.2.5 圆弧2.2.6 圆2.2.7 立方体2.2.8 几何体2.2.9 移动、旋转、缩放2.2.10 自由移动 / 旋转 2 Scene 窗口中显示 GUI3 HandleUtility4 G…
阅读更多...
用Python代码锁定Excel单元格以及行和列

用Python代码锁定Excel单元格以及行和列

Excel能够帮助用户高效地组织数据&#xff0c;还支持复杂的公式计算和数据分析。而随着团队协作的日益频繁&#xff0c;保护数据的准确性和完整性变得尤为重要。在Excel表格中&#xff0c;我们可以通过锁定特定的单元格或区域&#xff0c;防止对单元格内容进行随意修改&#xf…
阅读更多...
C++面向对象程序设计 - 命名空间

C++面向对象程序设计 - 命名空间

命名空间是ANSI C引入的可以由用户命名的作用域&#xff0c;用来处理程序中常见的同名冲突。 在C语言中定义了三个层次的作用域&#xff0c;即文件&#xff08;编译单元&#xff09;、函数和复合语句。C又引入了类作用域&#xff0c;类是出现在文件内的。在不同的作用域中可以定…
阅读更多...
14.shell awk数组

14.shell awk数组

awk数组 awk数组awk数组示例Nginx日志分析 awk数组 1.什么是awk数组 数组其实也算是变量,传统的变量只能存储一个值,但数组可以存储多个值 2.awk数组应用场景 通常用来统计、比如:统计网站访问TOP10、网站url访问TOP10等等 3.awk数组统计技巧 1.在awk中,使用数组时,不仅可以…
阅读更多...
ceisum只聚合效果展示

ceisum只聚合效果展示

忙于开发三维引擎的扩展功能&#xff0c;实在时间太少了&#xff0c;仓促截几张图&#xff0c;看一下聚合效果。 1.聚合又文字标签 四种效果&#xff1a;如下 2.聚合无文字标签
阅读更多...
Docker(一)-认识Docker

Docker(一)-认识Docker

1.docker理念 Docker是基于Go语言实现的云开源项目。 Docker的主要目标是“Build,Ship and Run Any App,Anywhere”&#xff0c;也就是通过对应用组件的封装&#xff0c;分发&#xff0c;部署&#xff0c;运行等生命周期的管理&#xff0c;使用户的应用及其运行环境能够做到”…
阅读更多...
jenkins使用注意问题

jenkins使用注意问题

1.在编写流水线时并不知道当前处在哪个目录&#xff0c;导致名使用不当&#xff0c;以及文件位置不清楚 流水线任务默认路径是&#xff0c;test4_mvn为jenkins任务名 [Pipeline] sh (hide)pwd /var/jenkins_home/workspace/test4_mvn maven任务也是&#xff0c;看来是一样的…
阅读更多...
CV每日论文--2024.6.14

CV每日论文--2024.6.14

1、ICE-G: Image Conditional Editing of 3D Gaussian Splats 中文标题&#xff1a;ICE-G&#xff1a;3D 高斯斑点的图像条件编辑 简介&#xff1a;近年来,出现了许多技术来创建高质量的3D资产和场景。然而,当涉及到这些3D对象的编辑时,现有方法要么速度慢、要么牺牲质量,要么…
阅读更多...
数组(C语言)(详细过程！！！)

数组(C语言)(详细过程！！！)

目录 数组的概念 一维数组 sizeof计算数组元素个数 二维数组 C99中的变⻓数组 数组的概念 数组是⼀组相同类型元素的集合。 数组分为⼀维数组和多维数组&#xff0c;多维数组⼀般比较多见的是二维数组。 从这个概念中我们就可以发现2个有价值的信息&#xff1a;(1)数…
阅读更多...
flask_sqlalchemy时间缓存导致datetime.now()时间不变问题

flask_sqlalchemy时间缓存导致datetime.now()时间不变问题

问题是这样的&#xff0c;项目在本地没什么问题&#xff0c;但是部署到服务器过一阵子发现&#xff0c;这个时间会在某一刻定死不变。 重启uwsgi后&#xff0c;发现第一条数据更新到了目前最新时间&#xff0c;过了一会儿再次发送也变了时间&#xff0c;但是再过几分钟再发就会…
阅读更多...
软件测试--Mysql快速入门

软件测试--Mysql快速入门

文章目录 软件测试-mysql快速入门sql主要划分mysql常用的数据类型sql基本操作常用字段的约束&#xff1a;连接查询mysql内置函数存储过程视图事务索引 软件测试-mysql快速入门 sql主要划分 sql语言主要分为&#xff1a; DQL&#xff1a;数据查询语言&#xff0c;用于对数据进…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023