【数据结构和算法】实现带头双向循环链表(最复杂的链表)(上)

简介: 【数据结构和算法】实现带头双向循环链表(最复杂的链表)(上)

前言

带头双向循环链表,是链表中最为复杂的一种结构,我们主要实现的功能为,头插尾插,头删尾删,初始化、打印、指定pos位置插入结点或者删除结点、寻找结点、摧毁链表等函数。


一、带头双向循环链表是什么?

如图所示:


二、实现带头双向循环链表

1.结构体和要实现函数

结构体如下:

1. typedef struct DSLDataType;
2. //定义双向链表的结构体
3. 
4. //双向链表每一个节点都有一个前驱节点和后继节点,可以根据节点获得其前后的节点
5. typedef struct DSListNode {
6.  struct DSListNode* prev;//前驱节点
7.  struct DSListNode* next;//后继节点
8.  int value;//数据域
9. }DSLNode;//重定义

相比单向链表,多一个指针域prev,指向前面的结点地址

实现功能的函数:

1. //初始化
2. DSLNode*ListInit();
3. //打印链表
4. void ListPrint(DSLNode* ps);
5. //尾部插入
6. void ListPushBack(DSLNode* ps, int data);
7. //头部插入
8. void ListPushFront(DSLNode* ps, int data);
9. //尾部删除
10. void ListPopBack(DSLNode* ps);
11. //头部删除
12. void ListPopFront(DSLNode* ps);
13. //判空
14. bool ListEmpty(DSLNode* ps);
15. //返回链表节点个数
16. int Listsize(DSLNode* ps);
17. //寻找指定元素,返回对应的节点
18. DSLNode* ListFind(DSLNode* ps, int data);
19. //在pos之前插入节点
20. void ListInsert(DSLNode* pos, int data);
21. //删除pos位置结点
22. void ListEarse(DSLNode* pos);
23. //摧毁链表
24. void ListDestory(DSLNode* ps);

2.初始化和打印链表

1. //对于函数的实现
2. //初始化
3. DSLNode* ListInit() {
4.  //初始化创建链表
5.  //创建新节点
6.  DSLNode* num = (DSLNode*)malloc(sizeof(DSLNode));
7.  //判断是否创建成功
8.  if (num == NULL) {
9.    perror("malloc fail\n");
10.     exit(-1);
11.   }
12.   num->prev = num;
13.   num->next = num;//作为头节点,前驱和后驱结点都指向自己
14.   return num;
15. }
16. 
17. //打印链表
18. void ListPrint(DSLNode* ps) {
19.   assert(ps);//断言
20.   DSLNode* cur = ps->next;
21.   printf("phead->");
22.   while (cur != ps) {//双向链表,回到ps,就表示转了一圈
23.     printf("%d->", cur->value);
24.     cur = cur->next;
25.   }
26.   printf("NULL\n");
27. }

3.头插和尾插

尾插如图所示:

代码如下:

1. 
2. DSLNode* CreatNode(int data) {//创建新节点
3.  DSLNode* cur = (DSLNode*)malloc(sizeof(DSLNode));
4.  if (cur == NULL) {
5.    perror("malloc fail\n");
6.    exit(-1);
7.  }
8.  cur->next = cur->prev = NULL;
9.  cur->value = data;
10. }
11. //尾部插入
12. void ListPushBack(DSLNode* ps, int data) {
13.   assert(ps);//断言
14.   DSLNode* newnode = CreatNode(data);
15.   DSLNode* tail = ps->prev;//把头节点之前的那个地址给tail
16.   tail->next = newnode;//将ps之前的那个数值,实际上是这个双向链表的最后一个元素的位置,的next指针指向新节点
17.   newnode->prev = tail;//新节点前后为 tail和ps
18.   newnode->next = ps;
19.   ps->prev = newnode;//tail的两个指针域都指向完成,就只剩下ps的前驱指针
20. 
21. }

头插如图所示:

代码如下:

