【数据结构初阶】链表分类与双向带头循环链表接口实现

2024-09-07 20:12
文章标签 实现 接口 链表 数据结构 分类 初阶 双向 循环 带头

本文主要是介绍【数据结构初阶】链表分类与双向带头循环链表接口实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 1. 链表的分类
  • 2. 双向带头循环链表接口实现
    • 2. 1 结点声明
    • 2. 2 创建链表节点
    • 2. 3 初始化链表
    • 2. 4 打印链表
    • 2. 5 尾插
    • 2. 6 判空
    • 2. 7 尾删
    • 2. 8 头插
    • 2. 9 头删
    • 2. 10 查找
    • 2. 11 在指定位置删除与插入
    • 2. 12 销毁
  • 3. 链表接口测试
  • 4. 单链表与双链表
  • 5. 顺序表与链表

1. 链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2x2x2）链表结构：
1
2
虽然有这么多的链表的结构，但是我们实际中最常用只有两种结构：单链表和双向带头循环链表。

  1. 无头单向非循环链表：也就是上一篇博客中的单链表，结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在题目中出现很多。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这个结构虽然结构复杂，但是使用代码实现以后会发现复杂的结构会带来很多优势，接口的实现反而简单了。

这篇博客将主要介绍双向带头循环链表（以下简称双链表）的接口实现。
我们不可能将以上8种链表的接口全部实现一遍，因为这没有意义，我们只需要将最简单和最复杂的链表实现一下，就可以很容易类推出其他链表的接口该怎么写了。

2. 双向带头循环链表接口实现

2. 1 结点声明

和单链表结点是相似的，只是除了指向下一个节点的指针之外，还要加上指向上一个节点的指针。

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;	//指向上一个节点struct ListNode* prev;	//指向下一个节点
}ListNode;

2. 2 创建链表节点

ListNode* BuyListNode(LTDataType x);

和单链表一样，创建节点的操作也是经常需要进行的，所以我们先实现一下。
操作基本和单链表中的创建节点一样，只是要注意双链表中有两个指针需要进行初始化。

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

2. 3 初始化链表

ListNode* ListCreate();

双链表是需要初始化的，因为它和单链表不同，它有一个不存储数据的头结点（哨兵位），那么这个初始化就是创建这个头结点。
另外需要注意，双链表还是一个循环链表，那么头结点中的prev和next指针都不能置为空，应该指向它本身，这样才能循环起来。

ListNode* ListCreate()
{ListNode* phead = BuyListNode(-1);	//头结点不存储值，但是还是需要传递一个if (phead == NULL){perror("ListCreate()::malloc");exit(1);}phead->next = phead->prev = phead;	//让这两个指针都指向它本身return phead;
}

2. 4 打印链表

void ListPrint(ListNode* phead);

打印链表也很简单，遍历链表，打印data，但是问题在于：循环应该什么时候停下来？
我们在创建链表的时候给头结点存储了数据-1，难道要通过判断结点数据是不是-1吗？如果这样的话，如果链表中其他节点存储了-1该怎么办呢？
正确的处理办法是，当cur在遍历链表时，判断cur->next!=phead是否成立就可以了。

void ListPrint(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");	//打印完换行，方便连续打印
}

2. 5 尾插

void ListPushBack(ListNode* phead, LTDataType x);

我们先来看尾插，想要尾插，我们有这几个步骤：

  1. 创建新节点存储数据
  2. 新节点的下一个指向头结点
  3. 新节点的上一个指向原来的尾节点
  4. 原来的尾节点指向新节点
  5. 头节点的上一个指向新节点

我们该怎么找到尾节点呢？遍历链表吗？
并不需要，phead->prev不就是尾节点了吗？

void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);if (newnode == NULL){perror("ListPushBack()::malloc");exit(1);}//由于是通过phead->prev找到的尾节点，所以在对尾节点的操作完成之前，不能修改phead->prevnewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;	//这一步必须是最后一步，其他的顺序可以调换
}

可以发现，相对单链表，双链表的尾插的时间复杂度明显降低了。
单链表由于要遍历链表寻找尾节点，所以时间复杂度是O(N)，但是双链表不需要，时间复杂度是O(1)，这对于链表这样需要大量存储数据的数据结构来说是非常有优势的。

2. 6 判空

bool ListEmpty(ListNode* phead);

判断双链表中除了头节点是否还有其他节点，为后续的删除操作做准备。

逻辑很简单，判断头结点的下一个节点是不是头节点就可以了。

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

2. 7 尾删

void ListPopBack(ListNode* phead);

尾删有这么几个步骤：

  1. 尾节点的上一个节点的next指针指向phead
  2. 头节点的prev指向尾节点的上一个节点
  3. 释放原本的尾节点

但是有一点需要注意，如果链表中只有一个头节点的话，我们就不能再删除了，否则结果无法预测。

void ListPopBack(ListNode* phead)
{assert(phead);				//形参不为空指针assert(!ListEmpty(phead));	//链表不为空ListNode* del = phead->prev;//把原来的尾节点存储起来，方便使用del->prev->next = phead;	//步骤1phead->prev = del->prev;	//步骤2free(del);					//步骤3del = NULL;
}

