在之前的顺序表专题中我们了解了顺序表的结构，知道了顺序表的底层是数组，以及学习了如何实现顺序表的增、删、查、改等功能。但顺序表中也是存在一些结构上的不足的，当我们实现顺序表的插入与删除时一些方法内需要将整个顺序表都移动一位，这就使得代价的效率受到影响，同时在顺序表中开辟新空间的时候有可能是需要将顺序表内的内容再重新拷贝一份的；这也使得代码的运行效率受到影响，并且在顺序表中增加顺序表的空间我们是以二倍来增加的；这势必会有⼀定的空间浪费。

所以以上的分析表明顺序表是存在较大的缺陷的，那么是否有更好的方式实现顺序表相同的功能呢？答案是有的，就是链表，本篇就将解析链表的结构是什么样的；以及如何实现链表让其也能实现数据的增、删、查、改，接下来就开始链表的学习吧！

 

 

---

1.链表的概念及结构

 1.1链表的概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 

同时链表也是线性表，链表在逻辑结构上是连续的，但在物理结构上链表不是连续的

 

 1.2链表的结构 

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉加上，不会影响其他车厢，每节车厢都是独立存在的。

 

车厢是独立存在的，且每节⻋厢都有车门。假设每节⻋厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？

最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。 

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”，那么在链表中每个节点的“钥匙”是什么呢？

其实就是下一个节点的的地址（指针变量），链表中每个节点都是独立申请的（即需要插入数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。通过下一个节点的地址就可以对下一个节点进行相关操作了

例如以下链表

图中指针变量 plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。 

 

在之前我们学习过结构体，在此要实现链表的结构代码就需要用到结构体，定义一个结构体struct SListNode来表示结构体的节点，同时在结构体中定义一个整型变量data来表示节点中存放的数据信息，再定义一个结构体指针来存放下一个节点的地址

<code>typedef int SLDateType;//将int重命名，方便之后要修改数据类型时修改

typedef struct SListNode//将结构体重命名，简化结构体的名称

{

SLDateType date;//节点内数据

struct SListNode* next;//下一个节点的指针

}SLTNode;

 

 2.单链表的实现

 2.1程序文件的设置

 

在实现单链表中是将程序分为以下三个文件

注：在SList.h中在文件的头部写入以下代码中要使用到的库函数的头文件

 

 2.2 展示单链表

要实现单链表的打印在屏幕上，首先就需要在SList.h内完成打印单链表函数的声明 ，在此将该函数命名为SLPrint，函数的参数就是结构体指针，同时该函数无返回值

<code>void SLTPrint(SLTNode* phead);//打印链表

之后要在SList.c内完成打印函数的实现就先要分析如何来实现单链表的打印

例如以下单链表的图示，一开始phead是指向第一个节点，要使得该指针指向下一个节点就要将指针phead重新赋值为该节点中存放的下一个节点的指针，也就是phead=phead->next。

在此之后phead就指向下一个节点了，一直重复以上操作就可以将每个节点都遍历一遍，那么在什么时候结束遍历呢？

就是当phead指向的节点为NULL时，就将单链表中全部节点都遍历一遍了

分析了如何来实现单链表的打印后就可以在SList.c内完成函数SLTPrint的实现

<code>void SLTPrint(SLTNode* phead)//打印链表

{

SLTNode* pcur = phead;

while (pcur)

{

printf("%d -> ", pcur->date);

pcur = pcur->next;

}

printf("NULL\n");

}

 

2.3 在链表中查找指定数据 

 

要实现一个函数能查找在单链表中是否存在要查找的数据，首先就要在SList.h内声明该函数

SLTNode* SLTFind(SLTNode* phead, SLDateType x);//在链表中查找指定数据

将该函数命名为SLFind，函数的参数有两个，一个是单链表首节点的指针，第二个参数是要查找的数据，函数的返回类型就为SLTNode*，即结构体指针类型

在此之后就是在SList.c内完成函数的实现 

SLTNode* SLTFind(SLTNode* phead, SLDateType x)//在链表中查找指定数据

