欢迎光临
个人主页：欢迎大家光临——>沙漠下的胡杨
各位大帅哥，大漂亮
如果觉得文章对自己有帮助
可以一键三连支持博主
你的每一分关心都是我坚持的动力
☄： 本期重点 ：数据结构篇单链表实现
希望大家每天都心情愉悦的学习工作。
学数据结构，先学画图，本期和小胡杨一起开始绘画之旅吧！
目录
什么是单链表呢？
链表的实际地址的存放
创建链表
申请结点
链表的尾插
链表的头插
链表的头删：
链表的尾删
查找链表元素：
修改链表元素
在链表任意位置后插
在链表任意位置前插
在链表任意位置后删
删除链表的任意位置
链表的打印
链表空间释放
关于整体的代码头文件篇：
关于整体代码源文件：
什么是单链表呢？
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
类似于向一条链串联起来的一样。
链表的实际地址的存放
链表我们一般的图示为下面的样子：
实际上我们要看链表的实际地址存放：
代码如下：
这是单链表的实际存放的地址
创建链表
首先我们要先创建链表，用结构体创建这就不在多说啦，关于这个头文件定义结构体细节处理都在代码中了。 结构体有不明白的请移步☞结构体详解
申请结点
我们有链表了，但是我们还没有链表的组成成员呀！所以我们要申请结点，什么时候需要申请结点呢？那肯定是选择插入就会需要结点啊，所以我们不妨写函数是就直接申请结点，并附上数据，指针我们可以默认指向为NULL。
看下代码：
我们可以直接要把要赋给的值传给函数，然后开辟一个结点的空间，进行断言，判断是否申请到了空间，接着把要赋给的值给data，把结点指针的指向NULL。
链表的尾插
首先我们先想一下传什么参数呢？
首先是要插入的值，那么是传链表的地址，还是直接传链表呢？如果链表为NULL呢？
我们先看一个示意图：
我们已经有啦一个结点，并且已经放好值了，那么怎么操作呢？我们只需要把d3中的next的NULL指向新开辟的结点，是不是就可以啦！接着看图：
变为这个样子就可以啦。（最重要的是plist没有改变）
可是如果我们的链表没有元素呢？接着看图：
此时的plist是为NULL，那我们直接吧plist指向 d 的地址就好呀，并且只有一个 d 刚好d的下一个结点为NULL。（注意：plist已经由空指针变为了指向新节点 d 了）
看下代码（很多人都会错误的示范）：
这样写的话有没有一点点的不妥呢？
我们调试下，发现plist没有变，链表没有插入，接着看图：
我们得出了一个结论：
不是传指针，就可以改变这个指针的指向的，我们应该传二级指针的形式，然后解引用，达到改变plist地址的效果，所以我们链表所有的插入 和 删除函数都传二级指针，传二级指针时，我们使用头结点只要解引用就好了。
所以正确的代码为：
其他的都没有改变，只是把用链表头的地方，改为解引用链表头。
链表的头插
头插我们依然要考虑这个问题就是 plist 是否改变呢？
这是肯定的，头插就是换个头呀！就是链表的头被改变了，所以我们要传地址。
我们接着看个图来理解下：
这是刚开始的情况，我们要把 plist 的地址放入新结点，并且把plist改为新结点的地址。
下面我们接着看图示：
我们是没有plist，但是我们有 pphead，直接解引用就是头结点。
需要注意的点：
必须要先进行步骤一，再进行步骤二，否则，我们的头结点就被覆盖了，然后就找不到以后的节点啦，所以我们一定要先执行步骤一，在执行步骤二。
下图是先执行步骤二，在执行步骤一的后果（死循环）：
下面是正确的代码：
链表的头删：
链表的头删很简单，我们还是传递二级指针，因为如果就一个结点，删除后变为了NULL，此时链表的指向还是发生了变换。
看下面图示：
我们只需要把原来头结点的指向第二个结点，然后把原来头结点free掉就可以啦。
需要注意的是：
我们要先创建一个结点指针，保存第二个结点的地址
然后我们要释放原来的头指针（*pphead）
接着把保存第二个结点的地址赋值给 *pphead，让它成为新的链表的头指针。
如果刚好是一个结点，也是可以的，因为*pphead的下个结点为NULL
我们先把NULL存起来，然后把 *pphead 这个结点 free掉
再把NULL放到*pphead中，就变为NULL了，符合条件。
下面是代码：
链表的尾删
链表的尾删我们要考虑的就要多点，如果有一个结点，和有多个结点分开分析
还是先看图：
如果是这种情况，就直接free掉，然后置为NULL就好了。
这种情况就要把d3这个结点 free掉，然后把 d2 结点的指向NULL就好了。
那我们怎么找到 d2 呢？接着看图：
这就是我们写代码的实际逻辑啦，下面是代码，代码中的注释部分是第二种办法，通过访问两次下一个指针的指向：
查找链表元素：
查找就很简单了，我们直接暴力查找就好啦：
看下代码：
需要注意的地方：
首先，我们要先保存头指针，不要改变头指针。
其次，我们要考虑代码的健壮性，并且配合其他的函数接口使用，所以我们返回值设定为结点指针。如果找不到，我们就返回NULL。
修改链表元素
修改就可以配合查找一起使用也很简单，直接看代码吧：
我们可以通过查找到的下标，进行修改，没啥说的。
在链表任意位置后插
在链表任意位置后插入，首先我们应该找该位置，然后进行插入。
先看图：
这个插入位置我们已知，然后我们只需要改变指向就可以啦，接着看图：
我们要注意的是先进行步骤一，在进行步骤二，顺序一定不能反，否则就和头插一样死循环了。
下面是具体的代码：
在链表任意位置前插
在链表任意位置后插，这个比较复杂啦。下面看图一点点的分析：
首先如果只有一个结点，那就相当于头插了
和头插一样，不在赘述啦~
如果有多个结点，就复杂啦~ 我们先看图吧：
我们怎么知道这个位置前一个的结点值呢？方法其实和尾删一样，使用一个变量遍历，循环结束的条件变为 p1->next != 这个位置 。
看下图：
最后看下代码：
在链表任意位置后删
删除任意位置比较简单，我们只需要注意一点，
就是链表元素为1时，就没有后续啦，就不能删除啦。
还是看下图吧：
只有一个结点，不能删除后面的元素，其他的，直接覆盖，然后free掉pos位置的结点
我们直接看代码吧：
删除链表的任意位置
这个又点麻烦，我们一点点分析：
首先如果这个位置在链表的头上，那么我们就是头删，
还是看图：
如果在其他位置删除，和任意位置前插一样，我们要创建一个指针结点，进行遍历，循环结束的条件是 p1->next != pos,然后把断裂的链表链接就好啦。
接着看图吧：
下面是代码：
链表的打印
打印可以不用传链表地址，我们不会修改链表内容，还有一点就是创建临时变量来遍历。
看代码吧：
链表空间释放
这个没说的，还是要传链表的地址，因为我们要把链表置为NULL
直接看代码吧：
关于整体的代码头文件篇：
- #pragma once
-
- #define _CRT_SECURE_NO_WARNINGS
-
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
-
- typedef int SLTDataType;
-
- typedef struct SListNode
- {
- SLTDataType data;
- struct SListNode *next;
- }SLTNode;
-
- void SListPrint(SLTNode* pphead);//打印
-
- SLTNode* BuySListNode(SLTDataType x);//申请新节点
-
- void SListPushBack(SLTNode **pphead, SLTDataType x);//尾插
-
- void SListPushFrond(SLTNode **pphead, SLTDataType x);//头插
-
- void SListPopFrond(SLTNode **pphead);//头删
-
- void SListPopBack(SLTNode **pphead);//尾删
-
- SLTNode* SListFind(SLTNode *pphead, SLTDataType x);//查找
-
- void SListInsertBefore(SLTNode **pphead, SLTNode *pos, SLTDataType x);//任意位置前插
-
- void SListInsertAfter(SLTNode *pos, SLTDataType x);//任意位置后插
-
- void SListErase(SLTNode **pphead, SLTNode *pos);//删除任意位置
-
- void SListEraseAfter(SLTNode *pos);//任意位置后删
-
- void SListDestroy(SLTNode **pphead);//释放链表
-
- void SListModify(SLTNode *pos, SLTDataType x);//修改链表
关于整体代码源文件：
- #include "SList.h"
-
- void SListPrint(SLTNode* pphead)
- {
- SLTNode* cur = pphead;
- while (cur)
- {
- printf("%d->", cur->data);
- cur = cur->next;
- }
- printf("NULL\n");
- }
-
- SLTNode* BuySListNode(SLTDataType x)
- {
- SLTNode* newnode = (SLTNode *)malloc(sizeof(SLTNode));
- assert(newnode);
- newnode->next = NULL;
- newnode->data = x;
-
- return newnode;
- }
-
-
- void SListPushBack(SLTNode **pphead, SLTDataType x)
- {
- SLTNode* newnode = BuySListNode(x);
-
- if (*pphead == NULL)
- {
- *pphead = newnode;
- }
- else
- {
- SLTNode* cur = *pphead;
- while (cur->next)
- {
- cur = cur->next;
- }
- cur->next = newnode;
- }
- }
-
- void SListPushFrond(SLTNode **pphead, SLTDataType x)
- {
- SLTNode* newnode = BuySListNode(x);
- newnode->next = *pphead;
- *pphead = newnode;
- }
-
- void SListPopBack(SLTNode **pphead)
- {
- assert(*pphead);
-
- if ((*pphead)->next == NULL)
- {
- free(*pphead);
- *pphead = NULL;
- }
- else
- {
- //方法二
- //SLTNode *cur = *pphead;
- //while (cur->next->next != NULL)
- //{
- //cur = cur->next;
- //}
- //free(cur->next);
- //cur->next = NULL;
- SLTNode *tail = *pphead;
- SLTNode *tailprev = NULL;
- while (tail->next != NULL)
- {
- tailprev = tail;
- tail = tail->next;
- }
- free(tail);
- tailprev->next = NULL;
- }
- }
-
-
- void SListPopFrond(SLTNode **pphead)
- {
- assert(pphead);
- SLTNode* next = (*pphead)->next;
- free(*pphead);
- *pphead = next;
- }
-
-
- SLTNode* SListFind(SLTNode *pphead, SLTDataType x)
- {
- SLTNode* cur = pphead;
- while (cur)
- {
- if (cur->data == x)
- {
- return cur;
- }
- cur = cur->next;
- }
-
- return NULL;
- }
-
- void SListInsertBefore(SLTNode **pphead, SLTNode *pos, SLTDataType x)
- {
- assert(pos);
-
- if (pos == *pphead)
- {
- SListPushFrond(pphead, x);
- }
- else
- {
- SLTNode *prve = *pphead;
- while (prve->next != pos)
- {
- prve = prve->next;
- }
- SLTNode* newnode = BuySListNode(x);
- newnode->next = pos;
- prve->next = newnode;
- }
- }
-
- void SListInsertAfter(SLTNode *pos, SLTDataType x)
- {
- assert(pos);
-
- SLTNode* newnode = BuySListNode(x);//注意下面代码的位置
- newnode->next = pos->next;
- pos->next = newnode;
- }
-
- void SListErase(SLTNode **pphead, SLTNode *pos)
- {
- assert(pphead);
- assert(pos);
-
- if (*pphead == pos)
- {
- SListPopFrond(pphead);
- }
- else
- {
- SLTNode *prve = *pphead;
- while (prve->next != pos)
- {
- prve = prve->next;
- }
- prve->next = pos->next;
- free(pos);
- pos = NULL;
- }
- }
-
- void SListEraseAfter(SLTNode *pos)
- {
- assert(pos);
- SLTNode *next = pos->next;
- if (next)
- {
- pos->next = next->next;
- free(next);
- next = NULL;
- }
- }
-
- void SListDestroy(SLTNode **pphead)
- {
- assert(pphead);
-
- SLTNode *cur = *pphead;
- while (cur)
- {
- SLTNode *next = cur->next;
- free(cur);
- cur = next;
- }
-
- *pphead = NULL;
- }
-
- void SListModify(SLTNode *pos, SLTDataType x)
- {
- assert(pos);
-
- pos->data = x;
- }
———————————————————————————————————————————
