admin管理员组文章数量:1794759
【数据结构】顺序表和链表——链表（包含大量经典链表算法题）
1. 单链表
1.1 概念与结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。
在链表里，每节“车厢”是什么样的呢？
1.1.1 结点
与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”
结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。
图中指针变量plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点，如果我们希望plist“指向”第二个结点时，只需要修改plist保存的内容为0x0012FFA0即可。
链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。
1.1.2 链表的性质
1、链式结构在逻辑上是连续的，在物理结构上不⼀定连续 2、结点一般是从堆上申请的 3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续
结合前面学到的结构体知识，我们可以给出每个结点对应的结构体代码：
假设当前保存的结点为整型：
代码语言：javascript代码运行次数：0运行复制struct SListNode
{
int data; //结点数据
struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。
当我们想要从第一个结点走到最后一个结点时，只需要在当前结点拿上下一个结点的地址就可以了。
1.1.3 链表的打印
给定的链表结构中，如何实现结点从头到尾的打印？
思考：当我们想保存的数据类型为字符型、浮点型或者其他⾃定义的类型时，该如何修改？
1.2 实现单链表
SList.h
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; //结点数据
struct SListNode* next; //指针保存下一个结点的地址
}SLTNode;
void SLTPrint(SLTNode* phead);
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode * SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** pphead);上面这部分是链表实现所需要的节点结构和一些方法，其中具体的方法由读者自己先来尝试实现，如有不会的可以在讨论区询问，将会由作者或者其它积极的读者来解答❤️❤️❤️
1.3 链表的分类
链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：
链表说明：
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向链表
- 无头单向非循环链表（俗称：单链表）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表（俗称：双向链表）：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
1.4 单链表算法题
1.4.1 移除链表元素
/
OJ代码有bug怎么办？VS调试技能用起来
（1）将OJ代码复制粘贴到vs上
（2）创建测试方法，调用本次要调试的目标方法
（3）利用vs调试工具排查代码问题
1.4.2 反转链表
/
1.4.3 链表的中间结点
/
1.4.4 合并两个有序链表
/
1.4.5 链表分割
1.4.6 链表的回文结构
1.4.7 相交链表
/
1.4.8 环形链表1
/
本文标签： 数据结构顺序表和链表链表（包含大量经典链表算法题）
版权声明：本文标题：【数据结构】顺序表和链表——链表（包含大量经典链表算法题） 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754680928a1705123.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论