目录
本章我们将主要讲解:
单链表及其实现
注:如果还不会顺序表,这里附上链接:数据结构-顺序表实现超详解(小白也能看懂的保姆级教程~)
链表是一种物理存储结构上非连续、非顺序的存储结构 数据元素的逻辑顺序是通过链表中的指针链接次序实现的
链表结构在逻辑上为连续的,但是物理上(内存中)不一定连续 链表节点都是在堆上申请出来的,申请空间按一定策略分配
链表具有多种结构:单向\双向,带头\不带头,循环\非循环 实际上最常用的是:无头单向非循环链表,带头双向循环链表
无头单向非循环链表 | 结构简单,一般不会单独用来存数据实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等 |
---|---|
带头双向循环链表 | 结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表这个结构虽然结构复杂,但是会带来很多优势 |
注:这里具体实现无头单向非循环链表
//无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 为什么不在pos位置之前插入:效率不高
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 为什么不删除pos位置:同样效率不高
void SListEraseAfter(SListNode* pos);
值域 | 用于保存需要存储的值 |
---|---|
址域 | 指向下一个节点地址(便于访问遍历),连接相邻节点 |
//默认链表数据类型
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SLTNode;
对于链表来说,每需要空间就需要进行开辟,这里我们将之封装成一个函数,便于后续调用直接使用(开辟的同时进行赋值)
//链表节点开辟
SLTNode* BuySListNode(SLTDateType x)
{
//动态分配一个节点
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
//分配失败则打印错误信息并结束进程
perror("newnode fail:");
exit(-1);
}
//成功则进行赋值
newnode->data = x;
newnode->next = NULL;
//返回节点地址,以便后续操作
return newnode;
}
//链表数据打印
void SListPrint(SLTNode* phead)//一级指针接收一级指针(打印不需改变指针本身内容)
{
//创建一个寻址指针
SLTNode* cur = phead;
while (cur!=NULL)//后续还有节点
{
//打印数据并指向下一个节点
printf("%d->", cur->data);
cur = cur->next;
}
//最后打印空指针
printf("NULL\n");
return;
}
//链表尾插数据
void SListPushBack(SLTNode** pphead, SLTDateType x)//二级指针接收一级指针(尾插存在需改变链表指针本身内容)
{
//避免传入错误(直接报错便于找到错误位置)
assert(pphead);
//接收新节点的地址
SLTNode* newnode=BuySListNode(x);
//头节点为空
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾节点
SLTNode* tail = *pphead;//创建寻址节点
//两个及以上节点的情况
while (tail->next != NULL)
{
//指向下一个节点
tail = tail->next;
}
//找到了
tail->next = newnode;
}
return;
}
注:这是一个非常好的代码习惯
//链表前删数据
void SListPopFront(SLTNode** pphead)
{
//避免传入错误(直接报错便于找到错误位置)
assert(pphead);
//链表为空的情况
if (*pphead == NULL)
{
return;
}
//创建指针保存第二个节点地址
SLTNode* next = (*pphead)->next;
//释放当前头结点空间
free(*pphead);
//更新头结点数据
*pphead = next;
return;
}
//链表数据查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
//创建寻址指针
SLTNode* cur = phead;
while (cur!=NULL)
{
if (cur->data == x)//找到数据符合节点
{
return cur;//返回节点地址(好处:以便后续再寻找或修改)
}
else
{
//找下一个节点
cur = cur->next;
}
}
//未找到数据符合节点
return NULL;
}
//链表pos位置往前插入(较难)(还有在pos位置之后插入,简单点)
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
//避免传入错误(直接报错便于找到错误位置)
assert(pphead);
assert(pos);
SLTNode* newnode = BuySListNode(x);
//首结点符合的情况
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
//创建寻址指针
SLTNode* cur = *pphead;
while (cur !=NULL)
{
if (cur->next!= pos)
{
cur = cur->next;//找到下一节点
}
else // 找到对应空间
{
cur->next = newnode;
newnode->next = pos;
return;//结束寻找(否则会一直插入,造成死循环)
}
}
}
//未找到则什么也不干
return;
}
注:一定要注意修改链接节点址域的先后,避免地址的丢失
//链表pos位置往后插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
return;
}
//链表pos位置删除
void SListErase(SLTNode** pphead, SLTNode* pos)
{
//避免传入错误(直接报错便于找到错误位置)
assert(pphead);
assert(pos);
//头结点符合的情况
if (*pphead == pos)
{
*pphead = (*pphead)->next;
free(pos);
}
else
{
//创建寻址指针
SLTNode* cur = *pphead;
while (cur != NULL)
{
if (cur->next != pos)
{
cur = cur->next;//找到下一节点
}
else // 找到对应空间
{
SLTNode* next = cur->next->next;
free(cur->next);
cur->next = next;
return;//结束寻找
}
}
}
//未找到则什么也不干
return;
}
//链表节点释放
void SListDestory(SLTNode** pphead)
{
//避免传入错误(直接报错便于找到错误位置)
assert(pphead);
//遍历释放
SLTNode* cur = *pphead;
while (cur)
{
//保存下一个地址
SLTNode* next = cur->next;
free(cur);
cur = next;
}
//置空
*pphead = NULL;
return;
}
不带头单链表到这里就讲解完了,学完顺序表和链表我们可以将之做一个对比~
顺序表 | 链表 | |
---|---|---|
优点 | 支持随机访问 注:有些算法需要结构支持随机访问:二分查找,快排等 | 按需申请空间(空间使用合理)插入效率高(不用像顺序表样挪动数据) |
缺点 | 扩容空间有消耗(空间碎片化以及空间浪费)插入数据需要挪动数据有消耗 | 不支持随机访问(无法用下标直接访问)注:后一个空间访问前一个空间需要再遍历链表 |