=========================================================================
相关代码gitee自取:
C语言学习日记: 加油努力 (gitee.com)
=========================================================================
接上期:
【数据结构初阶】三、 线性表里的链表(无头+单向+非循环链表 -- C语言实现)-CSDN博客
=========================================================================
引言
通过上期对单链表(无头+单向+非循环链表)的介绍和使用
我们可以知道顺序表和链表的区别:
顺序表和链表的一些区别:
- 单链表(无头+单向+非循环链表)只有一个后继指针next指向下一个结点,
而双向链表不仅有后继指针next还有一个前驱指针prev指向上一个结点
- 上篇单链表只能顺着往后遍历,不能倒着往回走,
会造成一些操作很困难(回文、逆置等操作),
而双向链表能顺着往后遍历也能倒着往回遍历更多区别图示:
不同点(方面) 顺序表 链表 存储空间上 物理上一定连续 逻辑上连续,但物理上不一定连续 随机访问 支持 -- O(1) 不支持 -- O(N) 任意位置插入或者删除 可能需要搬移元素,效率低 -- O(N) 只需修改指针指向 插入时的容量(空间) 动态顺序表,空间不够时需要扩容 没有容量的概念(分成一个个结点) 应用场景 元素高效存储+频繁访问 频繁在任意位置插入和删除 缓存利用率 高 低 注:缓存利用率 参考 存储体系结构 以及 局部原理性
回顾上期中提到的带头双向循环链表:
带头双向循环链表
简介:
结构最复杂,一般用在单独存储数据。
实际中使用的链表数据结构,都是带头双向循环链表。
另外这个结构虽然结构复杂,
但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了
图示:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 . 双向链表的实现
(带头+双向+循环 链表)
(详细解释在图片的注释中,代码分文件放最后)
实现具体功能前的准备工作
- 包含之后会用到的头函数
- 创建双向链表数据类型 -- 链表结点中数据域里存储的数据的类型
- 创建双向链表结点结构体(类型) -- 结点中应有 数据域 和 指针域
图示
---------------------------------------------------------------------------------------------文章来源:https://www.uudwc.com/A/aYDJG/
BuyLTNode函数 -- 创建双向循环链表结点
- 为创建结点开辟动态空间,并检查是否开辟成功
- 开辟成功后,初始化结点数据域和指针域
- 最后返回开辟的空间地址
图示
---------------------------------------------------------------------------------------------
LTInit函数 -- 带头双向循环链表初始化函数
- 初始化时先使用BuyLTNode函数创建哨兵位
- 因为要实现循环,
所以让哨兵位后继指针next和前驱指针prev都指向自己
- 初始化后返回链表哨兵位
图示
---------------------------------------------------------------------------------------------
LTPrint函数 -- 打印双向链表各结点数据域数据
- assert断言头指针(哨兵位地址)不为空
- 创建结点指针cur进行遍历
- 使用while循环进行遍历打印
图示
测试 -- LTPrint函数
---------------------------------------------------------------------------------------------
LTPushBack函数 -- 向链表尾部插入一个结点(尾插)
- assert断言头指针(哨兵位地址)不为空
- 通过哨兵位配合前驱指针prev获得尾结点地址
- 调用BuyLTNode函数为尾插操作创建尾插结点newnode
将尾插结点和原尾部结点连接
将尾插结点和哨兵位进行连接
图示
测试 -- LTPushBack函数
---------------------------------------------------------------------------------------------
LTPopBack函数 -- 删除链表尾部结点(尾删)
- assert断言 头指针(哨兵位地址)不为空 和 双向链表不为空链表
- 通过哨兵位的前驱指针prev获得尾结点tail,
再通过尾结点tail获得倒数第二个结点tailPrev
- 释放(删除)尾结点tail
让倒数第二个结点tailPrev成为新的尾结点,
为保持循环,把tailPrev和哨兵位连接起来图示
测试 -- LTPopBack函数
---------------------------------------------------------------------------------------------
LTPushFront函数 -- 向链表头部插入一个结点(头插)
- assert断言头指针(哨兵位地址)不为空
- 调用BuyLTNode函数为头插操作创建头插结点newnode
- 创建一个first指针保存原本第一个结点地址
哨兵位后继指针next指向头插结点newnode,
头插结点newnode前驱指针prev指向哨兵位
头插结点newnode后继指针next指向原本头结点first,
原本头结点first前驱指针prev指向头插结点newnode图示
测试 -- LTPushFront函数
---------------------------------------------------------------------------------------------
LTPopFront函数 -- 删除链表头部结点(头删)
- assert断言 头指针(哨兵位地址)不为空 和 双向链表不为空链表
- 通过哨兵位后继结点next获得头结点地址,
再通过first结点获得第二个结点
- 释放头结点first
让哨兵位后继结点next指向第二个结点second,
第二个结点的前驱指针prev指向哨兵位图示
测试 -- LTPopFront函数
---------------------------------------------------------------------------------------------
LTSize函数 -- 求链表有效结点个数(求链表长度)
- assert断言头指针(哨兵位地址)不为空
- 创建变量size存放链表长度,
创建结点指针cur进行遍历
- 使用while循环遍历链表,计算链表长度
最后返回链表长度size
图示
测试 -- LTSize函数
---------------------------------------------------------------------------------------------
LTFind函数 -- 在双向链表中查找数据域数据为x的结点地址
- assert断言头指针(哨兵位地址)不为空
- 创建遍历指针cur,保存第一个结点地址
- 使用while循环进行遍历查找
未找到则返回空指针
图示
测试 -- LTFind函数
---------------------------------------------------------------------------------------------
LTInsert函数 -- 在pos结点之前插入数据域数据为x的结点
- assert断言头指针(哨兵位地址)不为空
- 通过pos结点获得前一个结点posPrev地址
- 使用BuyLTNode函数为插入结点开辟空间
posPrev结点的后继指针next指向newnode,
newnode前驱指针prev指向posPrev
newnode后继指针next指向pos,
pos结点前驱指针prev指向newnode图示
测试 -- LTInsert函数
---------------------------------------------------------------------------------------------
LTErase函数 -- 删除pos结点
- assert断言删除位置结点pos不为空
- 保存要删除结点pos的前一个结点posPrev地址,
保存要删除结点pos的后一个结点posNext地址
- 释放掉pos结点
将pos前结点posPrev的后继指针指向posNext,
将pos后结点posNext的前驱指针指向posPrev图示
测试 -- LTErase函数
---------------------------------------------------------------------------------------------
LTDestroy函数 -- 销毁链表
- assert断言头指针(哨兵位地址)不为空
- 创建遍历指针cur,保存第一个结点地址
- 使用while循环遍历释放有效结点
最后释放哨兵位
图示
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2 . 对应代码
List.h -- 双向链表头文件
#pragma once //双向链表头文件: //包含之后需要用到的头文件: #include<stdio.h> #include<stdlib.h> #include<assert.h> //定义双向链表数据域数据类型: typedef int LTDataType; //创建双向链表结点类型: typedef struct ListNode { //数据域: LTDataType data; //双向链表指针域: //后继指针--指向后一个结点: struct ListNode* next; //前驱指针--指向前一个结点: struct ListNode* prev; }LTNode; //类型简称LTNode //函数声明: //创建链表结点--创建双向循环链表结点 //接收要插入创建结点数据域的数据 //返回创建结点的地址 LTNode* BuyLTNode(LTDataType x); //双向链表初始化--带头双向循环链表初始化函数 //返回初始化结点的地址 LTNode* LTInit(); //打印链表--打印双向链表各结点数据域数据 //接收链表头指针(phead) LTNode* LTPrint(LTNode* phead); //双向链表尾插函数--向链表尾部插入一个结点(尾插): //接收链表头指针(phead)、要尾插进链表的值(x) void LTPushBack(LTNode* phead, LTDataType x); //双向链表尾删函数--删除链表尾部结点(尾删) //接收链表头指针(phead) void LTPopBack(LTNode* phead); //双向链表头插函数--向链表头部插入一个结点(头插): //接收链表头指针(phead)、要头插进链表的值(x) void LTPushFront(LTNode* phead, LTDataType x); //双向链表头删函数--删除链表头部结点(头删) //接收链表头指针(phead) void LTPopFront(LTNode* phead); //求链表结点个数函数--求链表有效结点个数(求链表长度) //接收链表头指针(phead) int LTSize(LTNode* phead); //双向链表查找函数--在双向链表中查找数据域数据为x的结点地址 //接收链表头指针(phead)、要在链表中查找的值(x) LTNode* LTFind(LTNode* phead, LTDataType x); //双向链表插入函数--在pos结点之前插入数据域数据为x的结点 //接收插入位置(pos)、要插入链表的值(x) void LTInsert(LTNode* pos, LTDataType x); //双向链表删除函数--删除pos结点 //接收要删除结点地址(pos) void LTErase(LTNode* pos); //双向链表销毁函数--销毁链表 //接收要销毁链表头系欸但(phead) void LTDestroy(LTNode* phead);
---------------------------------------------------------------------------------------------
文章来源地址https://www.uudwc.com/A/aYDJG/
List.c -- 双向链表函数实现文件
#define _CRT_SECURE_NO_WARNINGS 1 //双向链表函数实现文件: //包含双向链表头文件: #include "List.h" //函数实现: //创建链表结点--创建双向循环链表结点 //接收要插入创建结点数据域的数据 LTNode* BuyLTNode(LTDataType x) { //为创建结点开辟动态空间: LTNode* node = (LTNode*)malloc(sizeof(LTNode)); //检查是否开辟失败: if (node == NULL) //返回NULL,开辟失败 { //打印错误信息: perror("malloc fail"); //终止程序: exit(-1); } //把x放入结点数据域: node->data = x; //设置双向链表指针域: node->next = NULL; node->prev = NULL; //开辟成功则返回开辟空间地址 return node; } //链表初始化--带头双向循环链表初始化函数 //接收链表头指针(phead) LTNode* LTInit() { //初始化时先使用BuyLTNode函数创建哨兵位: LTNode* phead = BuyLTNode(-1); //返回哨兵位指针 //因为要实现循环, //所以让哨兵位后继指针next和前驱指针prev都指向自己: phead->next = phead; phead->prev = phead; //这样即使链表为空,它也是有头有尾的,即哨兵位phead //初始化后返回链表哨兵位: return phead; } //打印链表--打印双向链表各结点数据域数据 //接收链表头指针(phead) LTNode* LTPrint(LTNode* phead) { //assert断言头指针(哨兵位地址)不为空: assert(phead != NULL); //创建结点指针cur进行遍历: //指针cur应该从哨兵位(头指针)下一个结点开始 LTNode* cur = phead->next; printf("phead <==> "); //因为是循环链表,不是以NULL空指针结尾 //所以应该是当指针cur遍历回到哨兵位就终止遍历: while (cur != phead) //如果只用哨兵位,链表为空, //phead->next还是phead,不会进行打印 { //打印数据域内容: printf("%d <=> ", cur->data); //打印完当前结点数据域数据后cur移向下个结点: cur = cur->next; } //打印完一个链表后换行: printf("\n"); } //向链表尾部插入一个结点(尾插): //接收结点头指针(phead)、要尾插进链表的值(x) void LTPushBack(LTNode* phead, LTDataType x) { //assert断言头指针(哨兵位地址)不为空: assert(phead != NULL); //通过哨兵位找到尾结点: //因为是循环链表: //所以哨兵位(带头链表)的前一个结点就是尾结点 LTNode* tail = phead->prev; //调用前驱指针获得尾结点 //调用BuyLTNode函数为尾插创建尾插结点newnode: LTNode* newnode = BuyLTNode(x); //尾插结点前驱指针prev指向原本的尾结点: newnode->prev = tail; //原本尾结点后继指针next指向尾插结点: tail->next = newnode; //尾插结点后继指针next指向头结点: newnode->next = phead; //头结点前驱指针指向尾插结点: phead->prev = newnode; //带头+双向+循环 链表: //对比单链表,因为有哨兵位不用考虑链表为空的情况, //且不需要二级指针,通过操纵哨兵位这个结构体, //替换用二级指针操作头指针的操作 /* //第二种方法:复用LTInsert函数 //在哨兵位前插入一个值x就是尾插了: LTInsert(phead, x); */ } //双向链表尾删函数--删除链表尾部结点(尾删) //接收链表头指针(phead) void LTPopBack(LTNode* phead) { //assert断言头指针(哨兵位地址)不为空: assert(phead != NULL); //assert断言双向链表不是空链表: assert(phead->next != phead); //如果哨兵位的下一个结点还是哨兵位说明是空链表 //通过哨兵位的前驱指针prev获得尾结点tail: LTNode* tail = phead->prev; //再通过尾结点tail获得倒数第二个结点tailPrev: LTNode* tailPrev = tail->prev; //释放(删除)尾结点tail: free(tail); //这时就让倒数第二个结点tailPrev成为新的尾结点 //为保持循环,把tailPrev和哨兵位连接起来: tailPrev->next = phead; //tailPrev后继指针指向哨兵位 phead->prev = tailPrev; //哨兵位前驱指针指向tailPrev //带头+双向+循环 链表: //对比单链表,这里双向链表在尾删时因为有哨兵位的存在 //即使链表只剩一个结点,也不用进行判断单独处理进行置空 //这一个结点删掉后,还有哨兵位存在 /* //第二种方法:复用LTErase函数 //传尾结点地址给LTErase函数即可: LTErase(phead->prev); */ } //双向链表头插函数--向链表头部插入一个结点(头插): //接收链表头指针(phead)、要头插进链表的值(x) void LTPushFront(LTNode* phead, LTDataType x) { //第二种方法:多定义一个指针 //assert断言头指针(哨兵位地址)不为空: assert(phead != NULL); //调用BuyLTNode函数为头插创建头插结点newnode: LTNode* newnode = BuyLTNode(x); //创建一个first指针保存原本第一个结点地址: LTNode* first = phead->next; //哨兵位后继指针next指向头插结点newnode: phead->next = newnode; //头插结点newnode前驱指针prev指向哨兵位: newnode->prev = phead; //头插结点newnode后继指针next指向原本头结点first: newnode->next = first; //原本头结点first前驱指针prev指向头插结点newnode: first->prev = newnode; /* //assert断言头指针(哨兵位地址)不为空: assert(phead != NULL); //第一种方法:需要注意连接的顺序 //调用BuyLTNode函数为头插创建头插结点newnode: LTNode* newnode = BuyLTNode(x); //先将头插结点的后继节点next连接上原本头结点: newnode->next = phead->next; //哨兵位的后继指针指向的就是头结点 //再将原本头结点的前驱指针prev指向头插结点newnode: phead->next->prev = newnode; //哨兵位连接上头插节点newnode: phead->next = newnode; //头插结点newnode的前驱指针指向哨兵位: newnode->prev = phead; */ /* //第三种方法:复用LTInsert函数 //在哨兵位后一个结点前插入一个值x就是头插了: LTInsert(phead->next, x); */ } //双向链表头删函数--删除链表头部结点(头删) //接收链表头指针(phead) void LTPopFront(LTNode* phead) { //assert断言头指针(哨兵位地址)不为空: assert(phead != NULL); //assert断言双向链表不是空链表: assert(phead->next != phead); //如果哨兵位的下一个结点还是哨兵位说明是空链表 //通过哨兵位后继结点next获得头结点地址: LTNode* first = phead->next; //再通过first结点获得第二个结点: LTNode* second = first->next; //释放头结点first: free(first); //让哨兵位后继结点next指向第二个结点second: phead->next = second; //第二个结点的前驱指针prev指向哨兵位: second->prev = phead; //带头+双向+循环 链表: //对比单链表,这里双向链表在头删时因为有哨兵位的存在 //即使链表只剩一个结点,也不用进行判断单独处理进行置空 //这一个结点删掉后,还有哨兵位存在 /* //第二种方法:复用LTErase函数 //传第一个结点地址给LTErase函数即可: LTErase(phead->next); */ } //求链表结点个数函数 //接收链表头指针(phead) int LTSize(LTNode* phead) { //assert断言头指针(哨兵位地址)不为空: assert(phead != NULL); int size = 0; //存放链表长度 //创建结点指针cur进行遍历: //指针cur应该从哨兵位(头指针)下一个结点开始 LTNode* cur = phead->next; //因为是循环链表,不是以NULL空指针结尾 //所以应该是当指针cur遍历回到哨兵位就终止遍历: while (cur != phead) //如果只有哨兵位,链表为空, //phead->next还是phead,不会进行打印 { ++size; //遍历一遍长度+1 //cur移向下个结点: cur = cur->next; } //返回链表长度: return size; } //双向链表查找函数--在双向链表中查找数据域数据为x的结点地址 //接收链表头指针(phead)、要在链表中查找的值(x) LTNode* LTFind(LTNode* phead, LTDataType x) { //assert断言头指针(哨兵位地址)不为空: assert(phead != NULL); //创建遍历指针cur,从第一个结点开始: LTNode* cur = phead->next; //使用while循环进行遍历: while (cur != phead) //如果只有哨兵位,链表为空, //phead->next还是phead,不会进行打印 { if (cur->data == x) //找到要找的值了: { return cur; //返回该值结点 } //调整指针: cur = cur->next; } //未找到则返回空指针: return NULL; } //双向链表插入函数--在pos结点之前插入数据域数据为x的结点 //接收插入位置(pos)、要插入链表的值(x) void LTInsert(LTNode* pos, LTDataType x) { //assert断言插入位置pos不为空: assert(pos != NULL); //通过pos结点获得前一个结点posPrev地址: LTNode* posPrev = pos->prev; //使用BuyLTNode函数为插入结点开辟空间: LTNode* newnode = BuyLTNode(x); //posPrev结点的后继指针next指向newnode: posPrev->next = newnode; //newnode前驱指针prev指向posPrev: newnode->prev = posPrev; //newnode后继指针next指向pos: newnode->next = pos; //pos结点前驱指针prev指向newnode: pos->prev = newnode; } //双向链表删除函数--删除pos结点 //接收要删除结点地址(pos) void LTErase(LTNode* pos) { //assert断言删除位置结点pos不为空: assert(pos != NULL); //保存要删除结点pos的前一个结点posPrev地址: LTNode* posPrev = pos->prev; //保存要删除结点pos的后一个结点posNext地址: LTNode* posNext = pos->next; //释放掉pos结点: free(pos); //将pos前结点posPrev的后继指针指向posNext: posPrev->next = posNext; //将pos后结点posNext的前驱指针指向posPrev: posNext->prev = posPrev; } //双向链表销毁函数--销毁链表 //接收要销毁链表头系欸但(phead) void LTDestroy(LTNode* phead) { //assert断言头指针(哨兵位地址)不为空: assert(phead != NULL); //创建遍历指针cur,从第一个结点开始: LTNode* cur = phead->next; //使用while循环进行遍历释放: while (cur != phead) { //释放前先存储下一个结点地址: LTNode* next = cur->next; //释放当前结点: free(cur); //调整指针: cur = next; } //删除完有效结点后,最后再释放哨兵位: free(phead); }
---------------------------------------------------------------------------------------------
Test.c -- 双向链表测试文件
#define _CRT_SECURE_NO_WARNINGS 1 //双向链表函数测试文件: //包含双向链表头文件: #include "List.h" //测试函数-- //LTInit、LTPushBack、LTPrintf函数 void TestList1() { //初始化一个双向链表: LTNode* plist = LTInit(); //初始化后使用尾插函数插入数据: LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); //打印当前双向链表: LTPrint(plist); } //测试函数--LTPopBack函数 void TestList2() { //初始化一个双向链表: LTNode* plist = LTInit(); //初始化后使用尾插函数插入数据: LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); //打印当前双向链表: LTPrint(plist); //进行尾删: LTPopBack(plist); //打印当前双向链表: LTPrint(plist); //进行尾删: LTPopBack(plist); //打印当前双向链表: LTPrint(plist); //进行尾删: LTPopBack(plist); //打印当前双向链表: LTPrint(plist); } //测试函数--LTPushFront函数 void TestList3() { //初始化一个双向链表: LTNode* plist = LTInit(); //初始化后使用尾插函数插入数据: LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); //打印当前双向链表: LTPrint(plist); //进行头插: LTPushFront(plist, 1000); //打印当前双向链表: LTPrint(plist); } //测试函数--LTPopFront函数 void TestList4() { //初始化一个双向链表: LTNode* plist = LTInit(); //初始化后使用尾插函数插入数据: LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); //打印当前双向链表: LTPrint(plist); //进行头删: LTPopFront(plist); //打印当前双向链表: LTPrint(plist); } //测试函数--LTSize函数 void TestList5() { //初始化一个双向链表: LTNode* plist = LTInit(); //初始化后使用尾插函数插入数据: LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); //打印当前双向链表: LTPrint(plist); //计算链表长度: int size = LTSize(plist); //打印当前双向链表: printf("链表长度为:%d", size); } //测试函数--LTFind函数 void TestList6() { //初始化一个双向链表: LTNode* plist = LTInit(); //初始化后使用尾插函数插入数据: LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); //打印当前双向链表: LTPrint(plist); //使用查找函数: LTNode* find = LTFind(plist, 2); //打印找到的地址 printf("0x%xn", find); } //测试函数--LTInsert函数 void TestList7() { //初始化一个双向链表: LTNode* plist = LTInit(); //初始化后使用尾插函数插入数据: LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); //打印当前双向链表: LTPrint(plist); //使用插入函数: LTInsert(plist->next->next, 100); //打印当前双向链表: LTPrint(plist); } //测试函数--LTErase函数 void TestList8() { //初始化一个双向链表: LTNode* plist = LTInit(); //初始化后使用尾插函数插入数据: LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); //打印当前双向链表: LTPrint(plist); //使用删除函数: LTErase(plist->next->next); //打印当前双向链表: LTPrint(plist); } //主函数: int main() { //调用测试函数: //TestList1(); //TestList2(); //TestList3(); //TestList4(); //TestList5(); //TestList6(); //TestList7(); TestList8(); return 0; }