数据结构——带头双向循环链表上

简介: 数据结构——带头双向循环链表上

带头双向循环链表的结构

带头双向循环链表的结构如下图:


723fc34930e149d1b510f37372dd4fd6.png




可以看到,带头双向循环链表是结构最复杂的链表


但是在实际使用链表结构存储数据时,都是使用带头双向循环链表,虽然这个结构有些复杂,但是这样的结构会给我们带来很多优势,实现代码的时候反而简单了


下面我们来实现一下带头双向循环链表


带头双向循环链表的实现

因为这是一个双向链表,所以要在结构体中定义2个结构体类型指针,用来指向节点的前一个结点和后一个结点


所以带头双向循环链表的结构体如下:


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


建立新节点

这里还是使用malloc去建立一个结点,其余的与单链表中建立新节点类似,这里不多说。


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


初始化函数

因为这个结构是包含头节点的,所以要在初始化函数中把头节点定义出来


LTNode* phead = BuyNewNode(-1);
1

因为此时只有头节点一个结点,又因为结构是循环的,所以头节点的下一个结点和上一个节点都是头节点自己


phead->next = phead;
phead->prev = phead;
1
2
所以,初始化的代码为:
LTNode* LTInit()
{
  LTNode* phead = BuyNewNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
1


打印函数

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


判空函数

当只剩头节点一个节点时,链表就为空了,所以当phead->next == phead时,就说明链表为空了


bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}


尾插函数

尾插函数第一步就是要找尾,在单链表中,想要找到尾就需要遍历一遍链表,效率低耗时


但是在带头双向循环链表中,找到尾很简单,尾节点就是头节点的前一个节点


然后再依次将结点前后链接上即可


a82cccceb0244e83b4f6fde3d9077f32.png

void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyNewNode(x);
  LTNode* tail = phead->prev;
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}


头插函数

在实现单链表时,头节点就是头指针指向的结点

在带头双向循环链表中,头节点就是头节点的下一个结点


6871a36b263b4ea3824a89347f53a6b5.png


void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyNewNode(x);
  LTNode* nex = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = nex;
  nex->prev = newnode;
}


尾删函数

在单链表中,我们循环需要找到尾节点以及尾节点前面的节点,十分的麻烦

但是在带头双向循环链表中,就没有这样的问题



d19aebeac5a740378dbdf55f3a2b451f.png


头节点的prev就是尾节点tail,尾节点的prev就是尾节点的前一个节点tailprev


然后将tailprev当成尾节点链接起来,最后free掉tail


void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* tail = phead->prev;
  LTNode* tailprev = tail->prev;
  tailprev->next = phead;
  phead->prev = tailprev;
  free(tail);
  tail = NULL;
}


头删函数

void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* del = phead->next;
  LTNode* nex = del->next;
  phead->next = nex;
  nex->prev = phead;
  free(del);
  del = NULL;
}


头删与尾删类似,不多说


查找函数

在单链表中,查找某个节点的循环条件是什么时候遇到空,什么时候结束循环


在带头双向循环链表中,循环条件则是遇到头节点,就结束循环


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;
}
—————————


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