2. 8 头插

void ListPushFront(ListNode* phead, LTDataType x);

注意头插是在头结点后面插入，否则就成了尾插。
头插有这么几个步骤：

  1. 创建新节点存储数据
  2. 新节点的prrev指向phead
  3. 新节点的next指向phead->next
  4. phead->next的prev指向新节点
  5. phead的next指向新节点（同样地，这一步也必须是最后一步）
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);	//1newnode->prev = phead;			//2phead->next->prev = newnode;	//3newnode->next = phead->next;	//4phead->next = newnode;			//5
}

2. 9 头删

void ListPopFront(ListNode* phead);

注意头删是删除头节点后面的节点，而不是删除头结点。
头删有这么几个步骤：

  1. 判空，将要被删除的节点存储为del（和尾删一样，方便使用）
  2. phead的next指向del->next
  3. del->next的prev指向phead
  4. 释放del

2，3步没有顺序限制。

void ListPopFront(ListNode* phead)
{assert(phead);assert(!ListEmpty(phead));ListNode* del = phead->next;//1phead->next = del->next;	//2del->next->prev = phead;	//3free(del);del = NULL;					//4
}

2. 10 查找

ListNode* ListFind(ListNode* phead, LTDataType x);

查找双链表中存储了数据x的第一个节点，并返回节点，如果没有找到，就返回NULL。

思路就是遍历链表，对比数据，而遍历链表已经在打印函数中解释过，这里便不再赘述。
这个函数为后续两个函数做准备。

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

2. 11 在指定位置删除与插入

删除

void ListErase(ListNode* pos);

删除是将pos节点删除，pos节点一般来自上面的查找函数。
但是查找函数可能会返回NULL，所以要注意对pos判空。
删除函数有这么几个步骤：

  1. pos判空
  2. 将pos的上一个节点的next置为pos的下一个节点
  3. 将pos的下一个节点的prev置为pos的上一节点
  4. 释放pos

2，3步没有固定顺序。

void ListErase(ListNode* pos)
{assert(pos);	//1pos->prev->next = pos->next;	//2pos->next->prev = pos->prev;	//3free(pos);pos = NULL;		//4
}

插入

void ListInsert(ListNode* pos, LTDataType x);

插入函数用于在pos前插入节点。
插入有这几个步骤：

  1. 创建新节点
  2. 新节点的next指向pos
  3. 新节点的prev指向pos->prev
  4. pos的上一个节点的next指向新节点
  5. pos的prev指向新节点

第5步必须在3，4步后面（建议直接放最后）。

void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x);	//1if (!newnode){perror("ListInsert()::malloc");exit(1);}newnode->next = pos;		//2newnode->prev = pos->prev;	//3pos->prev->next = newnode;	//4pos->prev = newnode;		//5
}

2. 12 销毁

void ListDestory(ListNode* phead);

双链表的节点也都是动态开辟出来的，所以也要记得释放，防止内存泄漏。
遍历链表逐个释放节点就可以了，注意为了顺利地遍历链表，要把头节点放到最后释放。

void ListDestory(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){ListNode* Next = pcur->next;free(pcur);pcur = Next;}free(phead);
}

3. 链表接口测试

事实上，我们本应该在实现一个接口后就对其进行测试，但是在博客中不方便频繁插入测试代码，所以我们在最后统一进行测试。
测试时，要注意要使用到所有的接口，并且在每一次接口调用之后，都对链表进行打印，观察是否符合预期。

#include"List.h"
void test1()
{ListNode* plist = ListCreate();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListPopBack(plist);ListPrint(plist);ListPopBack(plist);ListPrint(plist);ListPopBack(plist);ListPrint(plist);ListPopBack(plist);ListPrint(plist);//ListPopBack(plist);	//用来测试当链表中只有一个头结点时，是否会按照预期报错ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);ListPrint(plist);ListNode* pos = ListFind(plist, 4);	//在这里多测试几个数，特别是特殊情况if (!pos)printf("没找到");elseListInsert(pos, 11);	//在4前面加上一个11ListPrint(plist);ListErase(pos);ListPrint(plist);ListDestory(plist);plist = NULL;
}int main()
{test1();return 0;
}

测试结果：
1

4. 单链表与双链表

相比起单链表，由于双链表能够直接找到上一个节点，所以很多函数的实现不需要再遍历链表去找上一个节点，时间复杂度大大降低，这便是双链表的最大优势。
当然，头结点与循环结构同样带来了一些优势，可以自己体会一下。

5. 顺序表与链表

不同点顺序表链表
存储空间物理上连续逻辑上连续，但物理上不一定连续
随机访问支持：O(1)不支持：O(N)
任意位置插入或删除需要移动元素，效率低只需改变指针指向，效率高
插入动态顺序表，空间不够时需要扩容，会有空间浪费。静态顺序表空间不够便无法再插入没有容量的概念，按需申请释放，没有空间浪费
应用场景元素高速存储，频繁访问任意位置高效插入删除

谢谢你的阅读，喜欢的话来个点赞收藏评论关注吧！
我会持续更新更多优质文章

这篇关于【数据结构初阶】链表分类与双向带头循环链表接口实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1146042。

相关文章

基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2