初阶数据结构【单链表及其接口的实现】

1. 链表的概念及结构

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

1. 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续；
2. 现实中的结点一般都是从堆上申请出来的；
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表:

2. 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
![[Pasted image 20261018111027.png|379]]

2.1. 带头或者不带头

1. 带头链表：最前面有一个头节点，称作“哨兵位”，它不存储数据，用来指向第一个存储有效数据的节点；
2. 不带头链表：直接从第一个节点开始，没有额外的头节点。

带头链表

不带头链表

2.2. 单向或者双向

1. 单向链表：每个节点只包含一个指向下一个节点的地址。它只能从前往后遍历，不能从后往前遍历；
2. 双向链表：每个节点包含两个地址，一个指向前一个节点，一个指向后一个节点。它可以从任一节点开始向前或向后遍历。
   

2.3. 循环或者非循环

1. 循环链表：链表的最后一个节点的地址域指向链表的第一个节点，形成一个闭环;
2. 非循环链表：链表的最后一个节点的地址域为空（null），表示链表的结束。
   
   虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

3. 单链表接口实现

我们先定义一个以下的单链表：

typedefintSListDataType;typedefstructSListNode{SListDataType data;structSListNode*next;}SListNode;

使用接口的时候我们将单链表的第一个节点的地址传个接口： 刚开始的时候我们还没有对单链表开辟空间，所以是个空链表，即头指针为NULL

//头指针SListNode*pList=NULL;

3.1. 单链表基本功能接口

3.1.1. 打印输出

为了方便我们进行对其他接口的验证我们先写一个打印单链表的接口：

