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

简介: 带头双向循环链表带头双向循环链表的优点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语言,数据结构的博客,撒花!



































相关文章
|
12天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
30 5
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
61 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
43 0
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
24 0
|
2月前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
2月前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
2月前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
24 0