数据结构-单链表-详解-1
1.前言
在数据结构-顺序表-详解中，我详细介绍了顺序表的实现，而顺序表也有一些缺点：
- 中间，头部插入时，需整体挪动数据，效率低下。
- 空间不够时扩容，有一定的消耗，也可能有一定空间浪费。
为了解决这些问题，引入了链表这一数据结构：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表中，一个数据存入一个内存块，通过指针相连。这种结构使得插入和删除操作变得高效，因为只需要更新指针即可完成这些操作，而无需移动数据本身。
在功能上，顺序表与链表互补，相辅相成。
链表有很多种：
- 单向或双向
- 带头或不带
- 循环或非循环
今天讲单链表。
与实现顺序表时类似，为了更好地组织代码，单链表在实现时建议放入三个文件中：
| SList.h | SList.c | test.c |
|---|---|---|
| 头文件 | 源文件 | 测试文件 |
| 引用头文件，函数声明，宏定义，结构体定义 | 具体的函数实现 | 验证功能是否正确 |
.c文件都只需引用SeqList.h，可避免头文件的重复引用。
注：引用自建的头文件使用双引号：#include "SList.h"
关于命名：
SList中的S指single。
本文其他命名方式与顺序表一致，不再赘述。
2.结点
单链表一个内存块中需存储一个数据和一个指针。
对于多种类型的数据，使用结构体存储，在链表中，将这样的结构体称为结点。
SList.h：
typedef int SLTDataType;
typedef struct SLTNode
{
SLTDataType data;
struct SLTNode* next;
}SListNode;
这段代码定义了一个名为SListNode的结构体类型，用于表示单链表中的结点。
每个结点包含一个数据成员data和一个指向下一个结点的指针next。
需注意，关于next的定义，以下两种写法是错误的：
SLTNode* next;
SListNode* next;
第一种写法，在C语言中属于类型不完整。
第二种写法，在还没typedef时不能使用重定义类型。
3.打印
SList.h：
void SListPrint(SListNode* phead);
SList.c：
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
这段代码定义了一个名为SListPrint的函数，它接受一个指向链表头结点的指针作为参数。通过遍历链表，依次打印出每个结点的数据，最后输出NULL来表示链表的结尾。
其中，cur != NULL，即cur非0，为真。
可简化为：while(cur)
3.1关于断言
在顺序表中，函数的第一行一定是assert断言，而链表中有时不需要断言，为什么？
- 顺序表中，传入函数的指针指向的是结构体，结构体存在内存的一块空间中，有具体地址；并且，顺序表为不为空，取决于结构体中
size的大小，因此，指针不能为NULL，需要断言。 - 单链表中，指向头结点的是指针，链表为空时指针可以为
NULL，因此有时不需要断言。
3.2下一结点的找法
错误写法：
cur++;
++可以找下一个位置吗？可以，但只能用在连续存放的情况下，如顺序表。
链表是非连续存放的，可以通过画图来理解：
物理结构
画出了实实在在数据内存中的变化，能帮助彻底理解。
逻辑结构
为了便于理解，形象化画出来的。
因此，使用cur = cur->next，可将下一结点的地址赋值给cur指针。
通过以上的介绍和代码实现，我们不仅了解了单链表的基本概念，还掌握了如何创建和打印单链表。希望这些内容能帮助你更好地理解单链表，并激发你进一步探索数据结构的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！