voidSListPrint(SListNode*phead){//如果这个链表是空链表，那头指针就是指向NULL，所以此处无需加断言SListNode*cur=phead;if(cur==NULL){printf("空链表!");}while(cur!=NULL){printf("%d->",cur->data);cur=cur->next;}printf("NULL\n");}

注：这里可能你会觉得为什么要重新定义一个pcur来遍历，直接用phead不就可以了吗？如果我们用phead来遍历，那等我们下次再来使用phead的时候，就不是链表的头的位置了，所以这里我们将phead给pcur就是为了让phead一直指向我们链表的头；

3.1.2. 空间的开辟接口

我们在实现单链表的增加和插入的时候，我们肯定会开辟一个新的节点，容易让程序冗余，所以我们写一个开辟一个新节点的函数接口，方便后面的使用：

//创造节点函数SListNode*CreateSListNode(SListDataType x){SListNode*newNode=(SListNode*)malloc(sizeof(SListNode));if(newNode==NULL){perror("malloc");exit(-1);}newNode->data=x;//放入数据xnewNode->next=NULL;returnnewNode;}

3.1.3. 单链表销毁

当我们在程序彻底结束的时候要对我们开辟的空间进行一个释放，我们可以使用这个接口： 我们在写这个接口的时候我们要注意：

我们在释放一个节点后，下一个节点的地址就丢失了，所以我们要定义个指针变量cur来存储地址： cur = plist； 先将plist指向下一个节点：plist = plist->next; 再释放cur的空间：free(cur); 最后将cur指向的空间更新为此时的plist

当cur为空的时候全部的节点被释放，结束循环：

voidSListDestroy(SListNode*plist){assert(plist);//防止plist为NULLSListNode*cur=plist;while(cur){plist=plist->next;free(cur);cur=plist;}}

3.2. 单链表的增加节点接口

3.2.1. 单链表的尾插

因为链表不能和顺序表一样直接定位到最后一个元素，我们无法得知最后一个节点的地址，所以我们要进行找尾的操作：

这个时候跳出循环的tail就是最后一个节点的地址；
这个时候我们不难写出下面的代码，但是，如果我们测试在一个空链表执行尾插操作时，我们会发现结果并不如我们所料想的一样；

这是为什么呢？通过调试我们发现：

newNode的确把值赋给了形式参数phead，但是，phead的改变却没有影响实参pList；所以这里我们是“传值调用”，但是有人会说这里的pList不是指向一个结点的地址吗，为什么是传值调用呢？

当我们要修改pList时，尽管pList本来就是指向一个结点的地址，地址本身是一个值，形参只是实参的拷贝，我们如果只传pList，那么改变的只是形参phead，并不会改变外面的实参pList;所以我们要传pList的地址，也就是一个二级指针;

所以我们将pList的地址(&pList)传入函数得到下面的答案：

//尾插voidSListPushBack(SListNode**pphead,SListDataType x){SListNode*newNode=CreateSListNode(x);//如果phead为空if(*pphead==NULL){*pphead=newNode;}else{//找尾SListNode*tail=*pphead;while(tail->next!=NULL){tail=tail->next;}tail->next=newNode;}}

3.2.2. 单链表的头插

我们首先用开辟新节点的接口来开辟一个新节点：newNode：

首先这里我们要注意先后顺序：

我们要先将新节点的next置为第一个节点的地址（即plist）； 再将头指针指向新节点：newNode->next = *pphead; *pphead = newNode;

如果相反，会造成原来的第一个节点地址丢失；

其次，这里我们要对plist的值做修改，同理，我们要传plist的指针才可以达到此效果：

//头插voidSListPushFront(SListNode**pphead,SListDataType x){assert(pphead);SListNode*newNode=CreateSListNode(x);newNode->next=*pphead;*pphead=newNode;}

3.2.3. 单链表在pos后插入接口

//插入（在后面）voidSListInsertAfter(SListNode*pos,SListDataType x){assert(pos);SListNode*newNode=CreateSListNode(x);newNode->next=pos->next;pos->next=newNode;}

3.3. 单链表的删除节点接口

3.3.1. 单链表的尾删

尾删我们要注意在释放最后一个结点后，倒数第二个结点的next如果我们没有将它置空，那它将会变成一个野指针，所以我们必须要将其置空，那我们必须知道倒数第二个结点的地址，才可以修改它的next值，所以我们在找尾操作中要定义一个prev指针总是指向我们找尾指针的前一个结点：

voidSListPopBack(SListNode**pphead){//1.空if(*pphead==NULL){return;}//2.只有一个elseif((*pphead)->next==NULL){free(*pphead);*pphead=NULL;}//3.一个以上else{//定义个指针prev来指向tail指向的节点的前一个节点；SListNode*prev=NULL;SListNode*tail=*pphead;while(tail->next!=NULL){prev=tail;tail=tail->next;}free(tail);prev->next=NULL;}}

3.3.2. 单链表的头删

//头删voidSListPopFront(SListNode**pphead){//1.为空不删if(*pphead==NULL)//防止我们对空指针进行解引用{return;}//2.如果只有1个节点 或 3.有一个以上的节点else{SListNode*next=(*pphead)->next;free(*pphead);*pphead=next;}}

3.3.3. 单链表删除pos后一结点

这个不难写，我们先讲要删除的结点指针记录下来给next方便后面释放，再将pos指向下下一个结点，最后释放要删除的next结点；

//删除pos位置的节点voidSListEraseAfter(SListNode*pos){assert(pos);SListNode*next=pos->next;//下一个节点的地址SListNode*nextnext=next->next;//下下一个节点地址pos->next=nextnext;free(next);}

3.4. 删除pos结点

有了单链表删除pos后一节点做铺垫，我们知道：
想要删除pos结点，我得先找到pos的前一个结点，所以我们先通过遍历来找到pos前一个结点，才可以删除pos结点；

这个时候要考虑到pos为头结点的时候了，这个时候问题就变成头删了；

//删除pos位置的结点voidSListErase(SListNode**pplist,SListNode*pos){assert(pos&&pplist&&*pplist);if(pos==*pplist){SListPopFront(pplist);}else{SListNode*prev=*pplist;while(prev->next!=pos){prev=prev->next;}prev->next=pos->next;free(pos);pos=NULL;}}

3.5. 单链表的修改接口

这个实现比较简单,直接修改对应的值就可以了

//修改pos指向的节点值voidSListUpdata(SListNode*pos,SListDataType x){assert(pos);pos->data=x;}

3.6. 单链表的查找接口

为方便后面的插入接口我们需要找到单链表的某个节点的地址，以方便插入和修改：

我们采取遍历的方式，如果没有此节点，我们返回NULL

SListNode*SListFind(SListNode*plist,SListDataType x){SListNode*cur=plist;while(cur){if(cur->data==x){returncur;}cur=cur->next;}returnNULL;}