单链表的实现

代码位置

[Gitee](sllist/sllist · petrichor/2024-summer-c-language - 码云 - 开源中国 (gitee.com))

概念与结构

概念：

​ 链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

​ 类比火车地铁，都是一节一节的

• 淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/ 加上，不会影响其他车厢，每节车厢都是独立存在的。

在链表⾥，每节“⻋厢”是什么样的呢?

结构：

​ 与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”。

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。

• 图中指针变量plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望 plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。
• 链表中每个结点都是独立申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、结点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

---

链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2x2x2）链表结构：

链表说明：

• 虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表
  1. 无头单向非循环链表：结构简单，⼀般不会单独⽤来存数据。实际种更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
  2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。但是这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，在下一篇博客我们将进行双向链表的实现。

单链表的实现

即不带头单向不循环链表

单链表的创建和打印及销毁

---

SList.h(其中方法会一一讲到)

• 定义链表结构
• 将存储数据类型重命名(方便之后替换->例如我们要求单链表内存储char类型数据，只用改一行代码即可)
• 函数的声明，声明的时候参数只需要类型就可以了，名字加不加都一样

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode 
{SLTDataType data;struct SListNode* next;
}SLTNode;void creatlist();
SLTNode* SLTBuyNode(SLTDataType x);
void printlist(SLTNode*);//插入
void SLTPushBack(SLTNode**, SLTDataType);
void SLTPushFront(SLTNode**, SLTDataType);//删除
void SLTPopBack(SLTNode**);
void SLTPopFront(SLTNode**);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//指定位置插入数据
void SLTInsert(SLTNode**, SLTDataType, SLTNode*);
void SLTInsertAfter( SLTDataType, SLTNode*);//删除指定节点
void SLTErase(SLTNode**, SLTNode*);
void SLTEraseAfter(SLTNode*);//销毁链表
void SListDestroy(SLTNode**);

---

test.c

• 用来测试我们写的函数(函数的调用)
• 这一部分就是自己写的时候用的测试用例，随便什么都行

养成好习惯，写一个方法测试一次，不然找错误的时候会很痛苦😜

#include "sllist.h"
//实际操作中不会这么去创建链表
void creatlist()
{SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTNode* plist = node1;printlist(plist);}void test1(){SLTNode* plist = NULL;//SLTPushBack(&plist, 1);//SLTPushBack(&plist, 2);//SLTPushBack(&plist, 3);//SLTPushBack(&plist, 4);SLTPushBack(NULL, 4);SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 4);SLTPushFront(&plist, 3);//SLTPopBack(&plist);//SLTPopBack(&plist);//SLTPopFront(&plist);//SLTPopFront(&plist);//SLTNode* m=SLTFind(plist, 3);//if (m!= NULL)//{//	printf("找到了\n");//}SLTInsert(&plist, 3, m);//SLTInsertAfter( 6, m);//	SLTErase(&plist, m);//SLTEraseAfter(m);SListDestroy(&plist);printlist(plist);}int main()
{//creatlist();test1();return 0;
}

单链表的创建

可以看到在creatlist中我们是先随便申请几个节点然后将他们首尾相连

但链表的性质是每个节点都是独立申请的，即我们有需要才去申请一块节点的空间，所以我们实际中我们不会这样创建链表，只需一开始创建一个链表结点类型的指针plist，并将其置为空，表示此时链表为空，之后需要的时候我们通过插入一个节点并始终保持plist指向单链表第一个节点即可。

单链表的打印

void printlist(SLTNode* phead)
{assert(phead);SLTNode* p1 = phead;while (p1){printf("%d ", p1->data);p1 = p1->next;}
}

• 一般情况下，单链表已知的都是指向第一个节点的指针plist，因为我们只是打印不需要改变plist的指向，即不需要改变plist的值，所以我们用一级指针即可。
• 基本思想仍是遍历

单链表的销毁

void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* p1 = pcur;pcur = pcur->next;free(p1);p1 = NULL;}*pphead = NULL;
}

