跳到主要内容数据结构：单链表详解 | 极客日志C算法
数据结构：单链表详解
单链表的数据结构与 C 语言实现。内容包括单链表概念、节点定义、以及核心操作函数的编写，如头插尾插、头删尾删、指定位置插入删除、查找与销毁等。文章提供了完整的头文件、源文件及测试代码示例，帮助读者理解线性表在内存中的动态分配与指针操作逻辑。
GitMaster5 浏览 单链表详解
1、单链表的概念
链表是一种线性数据结构，由一系列节点组成。每个节点包括两部分：存储当前节点的**数据（数据区域）**和下一个节点的地址（指针区域）。
简单理解，单链表可以比作火车，有车厢和挂钩。每一节车厢就是一个节点，节点里存储数据 data，车厢之间有挂钩（节点里有指针 next）。
2、单链表的实现
1. 创建三个文件
- SList.h 文件：放函数声明
- SList.c 文件：实现.h 文件中函数功能
- test.c 文件：测试函数功能
函数功能目录 .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);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront;
;
;
SLTNode* ;
;
;
;
;
;
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
(SLTNode** pphead, SLTDataType x)
void
SLTPopBack
(SLTNode** pphead)
void
SLTPopFront
(SLTNode** pphead)
SLTFind
(SLTNode* phead, SLTDataType x)
void
SLTInsert
(SLTNode** pphead, SLTNode* pos, SLTDataType x)
void
SLTInsertAfter
(SLTNode* pos, SLTDataType x)
void
SLTErase
(SLTNode** pphead, SLTNode* pos)
void
SLTEraseAfter
(SLTNode* pos)
void
SListDestroy
(SLTNode** pphead)
2. 单链表功能实现
2.1 单链表核心结构
typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data;
struct SListNode* next;
} SLTNode;
2.2 单链表的打印
void SLTPrint(SLTNode* phead) {
SLTNode* pcur = phead;
while (pcur) {
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
- 只看不改，所以这里不用二级指针
- 用 pcur 遍历，不动原来的头指针
- 只要节点不为空，就打印数据，然后走到下一个
2.3 创建新的节点
SLTNode* SLTBuyNode(SLTDataType x) {
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL) {
perror("malloc error");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
- 先向内存要一块能存一个节点的空间
- 把数据 data 赋值为 x
- 先让 next 指针置为空
- 返回这个节点
2.4 查找节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
SLTNode* pcur = phead;
while (pcur) {
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
- 用 pcur 代替 phead 遍历链表，找到返回节点地址，找不到返回 NULL
3、单链表的插入和删除
3.1 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL) {
*pphead = newnode;
} else {
SLTNode* ptail = *pphead;
while (ptail->next != NULL) {
ptail = ptail->next;
}
ptail->next = newnode;
}
}
- 为什么用二级指针？因为要修改头指针本身
- 先创建一个节点，用 ptail 遍历链表，直到 ptail 走到尾节点的位置停止遍历，把最后一个节点的指针指向新节点的地址
- 如果链表是空链表，直接将新创建的节点作为头节点
3.2 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
- 头插要改变头指针存放的地址，所以要用二级指针
- 新节点的 next 指针指向原来的头节点，新节点变成头节点
3.3 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead && *pphead);
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
if (pos == *pphead) {
SLTPushFront(pphead, x);
} else {
SLTNode* prev = *pphead;
while (prev->next != pos) {
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
- 用 prev 遍历链表，直到遍历到 pos 的前一个节点的位置停止遍历，此时需要把 prev，newnode，pos 连接到一起
3.4 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
- 先让 newnode 的指针域指向 pos 的后一个节点的地址，再让 pos 的指针域指向 newnode 的地址（正确）
- 先让 pos 的指针域指向 newnode 的地址，再让 newnode 的指针域指向 pos 的后一个节点的地址（错误）
第一步：pos→next=newnode 节点 A 的箭头指向了节点 N 此时 pos→next 已经不是节点 B，而是 N
第二步：newnode→next=pos→next 这是 pos→next 为 N，newnode→next 也为 N 节点 N 自己指向了自己，形成死循环
3.5 头删
void SLTPopFront(SLTNode** pphead) {
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
- 头删要改变头指针中存放的地址，所以用二级指针
- 改变头节点前需要先保留原来头节点的地址，否则更换完头节点后找不到原来的头节点了
3.6 尾删
void SLTPopBack(SLTNode** pphead) {
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL) {
free(*pphead);
*pphead = NULL;
} else {
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
while (ptail->next) {
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
- 尾删先要遍历一遍链表找到最后一个节点将其释放，要先找到倒数第二个节点，把倒数第二个节点的 next 指针置为空，再删除尾节点
3.7 在指定位置删除数据
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead && *pphead);
assert(pos);
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 是头节点时，调用头删函数
- 用 prev 找到 pos 的前一个节点
- 让 perv 跳过 pos，指向 pos 的下一个节点
- 释放 pos
3.8 删除 pos 位置后面的数据
void SLTEraseAfter(SLTNode* pos) {
assert(pos && pos->next);
SLTNode* del = pos->next;
del->next = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
- 要删除的节点是 del，所以把 pos 的 next 指针指向 del 的下一个节点，最后释放 del 节点
4、单链表的销毁
void SListDestroy(SLTNode** pphead) {
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur) {
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
5、测试文件
#include "SList.h"
void test01() {
SLTNode* nodel1 = (SLTNode*)malloc(sizeof(SLTNode));
nodel1->data = 1;
SLTNode* nodel2 = (SLTNode*)malloc(sizeof(SLTNode));
nodel2->data = 2;
SLTNode* nodel3 = (SLTNode*)malloc(sizeof(SLTNode));
nodel3->data = 3;
SLTNode* nodel4 = (SLTNode*)malloc(sizeof(SLTNode));
nodel4->data = 4;
nodel1->next = nodel2;
nodel2->next = nodel3;
nodel3->next = nodel4;
nodel4->next = NULL;
SLTNode* plist1 = nodel1;
SLTPrint(plist1);
}
void test02() {
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPushFront(&plist, 6);
SLTPrint(plist);
SLTPushFront(&plist, 7);
SLTPrint(plist);
SLTPushFront(&plist, 8);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* find = SLTFind(plist, 1);
if (find == NULL) {
printf("没有找到\n");
} else {
printf("找到了\n");
}
SLTInsert(&plist, find, 11);
SLTPrint(plist);
SLTInsertAfter(find, 12);
SLTPrint(plist);
SLTEraseAfter(find);
SLTPrint(plist);
}
int main() {
test02();
return 0;
}
