数据结构初阶|初阶数据结构——线性表——链表——不带头单向链表数据结构|c语言|算法|链表

想快速入门数据结构，推荐订阅作者的初阶数据结构专栏！此专栏预计更新：顺序表，链表，栈，队列，二叉树，排序算法等等

初阶数据结构我们通过c语言实现，所以此专栏也可以帮助大家巩固大家的c语言知识

知识回顾
在前一章中我们已经介绍了顺序表，相信大家对顺序表的实现已经有所了解了吧！
但是，这种数据结构，难免会有以下的缺陷

我们在中间位置插入或删除数据的话，可能需要挪动后面的所有数据，时间复杂度较高==(O(n))==
我们的空间是按照2倍的常数开辟的，可能会造成空间的浪费，比如我们的顺序表从100扩容到200，但我们只需要插入5个数据，剩下的195单位空间就被浪费了
增容过程也会造成资源的消耗

为了克服以上的缺陷，我们设计出了另外一种线性数据结构——链表
之所以叫它线性表，是因为它的逻辑结构是连续的，仍然满足线性表的特征
但它在物理结构上未必是关联的，连续的
在物理结构上非连续的话，我们可以利用地址，形成元素之间的相互联系
它的定义仍然是一个结构体,每个结构体，就是链表中的一个结点

struct ListNode { int data; //存放元素 struct ListNode* next; //存放下一个元素的地址，以此来链接元素 };

文章图片

文章图片

这种数据结构，它的空间就是按需申请的，没有任何空间的浪费，用多少申请多少
直接申请一个结点就行了
但却仍然不可避免的有缺陷：不支持随机访问(下标访问)
查找的时间复杂度为O(n)
实际中链表的实现方式有很多种，今天为大家介绍其中的一种，不带头的单向链表

后面会更新带头循环链表，敬请期待！

还是从增删查改来介绍链表怎么定义

目录

单链表定义
- 头文件定义
- 初始化
单链表插入
- 开辟结点
- 尾部插入
- 头部插入
- 任意位置插入(前面)
- 任意位置插入(后面)
单链表删除
- 尾部删除
- 头删
- 任意位置删除(当前位置)
- 任意位置删除(后面)
查找函数
其它函数

单链表定义头文件定义定义的方法，以及至于为什么这样定义已经在前一期说过了，不懂的小伙伴可以看我这篇关于顺序表的文章.里面关于顺序表的定义，很多都是相通的

//Slist.h #include #include #includetypedef int SLTDataType; //方便存储各种各样的数据typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; //重命名，简化后面代码的编写

初始化链表的初始化比较简单，在main函数中可以直接这样初始化

SLTNode* plist=NULL;

单链表插入开辟结点我们同样利用动态内存管理开辟空间
初始化方式:data为你需要插入的数据，next指向NULL
函数返回一个结构体类型

SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (!newnode) {printf("fail\n"); exit(-1); } newnode->data = https://www.it610.com/article/x; newnode->next = NULL; return newnode; }

尾部插入假设我们有下面的链表

文章图片

由于我们的链表不支持随机访问，所以不能直接找到尾部元素
我们也只能定义一个变量来遍历，然后直到某一个结点的next指向NULL

文章图片

所以我们可以写出以下的代码

void SListPushBack(SLTNode* phead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); SLTNode* cur = phead; while (cur->next) {cur = cur->next; } cur->next = newnode; }

这里的cur=cur->next需要另外解释一下
可以直接用物理图来解释

文章图片

但是，这个代码却有一个问题,我们可以尝试使用一下
使用示例：

SLTNode* plist=NULL; SListPushBack(plist,1);

但是程序却崩溃了

文章图片

原因其实是这样：
在我们初始化的时候plist设置的为空
所以当我们在空链表尾插的时候，将会崩溃，因为函数的参数是相对于指针变量的传值调用，并不会改变外部的链表仍然为空
而我们对地址进行传址调用时，就需要传一个二级指针进去
所以，最终代码如下

void SListPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); if (!(*pphead)) {*pphead = newnode; }//加上一个空指针判断 else {SLTNode* cur = *pphead; while (cur->next) {cur = cur->next; } cur->next = newnode; } }

正确使用示例

void Test1() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); }

效果图

文章图片