- 这里我们要改变plist的值了，所以传二级指针（其实也可以传一级，只不过在调用完后别忘了把plist置为空哦(❁´◡`❁)）

---

单链表的插入

单链表头插

既然要插入我们就要先申请一块空间

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = NULL;return node;
}

• 将申请新节点的函数分装起来，便于调用

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

• 连接新节点和plist
• 再让plist指向新节点

单链表尾插

void SLTPushBack(SLTNode** pphead , SLTDataType x)
{//申请新节点assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead==NULL){*pphead = newnode;}else{SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}

• 分两种情况
  • 链表为空，plist直接指向新节点
  • 链表不为空，找尾节点再插入

单链表在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTDataType x, SLTNode* pos)
{assert(pphead && pos);if (pos == *pphead){SLTPushFront(pphead,x);}else{SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}

• 分两种情况
  • 若是pos和plist相同，说明就是头插，调用即可
  • 第二种情况，找到pos之前一个节点，一定要先改newnode的next指针，否则找不到pos下一个节点了

单链表在指定位置之后插入数据

void SLTInsertAfter( SLTDataType x, SLTNode* pos)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

• 还是记得先改插入进来newnode的next指针

---

单链表的删除

单链表的头删

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

• 删除都别忘了判断链表是否为空，即plist是否为空

单链表的尾删

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}if (prev)//处理只有一个节点的情况{prev->next = NULL;prev=NULL;}else*pphead = NULL;free(ptail);ptail = NULL;
}

• 同样分两种情况

  • 当链表多于一个节点时，找尾节点以及其前一个节点，将尾节点释放并把前一个节点next指针置为空

  • 当链表只有一个节点时，不需要将前一个节点next指针置为空，此时需要将plist置为空

单链表在指定位置删除数据

void SLTErase(SLTNode** pphead, SLTNode* pos )
{assert(pos && pphead&&*pphead);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

• 分两种情况
  • pos和plist相同，即为头删
  • 第二种情况，先找到pos之前节点，再进行指针的更改即可

单链表在指定位置之后删除数据

void SLTEraseAfter( SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;	
}

• 先保存pos之后节点，改变pos的next指针后再释放del

---

单链表的查找指定位置节点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data==x){return pcur;}pcur = pcur->next;}return NULL;
}

• 找到就返回指向节点的指针，否则返回空
• 老规矩遍历就行了

SList.c(完整版)

#define _CRT_SECURE_NO_WARNINGS 1
#include "sllist.h"
void printlist(SLTNode* phead)
{SLTNode* p1 = phead;while (p1){printf("%d ", p1->data);p1 = p1->next;}
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = NULL;return node;
}void SLTPushBack(SLTNode** pphead , SLTDataType x)
{//申请新节点assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead==NULL){*pphead = newnode;}else{SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}if (prev)//处理只有一个节点的情况prev->next = NULL;else*pphead = NULL;free(ptail);ptail = NULL;
}void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data==x){return pcur;}pcur = pcur->next;}return NULL;}void SLTInsert(SLTNode** pphead, SLTDataType x, SLTNode* pos)
{assert(pphead && pos);if (pos == *pphead){SLTPushFront(pphead,x);}else{SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}void SLTInsertAfter( SLTDataType x, SLTNode* pos)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}void SLTErase(SLTNode** pphead, SLTNode* pos )
{assert(pos && pphead&&*pphead);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLTEraseAfter( SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;	
}void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* p1 = pcur;pcur = pcur->next;free(p1);p1 = NULL;}*pphead = NULL;
}

在单链表实现的函数中，特别有两点要注意：

1. 涉及到plist(指向第一个节点的指针)的指向改变时，一定记得传plist的地址，使用二级指针
2. 在尾插/尾删中，都需要依据链表是否为空/链表是否多于一个节点来分情况讨论，目的是避免对空指针进行解引用造成的错误。

以上就是单链表的实现方法啦，各位大佬有什么问题欢迎在评论区指正，您的支持是我创作的最大动力！❤️