系列专栏

list)并且学习了其中一种线性表——顺序表(Sequence

链表顾名思义带着链子的表。

日常生活中我们知道链子是用来链接两个东西的那么我们可以很容易理解顺序表是基于数组实现的是一个元素一个元素挨着的那链表我们就可以理解为每个元素用链子连接起来这样就形成了链表(Linked

1.2

那么我们得到了两个链表的组成的关键元素一个是每个元素我们管它叫节点(或结点)另一个就是那个链子。

而在C语言中我们用结构体来实现节点用指针来充当链连接两个节点。

在生活中链表类似于我们的火车的结构在物理上它是一种存储结构非顺序非连续的结构。

节点的组成主要由两个部分组成一个是数值域用来保存当前节点的数据一个是指针域用来保存下一个节点的地址(指针变量)。

如图所示指针变量plist保存的是第一个节点的地址如果我们想让plist指向第二个节点我们只需要将plist保存的内容修改为0x0012FFD0。

因为之前我们说了链表不同于顺序表它在内存中的地址不一定是连续的它是独立申请的(对其插入数据时才申请一个节点)。

我们需要通过指针才能从当前节点找到下一个节点。

所以我们可以通过一个结构体来实现一个节点它要有一个节点的数据以及一个指针变量来保存下一个节点的地址代码如下

struct

首先我们将节点传到打印函数然后我们创建了一个指向头结点的结构体指针利用循环从头遍历到尾每次打印完成令pcur指向pcur的next节点。

这里注意的就是结构体成员的访问的问题我们用到了-操作符在前面的博客我们都介绍过。

武器大师——操作符详解下-CSDN博客

上面我们知道了什么是链表那单链表又是什么呢单链表(Singly

Linked

(SLTNode*)malloc(sizeof(SLTNode));if

(node

首先我们用malloc函数动态申请一块内存然后将节点的数据赋进去。

void

接下来的代码逻辑特别简单首先我们通过buynode函数创建了一个节点然后我们判空如果这个链表是空的我们直接将指针变量pphead赋为node。

如果不是空的那我们就需要找到链表的尾部我们可以通过循环来找到尾部首先为了防止原来数据被破坏我们创建一个指向第一个节点的指针变量cur而不是直接遍历pphead。

这里还有一个细节就是我们传入的是二级指针因为我们要修改一个数据的话需要传地址而那个数据如果是指针的话我们就需要传指针的地址也就是二级指针。

2.1.2

这个代码逻辑也很简单首先我们assert断言防止访问空指针之后buynode函数申请节点然后将结点接到头部也就是*pphead之后别忘了将*pphead再指向node形成新的头。

2.2

尾删也很简单仔细思考我们只需要两步就能完成一个是找尾一个是删除。

//找尾

首先cur指向头prev指向空cur用来找尾prev用来保存上一个节点的地址。

当cur的下一个位置为NULL时循环结束意味着找到最后一个节点了我们将它所指的位置free掉(因为是动态开辟出来的)然后指针置空即可完成删除。

SLTNode*

tail-next;}free(tail-next);tail-next

NULL;

我们判断条件改成这样实际上我们找的tail是倒数第二个节点所以最后的删除需要改成tail的next为NULL。

2.2.2

头删的逻辑就更加简单了我们只需要创建一个变量来保存原来的头节点方便我们后续删除然后让原头节点移到下一个结点成为新的头结点然后删掉原来的。

如果我们不保存我们没有办法找到原来的头结点。

代码如下

{assert(pphead);assert(*pphead);SLTNode*

first

(*pphead)-next;free(first);first

NULL;

这个实现也很简单就是遍历然后匹配。

由于是查找而不是对数据进行修改所以传一级指针即可。

SLTNode*

将图画出来我们就清晰明了了。

我们如果想把node插入到pos前我们只需要将node的next指向pos然后将prev的next指向node这样就构成了插入操作。

试想一下1和2的操作可以调换顺序吗答案是不可以这是因为如果我们先做2这个时候我们就找不到pos了也就不能执行1操作了。

有人会问我创建两个变量来记录这两个点的位置不可以吗可以但是没必要。

之后我们来看代码部分首先我们要创建一个node节点用buynode函数。

正常情况我们需要找pos的前一个节点prev利用循环即可。

如果只有一个节点怎么办呢这个时候直接头插就可以了。

void

{assert(pphead);assert(pos);SLTNode*

node

x);return;}//找pos的前一个节点SLTNode*

prev

其实逻辑也是很简单的要删除pos的话我们需要找到pos前面的节点保存否则就找不到了。

void

NULL;SLTPopFront(pphead);return;}//找pos的前一个节点SLTNode*

prev

逻辑跟在pos前插入一样也要注意顺序只不过在pos之后插入不需要传链表第一个节点了只需要传pos即可。

void

pos){assert(pos);assert(pos-next);SLTNode

*del

其实看到这你就发现对链表的操作无非就是保存节点然后连接同时画图操作也可以对我们学习数据结构有所帮助。

2.5

我们将链表每个节点通过循环遍历free掉即可唯一比较吃操作的就是创建一个用于保存下一个节点的位置的指针。

//销毁链表