1. 
2. //头部插入
3. void ListPushFront(DSLNode* ps, int data) {
4.  assert(ps);
5.  //头部插入就是将ps之后的一个地址给临时变量tail
6.  DSLNode* tail = ps->next;
7.  DSLNode* newnode = CreatNode(data);//创建新节点
8.  ps->next->prev = newnode;
9.  newnode->next = ps->next;
10.     newnode->prev = ps;
11.     ps->next = newnode;
12. }

4.头删和尾删

尾部删除如图所示:

代码如下:

1. //判空
2. bool ListEmpty(DSLNode* ps) {
3.  assert(ps);//断言
4.  return ps->next == ps;//如果是只有一个ps头节点,则表示为空,返回true,否则返回false
5. 
6. }
7. //尾部删除
8. void ListPopBack(DSLNode* ps) {
9. 
10.   assert(ps);//断言
11.   assert(!ListEmpty(ps));//先判断是否为空
12.   DSLNode* cur = ps->prev;
13.   //将cur的next值为NULL
14.   ps->prev = ps->prev->prev;
15.   ps->prev->next = ps;
16.   //这是直接略过尾部最后一个元素
17.   //跳过ps之前的一个节点,先让其左右节点相连,然后释放这个地址
18.   free(cur);
19.   cur = NULL;
20. }

头部删除如图所示:

代码如下:

1. //头部删除
2. void ListPopFront(DSLNode* ps) {
3.  assert(ps);
4.  assert(!ListEmpty(ps));
5.  DSLNode* cur = ps->next;
6.  //头删  是将头节点之后的第一个节点删除释放空间
7.  ps->next = ps->next->next;
8.  ps->next->prev = ps;
9.  free(cur);
10.   cur = NULL;
11. }

5.查找和返回结点个数

查找:返回一个结点,根据data数值域,来返回第一个遇到的结点cur,若没有返回NULL

1. //返回链表节点个数
2. int Listsize(DSLNode* ps) {
3.  assert(ps);
4.  int count = 0;
5.  DSLNode* cur = ps->next;
6.  while (cur != ps) {
7.    count++;
8.    cur = cur->next;
9.  }
10.   return count;
11. }
12. //查找
13. DSLNode* ListFind(DSLNode* ps, int data) {
14.   assert(ps);
15.   DSLNode* cur = ps->next;
16.   while (cur != ps) {
17.     if (cur->value == data) {
18.       return cur;
19.     }
20.   }
21.   return NULL;//NULL表示不存在
22. }

6.在pos位置之前插入结点

如图所示:

代码如下:

1. //插入节点
2. void ListInsert(DSLNode* pos, int data) {
3. 
4.  assert(pos);
5.  //pos三种可能
6.  //1.空链表
7.  //2.只有一个节点
8.  DSLNode* cur = pos->prev;
9.  //双向链表可以直接找到pos之前的位置,单向链表只能进行循环
10.   DSLNode* newnode = CreatNode(data);
11.   pos->prev = newnode;//把新节点newnode的位置给pos的prev
12.   newnode->prev = cur;//cur表示的是创建new节点之前的时候pos之前的结点
13.   cur->next = newnode;
14.   newnode->next = pos;
15.   //另一种不使用cur的方法
16.   //newnode->next = pos;
17.   //pos->prev->next = newnode;
18.   //newnode->prev = pos->prev;
19.   //pos->prev = newnode;
20. }


目录
打赏
0
0
0
0
0
分享
相关文章
|
2月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
75 9
 算法系列之数据结构-二叉树
|
2月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
77 3
 算法系列之数据结构-Huffman树
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
36 0
|
2月前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
93 22
员工电脑监控系统中的 C# 链表算法剖析-如何监控员工的电脑
当代企业管理体系中,员工电脑监控已成为一个具有重要研究价值与实践意义的关键议题。随着数字化办公模式的广泛普及,企业亟需确保员工对公司资源的合理利用,维护网络安全环境,并提升整体工作效率。有效的电脑监控手段对于企业实现这些目标具有不可忽视的作用,而这一过程离不开精妙的数据结构与算法作为技术支撑。本文旨在深入探究链表(Linked List)这一经典数据结构在员工电脑监控场景中的具体应用,并通过 C# 编程语言给出详尽的代码实现与解析。
62 5
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
118 29
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
158 25
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
52 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等