{

SLTNode* pcur = phead;

while (pcur)

{

if (pcur->date == x)

{

return pcur;

}

pcur = pcur->next;

}

return NULL;

}

以上函数通过遍历的方法来查找指定的数据，如果在单链表中找到了就返回相应节点的指针，若在遍历完还未找到相应的数据就返回NULL 

编写完查找的函数就在test.c内测试是否能正常运行

 

#include "SList.h"

int main()

{

SLTNode* plist = NULL;

SLTPushBack(&plist, 1);

SLTPushBack(&plist, 2);

SLTPushBack(&plist, 3);

SLTNode*p=SLTFind(plist, 1);

if (p == NULL)

{

printf("找不到该数据\n");

}

else

{

printf("找到了\n");

}

return 0;

}

通过输出结果表明编写的查找函数没问题 

 

 

2.4单链表各功能的实现

 

2.4.1尾插 

例如以下的单链表中要将新节点插入到尾部要实现什么样的操作呢？

首先要创建一个新的节点，并将要插入的数据存放到新节点中，之后再将链表的末尾与新的节点连接，也就是要使得节点4的next指针指向新的节点

首先要在SList.h中对尾插函数进行声明

<code>void SLTPushBack(SLTNode* phead, SLDateType x);//尾插

 在此将尾插函数命名为SLPushFront，函数的参数有两个，一个是结构体指针指向单链表的第一个节点，第二个参数是要尾插到单链表中的变量，同时该函数无返回值

 

之后就是在SList.c内完成SLPushBack函数的实现

在该函数内要实现的是创建一个新的节点，也就是新创建一个结构，在此之后再找到原链表的尾节点，也就是最后一个结构体，之后将最后一个节点内的next指针指向新的节点

之前在打印链表的代码中我们实现了遍历链表

SLTNode* pcur = phead;

while (pcur)

{

pcur = pcur->next;

}

但以上的代码最后的指针pcur指向NULL，这和以上要找到链表的尾节点不符合，那么要对以上代码做出什么样的更改才能在循环后使得pcur指向链表的最后一个节点呢？ 

其实这时就只需要把循环的判断部分修改为(pcur->next)就可以了，这是因为pcur->next在while循环的判断部分就等价于(pcur->next！=NULL)，也就是当节点的next指针不等于NULL就进入循环，等于NULL就跳出循环，因为原链表的最后一个节点next等于NULL，此时再循环判断时就为假就跳出循环，之后pcur就指向尾节点

在找到原链表的尾节点后就是将要插入的数据存储到新节点，这时就需要先新创建一个节点

因为之后的头插，任意位置的插入都要创建新的节点，所以我们就创建一个函数来实现新节点的创建，该函数的参数就是要插入的数据，在开辟新节点成功后将新节点的next指针置为NULL，函数的返回值类型为SLTNode结构体指针，返回值就是指向新开辟的内存空间的指针

 

SLTNode* NewNode(SLDateType x)//为新节点开辟内存空间并将数据存储到节点内

{

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

if (newnode == NULL)//若开辟失败就在屏幕上显示错误信息，且退出函数

{

perror("newnode");

exit(1);

}

newnode->date = x;

newnode->next = NULL;

return newnode;

}

之后就将原链表的末尾连接上新创建的节点，就实现了单链表的尾插

void SLTPushBack(SLTNode* phead, SLDateType x)//尾插

{

SLTNode* newnode = NewNode(x);

SLTNode* ptail = phead;

while (ptail->next)

{

ptail = ptail->next;

}

ptail->next = newnode;

}

但以上代码还存在问题，问题是如果原链表内没有节点，也就是phead一开始就置为NULL时，因为ptail->next一直不为NULL，所以函数的while循环部分就会出现死循环 

所以就需要将以上函数就需要使用一个if...else语句，在phead为NULL时，直接将phead=newnode

否则就进入else部分，也就是进入以上的部分

<code>void SLTPushBack(SLTNode* phead, SLDateType x)//尾插

{

SLTNode* newnode = NewNode(x);

if (phead == NULL)

{

phead = newnode;

}

else

{

SLTNode* ptail = phead;

while (ptail->next)

{

ptail = ptail->next;

}

ptail->next = newnode;

}

}

