【数据机构】2. 线性表之“链表”

- 第 97 篇 -
Date: 2025 - 05 - 16
Author: 郑龙浩/仟墨
【数据结构 2】

续上一篇
线性表之“顺序表”

3 链表(用指针来首位相连)

一定要注意：头插头删之类的时候尽量使用二级指针！！！！

• 二级指针直接修改头指针，避免“无中生有”或“丢失链表”

• 插入或删除头节点时，需更新外部的头指针

• 二级指针能直接修改头节点或 next 指针，减少冗余代码

• 口诀：“改头换面用二级，只读遍历用一级”

  也就是，如果是只是读取无需改变，用一级指针；如果需要改变链表 ，则用二级指针

一级指针使用情况

• 只需读取节点内容，不修改指针本身。(不插入删除结点)
• 无法直接修改头指针：若函数内需要修改链表头（如头插法），调用方的头指针不会被更新

注意：

只要是通过 malloc/calloc/realloc 动态分配的内存，都必须用 free() 释放，否则指针将丢失，内存一直被占用，导致内存泄漏

① 基本介绍

一种逻辑上连续，物理上非连续 的线性结构

链表其实就是针对顺序表的缺点来进行设计的，比如中间或开头插入的时候效率很低，而链表效率就高

线性表的另一种物理实现方式，基于节点 + 指针的离散存储

• 物理上可能非连续，逻辑顺序通过指针维护，所以逻辑上可以认为是连续的
• 不支持随机访问（需从头遍历，时间复杂度 O(n)）
• 插入/删除只需修改指针（时间复杂度 O(1)）

结构如下:

• 数据域：存储数据
• 指针域：存储该数据的地址
• 结点：数据域与指针域结合 –> 结点

结点	头节点		第1个结点		第2个结点		第3个结点
数据			data1		data2		data3
指针	头指针	–>	p1	–>	p2	–>	p3

② 分类 与 变量命名

1 ）分类：

实际上链表结构非常的多，以下情况组合起来有8种结构：

1. 单向、双向
2. 箭头、不带箭头
3. 循环、非循环

一般常用只有两种：

• 无头单向非循环链表

  结点	头节点		第1个结点	第2个结点	第3个结点		第4个结点
  数据			data1		data2		data3
  指针	头指针	–>	p1	–>	p2	–>	p3

• 带头双向循环链表

  结点	头节点		第1个结点		第2个结点		第3个结点
  数据			data1		data2		data3
  指针	头指针	<–>	p1	<–>	p2	<–>	p3
  	└─←	<–	<–	<–	<–	<–	↲

2 ）大体介绍不同结构：

开头统一:

typedef int ElemType; // 将 int 重命名为 ElemType

1. 单链表

   • 结构体类型（单链表存储结构）

     整个结构体为一个结点

     // 单链表结点
     typedef struct SListNode {int data;                   // 数据域struct SListNode *next;     // 指针域（指向下一个节点）
     } SListNode;
     

   • 函数名

     统一为 SList + 操作名, 前缀为 SList

2. 静态链表

   • 结构体类型名（静态链表存储结构）

     整个结构体为一个结点

        // 静态链表节点（用数组下标代替指针）typedef struct StaticListNode {ElemType data;         // 数据域int cur;         // 下一个节点的数组下标（-1表示NULL）} StaticListNode; 
     

   • 函数名

     统一为 StaticList + 操作名, 前缀为 SList

3. 循环链表（循环链表存储结构）

   • 结构体类型名

     整个结构体为一个结点

     // 循环链表节点（与单链表结构相同，但尾节点指向头节点）
     typedef struct CListNode {int data;struct CListNode *next;
     } CListNode;
     

   • 函数名

     统一为 CList + 操作名, 前缀为 SList

4. 双链表

   • 结构体类型名（双链表存储结构）

     整个结构体为一个结点

     // 双链表节点
     typedef struct DListNode {int data;struct DListNode *prev;  // 前驱指针struct DListNode *next;  // 后继指针
     } DListNode;
     

   • 函数名

     统一为 DList + 操作名, 前缀为 SList

③ “单链表” 的实现:

phead 表示一级指针

pphead 表示二级指针

主程序文件test.c

