AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

[C语言数据结构]双向循环链表

2023-11-13 50
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： [C语言数据结构]双向循环链表

引:上次我们学习了单链表的实现，相对于双向循环链表来说，单链表的各中操作，比如说增删查改等都显得非常麻烦。所以接下来来学习一下双向循环链表吧！

💊1.双向循环链表：

💊1.1何为双向循环链表

如上所示：每个节点都有包含有两个指针域和一个数据域；
两个指针域一个存储前一个节点的地址，另一个存储下一个节点的地址；

这种结构虽然看起来比单链表复杂一些，但是可以简化一系列后来的增删查改的操作；

💊1.2双向循环链表的实现

💊1.2.1结构体的创建

这个结构体的创建和单链表的结构体的创建是大同小异，我们需要两个指针域，一个数据域；

代码：

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

💊1.2.2双向循环链表的初始化

LTNode* InitList(LTNode* Phead);

这个函数实现的双向循环链表的初始化功能，函数参数的话这边选择了一级指针和单链表的初始化函数不同，单链表所使用的是二级指针；而且初始化函数内部也有所不同；

代码：

//申请节点函数
LTNode* BuyListNode(LTDataType x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  node->data = x;
  node->next = node->prev = NULL;
  return node;
}
//初始化双向链表
LTNode* InitList(LTNode* phead)
{
  phead = BuyListNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

💊1.2.3双向链表的尾插

void  LTPushBack(LTNode* phead, LTDataType x);

对于双向循环链表来说，它的尾插非常简单，因为它不需要去遍历链表来找到链表的尾部节点；

代码：

//双向链表的尾插
void  LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyListNode(x);
  LTNode* tail = phead->prev;
  tail->next = newnode;
  newnode->prev = tail;
  phead->prev = newnode;
  newnode->next = phead;
}

💊1.2.4双向链表的尾部删除

双向链表的尾部删除的和尾部插入同样简单，因为它不需要遍历链表，只需要进行相应的链接操作即可。

代码：

//双向链表的尾部删除
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* tail = phead->prev;
  LTNode* tailprev = tail->prev;
  tailprev->next = phead;
  phead->prev = tailprev;
  free(tail); 
}

💊1.2.5双向链表的头插

链表的头插相对于单链表来说复杂程度不相上下，但也不难，因为有哨兵位节点的存在，在连接节点的时候还是相对方便的；

代码：

//双向链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyListNode(x);
  newnode->next = phead->next;
  phead->next->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}

💊1.2.6双向链表的数据的打印

函数的实现非常简单，简单的遍历链表即可，唯一需要注意到的点就是我们什么时候停下来；

代码：

//双向链表的打印
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

💊1.2.7双向链表的头部删除数据

双向链表头部删除数据很简单，只需要将phead->next删除之后再将phead->next->next和phead链接起来即可；

代码：

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

💊1.2.8双向链表寻找数据

方法和单链表是类似的，只是判断停止的条件不同；

代码：

//双向链表中寻找数据
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;
}

💊1.2.9在双向链表的任意位置插入数据

这里我们实现的是在这个位置前进行插入数据，逻辑非常简单。

分两个步骤：①申请空间；        ②链接节点；

代码：

//在双向链表的任意位置插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = BuyListNode(x);
  LTNode* pre = pos->prev;
  pre->next = newnode;
  newnode->prev = pre;
  newnode->next = pos;
  pos->prev = newnode;
}

对此函数我们可以实现复用，重新构建头插和尾插：

//双向链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTInsert(phead->next, x);
}
//双向链表的尾插
void  LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTInsert(phead, x);
}

💊1.2.10在双向链表的任意位置删除数据

这个函数我们实现的就是删除传入地址的节点，大的步骤也是分两个，先记录这个节点的前一个节点和后一个节点，然后free掉这个节点后，再链接；

代码：

//在双向链表的任意位置删除数据
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* pre = pos->prev;
  LTNode* next = pos->next;
  free(pos);
  pre->next = next;
  next->prev = pre;
}

对此函数进行复用，改进头删和尾部删除函数：

代码：

//双向连边头部删除数据
void LTPopFront(LTNode* phead)
{
  assert(phead);
  LTErase(phead->next);
}
//双向链表的尾部删除
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTErase(phead->prev);
}