编写完尾插的代码后就要在test.c内测试是否能正常运行

#include"SList.h"

void test1()

{

SLTNode* plist = NULL；

SLTPushBack(plist, 1);

SLTPushBack(plist, 2);

SLTPushBack(plist, 3);

SLTPrint(plist);

}

int main()

{

test1();

return 0;

}

在以上测试时就出现问题了，以上代码的输出结果为NULL，说明三次尾插都没有成功，这时为什么呢？

 

我们来调试看看，在调试时就可以看到当代码在SLTPushBack(plist,1)的末尾已经完成尾插，但是出了函数后的plist依然是指向NULL，这就是因为函数SLTPushBack进行的是传值调用， 传的是节点的指针，所以在函数内对形参的修改不会影响实参，因此指针plist依旧指向NULL

所以我们就要对以上代码进行修改了，让函数变为传址调用，这就要让函数的参数传的是地址，这样就在修改形参时就是在修改实参

在SList.h内修改函数的声明：

<code>void SLTPushBack(SLTNode** pphead, SLDateType x);//尾插

在SList.c内修改函数的实现： 

void SLTPushBack(SLTNode** pphead, SLDateType x)//尾插

{

assert(pphead);

SLTNode* newnode = NewNode(x);

if (*pphead == NULL)

{

*pphead = newnode;

}

else

{

SLTNode* ptail = *pphead;

while (ptail->next)

{

ptail = ptail->next;

}

ptail->next = newnode;

}

}

注：在以上代码中pphead不能为NULL，因此要加上assert断言 

以下图示就表示出了以上代码中的pphead等的实际意义 

 

 

2.4.2头插 

例如以下的单链表中要将新节点插入到头部要实现什么样的操作呢？

 

首先要创建一个新的节点，并将要插入的数据存放到新节点中，之后再将新节点与链表的第一个节点连接，也就是要使得新的节点的next指针指向节点1

首先要在SList.h中对头插函数进行声明

<code>void SLTPushFront(SLTNode** pphead, SLDateType x);//头插

将该函数命名为SLTPushFront，因为头插时依然要对参数进行修改，所以该函数还是要进行传址调用，也就是参数要是变量的地址，该函数的参数有两个，一个是节点指针的地址，另一个是要插入的数据

例如以下链表一开始*pphead指向节点1，之后创建的新节点newnode，之后让newnode->next=*pphead,之后再让*pphead=newnode就可以让该指针指向新的节点

通过以上的实例就可以来完成头插函数的实现 

<code>void SLTPushFront(SLTNode** pphead, SLDateType x)//头插

{

assert(pphead);

SLTNode* newnode = NewNode(x);

newnode->next = *pphead;

*pphead = newnode;

}

编写完头插的代码后就要在test.c内测试是否能正常运行 

#include"SList.h"

void test2()

{

SLTNode* plist = NULL；

SLTPushFront(&plist, 1);

SLTPushFront(&plist, 2);

SLTPrint(plist);

}

int main()

{

test2();

return 0;

}

运行就发现能正常打印出

 

 

2.4.3尾删 

例如以下的单链表中要将尾部的节点删除要实现什么样的操作呢？

首先要将节点4删除，也就是将节点4的内存空间释放，同时还要将节点3中的next指针不再指向节点4，也就是将该指针next置为NULL 

首先要在SList.h中对尾删函数进行声明

<code>void SLTPopBack(SLTNode** pphead);//尾删

将该函数命名为SLTPopBack，因为尾删时要对参数进行修改，所以该函数还是要进行传址调用，也就是参数要是变量的地址，该函数的参数是节点指针的地址

例如以下链表一开始*pphead指向节点1，之后要删除ptail所指向的节点，并且让prev节点内的prev指针指向NULL

所以在尾删代码中也可以像以上一样，用ptail指针来指向链表的尾节点，prev指针指向链表的尾节点的前一个节点

在尾删时节点的指针不能为NULL，因此还要对*pphead进行assert断言

并且当链表内只有一个节点时，会找不到ptail会找不到尾节点，所以就需要使用一个if...else语句，在*phead->next为NULL时，直接将free(*pphead)

