博主简介:努力学习的预备程序媛一枚~博主主页: @是瑶瑶子啦所属专栏: Java岛冒险记【从小白到大佬之路】 前言 因为瑶瑶子正在备战蓝桥杯和校内ACM选拔赛,最近在学习算法相关的知识。我是借
- 博主简介:努力学习的预备程序媛一枚~
- 博主主页: @是瑶瑶子啦
- 所属专栏: Java岛冒险记【从小白到大佬之路】
因为瑶瑶子正在备战蓝桥杯和校内ACM选拔赛,最近在学习算法相关的知识。我是借助AcWing网站来学习的,这篇文章是我学习就我学习内容的一个笔记,其中的一些对原理的解释是我学习过程中可能看到弹幕或者评论的小伙伴,觉得讲的很有道理醍醐灌顶,就引用过来了。
这篇是关于数据结构,主要是利用数组模拟各种数据结构,主要是提高算法效率。
对于一些比较晦涩难懂\让人头秃的地方,我习惯采用画图的方式来理解,所以你将看到我基于算法模板或题目精心绘制的图解,希望能帮助一起学算法的同学噢!
因为瑶瑶子目前还是小菜鸡,可能会有理解不到位的地方,或者可以理解得更好的地方,还请大家多多指出哦!❤
注意!下面每一种数据结构的讲解方式,采用代码模板+文字说明&解释+图解
作用:多用于邻接表,存储图和树
代码模板
// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点,后一个int head, e[N], ne[N], idx;//NULL相当于-1,所以head = -1相当于head=NULL// 初始化void init(){ head = -1; idx = 0;}// 在链表头插入一个数avoid insert(int a){ e[idx] = a, ne[idx] = head, head = idx ++ ;}//将x插入到下标是k的点之后void insert(int k, int x){e[idx] = x;ne[idx] = ne[k]ne[k] = idx;idx ++;}// 将头结点删除,需要保证头结点存在void remove(){ head = ne[head];}
e[N]
和存储该节点的next指针数组ne[N]
通过下标关联=-1
,这个-1相当于物理地址的NULL
,表示链表为空,即head指向一个头节点,而使用头插法,又巧妙的使这个空节点成为尾节点。联想结构体实现的单链表,最后一个节点的指针域是NULL
所以,数组实现单链表的最后一个节点,假设是i,那么ne[i]=-1
;比较点 | 结构体/类模拟Node | 数组模拟Node |
---|---|---|
节点本身指针 | 物理地址,node | 通过在数组下标,表示自身指针 |
数值域 | 就在结构体中定义node.val | val[node],通过数组来存储数值域 |
指针域 | 结构体中定义,node. next | next[node],通过数组来存储 |
图解
插入操作(头插法)
学习了数组模拟单链表,其实双链表就很好理解了。其实就是多了一个指针域。
//e[index],表示节点的值,l[index]表示节点的左指针,r[index]表示节点的右指针,idx表示当前用到哪个节点的”地址“int e[N],l[N],r[N],idx;//初始化void init(){ //0是左端点,1是右端点 r[0] = 1,l[1] = 0; idx = 2;}//在节点a的右边插入一个数xvoid insert(int a,int x){ //1、让待插入节点占位 e[idx] = x; //2、处理待插入点左右两侧 l[idx] = a,r[idx] = r[a];//注意,这里必须是r[a],因为a的下一个节点不一定和a顺序存储 //3、处理前一个节点和后一个节点 l[r[a]] = idx,r[a] = idx++;}
Java岛冒险记【从小白到大佬之路】
LeetCode每日一题–进击大厂
来源地址:https://blog.csdn.net/Yaoyao2024/article/details/129621855
--结束END--
本文标题: 【算法基础】数据结构| 单链表+双链表 代码实现+图解+原理
本文链接: https://www.lsjlt.com/news/411664.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-01
2024-04-03
2024-04-03
2024-01-21
2024-01-21
2024-01-21
2024-01-21
2023-12-23
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0