数据结构入门(C语言版)线性表带头双向循环链表接口实现(上)

简介: 第一步当然是先使用malloc函数申请内存空间,然后就是两个指针的建立,尾部指针指向头结点头部,头部指针指向头结点尾部,返回带头结点,头结点初始化完成。

5d74882d88c44e34904e221ddbc59cb0.png


导航


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


52c51e96575442859756ce7e7b6e8343.jpg


在上一篇博客我们讲述了链表的概念和结构,还实现了无头单向非循环链表接口写法,那么这一章节,我们来实现另一种常用的链表组成结构——带头双向循环链表。

如果对前面的链表基本概念还是不了解,可以看作者的上一篇博客:线性表中链表介绍及无头单向非循环链表接口实现


2、结构体及接口函数定义


首先是结构体的定义

代码如下:


typedef int LTDateType;
typedef struct ListNode
{
  LTDateType data;//结点存储元素
  struct ListNode* next;//下一结点指针
  struct ListNode* prev;//上一结点指针
}LTNode;


然后就是接口函数的定义

代码如下:


void ListInit(LTNode* phead);//哨兵位头结点初始化
LTNode* BuyListNode(LTDateType x);//动态申请结点
void ListPushBack(LTNode* phead, LTDateType x);//双向链表尾插
void ListPopBack(LTNode* phead);//双向链表尾删
void ListPushFront(LTNode* phead, LTDateType x);//双向链表头插
void ListPopFront(LTNode* phead);//双向链表头删
LTNode* ListFind(LTNode* phead, LTDateType x);//双向链表查找
void ListInsert(LTNode* pos, LTDateType x);//在pos位置前插入
void ListErase(LTNode* pos);//删除pos位置的结点
void ListPrint(LTNode* phead);//打印双向链表
void ListDestroy(LTNode* phead);//销毁双向链表


3、接口函数实现


在上一篇博客中我们讲到不带头的单非循环链表存在一定缺陷,就是无法访问上一结点,但是这一节讲的带头双向循环链表就很好的弥补了这一缺点,带头双向循环链表看来比单链表结构要复杂很多,但其实实现起来要比单链表更简单,更高效;下面我们就来实现带头双向循环链表的接口函数吧!


3.1 头结点初始化


头结点初始化(ListInit)

首先是我们的头结点的定义,它是不存放数据的,起到一个哨兵的作用

代码如下:


void ListInit(LTNode* phead)
{
  // 哨兵位头结点
  LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
  phead->next = phead;
  phead->prev = phead;
  return phead;
}


第一步当然是先使用malloc函数申请内存空间,然后就是两个指针的建立,尾部指针指向头结点头部,头部指针指向头结点尾部,返回带头结点,头结点初始化完成。


3.2 结点动态内存申请


结点动态内存申请(BuyListNode)

这个函数和上一篇中的单链表的函数类似

代码如下:


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


第一步也是先使用malloc函数申请内存空间,然后就是初始化这个结点的操作,将元素插入,两个指针指向空,返回新结点,完成结点初始化操作。


3.3 双向链表尾插


双向链表尾插(ListPushBack)

代码如下:


void ListPushBack(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* tail = phead->prev;
  LTNode* newnode = BuyListNode(x);
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}


这里我们先是把phead的上一级指针赋给tail

再将要插入的元素赋给临时结点newnode

接着将tail的下一级指针指向newnode

再将newnode上一级指针指向tail

newnode下一级指针指向被插入结点phead

最后将phead的上一级指针再指向newnode完成尾插操作


3.4 双向链表尾删


双向链表尾删(ListPopBack)

代码如下:


void ListPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//防止链表中无元素继续删除的断言
  LTNode* tail = phead->prev;
  phead->prev = tail->prev;
  tail->prev->next = phead;
  free(tail);
}


上述代码中第二个断言是为了防止链表中无元素继续删除

这里我们也是先把phead的上一级指针赋给tail

再将tail的上一级指针赋给phead的上一级指针

也就是指向要删除结点的上一结点

最后将要删除结点的前一个结点的下一级指针指向头结点

然后释放掉tail的内存空间完成尾删


3.5 双向链表头插


双向链表头插(ListPushFront)

代码如下:


void ListPushFront(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* newnode = BuyListNode(x);
  LTNode* next = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = next;
  next->prev = newnode;
}


这里我们先和尾插一样将要插入的元素值赋给临时结点newnode

将phead下一级指针赋给临时结点next

再将newnode赋给phead下一级指针

也就是把phead的尾部指针指向newnode

把phead赋给newnode的上一级指针

再将next赋给newnode的下一级指针

最后把newnode赋给next的上一级指针,完成头插

相关文章
|
10月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
403 1
|
5月前
|
存储 前端开发 Java
线性数据结构详解
本文介绍了线性数据结构中的核心概念——节点,以及基于节点构建的链表、队列和栈等重要数据结构。节点是计算机科学中基本的构建单元,包含数据和指向其他节点的链接。通过添加约束或行为,可以构建出单向链表、双向链表、队列和栈等复杂结构。
146 1
|
7月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
8月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
10月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
250 1
|
10月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
867 9
|
10月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
217 59
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
47 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语言实现,栈中存储
332 77