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

【数据结构】线性表——带头双向循环链表

2023-05-29 84
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 带头双向循环链表带头双向循环链表的优点1.支持任意位置时间复杂度为O(1)的插入和删除。2.按照需求申请释放空间，无需担心空间不够用，无需担心浪费。3.带头可以省去链表为空时的判断，可以使代码更加简约带头双向循环链表的缺点1.不可以进行下标随机访问。2.缓存利用率低带头双向循环链表是线性表的一种，带头双向循环链表是链式存储的线性表，不同于顺序表，链表在内存空间中不连续。带头：带头就是带哨兵位，可以省链表为空时进行的判断。双向：由结构体内的next指针下一条数据进行链接，由prev对前一条数据进行链接🧐。循环：以循环方式进行链接，头的（前一个）prev是尾

带头双向循环链表

  • 带头双向循环链表的优点

1.支持任意位置时间复杂度为O(1)的插入和删除。

2.按照需求申请释放空间，无需担心空间不够用，无需担心浪费。

3.带头可以省去链表为空时的判断，可以使代码更加简约

  • 带头双向循环链表的缺点

1.不可以进行下标随机访问。

2.缓存利用率低

带头双向循环链表是线性表的一种，带头双向循环链表是链式存储的线性表，不同于顺序表，链表在内存空间中不连续。

  • 带头：带头就是带哨兵位，可以省链表为空时进行的判断。
  • 双向：由结构体内的next指针下一条数据进行链接，由prev对前一条数据进行链接🧐。
  • 循环：以循环方式进行链接，头的（前一个）prev是尾，尾的next（后一个）是头。

PS:需要源码直接通过目录跳转到最后

带头双向循环链表主体结构

默认大小与扩容大小还有类型都可以是任意大小或类型

typedef int DListDataType;    //数据类型
typedef struct ListNode
{
  DListDataType data; 
  struct ListNode* prev;    //指针指向前一个结点
  struct ListNode* next;    //指针指向后一个结点
}LTNode;

dcb92cb1b69c42649ca32e9071cad2c7.png

带头双向循环链表操作函数介绍

LTNode* InitLTNode(); //链表初始化

void ListInsert(LTNode* pos, DListDataType x); //任意位置插入

void ListPushBack(LTNode* phead, DListDataType x); //尾插

void ListPushFront(LTNode* phead, DListDataType x); //头插

void print(LTNode* phead); //输出链表

void ListErase(LTNode* pos); //任意位置删除

void ListPopBack(LTNode* phead); //尾删

void ListPopFront(LTNode* phead); //头删

LTNode* LTModify(LTNode* phead, DListDataType x); //修改指定结点

LTNode* LTFind(LTNode* phead, DListDataType x); //查找指定结点

void LTDestory(LTNode* phead); //销毁链表

为了代码方便阅读，将带头双向循环链表操作函数全部放在LinkedList.c文件中，将头文件放在LinkedList.h，测试文件test.c 😮

带头双向循环链表操作函数实现

为了方便调试，建议每写完1-2个函数就进行测试，初始化之后，首先实现print函数可以方便我们进行调试。

带头双向循环链表的初始化函数：