#define _CRT_SECURE_NO_WARNINGS
#include "SListNode.h"
SListNode L;
void Check1() {SListNode* L = NULL; // 指向 “头结点”printf("\n尾插三次: 1~3\n");SListPushBack(&L, 1);SListPushBack(&L, 2);SListPushBack(&L, 3);SListPrint(L);printf("长度为: %d\n", SlistSize(L));printf("\n尾删3次\n");SListPopBack(&L);SListPrint(L);SListPopBack(&L);SListPrint(L);SListPopBack(&L);SListPrint(L);printf("长度为: %d\n", SlistSize(L));printf("\n头插三次: 1~3\n");SListPushFront(&L, 1);SListPushFront(&L, 2);SListPushFront(&L, 3);SListPrint(L);printf("长度为: %d\n", SlistSize(L));printf("\n头删3次\n");SListPopFront(&L);SListPrint(L);SListPopFront(&L);SListPrint(L);SListPopFront(&L);SListPrint(L);printf("长度为: %d\n", SlistSize(L));
}
// 测试代码2
Check2() {SListNode* L = NULL; // 新建链表printf("\n尾插三次: 1~3\n");SListPushBack(&L, 1);SListPushBack(&L, 2);SListPushBack(&L, 3);SListPrint(L);int num1, num2;printf("请输入num1查到的值与num2想修改成的值\n");scanf("%d%d", &num1, &num2);printf("\n查找数据num1，若找到则变为数据num2\n");SListNode* pos = SListFind(L, num1); // pos 指向链表中存放数据num1的结点if (pos != NULL) { // 如果找到了num1，则将数据 num1 换成 num2printf("找到了!\n");pos->data = num2;SListPrint(L); //打印改变之后的 “链表”}else {printf("没有找到");}
}
void Check3() {SListNode* L = NULL; // 新建链表printf("\n尾插三次: 1~3\n");SListPushBack(&L, 1);SListPushBack(&L, 2);SListPushBack(&L, 3);SListPrint(L);SListInsert(&L, SListFind(L, 2), 666);SListPrint(L);SListInsert(&L, SListFind(L, 1), 777);SListPrint(L);SListInsert(&L, L, 0);SListPrint(L);SListInsert(&L, SListFind(L, 66) + 1, 777);SListInsert(&L, NULL, 0);SListPrint(L);// 删除第一个结点SListErase(&L, SListFind(L, 0));SListPrint(L);// 删除中间结点SListErase(&L, SListFind(L, 666));SListPrint(L);// 删除不存在的结点SListNode a = { 99, NULL };SListErase(&L, &a);SListPrint(L);// 全删除后链表为空SListNode* LLL = NULL;SListPushBack(&LLL, 1);SListPrint(LLL);SListErase(&LLL, SListFind(LLL, 1));SListPrint(LLL);
}
// 目录
void memo() {
}
int main(void) {//Check1();//Check2();Check3();return 0;
}

接口文件LinkList.h

#pragma once
#include "stdio.h"
#include "SListNode.h"
#include "stdlib.h"
typedef int ElemType; // 将 int 重命名为 ElemType，element意思元素
// 单链表结点
typedef struct SListNode {int data;                   // 数据域struct SListNode* next;     // 指针域（指向下一个节点）
} SListNode;
// 动态申请一个新的结点  因为插入当中申请新结点的代码太多了，为了避免冗余代码，将重复代码部分重新封装成了一个新的函数
SListNode* BuySListNode(ElemType x);
// 打印
void SListPrint(SListNode* phead);
// 获取链表宽度（结点数量）
size_t SlistSize(SListNode* phead);
// 头插
void SListPushFront(SListNode** pphead, ElemType x);
// 头删
void SListPopBack(SListNode** pphead);
// 尾插
void SListPushBack(SListNode** pphead, ElemType x);
// 尾删
void SListPopBack(SListNode** pphead);
// 查找
SListNode* SListFind(SListNode* phead, ElemType x);
// 在pos位置之前插入x
void SListInsert(SListNode** pphead, SListNode* pos, ElemType x);
// 删除pos位置的值
void SListErase(SListNode** pphead, SListNode* pos);