以下就是在SList.c内完成SLTPopBack函数的实现

<code>void SLTPopBack(SLTNode** pphead)//尾删

{

assert(pphead && *pphead);

if ((*pphead)->next == NULL)

{

free(*pphead);

*pphead = NULL;

}

else

{

SLTNode* ptail = *pphead;

SLTNode* prev = *pphead;

while (ptail->next)

{

prev = ptail;

ptail = ptail->next;

}

free(ptail);

ptail = NULL;

prev->next = NULL;

}

}

 编写完尾删的代码后就要在test.c内测试是否能正常运行 

#include"SList.h"

void test3()

{

SLTNode* plist = NULL；

SLTPushBack(&plist, 1);

SLTPushBack(&plist, 2);

SLTPushBack(&plist, 3);

SLTPrint(plist);

SLTPopBack(&plist);

SLTPrint(plist);

}

int main()

{

test3();

return 0;

}

运行就发现能正常打印出 

 

 

 

 2.4.4头删

 例如以下的单链表中要将头部的节点删除要实现什么样的操作呢？

 

 要将节点1删除，也就是将节点1的内存空间释放

 

 首先要在SList.h中对头删函数进行声明

<code>void SLTPopFront(SLTNode** pphead);//头删

 将该函数命名为SLTPopFront，因为头删时要对参数进行修改，所以该函数还是要进行传址调用，也就是参数要是变量的地址，该函数的参数是节点指针的地址

例如以下链表一开始*pphead指向节点1，之后要删除*pphead所指向的节点，这就先要创建一个指针变量next保存*pphead的下一个节点的指针，在销毁*pphead指向的节点后，之后让*pphead指向next指向的节点

 

 

以下就是在SList.c内完成SLTPopFront函数的实现

在头删时节点的指针不能为NULL，因此还要对*pphead进行assert断言

<code>void SLTPopFront(SLTNode** pphead)//头删

{

assert(pphead && *pphead);

SLTNode* next = (*pphead)->next;

free(*pphead);

*pphead = next;

}

 编写完头删的代码后就要在test.c内测试是否能正常运行 

#include"SList.h"

void test4()

{

SLTNode* plist = NULL；

SLTPushBack(&plist, 1);

SLTPushBack(&plist, 2);

SLTPushBack(&plist, 3);

SLTPrint(plist);

SLTPopFront(&plist);

SLTPrint(plist);

}

int main()

{

test4();

return 0;

}

运行就发现能正常打印出  

 

 

 2.4.5在指定位置前插入

例如以下的单链表中要新节点插入到节点3之前将要实现什么样的操作呢？

首先要创建一个新的节点，并将要插入的数据存放到新节点中，之后再将链表的节点2与新的节点连接；链表的节点3与新的节点连接，也就是要使得节点2的next指针指向新的节点；新的节点的next指针指向节点3

首先要在SList.h中对在指定位置前插入函数进行声明  

<code>void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDateType x);//在指定位置之前插入

将该函数命名为SLTInsert，因为插入时要对参数进行修改，所以该函数还是要进行传址调用，也就是参数要是变量的地址，函数的参数有三个，一个是结构体指针指向单链表的第一个节点，第二个参数是要插入位置的指针，第三个参数是要尾插到单链表中的变量，同时该函数无返回值

 

例如以下链表pos指针指向节点3，首先创建一个指针prev指向pos指针指向的节点之前的节点 ，将prev内的next指向新节点，再使得newnode指向的新节点的next指针指向pos指针指向的节点，这就完成了在节点3前插新节点

 以下就是在SList.c内完成SLTInsert函数的实现

在指定位置插入函数中，pphead不能指向NULL，同时如果*pphead为空的话，那么pos参数在调用的时候就无法确定其的值，所以*pphead也不能指向NULL，因此要给pphead和*pphead都assert断言。并且pos也不能指向NULL，所以给pos也进行assert断言

在pos就是链表的头节点时，就找不到pos之前的节点，所以要使用一个if...else语句将情况分类，在pos等于*pphead时候就直接调用头插函数，其他情况时就进入else语句

