数据结构——线性表的链式存储结构3(双向循环链表)

简介: 数据结构——线性表的链式存储结构3(双向循环链表)

目录

前言

定义

双向循环链表的构建

双向循环链表的初始化

新节点的创建

双向循环链表的尾插

双向循环链表的头插

双向循环链表数据的逐一打印

双向循环链表的尾删

双向循环链表的头删

双向循环链表某数据位置的查找

双向循环链表任意位置的插入

双向循环链表任意位置的删除

前言

在之前讲的链表中,有了头结点时,我们可以用O(1)的时间访问第一个结点,但对于要访问到最后一个结点,却需要O(n)的时间,因此出现了双向链表。

定义

在单链表的每个结点中,在设置一个指向其前驱结点的指针域,最后一个结点又指向头结点,头节点的前驱指针指向最后一个结点,从而构成一个回路。

image.png

双向循环链表的构建

typedef int LTDatype;
typedef struct ListNode
{ 
  struct ListNode* next;//后驱指针
  struct ListNode* prev;//前驱指针
  LTDatype data;
}ListNode;

双向循环链表的初始化

ListNode* ListInit(void)
{
  ListNode* phead = BuyListNode(0);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

初始化后

image.png

新节点的创建

ListNode* BuyListNode(LTDatype x)
{
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL; 
  return newnode;
}

双向循环链表的尾插

void pushback(ListNode* phead, LTDatype x)
{
  assert(phead);
  ListNode* tail = phead->prev;
  ListNode* newnode = BuyListNode(x);
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}

双向循环链表的头插

void pushfront(ListNode* phead,LTDatype x)
{
  assert(phead);
  ListNode* newnode = BuyListNode(0);
  ListNode* first = phead->next;
  newnode->data = x;
  newnode->next = first;
  newnode->prev = phead;
  first->prev = newnode;
  phead->next = newnode;
}

双向循环链表数据的逐一打印

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

双向循环链表的尾删

void popback(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  ListNode* tail = phead->prev;
  ListNode* tail2 = tail->prev;
  phead->prev = tail2;
  tail2->next = phead;
  free(tail);
}

双向循环链表的头删

void popfront(ListNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  ListNode* first = phead->next;
  ListNode* second = first->next;
  phead->next = second;
  second->prev = phead;
  free(first);
}

双向循环链表某数据位置的查找

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

双向循环链表任意位置的插入

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

双向循环链表任意位置的删除

void ListErase(ListNode* pos)
{
  assert(pos);
  ListNode* next = pos->next;
  ListNode* prev = pos->prev;
  next->prev = prev;
  prev->next = next;
  free(pos);
}
相关文章
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
176 30
|
7月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
255 25
|
8月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
254 10
|
8月前
|
存储 算法 测试技术
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
200 7
|
8月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
296 5
|
8月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
174 5
|
10月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
210 59
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
35 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
8月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
321 77