一、引文
从数据结构初阶之顺序表的介绍与动态顺序表的实现-CSDN博客中我们知道了动态顺序表并且实现了动态顺序表,但是对于动态顺序表存在以下几个不足:
(1)中间 / 头部的插入删除操作时间复杂度为 O (N);
(2)扩容需要申请新空间,拷贝旧数据,释放旧空间,这一系列操作会有不小的消耗。(扩容一般是呈 2 倍的增长,这势必会导致一定的空间浪费。比如当前容量为 100,满了以后会扩容到 200,我们再继续插入了 5 个数据,后面没有数据插入了,那么就浪费了 95 个数据空间)
那么该如何解决这些问题呢?接下来我们介绍单链表就很好地解决上述问题,正文启:
二、链表的概念和结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的逻辑结构一定是线性的,物理结构不一定是线性的。
1、结点
与顺序表不同的是,链表里的每块部分都是独立申请下来的空间,我们称之为 “结点 / 节点”。
结点的组成主要有两个部分:
(1)当前结点要保存的数据;
(2)保存下一个结点的地址(指针变量)。
图中指针变量 plist 保存的是第一个结点的地址,我们称 plist 此时 “指向” 第一个结点,如果我们希望 plist “指向” 第二个结点时,只需要修改 plist 保存的内容为第二个结点的地址即可。
链表中每个结点都是独立申请的(即需要插入数据时才去申请一块结点的空间),我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。
2、链表的性质
(1)链式机构在逻辑上是连续的,在物理结构上不一定连续;
(2)结点一般是从堆上申请的空间;
(3)从堆上申请来的空间,是按照一定策略分配出来的,每次申请的空间可能连续,可能不连续。
三、单链表的实现
项目创建的时候,要创建一个头文件(.h)SList.h ,两个源文件(.c)SList.c ,test.c 。SList.h 用于定义结构体和声明函数;SList.c 用于实现函数;test.c 用于测试函数,每实现一个函数要进行相应的测试。编写代码过程中要勤测试,避免写出大量代码后再测试,如果出现问题,问题无从定位。
1、SList.h:
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义单链表(结点)结构体
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//声明打印链表的函数
void Print_SList(SLTNode* phead);
//声明创建一个结点的函数
SLTNode* Create_SListNode(SLTDataType x);
//声明尾插一个结点到单链表的函数
void Push_Back_SList(SLTNode** pphead, SLTDataType x);
//声明头插一个结点到单链表的函数
void Push_Front_SList(SLTNode** pphead, SLTDataType x);
//声明尾删单链表的一个结点的函数
void Pop_Back_SList(SLTNode** pphead);
//声明头删单链表的一个结点的函数
void Pop_Front_SList(SLTNode** pphead);
//声明查找指定结点的函数
SLTNode* Find_SList(SLTNode* phead, SLTDataType x);
//声明在指定位置之前插入数据的函数
void Insert_Front_SList(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//声明在指定位置之后插入数据的函数
void Insert_Back_SList(SLTNode* pos, SLTDataType x);
//声明删除指定结点的函数
void Del_SList(SLTNode** pphead, SLTNode* pos);
//声明删除pos之后的结点的函数
void Del_Back_SList(SLTNode* pos);
//声明销毁链表的函数
void Destroy_SList(SLTNode** pphead);
2、SList.c:
#include"SList.h"
//实现打印链表的函数
void Print_SList(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur != NULL)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//实现创建一个结点的函数
SLTNode* Create_SListNode(SLTDataType x)
{
//动态申请一个结点的空间
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//申请失败直接退出
if (!newnode)
{
perror("malloc fail");
exit(1);
}
//申请成功将新节点的data赋值为x,并将next置为NULL
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//实现尾插一个结点到单链表的函数
void Push_Back_SList(SLTNode** pphead, SLTDataType x)
{
//pphead不能为NULL,即Push_Back_SList(NULL, x)不被允许
assert(pphead);
//先申请一个新的结点
SLTNode* newnode = Create_SListNode(x);
//如果链表为空,则新的结点就是头结点
if (*pphead == NULL)
{
*pphead = newnode;
}
//如果链表不为空,就先找到尾结点,再把尾结点和新节点链接起来
else
{
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}
//实现头插一个结点到单链表的函数
void Push_Front_SList(SLTNode** pphead, SLTDataType x)
{
//pphead不能为NULL,即Push_Front_SList(NULL, x)不被允许
assert(pphead);
//先申请一个新的结点
SLTNode* newnode = Create_SListNode(x);
//使新节点的next指向头结点
newnode->next = *pphead;
//更新头结点为新的结点
*pphead = newnode;
}
//实现尾删单链表的一个结点的函数
void Pop_Back_SList(SLTNode** pphead)
{
//pphead不能为NULL,即Pop_Back_SList(NULL)不被允许;*pphead不能为空,即不能对空链表进行尾删
assert(pphead && *pphead);
//尾删的结点正好是头结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
// 尾删的结点不是头结点
else
{
//定义一个prev指针负责找到尾结点的前驱结点,ptail负责找到尾结点
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
//实现头删单链表的一个结点的函数
void Pop_Front_SList(SLTNode** pphead)
{
//pphead不能为NULL,即Pop_Front_SList(NULL)不被允许;*pphead不能为空,即不能对空链表进行尾删
assert(pphead && *pphead);
//pcur来记住头结点的地址
SLTNode* pcur = *pphead;
//让头结点移动到下一个节点处
*pphead = (*pphead)->next;
free(pcur);
pcur = NULL;
}
//实现查找指定结点的函数
SLTNode* Find_SList(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//实现在指定位置之前插入结点的函数
void Insert_Front_SList(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
//pphead不能为NULL,即Insert_Front_SList(NULL, pos,x)不被允许;pos不能为NULL
assert(pphead && pos);
//如果pos就是头结点,就是头插
if (pos == *pphead)
{
Push_Front_SList(pphead, x);
}
//pos不是头结点
else
{
//创建一个新节点
SLTNode* newnode = Create_SListNode(x);
//ptail找pos的前驱结点
SLTNode* ptail = *pphead;
while (ptail->next != pos)
{
ptail = ptail->next;
}
newnode->next = pos;
ptail->next = newnode;
}
}
//实现在指定位置之后插入数据的函数
void Insert_Back_SList(SLTNode* pos, SLTDataType x)
{
//pphead不能为NULL,即Insert_Back_SList(NULL, pos,x)不被允许;pos不能为NULL
assert(pos);
//创建一个新节点
SLTNode* newnode = Create_SListNode(x);
//下面两行不能交换位置,如果交换位置 ptail->next = newnode->next; 先使ptail->next指向newnode,再执行 newnode->next = ptail->next; newnode会指向它本身
newnode->next = pos->next;
pos->next = newnode;
}
//实现删除指定结点的函数
void Del_SList(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos);
//要删除的pos就是头结点,就是头删
if (pos == *pphead)
{
Pop_Front_SList(pphead);
}
//要删除的pos不是头结点
else
{
SLTNode* ptail = *pphead;
while (ptail->next != pos)
{
ptail = ptail->next;
}
ptail->next = pos->next;
free(pos);
pos = NULL;
}
}
//实现删除pos之后的结点的函数
void Del_Back_SList(SLTNode* pos)
{
assert(pos && pos->next);
//tmp用来记住pos之后的结点
SLTNode* tmp = pos->next;
pos->next = tmp->next;
free(tmp);
tmp = NULL;
}
//实现销毁链表的函数
void Destroy_SList(SLTNode** pphead)
{
//pphead不能为NULL,并且*pphead不能是空链表
assert(pphead && *pphead);
SLTNode* ptail = *pphead;
SLTNode* pcur = ptail;
while (ptail)
{
ptail = ptail->next;
free(pcur);
pcur = ptail;
}
*pphead = NULL;
}
test.c自行测试,这里不予提供。
四、回归
我们再回到引文的部分,对于动态顺序表的问题就能很好地解决了,单链表中间 / 头部的插入删除操作时间复杂度为 O (1);单链表不需要扩容,即用即增;链表没有额外的空间浪费。
但是我们需要明确的是没有最好的数据结构,只有在特定场景下最适合的数据结构!