【C语言】数据结构——带头双链表实例探究

💗个人主页💗
⭐个人专栏——数据结构学习⭐
💫点击关注🤩一起学习C语言💯💫

目录

  • 导读：
  • 1. 双链表结构特征
  • 2. 实现双向循环链表
    • 2.1 定义结构体
    • 2.2 创造节点
    • 2.3 双向链表初始化
    • 2.4 双向链表打印
    • 2.5 双向链表尾插
    • 2.6 双向链表尾删
    • 2.7 双向链表头插
    • 2.8 双向链表头删
    • 2.9 双向链表查找
    • 2.10 双向链表任意位置插入
    • 2.11 双向链表任意位置删除
    • 2.12 双链表销毁
    • 2.13 利用任插、任删完成头尾插入和头尾删除

导读：

我们在前面学习了单链表和顺序表。
今天我们来学习双向循环链表。
在经过前面的一系列学习，我们已经掌握很多知识，相信今天的内容也是很容易理解的。
关注博主或是订阅专栏，掌握第一消息。

1. 双链表结构特征

今天我们要学的是双向带头循环列表。
双向循环链表是一个链表的数据结构，每个节点包含两个指针，分别指向前一个节点和后一个节点。与普通的链表不同的是，双向循环链表的尾节点的后继节点指向头节点，头节点的前驱节点指向尾节点，形成一个闭环。
在这里插入图片描述
双向循环链表的特点是可以从任意一个节点开始遍历整个链表。

由于每个节点都可以直接访问前一个节点和后一个节点，所以在双向循环链表中插入和删除节点的操作更加方便和高效。
在插入和删除节点时，只需要修改相邻节点的指针即可，不需要像普通链表那样需要遍历找到前一个节点。

2. 实现双向循环链表

我们需要创建两个 C文件: study.c 和 SList.c，以及一个 头文件： SList.h。
头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

2.1 定义结构体

typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。

若struct SeqList {}这样来定义结构体的话。在申请SeqList 的变量时，需要这样写，struct SList n;
若用typedef，可以这样写，typedef struct SList{}SL; 。在申请变量时就可以这样写，SL n;
区别就在于使用时，是否可以省去struct这个关键字。

定义两个指针next和prev，分别指向该节点的下一个节点和前一个节点，data记录该节点存放的值。

typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;

2.2 创造节点

因为链表的插入都需要新创建一个节点，为了方便后续的使用以及避免代码的重复出现，我们直接定义函数，后续直接调用即可。

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

malloc开辟一块空间，存入想要插入的值，前后指针闲置为空，后面调用后再去改变，返回该节点的指针。

2.3 双向链表初始化

先把哨兵位创建出来，前后指针都先指向自己，该节点不存储任何实际的数据，只是作为链表的起始点。

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

2.4 双向链表打印

方便我们后面测试代码是否出错。

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

2.5 双向链表尾插

首先，需要找到链表的尾节点（即头节点的前驱节点）。
然后将新节点插入到尾节点的后面，即新节点的前驱指向尾节点，新节点的后继指向头节点（即原先的尾节点的后继节点），头节点的前驱指向新节点，头节点的后继指向新节点。
最后，将新节点作为尾节点。

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;//尾节点LTNode* newnode = CreateLTNode(x);//新建一个节点tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

我们用尾插插入1，2，3，4来进行测试。

void TestLT1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);}
int main()
{TestLT1();return 0;
}

在这里插入图片描述
最开始的时候链表只有一个哨兵位，它的前后指针都是指向自己，所以找尾节点找到的就是哨兵位。
在这里插入图片描述
第一个数据的插入：
在这里插入图片描述

第二个数据的插入：

在这里插入图片描述

2.6 双向链表尾删

要实现带头双向循环链表的尾删操作，可以按照以下步骤：

  1. 首先判断链表是否为空，如果为空，则直接返回。

  2. 如果链表不为空，找到链表中的最后一个节点的前一个节点，即尾节点的前一个节点。

  3. 将尾节点的前一个节点的next指针指向头节点，即将尾节点从链表中移除。

  4. 释放尾节点的内存空间。

  5. 更新链表的尾指针，即将尾指针指向尾节点的前一个节点。

void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next);LTNode* tail = phead->prev;//最后一个节点LTNode* tailprev = tail->prev;//倒数第二个节点phead->prev = tailprev;tailprev->next = phead;free(tail);tail = NULL;
}

测试：

void TestLT1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);}
int main()
{TestLT1();return 0;
}

在这里插入图片描述

在这里插入图片描述

2.7 双向链表头插

