文章目录
一、单链表
1.1概念与结构
1.2结点
1.3链表的性质
1.4链表的打印
二、实现单链表
SList.h
SList.c
申请新节点
尾插
头插
尾删
头删
在指定位置之前插入数据
在指定位置之后插入数据
删除指定位置结点
删除指定位置之后的结点
销毁结点
test.c
一、单链表
1.1概念与结构
概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
我们可以用火车类比一下：
淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/ 加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。
在链表⾥，每节“⻋厢”是什么样的呢？
1.2结点
与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”
结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。
图中指针变量 plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望
plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。
链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。
（注意：在链表中，没有增容的概念，需要插入新的数据，直接申请一个结点大小的空就可以了）
1.3链表的性质
1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续
2、结点⼀般是从堆上申请的
3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续
结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码：
#include<stdio.h>
#include<stdlib.h>
//定义链表的结构
typedef int SLTDataType; // 方便后面一键替换
typedef struct SListNode {
SLTDataType data; //数据类型
struct SListNode* next; // 下个节点的起始地址
}SLNode;1.4链表的打印
- 首先在头文件SList.h中定义并且在SList.中实现方法
void SLTPrint(SLNode* phead)
{
SLNode* pcur = phead; //指向第一个结点 node1 的地址；
while (pcur)
{
printf("%d->", pcur->data); // 第一次打印 node1—> data =1；
pcur = pcur->next; // 1)pcur 指针变量保存第一个结点的地址
// 2)对 pcur 解引用拿到 next 指针变量中的地址（下一个结点 node2 的地址）
// 3)赋值给 pcur ，此时 pcur 保存的地址为 node1->next 的地址，即 pcur “指向了下一个结点（node2）”
}
printf("NULL\n");
}- 然后在测试文件 test.c 中申请节点空间
#include"SList.h"
void creatslist() {
SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));
node1->data = 1;
SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));
node2->data = 2;
SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));
node3->data = 3;
SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));
node4->data = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
//第一个结点的地址作为参数传递过去
SLNode* plist = node1;
SLTPrint(plist);
}
int main()
{
creatslist();
}
二、实现单链表
SList.h
#include<stdio.h>
#include<stdlib.h>
//定义链表的结构
typedef int SLTDataType; // 方便后面一键替换
typedef struct SListNode {
SLTDataType data; //数据类型
struct SListNode* next; // 下个节点的起始地址
}SLNode;
//打印链表
void SLTPrint(SLNode* phead)
//头部插⼊删除/尾部插⼊删除
void SLTPushBack(SLNode** pphead, SLTDataType x);
void SLTPushFront(SLNode** pphead, SLTDataType x);
void SLTPopBack(SLNode** pphead);
void SLTPopFront(SLNode** pphead);
//查找
SLTNode* SLTFind(SLNode* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//删除pos结点
void SLTErase(SLNode** pphead, SLNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLNode* pos, SLTDataType x);
//删除pos之后的结点
void SLTEraseAfter(SLNode* pos);
//销毁链表
void SListDestroy(SLNode** pphead);SList.c
申请新节点
//申请新节点
SLNode* SLTBuyNode(SLTDataType x)
{
SLNode* node = (SLNode*)malloc(sizeof(SLNode));
if (node == NULL)
{
perror("malloc fail!");
}
node->data = x;
node->next = NULL;
return node;
}
尾插
（补充：形参的改变要影响实参，必须传实参的地址）
举个简单的例子:
int a = 1;
&a; //取地址
int* pa = &a;
&pa; //去指针pa变量的地址
void SLTPushBack(SLNode** pphead, SLTDataType x)
{
assert(pphead);
//申请新节点
SLNode* newnode = SLTBuyNode(x);
if (*pphead == NULL) //指向第一个节点的指针为空
{
*pphead = newnode;
}
else
{
//找尾结点
SLNode* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = newnode;
}
}- 第一个结点：*plist ——————> **pphead
- 指向第一个结点的指针： plist ——————> *pphead
- 指向指向第一个结点的指针的地址：&pilst——————> pphead
头插
void SLTPushFront(SLNode** pphead, SLTDataType x)
{
//申请新节点
SLNode* newnode = SLTBuyNode(x);
newnode->next = *pphead; //新结点指向的是原来头结点的地址
*pphead = newnode; //新插入的结点变成头节点
}尾删
void SLTPopBack(SLNode** pphead)
{
//链表为空，不可删除
assert(pphead && *pphead);
//处理链表只有一个结点的情况，当只有一个结点，删除的就是头结点
if ((*pphead)->next == NULL) // *pphead 头结点指向下一个地址为空，说明只有一个结点
{
free(*pphead);
*pphead = NULL;
}
else
{
SLNode* ptail = *pphead; //创建一个用于遍历链表的指针 ptail
SLNode* prev = NULL; //创建一个空指针 prev
while (ptail->next != NULL)
{
prev = ptail; //将 ptail 指向下一个的结点赋值给 prev
ptail = ptail->next; // ptail 继续指向下一个几点，一直循环赋值，直到 prev 指向的下一个结点为 NULL后释放删除
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}头删
void SLTPopFornt(SLNode** pphead)
{
//链表为空，不可删除
assert(pphead && *pphead);
SLNode* next = (*pphead)->next; //创建指针 next 为 *phead 指向的下一个结点
free(*pphead); //先释放
*pphead = next; //后赋值
}在指定位置之前插入数据
void SLTInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead) //pos 和 头结点相等，说明是在头结点前插入数据，相当于头插
{
SLTPushFront(pphead, x);
}
else
{
SLNode* newnode = SLTBuyNode(x); //创建一个结点
SLNode* prve = *pphead; //创建指针 pcur 遍历链表
while (prve->next != pos)
{
prve = prve->next;
}
newnode->next = pos; //当 prve -> next = pos 也就是到达 pos 前的结点，插入 newnode ，让 newnode->mext = pos
prve->next = newnode; //零 prve->next = newnode
}
}在指定位置之后插入数据
void SLTInsertAfter(SLNode*pos, SLTDataType x)
{
assert(pos);
SLNode* newnode = SLTBuyNode(x); //创建一个结点
newnode->next = pos->next; //先让 newnode 指向的下一个结点为原来 pos 指向的结点
pos->next = newnode; //再让 newnode 赋值称为 原来 pos 指向的下一个结点
}
删除指定位置结点
void SLTErase(SLNode** pphead, SLNode* pos)
{
assert(pphead && *pphead);
assert(pos);
if (pos == *pphead) //处理链表只有一个结点的情况，当只有一个结点，删除的就是头结点
{
SLTPopFornt(pphead);
}
else
{
SLNode* prve = *pphead; //创建 prve 结点遍历链表
while (prve->next != pos)
{
prve = prve->next;
}
prve->next = pos->next; //当 prve->next 的结点就是 pos 时，prve->next = pos->next（意思就是跳过pos 结点）
free(pos); //释放pos ，NULL
pos = NULL;
}
}删除指定位置之后的结点
void SLTEraseAfter( SLNode* pos)
{
assert(pos && pos->next); //指定位置和指定位置之后的结点不能为空
SLNode* del = pos->next; //创建 del 结点为 pos->next 的节点
pos->next = pos->next->next; //跳过 del 结点
free(del); //释放 del ，NULL
del = NULL;
}销毁结点
void SLTDestory(SLNode** pphead)
{
assert(pphead && *pphead);
SLNode* pcur = *pphead;
while (pcur)
{
SLNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}test.c
#include"SList.h"
void SListtest()
{
SLNode* plist = NULL;
SLTPushBack(&plist, 4);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 1);
printf("尾插后的数据：");
SLTPrint(plist);
printf("\n");
SLTPushFront(&plist, 5);
printf("头插数据5 ：");
SLTPrint(plist);
printf("\n");
SLTPopBack(&plist);
printf("尾删后的数据：");
SLTPrint(plist);
printf("\n");
SLTPopFornt(&plist);
printf("头删后的数据：");
SLTPrint(plist);
printf("\n");
SLTFind(plist, 3);
SLNode* find1 = SLTFind(plist, 3);
SLTInsert(&plist, find1, 6);
SLTInsertAfter(find1, 7);
printf("在结点数据为3之前插入结点数据6，结点数据为3之后插入结点数据7：");
SLTPrint(plist);
printf("\n");
SLTEraseAfter(find1);
SLTErase(&plist, find1);
printf("删除结点数据为3以及结点数据为3之后的结点：");
SLTPrint(plist);
printf("\n");
SLTDestory(&plist);
printf("销毁链表plist：");
SLTPrint(plist);
}
int main()
{
SListtest();
return 0;
}
