（关于哨兵位结点）

哨兵位结点也叫哑节点。哨兵位结点也是头结点 。该节点不存储有效数据，只是为了方便操作 （如尾插时用带哨兵位的头结点很爽，不需要判空）。

有哨兵位结点的链表，第一个元素应该是链表第二个节点（head -> next，head为哨兵位结点）对应的元素。

有哨兵位结点的链表永不为空 （因为至少有一个结点——哨兵位结点），这样可以避免判断头是否为空，起到简化代码、减少出错的作用。

一、不带哨兵位单链表结点的创建

🚩
下面的自定义类型、函数名里SLT：
来源于单链表的英文：Single Linked List

1.1 typedef 链表的数据类型

typedef 一下链表数据域的数据类型，目的 是如果以后需要改变链表数据类型直接在typedef后改一下即可，否则要在程序中一个个的改，麻烦并且易出错

typedef int SLTDataType;
1

1.2 结点的结构体创建

凡是有多个数据的 → 创建结构体。
数据域： 存储的数据data，类型是SLTDataType。
指针域： 存下一个结点的地址next，类型是结构体指针 struct SListNode*。

typedef struct SListNode//line1
{//line2
SLTDataType data;//数据域//line3
struct SListNode* next;//指针域//line4
}SLTNode;//line5
1
2
3
4
5

🔺 注意：指针域的结构体指针不可以是SLTNode*
编译器的查找规则：编译的时候，如果要用到一个函数或者一个类型，它不会向下查找，只能向上查找。具体来说，SLTNode*在第五行以后才起作用，在第四行的时候还没有定义“SLTNode* ”

二、单链表要实现的功能

1、打印链表：将链表各个结点数据域中的数据按顺序打印出来

2、创建一个新结点：插入一个结点的时候要创建一个新结点，干脆封装成一个函数，后面直接调用即可

3、在链表尾部插入一个数据（尾插）

4、删除链表尾部的结点（尾删）

5、在链表头部插入一个数据（头插）

6、删除链表头部的结点（头删）

7、查找某个结点：返回结点地址

8、删除某个结点

9、单链表中插入结点

10、销毁链表

三、需要包含的头文件

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
1
2
3

四、函数接口一览

//打印 单链表
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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

为什么有些函数参数传递的是二级指针，有些是一级指针？

因为有些函数需要改变传入的结点 。

phead可能为空：链表一开始为空（main()函数中定义SLTNode* phead = NULL），对于插入类的函数，第一次插入时phead为空，那么就要改变phead指向的空间（要在函数中创建一个新结点，phead改变为该结点的地址），即需要改变phead，而phead是一级指针，因为要改变指针需要传递指针的指针——二级指针，即传递指针变量phead的地址——&phead。

但是像打印这样的函数，不需要改变phead，只需要遍历一遍链表，打印出各结点的数据即可，所以传phead（一级指针）就好，不需要二级指针。

五、功能的实现

1）打印单链表

//打印 单链表
void SLTPrint(SLTNode* phead);
1
2

void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;//①
while (cur != NULL)//②
{
printf("%d -> ",cur->data);
cur = cur->next;//③
}
printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

① 这里也可以直接用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
}
1
2
3
4
5
6
7
8
9
10
11
12
13

①动态开辟一个新节点，.h头文件里要包含 <stdlib.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
2
3
4
5
6
7
8
9
10

上面这段代码的前提是，我们已经假定这个链表有>=1个节点，但是如果*pphead为空呢？
如果为空，则只执行：

SLTNode* newnode = BuySLTNode(x);
SLTNode*tail = *pphead;
1
2

初始化：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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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;//④
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

①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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5）头插

按照尾插的路子，可能会这样写：

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuySLTNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

当然没有错，但是仔细想一想，其实没有必要判断*pphead是否为空，因为即使*pphead为空，执行else部分依然没毛病！

化简为：

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}
1
2
3
4
5
6
7

6）头删

头删相比较尾删很简单，因为不需要像尾删一样找tail前一个结点。

头删可以直接删：

void SLPopFront(SLTNode** pphead)
{
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;//临时存一下第二个元素的结点
    free(*pphead);
    *pphead = next;
}
1
2
3
4
5
6
7

7）查找

查找链表中的某个元素，只需遍历一遍链表。返回data == 要查找的元素第一次出现的节点的地址；如果链表中没有要查找的元素，返回NULL。

<注意，空链表也可以查找，返回NULL即可>↓

SLTNode* SLFind(SLTNode* phead, SLDataType x)
{
    SLTNode* cur = phead;
    while (cur)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

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
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

10）销毁

对于销毁链表，如果只free掉 *pphead行么？
当然不行！！

因为单链表由一个一个的结点连接起来的。如果只free(*pphead)，头结点是释放了，但是后面的节点没被释放，还占用着空间但是已经找不到他们的地址了。

所以应该逐个释放👇

void SLDestroy(ListNode** pphead)
{
ListNode* cur = *pphead;
while (cur)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL; //最后别忘了置空
}
1
2
3
4
5
6
7
8
9
10
11

销毁完后 最好把*pphead 置空，防止销毁链表后对链表误操作而导致的野指针问题。