头插法是指将新的节点插入链表的头部，而不是尾部。
在带头双向链表中，首先创建一个新的节点，并将其next指针指向原来的头节点，然后将原来的头节点的prev指针指向新的节点即可。

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = CreateLTNode(x);//增加新节点LTNode* next = phead->next;//记录原先的第一个节点phead->next = newnode;newnode->prev = phead;newnode->next = next;next->prev = newnode;
}

测试：

void TestLT2()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushFront(plist, 99);LTPushFront(plist, 88);LTPushFront(plist, 77);LTPushFront(plist, 66);LTPushFront(plist, 55);LTPrint(plist);
}
int main()
{TestLT2();return 0;
}

在这里插入图片描述
在这里插入图片描述

2.8 双向链表头删

带头双向链表的头删操作可以通过以下步骤实现：

  1. 如果链表为空，直接返回。
  2. 将头节点的下一个节点指针保存在一个临时变量中。
  3. 将头节点的下一个节点的前驱节点指针指向空。
  4. 将临时变量指向的节点的前驱节点指针指向空。
  5. 将头节点指向临时变量指向的节点。
  6. 释放临时变量指向的节点的内存空间。
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next);LTNode* del = phead->next;//第一个节点LTNode* next = del->next;//第二个节点phead->next = next;next->prev = phead;free(del);del = NULL;
}

测试：

void TestLT2()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushFront(plist, 99);LTPushFront(plist, 88);LTPushFront(plist, 77);LTPushFront(plist, 66);LTPushFront(plist, 55);LTPrint(plist);LTPopFront(plist);LTPrint(plist);
}
int main()
{TestLT2();return 0;
}

在这里插入图片描述
在这里插入图片描述

2.9 双向链表查找

在带头双向链表中查找一个特定的元素可以按照以下步骤进行：

  1. 如果链表为空，则返回空指针或者空值，表示找不到目标元素。
  2. 通过指针访问链表的第一个节点，即头节点的下一个节点。
  3. 从第一个节点开始，依次遍历链表的每一个节点，直到找到目标元素或者遍历到链表的末尾。
    4 如果找到目标元素，返回该节点的指针或者该节点的值，表示找到了目标元素。
  4. 如果遍历到链表的末尾都没有找到目标元素，则返回空指针或者空值，表示找不到目标元素。
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 双向链表任意位置插入

我们利用查找函数，插入到找到的数前面。

  1. 判断链表里是否有这位数。
  2. 创建一个新节点。
  3. 改变pos位置前一个节点、pos节点和新节点的前后驱指针。
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = CreateLTNode(x);//增加新节点LTNode* cur = pos->prev;//pos前一个节点cur->next = newnode;newnode->prev = cur;pos->prev = newnode;newnode->next = pos;
}

测试：

//任意位置插入测试
void TestLT5()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);if (LTFind(plist, 2)){LTNode* pos = LTFind(plist, 2);LTInsert(pos, 999);LTPrint(plist);}else{printf("fail\n");}
}
int main()
{TestLT5();return 0;
}

在这里插入图片描述

2.11 双向链表任意位置删除

仍然是利用查找函数，删除find函数返回的节点。

  1. 判断是否存在这个数。
  2. 把该节点的前一个节点和后一个节点相关联。
  3. 释放该节点。
void LTErase(LTNode* pos)
{assert(pos);LTNode* before = pos->prev;//pos前一个节点LTNode* next = pos->next;//pos后一个节点before->next = next;next->prev = before;free(pos);pos = NULL;
}

测试：

//任意位置删除测试
void TestLT6()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushFront(plist, 99);LTPushFront(plist, 88);if (LTFind(plist, 2)){LTNode* pos = LTFind(plist, 2);LTErase(pos);}LTPrint(plist);
}
int main()
{TestLT6();return 0;
}

在这里插入图片描述

2.12 双链表销毁

动态内存开辟空间，使用完之后需要进行销毁。

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

2.13 利用任插、任删完成头尾插入和头尾删除

因为我们是带头双向链表，所以我们利用哨兵位就可以轻松找到链表的头尾结点。
所有我们只需要把哨兵位的位置做为参数，就可以轻易完成。

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead, x);
}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next);LTErase(phead->prev);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead->next, x);}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next);LTErase(phead->next);
}

测试：

//任意位置插入删除（头尾增删调用）
void TestLT4()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);LTPushFront(plist, 99);LTPushFront(plist, 88);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTDestory(plist);
}
int main()
{TestLT4();return 0;
}

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

【数据库系统概论】第7章-数据库设计

【数据库系统概论】第7章-数据库设计

