学习笔记---更进一步的双向链表专题~~

2023-10-28 22:20
文章标签 学习 链表 笔记 双向 专题 更进一步

本文主要是介绍学习笔记---更进一步的双向链表专题~~，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1. 双向链表的结构🦊

2. 实现双向链表🐝

2.1 要实现的目标🎯

2.2 创建+初始化🦋

2.2.1 List.h

2.2.2 List.c

2.2.3 test.c

2.2.4 代码测试运行

2.3 尾插+打印+头插🪼

思路分析

2.3.1 List.h

2.3.2 List.c

2.3.3 test.c

2.3.4 代码测试运行

2.4 尾删+头删🐊

2.4.0 思路分析

2.4.1 List.h

2.4.2 List.c

2.4.3 test.c

2.4.4 代码测试运行

2.5 查找数据+pos节点后插入+删除pos节点🦩

2.5.0 思路分析

2.5.1 List.h

2.5.2 List.c

2.5.3 test.c

2.5.4 代码测试运行

2.6 销毁☄️

2.6.0思路分析

1. 一级指针

2.6.1 List.h

2.6.2 List.c

2.6.3 test.c

2.6.4 代码测试运行

2. 二级指针

2.6.1 List.h

2.6.2 List.c

2.6.3 test.c

2.6.4 代码测试运行

2.7 完整代码💦

2.7.1 List.h

2.7.2 List.c

2.7.3 test.c

3. 顺序表和双向链表的分析🍻

1. 双向链表的结构🦊

这里的双向链表，准确的说是：带头双向循环链表

这里的“头节点”指的是“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨

的”。

“哨兵位”存在的意义：遍历循环链表避免死循环。

注意⚠️

双向链表的每一个节点存储一个有效数据+下一个节点的地址+上一个节点的地址

头节点和尾节点有些特殊：头节点指向的上一个节点的地址是尾节点，尾节点指向的下一个节点的地址是头节点

2. 实现双向链表🐝

2.1 要实现的目标🎯

我们需要多个接口帮助我们实现：创建、一系列具体操作、销毁

具体操作包括：头部/尾部插入数据、头部/尾部删除数据、打印出双向链表、指定节点之后插入数据、删除指定节点的数据、查找指定节点

2.2 创建+初始化🦋

2.2.1 List.h

#include<assert.h>
#include<string.h>
#include<stdbool.h>typedef int LTDataType;
//创建双向链表的结构体
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;//初始化
ListNode* LTInit();//不用传入参数，直接调用接口返回一个头节点

2.2.2 List.c

#include"List.h"
//初始化
ListNode* LTInit()//不用传入参数，直接调用接口返回一个头节点
{//为头节点申请空间ListNode* phead = (ListNode*)malloc(sizeof(ListNode));//判断开辟是否成功if (phead == NULL){perror("malloc error!\n");return;}//开辟成功--->初始化头节点phead->data = -1;//头节点不存储有效数据，可以任意赋值//只有哨兵位的时候，要实现双向链表，不能指向NULL，否则无法双向循环，所以我们指向自己phead->prev = phead->next = phead;return phead;
}

2.2.3 test.c

#include"List.h"
void ListTest()
{ListNode* plist = LTInit();
}
int main()
{ListTest();return 0;
}

2.2.4 代码测试运行

2.3 尾插+打印+头插🪼

思路分析

2.3.1 List.h

//在双向链表中不会改变哨兵位，所以这里都可以传一级指针
//尾插
void LTPushBack(ListNode* phead, LTDataType x);//打印
void LTPrint(ListNode* phead);//头插
void LTPushFront(ListNode* phead, LTDataType x);

2.3.2 List.c

//在双向链表中不会改变哨兵位，所以这里都可以传一级指针
// 只改变数据，不改变地址//开辟空间
ListNode* ListBuyNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc error!\n");return;}node->data = x;node->next = node->prev = NULL;return node;
}//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//注意哨兵位不能为空//申请空间ListNode* node = ListBuyNode(x);//先处理node的前驱指针和后继指针node->prev = phead->prev;node->next = phead;//再处理之前的尾节点和pheadphead->prev->next = node;phead->prev = node;
}//打印
void LTPrint(ListNode* phead)
{//哨兵位不能改变ListNode* cur = phead->next;while (cur != phead)//当cur再次指向phead的时候，循环结束{printf("%d->", cur->data);cur = cur->next;}printf("\n");
}//头插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);//注意哨兵位不能为空//申请空间ListNode* node = ListBuyNode(x);//node插入头节点之后才算头插//先处理node的前驱指针和后继指针node->prev = phead;node->next = phead->next;//再处理phead和phead->nextphead->next->prev = node;phead->next = node;
}

2.3.3 test.c

#include"List.h"
void ListTest()
{ListNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 LTPushFront(plist, 5);LTPrint(plist);//5 1 2 3 4 
}
int main()
{ListTest();return 0;
}

2.3.4 代码测试运行

2.4 尾删+头删🐊