<code>void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDateType x)//在指定位置前面插入

{

assert(pphead && *pphead);

assert(pos);

SLTNode* newnode = NewNode(x);

if (pos == *pphead)

{

SLTPushFront(pphead, x);

}

else

{

SLTNode* prev = *pphead;

while (prev->next!=pos)

{

prev = prev->next;

}

newnode->next = pos;

prev->next = newnode;

}

}

 编写完指定前位置的插入的代码后就要在test.c内测试是否能正常运行 

#include"SList.h"

void test5()

{

SLTNode* plist = NULL；

SLTPushBack(&plist, 1);

SLTPushBack(&plist, 2);

SLTPushBack(&plist, 3);

SLTPrint(plist);

SLTNode*p=SLTFind(plist, 1);

SLTInsert(&plist, p, 4);

SLTPrint(plist);

}

int main()

{

test5();

return 0;

}

 通过输出结果表明编写的在指定位置之前插入函数没问题 

 

 

2.4.6在指定位置后插入 

例如以下的单链表中要新节点插入到节点2之后将要实现什么样的操作呢？

首先要创建一个新的节点，并将要插入的数据存放到新节点中，之后再将链表的节点2与新的节点连接；链表的节点3与新的节点连接，也就是要使得节点2的next指针指向新的节点；新的节点的next指针指向节点3

                                                                                                          

首先要在SList.h中对在指定位置后插入函数进行声明 

<code>void SLTInsertAfter(SLTNode* pos, SLDateType x);// 在指定位置后插入

将该函数命名为SLTInsrtAfter，函数的参数有两个，第一个是参数是要插入位置的指针，第二个参数是要尾插到单链表中的变量，同时该函数无返回值

例如以下链表pos指针指向节点2，首先新创建一个节点并让newnode指向它，之后让新节点的next指针指向pos->next，再让pos指向的节点的next指针指向新节点，这就完成了在节点3后插新节点

  以下就是在SList.c内完成SLTInsertAfter函数的实现

pos也不能指向NULL，所以进行pos也assert断言

同时在代码内newnode->next = pos->next和pos->next = newnode的位置不能交换，否则就会使得newnode->next=newnode

<code>void SLTInsertAfter(SLTNode* pos, SLDateType x)//在指定位置之后插入

{

assert(pos);

SLTNode* newnode = NewNode(x);

newnode->next = pos->next;

pos->next = newnode;

}

编写完指定后位置的插入的代码后就要在test.c内测试是否能正常运行  

#include"SList.h"

void test6()

{

SLTNode* plist = NULL；

SLTPushBack(&plist, 1);

SLTPushBack(&plist, 2);

SLTPushBack(&plist, 3);

SLTPrint(plist);

SLTNode*p=SLTFind(plist, 1);

SLTInsertAfter(p, 5);

SLTPrint(plist);

}

int main()

{

test6();

return 0;

}

 运行就发现能正常打印出  

 

2.4.7删除指定位置

 例如以下的单链表中删除节点3要实现什么样的操作呢？

要删除节点3就只需要将节点2中的next指针指向节点4，再将节点3的内存空间释放

 

 首先要在SList.h中对删除指定位置函数进行声明 

<code>void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos位置的节点

将该函数命名为SLTErase，函数的参数有两个，第一个是结构体指针指向单链表的第一个节点，第二个参数是要删除位置的指针，同时该函数无返回值

 

例如以下链表一开始*pphead指向节点1，之后要删除pos所指向的节点，这就要先找到pos之前的节点，也就是指针prev指向的节点，之后让prev指向的节点的next指针指向pos->next节点，在此之后再释放pos节点

 以下就是在SList.c内完成SLTErase函数的实现

在删除时节点的指针不能为NULL，因此还要对*pphead进行assert断言

pos也不能指向NULL，所以进行pos也assert断言

并且当链表内头节点就为pos指向的节点时，会找不到prev会找不到尾节点，所以就需要使用一个if...else语句，在*pphead等于pos时，直接调用头删函数，其他情况时就进入else语句

<code>void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置的节点

