【数据结构 -- C语言】 双向带头循环链表的实现

简介: 【数据结构 -- C语言】 双向带头循环链表的实现

1、双向带头循环链表的介绍

我们将这个题目拆分开来可以提取三个关键字:双向,带头,循环。我们就以这三个关键字来展开介绍一下:
首先是双向:双向就说明了这个结点可以找到自己的前驱和后继,这一点与单链表存在本质的区别;


其次是带头:带头说明链表有一个头结点,这个头结点也可以称为哨兵位的头结点,此结点与其他结点是一样的,只是它的 data 域放的是随机值(有的会存放链表的长度);


最后是循环:循环说明了它的结构是一个环装,头结点的前驱结点存放着尾结点,尾结点的后继结点存放着头结点。


2、双向带头循环链表的接口

双向带头循环链表与单链表的功能是一样的,都是可以增删查改的,但是双向带头循环链表的特性让这么功能写的时候大大提高了我们的效率。

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* next;
  struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

3、接口实现

3.1 开辟结点

我们的链表是动态的链表,因此每次在插入的时候我们都需要 malloc 一个结点,我们将其封装成一个函数,方便后面的代码复用。

ListNode* BuyListNode(LTDataType x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (NULL == newnode)
  {
    perror("malloc fail:");
    return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}

3.2 创建返回链表的头结点

这一步是我们给链表创建一个哨兵位的头结点。因为是双向带头循环链表,因此我们让 prev 和 next 指针都指向自己,这样就算是只有一个头结点,我们也是双向循环的结构。

ListNode* ListCreate()
{
  ListNode* phead = BuyListNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

3.3 判断链表是否为空

这一步是我们为后面的删除时封装的一个判空功能函数,当链表存在的时候不排除链表为空的情况,因此我们封装此函数,以便后面的接口复用。

bool ListEmpty(ListNode* pHead)
{
  assert(pHead);
  return pHead->next == pHead;
}

3.4 打印

打印函数我们已经很熟悉了,但是双向带头循环链表的打印终止条件要注意,这里不再是以前的 cur == NULL,而是 cur != pHead ,当 cur 走到 pHead 时就说明我们已经遍历完整个链表了。

void ListPrint(ListNode* pHead)
{
  assert(pHead);
  ListNode* cur = pHead->next;
  printf("guard");
  while (cur != pHead)
  {
    printf("<==>%d", cur->data);
    cur = cur->next;
  }
  printf("<==>\n");
}

3.5 双向链表查找

查找不难,但是这里要注意,双向带头链表的第一个结点是哨兵位结点,因此我们要从哨兵位的下一个结点开始遍历查找(cur = pHead->next),循环的终止条件依然是 cur != pHead。

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* cur = pHead->next;
  while (cur != pHead)
  {
    if (cur->data == x)
      return cur;
    cur = cur->next;
  }
  return NULL;
}

3.6 双向链表在pos的前面进行插入

我们在找到pos位置后,在 pos 位置前进行插入,我们按下面的流程执行:
1、假如我们要在 data3 前插入一个 data4,我们先用定义一个结构体指针变量 prev,先将data3->prev (data2)结点保存在 prev 变量中;


2、再将 prev->next 改为 data4 ,然后将 data4->prev 改为 prev;


3、最后把 data4->next = data3,再把 data3->prev = data4。



void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);
  ListNode* prev = pos->prev;
  ListNode* newnode = BuyListNode(x);
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;
}

3.6.1 头插

头插的话我们与在pos位置前插入一致,先将第一个结点保存起来,然后进行插入。

void ListPushFront(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* newnode = BuyListNode(x);
  ListNode* first = pHead->next;//多写这一个变量下面的插入语句就可以无序写
  pHead->next = newnode;
  newnode->next = first;
  newnode->prev = pHead;
  first->prev = newnode;
}

3.6.2 尾插

尾插的话先将链表的尾结点保存起来,然后进行插入,还是与在pos位置前插入一样。

