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<stdio.h>#include<stdlib.h>#include<assert.h>

四、函数接口一览

//打印 单链表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头文件里要包含 <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个节点，但是如果*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。

<注意，空链表也可以查找，返回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 置空，防止销毁链表后对链表误操作而导致的野指针问题。