{

assert(pphead && *pphead);

assert(pos);

if (*pphead == pos)

{

SLTPopFront(pphead);

}

else

{

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

prev->next = pos->next;

free(pos);

pos = NULL;

}

}

 编写完删除指定位置的代码后就要在test.c内测试是否能正常运行

#include"SList.h"

void test7()

{

SLTNode* plist = NULL；

SLTPushBack(&plist, 1);

SLTPushBack(&plist, 2);

SLTPushBack(&plist, 3);

SLTPrint(plist);

SLTNode*p=SLTFind(plist, 2);

SLTErase(&plist, p);

SLTPrint(plist);

int main()

{

test7();

return 0;

}

 运行就发现能正常打印出  

 

2.4.8 删除指定位置之后的节点 

 例如以下的单链表中删除节点2之后的节点要实现什么样的操作呢？

要删除节点2之后的节点就只需要将节点3之前的节点中的next指针指向节点4，再将节点3的内存空间释放

  首先要在SList.h中对删除指定位置之后的节点函数进行声明 

<code>void SLTEraseAfter(SLTNode* pos);//删除pos之后的节点

将函数命名为SLTEraseAfter，函数的参数就为要删除位置之前节点的指针

 

例如以下链表pos指向节点2，要删除pos所指向的节点之后的节点，这就要先将pos指向的节点的next指针指向pos->next->next节点，在此之后再释放pos->next节点

  以下就是在SList.c内完成SLTEraseAfter函数的实现

首先指针pos指向的节点和pos指向的下一个节点都不能为空，所以要对pos和pos->next都进行assert断言

在此之后定义一个指针变量del指向pos指向节点之后的节点，这样就不会使用到pos->next->next这样的代码，会让代码简洁很多

<code>void SLTEraseAfter(SLTNode* pos)//删除pos之后的节点

{

assert(pos && pos->next);

SLTNode* del = pos->next;

pos->next = del->next;

free(del);

del = NULL;

}

编写完删除指定位置之后的节点的代码后就要在test.c内测试是否能正常运行

#include"SList.h"

void test8()

{

SLTNode* plist = NULL；

SLTPushBack(&plist, 1);

SLTPushBack(&plist, 2);

SLTPushBack(&plist, 3);

SLTPrint(plist);

SLTNode*p=SLTFind(plist, 1);

SLTEraseAfter(p);

SLTPrint(plist);

int main()

{

test8();

return 0;

}

 运行就发现能正常打印出  

 

2.5销毁单链表 

在之前我们完成了单链表中的各种功能，最后就要来学习如何销毁单链表 

  

首先要在SList.h中对销毁单链表函数进行声明 

<code>void SLTNodeDestory(SLTNode** pphead);//销毁链表

将该函数命名为SLTDestory，函数的参数就是要销毁的单链表的头节点指针的地址

 

以下就是在SList.c内完成SLTDestory函数的实现

首先指针*pphead和pphead都不能为空，所以要对*pphead和pphead都进行assert断言

使用遍历链表的方法来销毁链表，最后遍历完后将所有节点的空间释放后再将指针*pphea置为NULL

void SLTNodeDestory(SLTNode** pphead)//销毁链表

{

assert(pphead && *pphead);

SLTNode* pcur = *pphead;

SLTNode* next = *pphead;

while (pcur)

{

next = pcur->next;

free(pcur);

pcur = next;

}

*pphead = NULL;

}

#include"SList.h"

void test()

{

SLTNode* plist = NULL；

SLTPushBack(&plist, 1);

SLTPushBack(&plist, 2);

SLTPushBack(&plist, 3);

SLTNodeDestory(&plist);

SLTPrint(plist);

}

int main()

{

test();

return 0;

}

通过调试来检验销毁的代码是否正确

调试后通过SLTDestory函数后plist为NULL，说明销毁函数没问题

 

 

 

 3.单链表完整代码

 

SList.h

 

<code>#pragma once

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

#include<stdlib.h>

#include<assert.h>

typedef int SLDateType;

typedef struct SListNode

{

SLDateType date;//节点内数据

struct SListNode* next;//下一个节点的指针

}SLTNode;

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

SLTNode* SLTFind(SLTNode* phead, SLDateType x);//在链表中查找指定数据

void SLTPushFront(SLTNode** pphead, SLDateType x);//头插

void SLTPushBack(SLTNode** pphead, SLDateType x);//尾插

void SLTPopBack(SLTNode** pphead);//尾删

void SLTPopFront(SLTNode** pphead);//头删

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDateType x);//在指定位置之前插入

void SLTInsertAfter(SLTNode* pos, SLDateType x);// 在指定位置后插入

void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos位置的节点

void SLTEraseAfter(SLTNode* pos);//删除pos之后的节点

void SLTNodeDestory(SLTNode** pphead);//销毁链表

 SList.c

#include "SList.h"

void SLTPrint(SLTNode* phead)//打印链表

{

SLTNode* pcur = phead;

while (pcur)

{

printf("%d -> ", pcur->date);

pcur = pcur->next;

}

printf("NULL\n");

}

SLTNode* SLTFind(SLTNode* phead, SLDateType x)//在链表中查找指定数据

{

SLTNode* pcur = phead;

while (pcur)

{

if (pcur->date == x)

{

return pcur;

}

pcur = pcur->next;

}

return NULL;

}

SLTNode* NewNode(SLDateType x)//为新节点开辟内存空间并将数据存储到节点内

{

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

if (newnode == NULL)

{

perror("newnode");

exit(1);

}

newnode->date = x;

newnode->next = NULL;

return newnode;

}

void SLTPushBack(SLTNode** pphead, SLDateType x)//尾插

{

assert(pphead);

SLTNode* newnode = NewNode(x);

if (*pphead == NULL)

{

*pphead = newnode;

}

else

{

SLTNode* ptail = *pphead;

while (ptail->next)

{

ptail = ptail->next;

}

ptail->next = newnode;

}

}

void SLTPushFront(SLTNode** pphead, SLDateType x)//头插

{

assert(pphead);

SLTNode* newnode = NewNode(x);

newnode->next = *pphead;

*pphead = newnode;

}

void SLTPopBack(SLTNode** pphead)//尾删

{

assert(pphead && *pphead);

if ((*pphead)->next == NULL)

{

free(*pphead);

*pphead = NULL;

}

else

{

SLTNode* ptail = *pphead;

SLTNode* prev = *pphead;

while (ptail->next)

{

prev = ptail;

ptail = ptail->next;

}

free(ptail);

ptail = NULL;

prev->next = NULL;

}

}

void SLTPopFront(SLTNode** pphead)//头删

{

assert(pphead && *pphead);

SLTNode* next = (*pphead)->next;

free(*pphead);

*pphead = next;

}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDateType x)//在指定位置前面插入