文章目录 7.1 数据库设计概述7.2 需求分析7.2.1 需求分析的任务7.2.2 需求分析的难点7.2.2 需求分析的方法7.2.3 数据字典 7.3 概念结构设计7.3.1 概念模型7.3.2 E-R模型7.3.3 概念结构设计 7.4 逻辑结构设计7.4.1 E-R图向关系模型的转换7.4.2 数据模型的优化7.4.3 设计用户子模…
阅读更多...
PowerShell Instal 一键部署gitea

PowerShell Instal 一键部署gitea

gitea 前言 Gitea 是一个轻量级的 DevOps 平台软件。从开发计划到产品成型的整个软件生命周期，他都能够高效而轻松的帮助团队和开发者。包括 Git 托管、代码审查、团队协作、软件包注册和 CI/CD。它与 GitHub、Bitbucket 和 GitLab 等比较类似。 Gitea 最初是从 Gogs 分支而来…
阅读更多...
QT上位机开发（倒计时软件）

QT上位机开发（倒计时软件）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 倒计时软件是生活中经常遇到的一种场景。比如运动跑步&#xff0c;比如学校考试&#xff0c;比如论文答辩等等&#xff0c;只要有时间限制规定的地…
阅读更多...
21 UVM printer

21 UVM printer

uvm_printer 类提供了以不同格式打印 uvm_objects 的灵活性。我们已经讨论了使用 uvm_field_* 宏的 print() 方法&#xff0c;或者如果不使用 utils_begin/ end 宏&#xff0c;则编写 do_print() 方法。 UVM printer提供四种内置printer。 uvm_printeruvm_table_printeruvm_t…
阅读更多...
Git：远程仓库的使用

Git：远程仓库的使用

查看当前的远程库 要查看当前配置有哪些远程仓库&#xff0c;可以用git remote 命令&#xff0c;它会列出每个远程库的简短名字。在克隆完某个项目后&#xff0c;至少可以看到一个名为origin 的远程库&#xff0c;Git 默认使用这个名字来标识你所克隆的原始仓库&#xff1a; 也…
阅读更多...
DM达梦数据库表占用空间大小

DM达梦数据库表占用空间大小

问题描述&#xff1a; 项目涉及用户量大且数据量大&#xff0c;为提高查询性能采用分表方式处理数据&#xff1b;根据业务要求总共4张业务表&#xff0c;每张业务表扩展成100张表&#xff0c;系统中总共400张表。部署至测试环境发现测试环境占用的磁盘空间是开发环境的8倍。 问…
阅读更多...
从程序员到项目经理

从程序员到项目经理

前言 看到这个话题&#xff0c;博主不禁有感而发。那么就简单讲讲&#xff0c;从程序员到项目经理&#xff0c;需要具备哪些必备能力或基本的素养。 一、必备 1、技术能力 程序员首先必须成为一个名合格的coder&#xff0c;有思想有见解有态度。 无论身处什么开发岗位&…
阅读更多...
python2.x编码Unicode字符串

python2.x编码Unicode字符串

1 python2.x编码Unicode字符串 python2.x默认编码方法为ASCII码。字符串赋值时按系统默认编码自动编码&#xff0c;通过decode()方法解码为Unicode&#xff0c;再通过encode()方法编码为指定码。 1.1 编码解码基础知识 1.1.1 位 位(bit)是计算机存储数据的最小单位&#xf…
阅读更多...
数据之光：乡镇企业的发展利器——数据可视化

数据之光：乡镇企业的发展利器——数据可视化

数据可视化是一项强大的工具&#xff0c;它不仅在大型企业中发挥关键作用&#xff0c;而且在乡镇企业中也能作出显著贡献。那么&#xff0c;数据可视化究竟能为乡镇企业做出什么样的贡献呢&#xff1f; 首先&#xff0c;数据可视化为乡镇企业提供了更清晰的业务洞察。通过将庞大…
阅读更多...
超简单实用，推荐的深度学习科研必备网站（轻松找论文，代码项目，写论文综述）

超简单实用，推荐的深度学习科研必备网站（轻松找论文，代码项目，写论文综述）

一个非常有用的深度学习必备网站 网址推荐 接触新方向需要了解的内容1.在某一个研究方向下&#xff0c;有哪些算法模型可以用&#xff1f;不同算法之间效果对比如何&#xff1f;2.在某一个研究方向下&#xff0c;到底有哪些论文&#xff0c;模型是可以用的&#xff1f;3.在某一…
阅读更多...
Python中如何使用_new_实现单例模式

Python中如何使用_new_实现单例模式