LTNode* Phead = InitLTNode(); //初始化哨兵位
LTNode* BuyNewNode(DListDataType x)   //开辟一个新结点
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return NULL;
  }
  newnode->next = NULL;
  newnode->prev = NULL;
  newnode->data = x;
  return newnode;
}
LTNode* InitLTNode()
{
  LTNode* phead = BuyNewNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

必须先进行初始化哨兵位，将哨兵位指向自己形成循环

打印函数

先写出打印函数，方便进行调试

void print(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  printf("head");
  while (cur!=phead)
  {
    printf("->%d", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

带头双向循环链表插入函数：

指定结点后插入和查找函数

两个函数可以配合使用，使用LTFind查找到需要插入的位置，然后使用ListInsert进行更改

LTNode* LTFind(LTNode* phead, DListDataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
LTNode* BuyNewNode(DListDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return NULL;
  }
  newnode->next = NULL;
  newnode->prev = NULL;
  newnode->data = x;
  return newnode;
}
void ListInsert(LTNode* pos,DListDataType x)
{
  assert(pos);
  LTNode* newnode = BuyNewNode(x);
  LTNode* prev = pos->prev;
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}

5ab9d389fc5a4472857f19ee6ca6d86e.gif

头插

头插将新结点插入到哨兵位后面的结点

这里面有一种简单的写法，就是直接复用ListInsert，将哨兵位后面的结点传过去，也是头插的效果

void ListPushFront(LTNode* phead, DListDataType x)
{
  assert(phead);
    //第一种方法
  //ListInsert(phead->next,x);
    //第二种方法
  LTNode* newnode = BuyNewNode(x);
  LTNode* secound = phead->next;
  newnode->next = secound;
  secound->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}

尾插

从最后一个结点后面插入新结点

尾插也可以复用ListInsert函数

  • 尾插也会用到申请新结点的函数，这里不重复了
void ListPushBack(LTNode* phead, DListDataType x)
{
  assert(phead);
    //第一种办法
  //ListInsert(phead,x);
    //第二种办法
  LTNode* newnode = BuyNewNode(x);
  LTNode* tail = phead->prev;
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}

带头双向循环链表删除函数

指定结点删除

删除指定结点，配合STFInd使用，将指定节点前一个结点的next连接到指定结点后一个结点，再将指定结点后面结点的prev连接到指定指定结点前一个结点。
void ListErase(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  prev->next = next;
  next->prev = prev;
    free(pos);
}

头删

记得进行断言，当只有一个哨兵位时与头结点为空都无法进行删除

可以对STErase进行复用

void ListPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead != phead->next);
    //第一种方法
  //ListErase(phead->next);
    //第二种
  LTNode* secound = phead->next;
  phead->next = secound->next;
  secound->next->prev = phead;
  free(secound);
}

尾删

void ListPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead != phead->next);
    //第一种方法
    //ListErase(phead->prev);
    //第二种方法
  LTNode* tail = phead->prev;
  phead->prev = tail->prev;
  tail->prev->next = phead;
  free(tail);
}

带头双向循环链表修改函数

配合LTFind函数使用