{

assert(pphead && *pphead);

assert(pos);

SLTNode* newnode = NewNode(x);

if (pos == *pphead)

{

SLTPushFront(pphead, x);

}

else

{

SLTNode* prev = *pphead;

while (prev->next!=pos)

{

prev = prev->next;

}

newnode->next = pos;

prev->next = newnode;

}

}

void SLTInsertAfter(SLTNode* pos, SLDateType x)//在指定位置之后插入

{

assert(pos);

SLTNode* newnode = NewNode(x);

newnode->next = pos->next;

pos->next = newnode;

}

void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置的节点

{

assert(pphead && *pphead);

assert(pos);

if (*pphead == pos)

{

SLTPopFront(pphead);

}

else

{

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

prev->next = pos->next;

free(pos);

pos = NULL;

}

}

void SLTEraseAfter(SLTNode* pos)//删除pos之后的节点

{

assert(pos && pos->next);

SLTNode* del = pos->next;

pos->next = del->next;

free(del);

del = NULL;

}

void SLTNodeDestory(SLTNode** pphead)//销毁链表

{

assert(pphead && *pphead);

SLTNode* pcur = *pphead;

SLTNode* next = *pphead;

while (pcur)

{

next = pcur->next;

free(pcur);

pcur = next;

}

*pphead = NULL;

}

 

 

以上就是单链表专题的所有内容了，之后还会继续带来单链表的应用、双链表等的讲解，感谢你的支持，希望能得到你的点赞、收藏！