接口实现文件LinkList.c

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "SListNode.h"
#include "stdlib.h"
SListNode* BuySListNode(ElemType x) {// 申请一个新的结点SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode)); // 为新节点申请内存空间// 养成习惯：判断申请内存是否成功  虽然大概是成功的，但是还是要养成这个习惯if (NewNode == NULL) {printf("申请内存失败!\n");exit(-1);}NewNode->data = x; // 新节点 存入数据xNewNode->next = NULL; // 新节点 指向NULL（初始化），避免越界访问到其他地址return NewNode;
}
// 打印
void SListPrint(SListNode* phead) {SListNode* current = phead; // 当前结点的“地址”while (current != NULL) {printf("%d -> ", current->data); // 打印当前结点中的‘data’current = current->next; // 指向下一个“结点”}printf("NULL\n");
}
// 获取链表宽度（结点数量）
size_t SlistSize(SListNode* phead) {size_t len = 0; // 长度初始化为0SListNode* current = phead; // 遍历链表while (current != NULL) { // 当前节点不为空时计数len++; // 结点数量++current = current->next; // 当前结点指向下一个结点}return len; // 返回链表长度
}
// 头插
void SListPushFront(SListNode** pphead, ElemType x) {SListNode* NewNode = BuySListNode(x); // 创建新的结点NewNode->next = *pphead; // 让新的结点指向“原来的第一个结点”*pphead = NewNode; // 让存放第一个结点地址的*pphead变成存放新结点的地址，也就是让第一个结点变为新的结点 NewNode
}
// 头删
void SListPopFront(SListNode** pphead) {// 三种情况： 1 链表为空 2 链表只有一个结点 3 链表有大于1个的结点if (*pphead == NULL) { // 链表为空，表示无任何结点，则不进行删除操作return;}	else if ((*pphead)->next == NULL){ // 链表只有一个结点free(*pphead); // 释放第一个结点的内存空间，将内存还给操作系统*pphead = NULL; // *pphead = NULL; // 将头指针置空，避免指向已释放的内存（野指针）}else {SListNode* next = (*pphead)->next; // 保护第二个结点，避免释放第一个结点内存后找不到第二个结点free(*pphead); // 释放第一个结点*pphead = next; // 让头指针指向第二个结点}
}
// 尾插
void SListPushBack(SListNode** pphead, ElemType x) {SListNode* NewNode = BuySListNode(x); // 先开辟一个新的结点// 判断第一个结点是否为空，若为空，则开辟空间（也就是该链表没有任何数据）if (*pphead == NULL) { // 若节点为空*pphead = NewNode; // 让第一个结点指向新的结点} else {// 找到最后一个结点SListNode* tail = *pphead; // tail 翻译：尾// 找尾结点while (tail->next != NULL) { // 只要当前结点指向NULL，就表示没有下一个结点了，就表示了当前结点就是最后一个结点tail = tail->next;}tail->next = NewNode; // 将原链表的最后一个结点指向新的节点}
}
// 尾删
void SListPopBack(SListNode** pphead) {// 三种情况：1 链表为空（头结点指向 NULL，也就是无结点）   2 只有一个结点  3 有 多于 1 个的结点if (*pphead == NULL) {return;}else if ((*pphead)->next == NULL) {free(*pphead); // 释放第一个结点的内存*pphead = NULL; // *pphead = NULL; // 将头指针置空，避免指向已释放的内存（野指针）}else {SListNode* previous = NULL; // taile的前驱结点  最终找到的是倒数第二个结点SListNode* tail = *pphead; //  previous的后驱结点  最终找到的是最后一个结点while (tail->next != NULL) { // 寻找 最后结点previous = tail; // 指向后指针tail = tail->next; // 指向下一个结点}free(tail); // 释放最后一个结点的内存空间previous->next = NULL; // 让倒数第二个结点指向NULL，而非最后一个结点，因为最后一个结点已经是“野指针”}
}
// 查找   返回存放x的结点的地址(一级指针)
SListNode* SListFind(SListNode* phead, ElemType x) {SListNode* current = phead; // 遍历链表while (current != NULL && current->data != x) { // 如果结点非空且当前结点的data不是x，，则找下一个current = current->next; // 找到下一个结点}return current; // current 会有两种情况，一种是存放x的结点，一种是没找到存放NULL空地址
}
// 在pos位置之前插入x
void SListInsert(SListNode** pphead, SListNode* pos, ElemType x) {if (*pphead == NULL) { // 若没结点，则不删除return;}// 1 pos 是否合法 2 pos 是否指向第一个结点 3 pos 指向第一个以后的结点if (pos == NULL) { // 地址不对printf("pos地址为空地址，不合法\n");return;}if (*pphead == pos) { // pos 指向第一个结点SListPushFront(pphead, x);  // 直接尾插一个xreturn;}SListNode* previous = *pphead; // pos// 找到前驱结点while (previous != NULL && previous->next != pos) { previous = previous->next; // 指向下一个结点} // previous 在退出循环的时候的两种情况：1 找到前驱 2 没找到，存NULL指针// 插入xif (previous != NULL) { // 找到了SListNode* NewNode = BuySListNode(x); // 申请一个新的结点NewNode->next = pos; // 新的结点指向 pos 结点previous->next = NewNode; // pos的前驱结点指向新的结点} else {printf("没找到！\n");return;}
}
// 删除pos位置的值
void SListErase(SListNode** pphead, SListNode* pos) {// 情况：1 pos 是否合法 2 pos 是否指向第一个结点 3 pos 指向第一个以后的结点 // 如果pos指向空，则结点的地址不合法if (pos == NULL) { printf("pos地址为空，不合法！");return;}// 如果pos指向第一个结点if (pos == *pphead) {SListPopFront(pphead); // 直接头删return;}SListNode* previous = *pphead; // pos 的前驱结点// 找到 pos 的前驱结点while (previous != NULL && previous->next != pos) {previous = previous->next; // 指向下一个结点}if (previous == NULL) {printf("未找到要删除的结点\n");return;}previous->next = pos->next; // 让 pos 前驱节点指向 pos 的后驱结点free(pos); // 释放pos结点的内存空间
}