B.最简单结构的链表——不带哨兵位单链表的实现
- （关于哨兵位结点）
- 一、不带哨兵位单链表结点的创建
- 1.1 typedef 链表的数据类型
- 1.2 结点的结构体创建
- 二、单链表要实现的功能
- 三、需要包含的头文件
- 四、函数接口一览
- 为什么有些函数参数传递的是二级指针，有些是一级指针？
- 五、功能的实现
- 1）打印单链表
- 2）创建新节点
- 3）尾插
- 4）尾删
- 5）头插
- 6）头删
- 7）查找
- 8）删除
- 9）插入结点
- 10）销毁
（关于哨兵位结点）
哨兵位结点也叫哑节点。哨兵位结点也是头结点 。该节点不存储有效数据，只是为了方便操作 （如尾插时用带哨兵位的头结点很爽，不需要判空）。
有哨兵位结点的链表，第一个元素应该是链表第二个节点（head -> next，head为哨兵位结点）对应的元素。
有哨兵位结点的链表永不为空 （因为至少有一个结点——哨兵位结点），这样可以避免判断头是否为空，起到简化代码、减少出错的作用。
一、不带哨兵位单链表结点的创建
下面的自定义类型、函数名里SLT：
来源于单链表的英文：Single Linked List
1.1 typedef 链表的数据类型
typedef 一下链表数据域的数据类型，目的 是如果以后需要改变链表数据类型直接在typedef后改一下即可，否则要在程序中一个个的改，麻烦并且易出错
typedef int SLTDataType;1.2 结点的结构体创建
凡是有多个数据的 → 创建结构体。
数据域： 存储的数据data，类型是SLTDataType。
指针域： 存下一个结点的地址next，类型是结构体指针 struct SListNode*。
typedef struct SListNode//line1{//line2SLTDataType data;//数据域//line3struct SListNode* next;//指针域//line4}SLTNode;//line5 注意：指针域的结构体指针不可以是SLTNode*
编译器的查找规则：编译的时候，如果要用到一个函数或者一个类型，它不会向下查找，只能向上查找。具体来说，SLTNode*在第五行以后才起作用，在第四行的时候还没有定义“SLTNode* ”
二、单链表要实现的功能
1、打印链表：将链表各个结点数据域中的数据按顺序打印出来
2、创建一个新结点：插入一个结点的时候要创建一个新结点，干脆封装成一个函数，后面直接调用即可
3、在链表尾部插入一个数据（尾插）
4、删除链表尾部的结点（尾删）
5、在链表头部插入一个数据（头插）
6、删除链表头部的结点（头删）
7、查找某个结点：返回结点地址
8、删除某个结点
9、单链表中插入结点
10、销毁链表
三、需要包含的头文件
#include#include#include四、函数接口一览
//打印 单链表void SLTPrint(SLTNode* phead);//动态申请一个节点SLTNode* BuySLTNode(SLTDataType x);//尾插（并给节点中的data赋值）void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾删void SLTPopBack(SLTNode** pphead);//头插（并给节点中的data赋值）void SLTPushFront(SLTNode** pphead, SLTDataType x);//头删void SLTPopFront(SLTNode** pphead);//查找并返回结点地址SLTNode* SLFind(SLTNode* phead, SLDataType x);//删除某个结点void SLErase(SLTNode** pphead, SLTNode* pos);//pos前 插入结点void SLInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);//销毁void SLDestroy(SLTNode** pphead);为什么有些函数参数传递的是二级指针，有些是一级指针？
因为有些函数需要改变传入的结点 。
phead可能为空：链表一开始为空（main()函数中定义SLTNode* phead = NULL），对于插入类的函数，第一次插入时phead为空，那么就要改变phead指向的空间（要在函数中创建一个新结点，phead改变为该结点的地址），即需要改变phead，而phead是一级指针，因为要改变指针需要传递指针的指针——二级指针，即传递指针变量phead的地址——&phead。
但是像打印这样的函数，不需要改变phead，只需要遍历一遍链表，打印出各结点的数据即可，所以传phead（一级指针）就好，不需要二级指针。
五、功能的实现
1）打印单链表
//打印 单链表void SLTPrint(SLTNode* phead);void SLTPrint(SLTNode* phead){SLTNode* cur = phead;//①while (cur != NULL)//②{printf("%d -> ",cur->data);cur = cur->next;//③}printf("NULL\n");}① 这里也可以直接用phead进行循环，但是像这样创建一个 “当前节点” （cur源自单词current）会比较“美观”。（But 如果这个函数内部后面还需要用头节点的话就不能直接用phead，否则会找不到头）
② 控制结束的条件
③ 遍历
2）创建新节点
链表的结点：按需分配，随用随创
链表的头插、尾插（只要是插入）都需要创建一个新节点，然后插到对应位置。所以我们可以直接把“创建新节点”封装成一个函数，以便后面直接调用：
SLTNode* BuySLTNode(SLTDataType x){SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//①if(newnode == NULL)//②{perror("malloc newnode fail: ");return;}//③给新节点赋值newnode->x;newnode->next = NULL;return newnode;//别忘了返回newnode}①动态开辟一个新节点，.h头文件里要包含
②判断开辟是否成功，如果不成功则输出错误并返回
③给新节点的数据域赋值，指针域赋为空：NULL，这样做的好处是： 不需要最后对链表尾结点的指针域置空。
3）尾插
在链表尾部插入一个节点
先看这段代码：
void SLTPushBack(SLTNode** pphead, SLTDataType x);{SLTNode* newnode = BuySLTNode(x);SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}上面这段代码的前提是，我们已经假定这个链表有>=1个节点，但是如果*pphead为空呢？
如果为空，则只执行：
SLTNode* newnode = BuySLTNode(x);SLTNode*tail = *pphead;初始化：SLTNode* phead = NULL;
传参： SLTPushBack(&phead, x);）
当phead为NULL时，也就不存在tail->next了
所以切记要先判断*pphead是否为空：
void SLTPushBack(SLTNode** pphead, SLTDataType x){SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;//找原链表的尾结点while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}
4）尾删
尾删比较麻烦，因为要判断链表是否为空以及分情况讨论结点个数。
先看这段代码：
void SLTPopBack(SLTNode** pphead){assert(pphead && *pphead);//①SLTNode* tail, * tailpre;//②tail = *pphead->next;tailpre = *pphead;while (tail->next){tail = tail->next;tailpre = tailpre->next;}free(tail);//③tailpre->next = NULL;//④}①pphead（二级指针）和*pphead绝对不可以为空，最好断言一下
②定义tail和tail前一个结点tailpre，目的是释放tail后，直接得到新的尾结点，方便置空
③没必要再把tail置空：tail = NULL;因为tail是局部变量，函数结束就自动销毁了
④释放后，新的尾结点的next置空
看似没什么毛病·······
但是，上面没有考虑只有一个结点的情况！！
⚡如果只有一个结点， tail = *pphead->next;后，tail为NULL，下面的执行就出大问题了
解决办法是判断一下：
void SLTPopBack(SLTNode** pphead){assert(pphead && *pphead);if ((*pphead)->next == NULL)//只有一个结点{free(*pphead);*pphead = NULL;}else//>=2个结点{SLTNode* tail, * tailpre;tail = *pphead->next;tailpre = *pphead;while (tail->next){tail = tail->next;tailpre = tailpre->next;}free(tail);tailpre->next = NULL;}}5）头插
按照尾插的路子，可能会这样写：
void SLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{newnode->next = *pphead;*pphead = newnode;}}当然没有错，但是仔细想一想，其实没有必要判断*pphead是否为空，因为即使*pphead为空，执行else部分依然没毛病！
化简为：
void SLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;}6）头删
头删相比较尾删很简单，因为不需要像尾删一样找tail前一个结点。
头删可以直接删：
void SLPopFront(SLTNode** pphead){assert(pphead && *pphead);SLTNode* next = (*pphead)->next;//临时存一下第二个元素的结点free(*pphead);*pphead = next;}7）查找
查找链表中的某个元素，只需遍历一遍链表。返回data == 要查找的元素第一次出现的节点的地址；如果链表中没有要查找的元素，返回NULL。
↓
SLTNode* SLFind(SLTNode* phead, SLDataType x){SLTNode* cur = phead;while (cur){if (cur->data == x)return cur;cur = cur->next;}return NULL;}8）删除
分两种情况：链表只有一个节点、链表有多个节点。
1、只有一个节点：如果*pphead == pos，相当于头删，直接调用前面的函数即可。
2、有多个节点：遍历链表，直到找到地址为pos的结点，按照尾删的思路，删除即可。
void SLErase(SLTNode** pphead, SLTNode* pos){assert(pphead && *pphead && pos);//都不能为空if (*pphead == pos){SLPopFront(pphead);}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}SLTNode* next = cur->next->next;cur->next = next;free(pos);//一定要free}}9）插入结点
在pos前插入：
void SLInsert(SLTNode** pphead, SLTNode* pos, SLDataType x){assert(pphead && pos);if (pos == *pphead){SLPushFront(pphead, x);}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}SLTNode* insnode = BuyNode(x);cur->next = insnode;insnode->next = pos;}}10）销毁
对于销毁链表，如果只free掉 *pphead行么？
当然不行！！
因为单链表由一个一个的结点连接起来的。如果只free(*pphead)，头结点是释放了，但是后面的节点没被释放，还占用着空间但是已经找不到他们的地址了。
所以应该逐个释放
void SLDestroy(ListNode** pphead){ListNode* cur = *pphead;while (cur){ListNode* next = cur->next;free(cur);cur = next;}*pphead = NULL; //最后别忘了置空}销毁完后 最好把*pphead 置空，防止销毁链表后对链表误操作而导致的野指针问题。