单例模式是一个经典设计模式&#xff0c;简要的说&#xff0c;一个类的单例模式就是它只能被实例化一次&#xff0c;实例变量在第一次实例化时就已经固定。 在Python中常见的单例模式有None&#xff0c;这就是一个很典型的设计&#xff0c;通常使用 if xxx is None或者if xxx …
阅读更多...
ESP32S3+HX8347+3线SPI运行LVGL例程

ESP32S3+HX8347+3线SPI运行LVGL例程

一、clone lv_port_esp32到本地 git clone https://github.com/lvgl/lv_port_esp32.git 二、增加hx8347.c、hx8347.h components\lvgl_esp32_drivers\lvgl_tft下新增2个文件&#xff1a;hx8347.c、hx8347.h。因为lv_port_esp32中没有hx8347的驱动&#xff0c;需要自己写。这两个…
阅读更多...
分库分表之Mycat应用学习二

分库分表之Mycat应用学习二

3 Mycat 概念与配置 官网 http://www.mycat.io/ Mycat 概要介绍 https://github.com/MyCATApache/Mycat-Server 入门指南 https://github.com/MyCATApache/Mycat-doc/tree/master/%E5%85%A5%E9%97%A8%E6%8C%87%E5%8D%973.1 Mycat 介绍与核心概念 3.1.1 基本介绍 历史&#x…
阅读更多...
怎么使用FTP

怎么使用FTP

FTP服务器&#xff08;File Transfer Protocol Server&#xff09;是在互联网上提供文件存储和访问服务的计算机&#xff0c;它们依照FTP协议提供服务。FTP是File Transfer Protocol的缩写&#xff0c;即文件传输协议&#xff0c;是一种基于TCP的协议&#xff0c;采用客户/服务…
阅读更多...
软件测试/测试开发丨Python 数据类 dataclass 学习笔记

软件测试/测试开发丨Python 数据类 dataclass 学习笔记

dataclass 介绍 dataclass优势 可读性强操作灵活轻量 应用场景 创建对象完美融合平台开发 ORM 框架 案例 场景&#xff1a;如果创建一只猫&#xff0c;信息包括猫的名字、体重、颜色。同时打印这个对象的时候&#xff0c;希望能打印出一个字符串&#xff08;包含猫的各种信息&…
阅读更多...
Python跨年烟花秀

Python跨年烟花秀

写在前面 今年跨年怎么过呢~博主用python的pygame实现了一场炫酷的烟花秀&#xff0c;一起来看看吧&#xff01; 环境需求 python3.11.4及以上PyCharm Community Edition 2023.2.5pyinstaller6.2.0&#xff08;可选&#xff0c;这个库用于打包&#xff0c;使程序没有python环境…
阅读更多...
图灵日记之java奇妙历险记--继承和多态

图灵日记之java奇妙历险记--继承和多态

目录 继承概念继承语法父类成员访问子类中访问父类的成员变量子类中访问父类的成员方法 super关键字子类构造方法super和this初始化protected关键字继承方式final 关键字继承与组合 多态条件向上转型重写动态绑定&&静态绑定多态再理解向下转型多态的优缺点好处缺陷 继承…
阅读更多...
【Transformer】深入理解Transformer模型2——深入认识理解（下）

【Transformer】深入理解Transformer模型2——深入认识理解（下）

前言 Transformer模型出自论文&#xff1a;《Attention is All You Need》 2017年 近年来&#xff0c;在自然语言处理领域和图像处理领域&#xff0c;Transformer模型都受到了极为广泛的关注&#xff0c;很多模型中都用到了Transformer或者是Transformer模型的变体&#xff0…
阅读更多...
java springboot宠物医院管理系统

java springboot宠物医院管理系统

一.项目简介 宠物医院管理系统&#xff0c;java项目&#xff0c;springboot项目。eclipse和idea都能打开运行。 使用技术&#xff1a;springboot&#xff0c;mybatis&#xff0c;jsp&#xff0c;mysql 5.7 共分为三个角色&#xff1a;系统管理员、医生、用户 功能模块&…
阅读更多...
9. 进程

9. 进程

9. 进程 1. 进程与程序1.1 main() 函数由谁调用1.2 程序如何结束1.2.1 注册进程终止处理函数 atexit() 1.3 何为进程1.4 进程号 2. 进程的环境变量2.1 应用程序中获取环境变量2.1.1 获取指定环境变量 2.2 添加/删除/修改环境变量2.2.1 putenv()2.2.2 setenv()2.2.3 命令行式添加…
阅读更多...
最新文章

Copyright @ 2022~2023