【初阶数据结构】探索数据的多米诺链：单链表
文章目录
本篇介绍线性表链表中的单链表，链表由一系列节点组成，每个节点包含数据和指向下一个节点（对于单链表）或前后节点（对于双向链表）的指针
1.链表
1.1 概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
链式结构的逻辑一般是连续的，但是在物理存储上不一定是连续的，因为每个节点都是从堆上申请来的，从堆上申请的空间要根据实际情况分配空间，两次申请可能是连续的也有可能不是连续的
简单来说，每个节点都存储了下一个节点的地址，即能找到下一个节点，就形成了链表
我们还需要了解几个概念：
🚩头结点
图中的
plist就是头结点，位于链表的起始位置，但不存储实际的有效数据(有效数据指的是结构体的内的数据，而不是结构体地址)，主要作用是作为链表的入口，通过它的指针域来指向链表中的第一个实际存储数据的节点
🚩首节点
首节点就是跟在
头节点后的链表中第一个存储实际有效数据的节点
🚩哨兵位
哨兵位和头结点类似，通常
不存储实际数据，存储地址，哨兵位可以看成一个灵活的节点，可以在链表任何位置方便进行增删查改操作
每个节点的结构体：
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
1.2 分类
链表有三种分类方式
🚩⑴单向或双向
🚩⑵带头或不带头
🚩⑶循环或者非循环
这三种情况能组合出8种链表，这里我们只介绍两种常用的链表
无头单向非循环链表： 结构简单，实现麻烦，通常在面试笔试中以题目形式出现比较多(因为其他出成题目太难了)，单链表也更多的作为底层结构来进行算法应用
带头双向循环链表： 结构复杂，实现简单，这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了
2.单链表接口实现
2.1 单链表节点创建
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
顺序表中我们空间不够时需要不断扩容，链表中的节点申请函数就是这种类似的效果，但是顺序表是对它底层的数组进行二倍扩容，而节点申请函数一次性只能申请一个节点，用一个给一个，间接避免了空间浪费，注意返回的是新节点的地址
2.2 单链表打印
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
//while(cur->next != NULL)会遗漏最后一个数据
//while(cur != NULL)也可以这样写
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
//cur++只有数组才这么写
}
printf("NULL\n");
}
先传入头结点，然后我们需要一个cur指针作为移动指针来遍历单链表中的数据，每个节点的next都存储了下一个节点的地址，所以循环赋值就可以实现单链表的移动，最后一个节点指向的是空指针
🔥值得注意的是： 顺序表的打印需要断言传入的结构体指针是因为该指针涉及到访问，万一传入的空指针，会造成非法访问；链表的打印有可能该链表本来就是空的，空链表也是能打印的，而且也不涉及指针访问，所以加断言反而不合理
2.3 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
//分没有节点，和有节点的情况
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
凡是涉及增加删除节点的操作，都要考虑是否为空的情况要不要特别考虑，因此这里为空时直接将头指针和新节点链接即可；不为空时循环遍历找到最后一个节点，将最后一个节点和新节点连接
🔥值得注意的是： 循环判断条件为tail->next != NULL，因为为空时可能要修改头指针存的地址，所以应该传二级指针
2.4 单链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
头指针中存储的是第一个节点的地址，所以newnode->next = *pphead，然后newnode就成了第一个节点，那么当前头指针存的就是当前第一个节点newnode的地址
2.5 单链表尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);//*phead要指针访问所以要断言
if ((*pphead)->next == NULL)//分没有节点，和有节点的情况
{
free(*pphead);
*pphead = NULL;
}
else
{
//找最后一个节点的前一个节点
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;//free之后可以赋值但不能指针访问
}
}
当没有节点时，删除的就是头指针，直接释放即可；当有节点时，我们要给最后一个节点和倒数第二个节点做标记，因为最后一个节点要释放，倒数第二个节点需要把他的next置为NULL
2.6 单链表头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
先存储首节点的地址，便于把首节点的下一个节点传给头节点，注意不要先释放节点，避免非法访问
2.7单链表查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
这个和顺序表一样，通过简单的遍历链表 一 一 对比值即可
2.8 单链表在pos位置插入x
2.8.1 pos前
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
同样是分为链表为空和链表不为空的情况，当链表为空时，相当于头插；当链表不为空时，prev找到pos的前一个位置，然后进行链接操作即可
2.8.2 pos后
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
从代码形式上来看，pos后的插入明显是比pos前插入更简单的，pos前需要多传一个头指针参数，找到pos前一个数的位置；pos后只需要在pos后直接链接即可
2.9单链表在pos位置删除x
2.9.1 pos前
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
//pos = NULL;
}
}
和在pos位置删除其实是一样的，分为空和不空的链表，但是一般我们不在函数内将要删除的节点置为空，习惯性在函数外进行此操作
2.9.2 pos后
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
//del = NULL;
}
直接释放pos位置之后的节点即可，但是要注意需要断言pos->next，万一是最后一个节点的话，在其后删除会报错
2.2.10 单链表销毁
void SLTDestroy(SLTNode** pphead)
{
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* del = pcur;
pcur = pcur->next;
free(del);
}
*pphead = NULL;
}
销毁的方法也不难，就是遍历链表，只要链表不为空就循环释放节点，关键是我们在释放前要把下一个节点记录下来，如果直接释放了当前节点，那么就找不到下一个节点了，所以我们要把下一个节点保存下来才释放当前节点
3.代码展示
传送门：Gitee单链表代码
3.1 SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
SLTNode* BuySLTNode(SLTDataType x);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** pphead);
3.2 SList.c
#include "SList.h"
//打印
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//创建节点
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
//查找节点
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//pos前插入
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
if (pos == *pphead)
{
SLTPushBack(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
//pos前删除
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
//pos = NULL;
}
}
//pos后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//pos后删除
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
原文地址：https://blog.csdn.net/Zero_VPN/article/details/145186504
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！