2.4.0 思路分析

2.4.1 List.h

//尾删
void LTPopBack(ListNode* phead);//头删
void LTPopFront(ListNode* phead);

2.4.2 List.c

//尾删
void LTPopBack(ListNode* phead)
{//不能为空链表，只有一个哨兵位不能尾删assert(phead&&(phead->prev!=phead||phead->next!=phead));ListNode* del = phead->prev;//phead->prev就是尾节点//先处理deldel->prev->next = phead;//再处理pheadphead->prev = del->prev;free(del);del = NULL;
}//头删
void LTPopFront(ListNode* phead)
{//不能为空链表，只有一个哨兵位不能头删assert(phead && (phead->prev != phead || phead->next != phead));ListNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

2.4.3 test.c

#include"List.h"
void ListTest()
{ListNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 LTPushFront(plist, 5);LTPrint(plist);//5 1 2 3 4 LTPopBack(plist);LTPrint(plist);//5 1 2 3LTPopFront(plist);LTPrint(plist);//1 2 3
}
int main()
{ListTest();return 0;
}

2.4.4 代码测试运行

2.5 查找数据+pos节点后插入+删除pos节点🦩

2.5.0 思路分析

2.5.1 List.h

//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x);//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x);//删除pos节点
void LTErase(ListNode* pos);

2.5.2 List.c

//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur!= phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x)
{assert(pos);ListNode* node = ListBuyNode(x);//nodenode->next = pos->next;node->prev = pos;//pospos->next = node;node->next->prev = node;
}//删除pos节点
void LTErase(ListNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

2.5.3 test.c

#include"List.h"
void ListTest()
{ListNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 LTPushFront(plist, 5);LTPrint(plist);//5 1 2 3 4 LTPopBack(plist);LTPrint(plist);//5 1 2 3LTPopFront(plist);LTPrint(plist);//1 2 3ListNode* find = LTFind(plist, 1);/*LTPushAfter(find, 4);*/	//LTPrint(plist);//1 4 2 3LTErase(find);LTPrint(plist);//2 3}
int main()
{ListTest();return 0;
}

2.5.4 代码测试运行

2.6 销毁☄️

2.6.0思路分析

一开始的初始化，我们直接调用了接口，返回头节点进行初始化。我们没有考虑一级指针还是二级指针的问题。

那么，最后的销毁又该怎么办？是一级指针？还是二级指针？下面我们一一来尝试

1. 一级指针

2.6.1 List.h
//销毁
void LTDestroy(ListNode* phead);
2.6.2 List.c
//销毁
void LTDestroy(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while(cur!=phead){ListNode* next = cur->next;free(cur);cur = next;}//注意哨兵位还没有释放free(phead);phead = NULL;
}
2.6.3 test.c
#include"List.h"
void ListTest()
{ListNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 //LTPushFront(plist, 5);//LTPrint(plist);//5 1 2 3 4 //LTPopBack(plist);//LTPrint(plist);//5 1 2 3//LTPopFront(plist);//LTPrint(plist);//1 2 3//ListNode* find = LTFind(plist, 1);/*LTPushAfter(find, 4);*/	LTPrint(plist);//1 4 2 3//LTErase(find);//LTPrint(plist);//2 3LTDestroy(plist);}
int main()
{ListTest();return 0;
}
2.6.4 代码测试运行

一级指针：
phead的改变不影响plist，phead释放之后，plist指向已经释放掉的空间——>把plist置为空

那么置为空之前，还要不要将plist指向的空间再free一次？

我们尝试一下

那么再思考一下：一级指针是会导致phead的改变不影响plist，那么plist是什么没有改变？是指plist保存的值没有被改变还是plist的这块空间的地址没有被释放？

这里报错指的是plist指向无效地址

注意⚠️
如果plist的地址没有被释放，那么直接free（plist）是不会报错的

所以在一级指针的情况下：plist的地址已经被释放了，没有被置为空的可以理解是plist的地址名称

2.6.5 一级指针的改进---test.c

2. 二级指针

2.6.1 List.h
//销毁
//void LTDestroy(ListNode* phead);
void LTDestroy(ListNode** phead);
2.6.2 List.c
//销毁
void LTDestroy(ListNode** phead)
{assert(phead && *phead);ListNode* cur = (*phead)->next;while (cur != *phead){ListNode* next = cur->next;free(cur);cur = next;}free(*phead);*phead = NULL;
}
2.6.3 test.c
#include"List.h"
void ListTest()
{ListNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 //LTPushFront(plist, 5);//LTPrint(plist);//5 1 2 3 4 //LTPopBack(plist);//LTPrint(plist);//5 1 2 3//LTPopFront(plist);//LTPrint(plist);//1 2 3//ListNode* find = LTFind(plist, 1);///*LTPushAfter(find, 4);*/	LTPrint(plist);//1 4 2 3//LTErase(find);//LTPrint(plist);//2 3//LTDestroy(plist);//plist = NULL;LTDestroy(&plist);
}
int main()
{ListTest();return 0;
}
2.6.4 代码测试运行

虽然，二级指针不用手动将plist置为空
但是，更推荐一级指针，因为其他接口基本上都是一级指针——>保持接口的一致性

2.7 完整代码💦

2.7.1 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdbool.h>typedef int LTDataType;
//创建双向链表的结构体
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;//初始化
ListNode* LTInit();//不用传入参数，直接调用接口返回一个头节点//在双向链表中不会改变哨兵位，所以这里都可以传一级指针
//尾插
void LTPushBack(ListNode* phead, LTDataType x);//打印
void LTPrint(ListNode* phead);//头插
void LTPushFront(ListNode* phead, LTDataType x);//尾删
void LTPopBack(ListNode* phead);//头删
void LTPopFront(ListNode* phead);//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x);//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x);//删除pos节点
void LTErase(ListNode* pos);//销毁
void LTDestroy(ListNode* phead);

2.7.2 List.c

#include"List.h"
//初始化
ListNode* LTInit()//不用传入参数，直接调用接口返回一个头节点
{//为头节点申请空间ListNode* phead = (ListNode*)malloc(sizeof(ListNode));//判断开辟是否成功if (phead == NULL){perror("malloc error!\n");return;}//开辟成功--->初始化头节点phead->data = -1;//头节点不存储有效数据，可以任意赋值//只有哨兵位的时候，要实现双向链表，不能指向NULL，否则无法双向循环，所以我们指向自己phead->prev = phead->next = phead;return phead;
}//在双向链表中不会改变哨兵位，所以这里都可以传一级指针
// 只改变数据，不改变地址//开辟空间
ListNode* ListBuyNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc error!\n");return;}node->data = x;node->next = node->prev = NULL;return node;
}//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//注意哨兵位不能为空//申请空间ListNode* node = ListBuyNode(x);//先处理node的前驱指针和后继指针node->prev = phead->prev;node->next = phead;//再处理之前的尾节点和pheadphead->prev->next = node;phead->prev = node;
}//打印
void LTPrint(ListNode* phead)
{//哨兵位不能改变ListNode* cur = phead->next;while (cur != phead)//当cur再次指向phead的时候，循环结束{printf("%d->", cur->data);cur = cur->next;}printf("\n");
}//头插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);//注意哨兵位不能为空//申请空间ListNode* node = ListBuyNode(x);//node插入头节点之后才算头插//先处理node的前驱指针和后继指针node->prev = phead;node->next = phead->next;//再处理phead和phead->nextphead->next->prev = node;phead->next = node;
}//尾删
void LTPopBack(ListNode* phead)
{//不能为空链表，只有一个哨兵位不能尾删assert(phead&&(phead->prev!=phead||phead->next!=phead));ListNode* del = phead->prev;//phead->prev就是尾节点//先处理deldel->prev->next = phead;//再处理pheadphead->prev = del->prev;free(del);del = NULL;
}//头删
void LTPopFront(ListNode* phead)
{//不能为空链表，只有一个哨兵位不能头删assert(phead && (phead->prev != phead || phead->next != phead));ListNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x)
{assert(pos);ListNode* node = ListBuyNode(x);//nodenode->next = pos->next;node->prev = pos;//pospos->next = node;node->next->prev = node;
}//删除pos节点
void LTErase(ListNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁
void LTDestroy(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while(cur!=phead){ListNode* next = cur->next;free(cur);cur = next;}//注意哨兵位还没有释放free(phead);phead = NULL;
}

2.7.3 test.c

#include"List.h"
void ListTest()
{ListNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//1 2 3 4 LTPushFront(plist, 5);LTPrint(plist);//5 1 2 3 4 LTPopBack(plist);LTPrint(plist);//5 1 2 3LTPopFront(plist);LTPrint(plist);//1 2 3ListNode* find = LTFind(plist, 1);/*LTPushAfter(find, 4);*/	//LTPrint(plist);//1 4 2 3LTErase(find);LTPrint(plist);//2 3LTDestroy(plist);plist = NULL;
}
int main()
{ListTest();return 0;
}

3. 顺序表和双向链表的分析🍻

不同点顺序表链表（单链表）
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持O（1）不支持：O（N）
任意位置插入或者删除元素看你需要搬移元素，效率低O（N）只需要改变指针指向
插入动态顺序表，空间不够的时候需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁

本次的分享到这里就结束了！！！

PS：小江目前只是个新手小白。欢迎大家在评论区讨论哦！有问题也可以讨论的！

如果对你有帮助的话，记得点赞👍+收藏⭐️+关注➕

这篇关于学习笔记---更进一步的双向链表专题~~的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程（Gaussian Process，简称GP）是一种概率模型，用于描述一组随机变量的联合概率分布，其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数（或核函数） 1.3 核函数1.4 高斯过程回归（Gauss
阅读更多...
【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

系列文章目录 监督学习：参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归（SAheart.csv） 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学
阅读更多...
系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

本章知识考点：         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2