LTNode* LTFind(LTNode* phead, DListDataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
LTNode* LTModify(LTNode* phead, DListDataType x)
{
  LTNode* pos = LTFind(phead, x);
  int y;
  scanf("%d", &y);
  pos->data = y;
}

销毁带头双向循环链表

将每个结点依次释放。最后将哨兵位释放。

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

源代码文件

🌞🌞为了使代码更有阅读性，我们不建议把所有函数写在一个文件里，所以这里分成三个文件，模块化管理

test.c

测试文件

#include "DList.h"
void test1()
{
  LTNode* Phead = InitLTNode();
  ListPushBack(Phead, 666);
  ListPushBack(Phead, 777);
  ListPushBack(Phead, 9999);
  ListPushBack(Phead, 888);
  print(Phead);
  ListPopBack(Phead);
  print(Phead);
  ListPopFront(Phead);
  print(Phead);
  ListPopFront(Phead);
  ListPopFront(Phead);
  print(Phead);
  ListPushFront(Phead,111);
  print(Phead);
  ListPushFront(Phead, 112);
  print(Phead);
  LTDestory(Phead);
  Phead = NULL;
}
int main()
{
  test1();
}

DList.c

i将所有函数封装在此文件下

#include "DList.h"
LTNode* BuyNewNode(DListDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return NULL;
  }
  newnode->next = NULL;
  newnode->prev = NULL;
  newnode->data = x;
  return newnode;
}
LTNode* InitLTNode()
{
  LTNode* phead = BuyNewNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
void ListInsert(LTNode* pos,DListDataType x)
{
  assert(pos);
  LTNode* newnode = BuyNewNode(x);
  LTNode* prev = pos->prev;
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}
void ListPushBack(LTNode* phead, DListDataType x)
{
  //ListInsert(phead,x);
  assert(phead);
  LTNode* newnode = BuyNewNode(x);
  LTNode* tail = phead->prev;
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}
void ListPushFront(LTNode* phead, DListDataType x)
{
  //ListInsert(phead->next,x);
  assert(phead);
  LTNode* newnode = BuyNewNode(x);
  LTNode* secound = phead->next;
  newnode->next = secound;
  secound->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}
void ListErase(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  prev->next = next;
  next->prev = prev;
  free(pos);
}
void ListPopBack(LTNode* phead)
{
  //ListErase(phead->prev);
  assert(phead);
  assert(phead != phead->next);
  LTNode* tail = phead->prev;
  phead->prev = tail->prev;
  tail->prev->next = phead;
  free(tail);
}
void ListPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead != phead->next);
  //ListErase(phead->next);
  LTNode* secound = phead->next;
  phead->next = secound->next;
  secound->next->prev = phead;
  free(secound);
}
void print(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  printf("head");
  while (cur!=phead)
  {
    printf("->%d", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
LTNode* LTFind(LTNode* phead, DListDataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
LTNode* LTModify(LTNode* phead, DListDataType x)
{
  LTNode* pos = LTFind(phead, x);
  int y;
  scanf("%d", &y);
  pos->data = y;
}
void LTDestory(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur!=phead)
  {
    LTNode* next = cur->next;
    free(cur);  
    cur = next;
  }
  free(phead);
}

DLlist.h

将主程序所需要的函数全部在头文件中声明，增加代码阅读性

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
typedef int DListDataType;
typedef struct ListNode
{
  DListDataType data;
  struct ListNode* prev;
  struct ListNode* next;
}LTNode;
LTNode* InitLTNode();
void ListInsert(LTNode* pos, DListDataType x);
void ListPushBack(LTNode* phead, DListDataType x);
void ListPushFront(LTNode* phead, DListDataType x);
void print(LTNode* phead);
void ListErase(LTNode* pos);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
LTNode* LTModify(LTNode* phead, DListDataType x);
LTNode* LTFind(LTNode* phead, DListDataType x);
void LTDestory(LTNode* phead);

撒花

这就是实现带头双向循环链表的全部内容了，创作不易，还请各位小伙伴多多点赞👍关注收藏⭐，以后也会更新各种关于c语言，数据结构的博客，撒花！



































文章标签：
C语言
缓存
存储
关键词：
数据结构链表
线性表链表
数据结构线性表链表
数据结构线性表
数据结构双向循环链表
游客cxwjr657j6vg2
目录
相关文章
XIAZHI
|
2月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
67 4
RossyYan
|
2天前
|
存储 算法 测试技术
【C++数据结构——线性表】求集合的并、交和差运算（头歌实践教学平台习题）【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括： 1. **单链表表示集合**：使用单链表存储集合元素，确保元素唯一且无序。 2. **求并集**：遍历两个集合，将所有不同元素加入新链表。 3. **求交集**：遍历集合A，检查元素是否在集合B中存在，若存在则加入结果链表。 4. **求差集**：遍历集合A，检查元素是否不在集合B中，若满足条件则加入结果链表。 通过C++代码实现上述操作，并提供测试用例验证结果。测试输入为两个集合的元素，输出为有序集合A、B，以及它们的并集、交集和差集。 示例测试输入： ``` a c e f a b d e h i ``` 预期输出：
RossyYan
25 7
RossyYan
|
2天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通 - **任务描述**：实现单链表的基本运算。 - **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。 - **通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了测试通过后的预期输出结果。 开始你的任务吧，祝你成功！
RossyYan
20 5
RossyYan
|
2天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算（头歌实践教学平台习题）【合集】
本文档介绍了线性表的基本运算任务，涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法，并提供了测试说明和通关代码。 主要内容包括： - **任务描述**：实现顺序表的基本运算。 - **相关知识**：介绍线性表的基本概念及操作，如初始化、销毁、判定是否为空表等。 - **具体操作**：详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法，并附有代码示例。 - **测试说明**：提供测试输入和预期输出，确保代码正确性。 - **通关代码**：给出完整的C++代码实现，帮助完成任务。 文档
RossyYan
20 5
三三是该溜子
|
16天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
28 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
2月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
78 5
ephemerals__
|
2月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
126 4
XIAZHI
|
2月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
57 0
ephemerals__
|
2月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
86 0
ephemerals__
|
2月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
262 9