【初阶数据结构篇】单链表的实现（赋源码）

单链表的实现

代码位置

[Gitee](sllist/sllist · petrichor/2024-summer-c-language - 码云 - 开源中国 (gitee.com))

概念与结构

概念：

​ 链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

​ 类比火车地铁，都是一节一节的

• 淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/ 加上，不会影响其他车厢，每节车厢都是独立存在的。

在链表⾥，每节“⻋厢”是什么样的呢?

结构：

​ 与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”。

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。

• 图中指针变量plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望 plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。
• 链表中每个结点都是独立申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、结点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

---

链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2x2x2）链表结构：

链表说明：

• 虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表
  1. 无头单向非循环链表：结构简单，⼀般不会单独⽤来存数据。实际种更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
  2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。但是这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，在下一篇博客我们将进行双向链表的实现。

单链表的实现

即不带头单向不循环链表

单链表的创建和打印及销毁

---

SList.h(其中方法会一一讲到)

• 定义链表结构
• 将存储数据类型重命名(方便之后替换->例如我们要求单链表内存储char类型数据，只用改一行代码即可)
• 函数的声明，声明的时候参数只需要类型就可以了，名字加不加都一样

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode 
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


void creatlist();
SLTNode* SLTBuyNode(SLTDataType x);
void printlist(SLTNode*);

//插入
void SLTPushBack(SLTNode**, SLTDataType);
void SLTPushFront(SLTNode**, SLTDataType);


//删除
void SLTPopBack(SLTNode**);
void SLTPopFront(SLTNode**);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//指定位置插入数据
void SLTInsert(SLTNode**, SLTDataType, SLTNode*);
void SLTInsertAfter( SLTDataType, SLTNode*);


//删除指定节点
void SLTErase(SLTNode**, SLTNode*);
void SLTEraseAfter(SLTNode*);

//销毁链表
void SListDestroy(SLTNode**);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

test.c

• 用来测试我们写的函数(函数的调用)
• 这一部分就是自己写的时候用的测试用例，随便什么都行

养成好习惯，写一个方法测试一次，不然找错误的时候会很痛苦