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

简介: 这里的查找就是使用一个while循环遍历链表找到某节点的data符合要查找的值

3.6 双向链表头删


双向链表头删(ListPopFront)

代码如下:


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


和尾删一样这里的第二个断言也是为了防止链表中无元素继续删除

头删的第一步就是将phead的下一级指针赋给next

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

再将nextNext赋给phead的下一级指针

最后将phead赋给nextNext的上一指针

把next的内存空间释放完成头删


3.7 双向链表查找


双向链表查找(ListFind)

代码如下:


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


这里的查找就是使用一个while循环遍历链表找到某节点的data符合要查找的值

找到了便返回结点,如果遍历一遍没找到,则返回空(NULL)。


3.8 在pos位置前插入


pos位置前插入(ListInsert)

代码如下:


void ListInsert(LTNode* pos, LTDateType x)
{
  assert(pos);
  LTNode* posPrev = pos->prev;
  LTNode* newnode = BuyListNode(x);
  posPrev->next = newnode;
  newnode->prev = posPrev;
  newnode->next = pos;
  pos->prev = newnode;
}


插入函数的实现首先创建第一个临时结点posPrev

把pos的上一级指针赋给posPrev

将要插入的元素x赋给newnode

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

再将posPrev赋给newnode的上一级指针

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

最后将再将newnode赋给pos的上一级指针完成插入操作

在这里我们可以利用ListInsert函数将前面的尾插和头插进行同义替换

双向链表尾插(ListPushBack)同义替换

代码如下:


void ListPushBack(LTNode* phead, LTDateType x)
{
  assert(phead);
  ListInsert(phead, x);
}


双向链表头插(ListPushFront)同义替换

代码如下:


void ListPushFront(LTNode* phead, LTDateType x)
{
  assert(phead);
  ListInsert(phead->next, x);
}


3.9 删除pos位置的结点


删除pos位置的结点(ListErase)

代码如下:


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


首先将pos的上一级指针赋给posPrev

再将将pos的下一级指针赋给posNext

再将posNext赋给posPrev下一级指针

最后把posPrev赋给posNext上一级指针

将pos内存空间释放,使pos等于空(NULL),完成删除。

同样的,我们也可以利用这个ListErase函数对尾删和头删进行同义替换

双向链表尾删(ListPopBack)同义替换

代码如下:


void ListPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  ListErase(phead->prev);
}


双向链表头删(ListPopFront)同义替换

代码如下:


void ListPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  ListErase(phead->next);
}


3.10 打印双向链表


打印双向链表(ListPrint)

代码如下:


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


这里的打印操作同样是利用while循环进行一遍遍历打印输出


3.11 销毁双向链表


销毁双向链表(ListDestroy)

代码如下:


void ListDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
  phead = NULL;
}


和打印函数原理一样,只不过这里是再进行遍历的同时进行逐个删除

最后将phead内存空间释放,令phead等于空(NULL)完成链表销毁操作。

在这里最后讲一下断言,在之前的单链表那一节的接口函数都有,写断言是为了让代码更健壮

一旦出现了编译错误,我们可以立马排查出问题出在哪里,这是一个不错的代码习惯

带头双向循环链表接口代码可能不是那么好理解,但是实现起来时,却更方便,所以带头双向循环链表对于我们来说是非常必要的知识点!


4、顺序表和链表的区别


特征 顺序表 链表
存储空间 物理上一定连续 逻辑上连续物理上不一定连续
随机访问 支持:O(1) 不支持:O(N)
任意位置插入或删除元素 可能需要搬移元素,效率低O(N) 只需修改指针指向
插入 动态顺序表,空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁
缓存利用率


5、结语


顺序表到这一篇就结束了,这里的带头双向循环链表可能在代码体现上不是那么容易理解,这需要我们不断的去进行学习和实操,如果知识光看,在数据结构这门课的学习上是不会有提高的,最重要的还是练习!!!


制作不易,如有不正之处敬请指出,感谢大家的来访,UU们的观看是我坚持下去的动力,在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!不要忘了一键三连呦!

f9bd9d5b0bfe4679b40dcf390308cf69.png

相关文章
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
193 30
|
7月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
296 25
|
7月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
8月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
8月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
328 5
|
8月前
|
存储 编译器 C语言
【C语言程序设计——入门】C语言入门与基础语法(头歌实践教学平台习题)【合集】
本文档介绍了C语言环境配置和编程任务,主要内容包括: - **C语言环境配置**:详细讲解了在Windows系统上配置C语言开发环境的步骤。 - **第1关:程序改错**:包含任务描述、相关知识(如头文件引用、基本语法规则)、编程要求、测试说明及通关代码。 - **第2关:scanf函数**:涉及`scanf`和`printf`函数的格式与使用方法,提供编程要求、测试说明及通关代码。 文档结构清晰,涵盖从环境搭建到具体编程任务的完整流程,适合初学者学习和实践。
168 4
|
8月前
|
C语言
【C语言程序设计——入门】基本数据类型与表达式(头歌实践教学平台习题)【合集】
这份文档详细介绍了编程任务的多个关卡,涵盖C语言的基础知识和应用。主要内容包括: 1. **目录**:列出所有关卡,如`print函数操作`、`转义字符使用`、`数的向上取整`等。 2. **各关卡的任务描述**:明确每关的具体编程任务,例如使用`printf`函数输出特定字符串、实现向上取整功能等。 3. **相关知识**:提供完成任务所需的背景知识,如格式化输出、算术运算符、关系运算符等。 4. **编程要求**:给出具体的代码编写提示。 5. **测试说明**:包含预期输入输出,帮助验证程序正确性。 6. 文档通过逐步引导学习者掌握C语言的基本语法和常用函数,适合初学者练习编程技能。
220 1
|
9月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
C语言
C语言学生信息管理系统链表实现
C语言学生信息管理系统链表实现
253 0
C语言学生信息管理系统链表实现
史上最简单的C语言链表实现,没有之一
#include #include #include #define NR(x) (sizeof(x)/sizeof(x[0])) struct node { int data ; struct node *next ; }; void top_append_li...
1062 0