代码汇总：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDataType data;
}LTNode;
//初始化双向链表
LTNode* InitList();
//获取新的节点
LTNode* BuyListNode(LTDataType x);
//双向链表的尾插
void  LTPushBack(LTNode* phead, LTDataType x);
//双向链表的尾部删除
void LTPopBack(LTNode* phead);
//双向链表的头插
void LTPushFront(LTNode* phead, LTDataType x);
//双向链表的打印
void LTPrint(LTNode* phead);
//双向连边头部删除数据
void LTPopFront(LTNode* phead);
//双向链表中寻找数据
LTNode* LTFind(LTNode* phead, LTDataType x);
//在双向链表的任意位置插入和删除数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
//双向链表的判空
bool LTEmpty(LTNode* phead);
//双向链表大小的计算
size_t LTSize(LTNode* phead);
//双向链表的销毁
void LTDestroy(LTNode* phead);
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
LTNode* BuyListNode(LTDataType x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  node->data = x;
  node->next = node->prev = NULL;
  return node;
}
//初始化双向链表
LTNode* InitList()
{
  LTNode* phead = BuyListNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
//双向链表的尾插
void  LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  //LTNode* newnode = BuyListNode(x);
  //LTNode* tail = phead->prev;
  //tail->next = newnode;
  //newnode->prev = tail;
  //phead->prev = newnode;
  //newnode->next = phead;
  LTInsert(phead, x);
}
//双向链表的尾部删除
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  //LTNode* tail = phead->prev;
  //LTNode* tailprev = tail->prev;
  //tailprev->next = phead;
  //phead->prev = tailprev;
  //free(tail); 
  LTErase(phead->prev);
}
//双向链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  //LTNode* newnode = BuyListNode(x);
  //newnode->next = phead->next;
  //phead->next->prev = newnode;
  //phead->next = newnode;
  //newnode->prev = phead;
  LTInsert(phead->next, x);
}
//双向链表的打印
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//双向连边头部删除数据
void LTPopFront(LTNode* phead)
{
  assert(phead);
  //assert(phead->next != NULL);
  //LTNode* first = phead->next;
  //LTNode* second = first->next;
  //free(first);
  //phead->next = second;
  //second->prev = phead;
  LTErase(phead->next);
}
//双向链表中寻找数据
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;
}
//在双向链表的任意位置插入和删除数据
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = BuyListNode(x);
  LTNode* pre = pos->prev;
  pre->next = newnode;
  newnode->prev = pre;
  newnode->next = pos;
  pos->prev = newnode;
}
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* pre = pos->prev;
  LTNode* next = pos->next;
  free(pos);
  pre->next = next;
  next->prev = pre;
}
//双向链表的判空
bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next != phead;
}
//双向链表大小的计算
size_t LTSize(LTNode* phead)
{
  assert(phead);
  size_t x = 0;
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    x++;
    cur = cur->next;
  }
  return x;
}
//双向链表的销毁
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
}
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
int main()
{
  LTNode* phead = InitList();
  LTPushBack(phead, 1);
  LTPushBack(phead, 2);
  LTPushBack(phead, 3);
  LTPushBack(phead, 4);
  LTPushBack(phead, 5);
  LTPrint(phead);
  LTPrint(phead);
  LTNode* x = LTFind(phead, 3);
  if (x)
  {
    x->data = 100;
    LTPrint(phead);
  }
  LTPopBack(phead);
  LTPrint(phead);
  printf("%d\n", LTSize(phead));
  LTDestroy(phead);
  return 0;
}

以上就是双向循环链表表的实现和各个函数需要注意的细节，如果有错误可以在评论区指正！

 

文章标签：
C语言
存储
关键词：
数据结构c语言
数据结构链表
C语言数据结构
C语言循环
数据结构双向循环链表
小米睡不醒
目录
相关文章
ephemerals__
|
22天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
109 9
ephemerals__
|
21天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
60 16
ephemerals__
|
21天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
72 8
ephemerals__
|
24天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
50 4
ephemerals__
|
24天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
40 0
白子寰
|
1月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
35 3
Skyund
|
14天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明： 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数，即头文件中存在或已经定义过； 如果使用库函数，一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数，而且该函数与使用它的函数在同一个文件中，一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前，在函数的外部已做了函数声明，则在各个主调函数中不必多所调用的函数在做声明
Skyund
29 6
ephemerals__
|
1月前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余，其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值，并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出，支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
ephemerals__
39 10
c的前世今生
|
27天前
|
存储 算法 程序员
C语言：库函数
C语言的库函数是预定义的函数，用于执行常见的编程任务，如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作，提高开发效率。C标准库提供了丰富的函数，满足各种需求。
c的前世今生
32 1
ephemerals__
|
1月前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件，并通过求阶乘、打印整数每一位和求斐波那契数等实例，展示了递归的应用。递归的核心在于将大问题分解为小问题，但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点，提醒读者在实际编程中合理使用递归。
ephemerals__
61 7