链表的讲解与单链表的实现
- 一、链表的概念及结构
- 二、链表的分类
- 三、单链表的实现(使用VS2022)
- 1.销毁、打印内容
- 2.尾插尾删、头插头删
- 尾插
- 尾删
- 头插
- 头删
- 3.查找、指定插入、指定删除
- 查找
- 指定插入
- 指定删除
- 4.目标后一个插入、目标后一个删除
- 四、完整 SList.c 源代码
一、链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
每个元素都是独立申请下来的空间，被称为“节点/结点”。
节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。
链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。
typedef int SLTDataType;
typedef struct SLTNode
{
SLTDataType data; // 节点数据
struct SLTNode* next; // 下一个数据的地址
} SLTNode;
当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址（当没有下一个节点时保存的地址为空）。
当我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿上下一个节点的地址就可以了。
另外需要注意：
1、链式机构在逻辑上是连续的，在物理结构上不一定连续。
2、节点一般是从堆上申请的。
3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。
二、链表的分类
链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：
链表说明：
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表
1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现其结构会带来很多优势，实现反而简单。
三、单链表的实现(使用VS2022)
这里用VS2022的C语言来实现单链表。
单链表常用的增删改查等接口包括：
1.销毁、打印内容
2.尾插尾删、头插头删
3.查找、指定插入、指定删除
4.目标后一个插入、目标后一个删除
在 SList.h 中：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SLTNode
{
SLTDataType data; // 节点数据
struct SLTNode* next; // 下一个数据的地址
} SLTNode;
// 1.销毁、打印
void SListDestroy(SLTNode* phead);
void SListPrint(SLTNode* phead);
// 2.尾插尾删、头插头删
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPopBack(SLTNode** pphead);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopFront(SLTNode** pphead);
// 3.查找、指定插入、指定删除
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SListErase(SLTNode** pphead, SLTNode* pos);
// 4.目标后一个插入、目标后一个删除
void SListInsertAfter(SLTNode* pos, SLTDataType x);
void SListEraseAfter(SLTNode* pos);
1.销毁、打印内容
void SListDestroy(SLTNode* phead)
{
SLTNode* temp = phead;
while (temp)
{
SLTNode* next = temp->next;
free(temp);
temp = next;
}
phead = NULL;
}
void SListPrint(SLTNode* phead)
{
for (SLTNode* temp = phead; temp; temp = temp->next)
{
printf("%d ", temp->data);
}
printf("\n");
}
2.尾插尾删、头插头删
尾插
// 节点创建封装为函数
SLTNode* CreateNode(SLTDataType x)
{
SLTNode* temp = (SLTNode*)malloc(sizeof(SLTNode));
if (temp == NULL)
{
perror("malloc failed");
return NULL;
}
temp->data = x;
temp->next = NULL;
return temp;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newNode = CreateNode(x);
// 单链表要考虑头节点为空的情况
if (*pphead == NULL)
{
*pphead = newNode;
}
else
{
// 寻找尾节点
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
// 将尾节点next指向新节点
tail->next = newNode;
}
}
尾删
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead); // 删除时头节点不能为空
// 头节点下一个为空，直接删除头节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
// 尾部前面第一个节点
SLTNode* tailFront = *pphead;
while (tailFront->next->next)
{
tailFront = tailFront->next;
}
// 释放目标尾节点，将新一个尾节点next置空
free(tailFront->next);
tailFront->next = NULL;
}
}
头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newNode = CreateNode(x);
// 头节点为空或不为空都适用
newNode->next = *pphead;
*pphead = newNode;
}
头删
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* temp = (*pphead)->next;
free(*pphead);
*pphead = temp;
}
3.查找、指定插入、指定删除
查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
// 找到返回地址，反之返回空指针
for (SLTNode* temp = phead; temp; temp = temp->next)
{
if (temp->data == x)
{
return temp;
}
}
return NULL;
}
指定插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos); // 限定pos不能为空，则不能尾插
SLTNode* newNode = CreateNode(x);
/*
* 这里要考虑3种情况
* 1.头节点为空，直接赋值
* 2.头节点与目标节点相同，头插
* 3.遍历链表，寻找到目标节点后插入
*/
if ((*pphead) == NULL) // 1.头节点为空，直接赋值
{
*pphead = newNode;
}
else if ((*pphead) == pos) // 2.头节点与目标节点相同，头插
{
newNode->next = (*pphead);
(*pphead) = newNode;
}
else // 3.遍历链表，寻找到目标节点后插入
{
SLTNode* temp = *pphead;
while (temp->next != pos)
{
temp = temp->next;
}
newNode->next = pos;
temp->next = newNode;
}
}
指定删除
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if (*pphead == pos) // 1.头节点与目标节点相同
{
SLTNode* temp = (*pphead)->next;
free(*pphead);
*pphead = temp;
}
else // 2.遍历链表后删除目标节点
{
SLTNode* temp = *pphead;
while (temp->next != pos)
{
temp = temp->next;
}
temp->next = pos->next;
free(pos);
pos = NULL;
}
}
4.目标后一个插入、目标后一个删除
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newNode = CreateNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next); // 后一个不能为空
SLTNode* temp = pos->next->next;
free(pos->next);
pos->next = temp;
}
四、完整 SList.c 源代码
#include "SList.h"
void SListDestroy(SLTNode* phead)
{
SLTNode* temp = phead;
while (temp)
{
SLTNode* next = temp->next;
free(temp);
temp = next;
}
phead = NULL;
}
void SListPrint(SLTNode* phead)
{
for (SLTNode* temp = phead; temp; temp = temp->next)
{
printf("%d ", temp->data);
}
printf("\n");
}
// 节点创建封装为函数
SLTNode* CreateNode(SLTDataType x)
{
SLTNode* temp = (SLTNode*)malloc(sizeof(SLTNode));
if (temp == NULL)
{
perror("malloc failed");
return NULL;
}
temp->data = x;
temp->next = NULL;
return temp;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newNode = CreateNode(x);
// 单链表要考虑头节点为空的情况
if (*pphead == NULL)
{
*pphead = newNode;
}
else
{
// 寻找尾节点
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
// 将尾节点next指向新节点
tail->next = newNode;
}
}
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead); // 删除时头节点不能为空
// 头节点下一个为空，直接删除头节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
// 尾部前面第一个节点
SLTNode* tailFront = *pphead;
while (tailFront->next->next)
{
tailFront = tailFront->next;
}
// 释放目标尾节点，将新一个尾节点next置空
free(tailFront->next);
tailFront->next = NULL;
}
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newNode = CreateNode(x);
// 头节点为空或不为空都适用
newNode->next = *pphead;
*pphead = newNode;
}
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* temp = (*pphead)->next;
free(*pphead);
*pphead = temp;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
// 找到返回地址，反之返回空指针
for (SLTNode* temp = phead; temp; temp = temp->next)
{
if (temp->data == x)
{
return temp;
}
}
return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos); // 限定pos不能为空，则不能尾插
SLTNode* newNode = CreateNode(x);
/*
* 这里要考虑3种情况
* 1.头节点为空，直接赋值
* 2.头节点与目标节点相同，头插
* 3.遍历链表，寻找到目标节点后插入
*/
if ((*pphead) == NULL) // 1.头节点为空，直接赋值
{
*pphead = newNode;
}
else if ((*pphead) == pos) // 2.头节点与目标节点相同，头插
{
newNode->next = (*pphead);
(*pphead) = newNode;
}
else // 3.遍历链表，寻找到目标节点后插入
{
SLTNode* temp = *pphead;
while (temp->next != pos)
{
temp = temp->next;
}
newNode->next = pos;
temp->next = newNode;
}
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if (*pphead == pos) // 1.头节点与目标节点相同
{
SLTNode* temp = (*pphead)->next;
free(*pphead);
*pphead = temp;
}
else // 2.遍历链表后删除目标节点
{
SLTNode* temp = *pphead;
while (temp->next != pos)
{
temp = temp->next;
}
temp->next = pos->next;
free(pos);
pos = NULL;
}
}
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newNode = CreateNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next); // 后一个不能为空
SLTNode* temp = pos->next->next;
free(pos->next);
pos->next = temp;
}
