作者：一个喜欢猫咪的的程序员
专栏：《数据结构》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
前言：
单链表是一种链式存取的 数据结构 ，用一组地址任意的 存储单元 存放线性表中的数据元素。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素 的映象) + 指针 (指示后继元素 存储 位置)，元素就是存储数据的存储单元，指针就是连接每个结点的 地址 数据。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素 的映象) + 指针 (指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作 线性链表 （单链表），单链表是链式存取的结构。 链接方式存储的线性表简称为链表（Linked List）。 ② 链表中结点的逻辑次序和物理次序不一定相同。
单链表的结构和形成：
将一个结构体包含两个部分，一个是数据，一个是与本身结构体同类型的结构体指针
typedef int SLDataType; ct SListNode {//单链表 SLDataType data;//数据 struct SListNode* next;//指向下一个与本结构体相同的结构体变量的指针 }SLTNode;
这样就可以在结构体指针找到下一个结构体的位置，第一个指针找到了第二个结构体，第二个结构体指针找到第三个结构体，以此类推....这样就形成了一个链表。
逻辑结构：
但计算机实际上并没有指向的箭头啊，我们可以通过指针指向下一个结构体的地址来实现！
物理结构（从计算机角度）：
BuySLTNode（创建结构体）：
我们是动态开辟malloc结构体，malloc函数可能会异地扩、本地扩或者NULL，因此我们需要判断malloc返回值是否为空！以及我们需要把地址传回去，防止异地扩后，地址不同！
对于malloc函数不熟悉的同学可以看看我的另外一篇博客：对动态内存开辟有详细解释
言归正传。我们来看一下这个函数如何实现：
SLTNode* BuySLTNode(SLDataType x) {//创建结构体 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
CreateSList部分（n个结构体形成链表）：
我们这种情况是通过写4个语句来将这4个结构体穿起来，那如果我们要n个结构体形成链表呢？
我们结合一个图，来想想怎么把图中代码的能力实现，并实现n个呢？ n个结构体相连，所以肯定是for循环，利用BuyTNode创建动态结构体，我们再将下一个结构体的地址传给结构体的next指针以此类推.....
SLTNode* CreateSList(int n) {//将n个结构体形成链表 SLTNode* phead = NULL; SLTNode* plist = NULL; for (int i = 0; i < n; i++) { SLTNode* newnode = BuySLTNode(i); if (plist == NULL) { phead = plist = newnode; } else { plist->next = newnode; plist = newnode; } } return phead; } v
因为使用BuySLTNode创建结构体时，next都为NULL。
plist.next=newnode来形成链表，我们这边有一个矛盾，当第一个结构体时，并没有第二个来赋值，我们可以这样：plist=newnode，这样的时候当newnode为第二个结构体的地址的时候就不为NULL，就会将第二个结构体赋值给第一个结构体的next指针将之前的覆盖。
PrintSList（打印单链表）：
我们利用一个while循环遍历一遍打印就好。
void* PrintSList(SLTNode* phead) {//打印链表 SLTNode* cur = phead; while (cur!= NULL) //如果这里是cur->next != NULL的话，会少一个值，因为cur->next==NULL时，cur->data有值的，它的下一个结构体才没有值 { printf("[%d|%p]->", cur->data,cur->next); cur = cur->next;//这里如果想要直接cur->next=...的话有点困难 } printf("NULL"); }
如果这里是cur->next != NULL的话，会少一个值，因为cur->next==NULL时，cur->data有值的，它的下一个结构体才没有值
单链表的功能实现（增删查改）：
SLTPushBack尾插部分:
当plist不为NULL时：
我们尾插要先找尾部，即NULL的地方。然后将newnode插到null后面就好了。
我们来看下面这个尾插是否有错？
可能很多人觉得这样没有问题，但实际上是错的！！！
- tail为NULL和tail->next为NULL对于循环条件来说是不一样的。
- tail为NULL代表没有这个结构体，就下图4个结构体为例：当tail指向第4个结构体时，循环不会结束，tail下一个会指向NULL。当循环停止的时候，tail已经指向了NULL，而第四个结构体的next还是指向空，即使我们插进去一个结构体，也会在第四个结构体的时候next到NULL，相当于没有插入！
- tail->next为NULL代表没有下一个结构体了，这样tail->next=newnode就会将之前的尾部结构体和新加入的结构体连接起来形成链表！
当循环条件为tail.next！=NULL时：
void SLTPushBack(SLTNode* phead, SLDataType x) {//尾插 //assert(phead);//这里不需要断言，空链表也可以尾插 SLTNode* newnode = BuySLTNode(x); SLTNode* tail = phead; while (tail->next) { tail = tail->next; } tail->next = newnode; }
当plist为NULL时：
这个是我在plist为NULL时运行结果的截图：
这里错误是由指针传参导致的！
你一定很疑惑把我明明把指针传过去，传地址不是可以改变原来的值吗?没有错啊.
我们先来复习一下：
- 你的老师一定跟你说函数在传值调用时，形参不可以改变实参
！
- 传址调用才可以改变实参！
这是没有错的，但是它是相对而言的。
- 指针本质是一个地址，我们所说的指针的值是一个地址，而不是这个地址指向的值。
- NULL为空指针，NULL=0x0000000000（这是一个地址）。
我们要改变NULL这个指针的时候，注意：我们这里说要改变这个指针是指我们要改变这个地址（0x00000000），而不是这个地址的值。
那我们这里的 SLTNode* phead是不是相当于上图int a。
因此我们要改变NULL这个指针，我们需要传SLTNode**pphead进去，那我们*pphead就可以改变NULL的值了！
void SLTPushBack(SLTNode** pphead, SLDataType x) {//尾插 //assert(phead);//这里不需要断言，空链表也可以尾插 SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = newnode; } }