头部插入与尾部插入相似，这里不再做详细阐述，解释在代码里面

void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; //将新结点链接到原来的头结点 *pphead = newnode; //将新结点作为新的头结点 }

任意位置插入(前面) 这里需要的查找函数在本文的偏后位置，大家也可以点击目录直接定位
这里我们需要三个参数，分别是：
头结点的地址，插入位置**（需要查找函数定位）**，插入数字

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

以下是查找的思路，(假如在3的前面插入)
同样需要cur变量来寻找你传入的位置

文章图片

我们需要检查cur->next是不是我们需要的位置
下图中，cur->next就是pos位置

文章图片

然后开始malloc新结点，开始链接

文章图片

同理，这里如果为空指针会出现问题
但在这里，1个结点也会出现问题！
因为这里的cur和pos会指向相同位置
代码处理完将会这样

文章图片

所以我们仍然要加入特殊情况的处理方式

void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x) { if (pos == *pphead) {SListPushFront(pphead, x); } else {SLTNode* newnode = BuySListNode(x); SLTNode* cur = *pphead; while (cur->next != pos) {cur = cur->next; } newnode->next = pos; cur->next = newnode; }}

任意位置插入(后面) 任意位置后面的插入要简单的多，从参数都能看出来，少了一个

void SListInsertAfter(SLTNode* pos, SLTDataType x);

主要原因是因为我们的链表，在知道一个结点后，是可以找到下一个元素的
而前面的元素却找不到(只针对单链表)
过程（还是以3举例）

文章图片

特别声明！！！
这里的操作顺序不能颠倒，因为如果先改变pos->next的话，真正的next结点就不能够找到了

void SListInsertAfter(SLTNode* pos, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; }

单链表删除删除的实现，有一种情况就是对空链表进行删除操作
在这里我们不用这么墨迹，直接用粗暴的方法，直接assert断言！
尾部删除同样，需要一个tail指针，寻找链表的尾部元素
我们这里的结束条件是tail->next->next,也就是找到倒数第二个元素

文章图片

但是有一个只有一个元素尾删的问题
这里的tail->next->next就是对空指针的解引用，就会报错
【数据结构初阶|初阶数据结构——线性表——链表——不带头单向链表】我们同样需要加入特殊情况的讨论

void SListPopBack(SLTNode** pphead) { assert(*pphead); if (!((*pphead)->next)) {free(*pphead); *pphead = NULL; } else {SLTNode* tail = *pphead; while (tail->next->next) {tail = tail->next; } free(tail->next); tail->next = NULL; } }

头删头删就没那么多讲究了，直接上代码

void SListPopFront(SLTNode** pphead) { assert(*pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }

任意位置删除(当前位置) 这些函数直接开始上图

文章图片

void SListErase(SLTNode** pphead, SLTNode* pos) { assert(*pphead); if (pos == *pphead) {SListPopFront(pphead); } else {SLTNode* cur = *pphead; while (cur->next != pos) {cur = cur->next; } cur->next = pos->next; free(pos); } }

任意位置删除(后面)

文章图片

void SListEraseAfter(SLTNode* pos) { assert(pos->next); SLTNode* next = pos->next; pos->next = next->next; free(next); }

查找函数这里有两种实现方式，它们的返回值不同
一个返回链表的位置int型
一个直接返回此链表结点
本文采用后者实现
仍然使用暴力求解法

SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) {if (cur->data =https://www.it610.com/article/= x) {return cur; } cur = cur->next; } return NULL; }

使用方法
为插入，删除函数指示位置
使用示例：

void Test5() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPrint(plist); SLTNode* pos1 = SListFind(plist, 3); SListInsertAfter(pos1, 6); }//在3的后面插入一个6

如果有重复元素的链表怎么办？例如

1 1 1 1 1 2 3 4

使用方法先进行初始化，找到第一个结点的位置，利用循环，去访问

pos=SListFind(plist,1); //初始化 while(pos) { pos=SListFind(plist,1); //迭代过程 //你需要的其它操作 }

其它函数打印函数

void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) {printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }

销毁函数

void SListDestory(SLTNode** pphead) { assert(*pphead); SLTNode* cur = *pphead; SLTNode* next = NULL; while (cur) {next = cur->next; free(cur); cur = next; } *pphead = NULL; }