void ListPushBack(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* tail = pHead->prev;
  ListNode* newnode = BuyListNode(x);
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = pHead;
  pHead->prev = newnode;
}

3.6.3 更新头插、尾插写法

对比插入代码我们其实不难发现,头插、尾插与在pos位置前插入的代码逻辑是一样的,实现的功能根本上也没有变,那我们就在头插、尾插时直接复用 ListInsert 接口就可以实现。

1> 头插

void ListPushFront(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListInsert(pHead->next, x);
}

2> 尾插

因为是 pos 位置前插入,链表是双向循环的,所以传的第一个参数就是 pHead ,哨兵位结点前一个结点就是尾结点。

void ListPushFront(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListInsert(pHead, x);
}

3.7 双向链表删除pos位置的节点

我们在找到 pos 结点后,再将 pos 结点删除,我们按下面的流程执行:
1、定义两个结构体指针变量 posPrev与posNext,将 pos 位置前后结点分别保存在 posPrev与posNext 指针变量中;


2、将posPrev->next = posNext,再将 posNext->prev = posPrev;


3、释放掉 pos 结点,free(pos)。



void ListErase(ListNode* pos)
{
  assert(pos);
  ListNode* posPrev = pos->prev;
  ListNode* posNext = pos->next;
  posPrev->next = posNext;
  posNext->prev = posPrev;
  free(pos);
}

3.7.1 头删

头删的话我们先将 pHead->next结点与pHead->next->next结点保存下来,将哨兵位结点与头结点的下一个结点连接起来,再将头结点释放掉。

void ListPopFront(ListNode* pHead)
{
  assert(pHead);
  assert(!ListEmpty(pHead));
  ListNode* first = pHead->next;
  ListNode* second = first->next;
  pHead->next = second;
  first->prev = pHead;
  free(first);
}

3.7.2 尾删

尾删的话我们先将 pHead->prev结点与pHead->prev->prev结点保存下来,将哨兵位结点与尾结点的前一个结点连接起来,再将尾结点释放掉。

void ListPopBack(ListNode* pHead)
{
  assert(pHead);
  assert(!ListEmpty(pHead));
  ListNode* tail = pHead->prev;
  ListNode* tailPrev = tail->prev;
  tailPrev->next = pHead;
  pHead->prev = tailPrev;
    free(tail);
}

总结:在头删与尾删前要判断链表是否为空。

3.7.3 更新头删、尾删写法

对比删除代码我们其实不难发现,头删、尾删与删除pos位置结点的代码逻辑是一样的,实现的功能根本上也没有变,那我们就在头删、尾删时直接复用 ListErase 接口就可以实现。

1> 头删

void ListPopFront(ListNode* pHead)
{
  assert(pHead);
  assert(!ListEmpty(pHead));
  ListErase(pHead->next);
}

2> 尾删

void ListPopBack(ListNode* pHead)
{
  assert(pHead);
  assert(!ListEmpty(pHead));
  ListErase(pHead->prev);
}

3.8 双向链表销毁

链表的销毁主要是遍历一遍链表,从 cur = pHead->next 开始,循环终止的条件为 cur != pHead,遍历完再将哨兵位结点释放掉,整个链表就被释放掉了。

void ListDestory(ListNode* pHead)
{
  assert(pHead);
  ListNode* cur = pHead->next;
  while (cur != pHead)
  {
    ListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(pHead);
}

4、完整代码

完整代码在代码仓库,入口:C语言: C语言学习的代码,多复习 - Gitee.com

5、功能测试


相关文章
|
4月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
112 1
|
1月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
86 29
|
16天前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
1月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
95 25
|
2月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
2月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
62 5
|
3月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
3月前
|
存储 算法 C语言
【C语言】深入浅出:C语言链表的全面解析
链表是一种重要的基础数据结构,适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现,以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
920 6
|
4月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
104 5
|
4月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
102 1

热门文章

最新文章