《数据结构初阶》【顺序表 + 单链表 + 双向链表】

往期《数据结构初阶》回顾：
【时间复杂度 + 空间复杂度】

前言：

先聊些其他的东西！！！

在之前的博客中博主向大家信誓旦旦地宣布博主之后将持续更新的《数据结构初阶》这个系列的博客。
博客内容主要划分为：数据结构的介绍 + 数据结构的实现 + 数据结构的OJ练习，这三大板块的内容。
结果一动手发现——好家伙！三部分加起来有2万字，要是把OJ练习也塞进来，怕是要写成《数据结构从入门到放弃》了！
所以博主这里选择先将前两个板块的内容写成一篇博客，至于数据结构的OJ练习这个板块就单独成文。

---

温馨提示：这篇博客中的主要内容是代码，每个代码块中的代码都有非常详细的注释，相信各位勇士一定能征服这些数据结构！✨ （毕竟博主的注释写得比情书还用心💘）

什么是线性表？

线性表(Linear List)：是具有相同数据类型的n(n≥0)个数据元素的有限序列。

• 线性表是数据结构中最基本、最简单的一种结构。

• 线性表是一种在实际中广泛使用的数据结构。

• 常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑结构上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以 顺序结构 和 链式结构 的形式存储。

线性表有两种主要的存储结构：

1. 顺序存储结构（顺序表）

   • 用一组地址连续的存储单元依次存储线性表的元素
   • 可以通过数组实现

2. 链式存储结构（链表）

   • 用一组任意的存储单元存储线性表的元素

   • 每个元素除了存储数据外，还需要存储指向后继元素的指针

特性	顺序表 (Array List)	链表 (Linked List)
逻辑结构	1. 线性结构，元素按顺序排列 2. 通过下标直接表示逻辑关系	1. 线性结构，元素通过指针链接 2. 逻辑顺序由指针决定
物理结构	1. 连续内存空间存储 2. 物理顺序 = 逻辑顺序	1. 非连续内存存储（节点分散） 2. 物理顺序 != 逻辑顺序

什么是顺序表？

顺序表（Sequential List）：是线性表的顺序存储结构，即用一组地址连续的存储单元依次存储线性表中的数据元素。

顺序表在内存中的物理结构与逻辑结构一致，元素之间的顺序关系由存储位置决定。

顺序表的种类有哪些？

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素

--------------------------顺序表的静态存储实现-----------------------------// 定义顺序表的最大容量为7
#define N 7// 定义顺序表存储的数据类型为int（便于后续灵活修改数据类型）
typedef int SLDataType;// 定义静态顺序表的结构体
typedef struct SeqList
{size_t size;          //1.记录当前顺序表中有效数据的个数（即：表长）SLDataType array[N];  //2.静态分配的定长数组，用于存储顺序表元素
} SeqList;

2. 动态顺序表：使用动态开辟的数组存储

--------------------------顺序表的动态存储实现-----------------------------// 定义顺序表存储的数据类型（默认为int，可通过修改此处改变整个表的数据类型）
typedef int SLDataType;// 定义动态顺序表结构体
typedef struct SeqList
{size_t size;         //1.当前顺序表中实际存储的有效元素个数           size_t capacity;     //2.当前动态数组的总容量大小SLDataType* array;   //3.指向动态开辟的数组空间的首地址     
} SeqList;

什么是链表？

链表（Linked List） ：是一种线性表的 链式存储结构，它通过 指针（或引用） 将一组 零散的内存块（结点）串联起来，形成逻辑上的线性序列。

链表的种类有哪些？

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

单向或者双向

带头或者不带头

循环或者非循环

虽然链表有这么多的结构，但是我们实际中最常用的只有以下两种结构：

• 无头单向非循环链表：又名为 单链表
  • 结构最简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构
  • 如：哈希桶、图的邻接表等等。
• 带头双向循环链表：又名为 双向链表
  • 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表

---------------顺序表---------------

动态顺序表的实现

头文件

-------------------------------SeqList.h--------------------------------#pragma once//任务1：包含需要使用的头文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//任务2：定义顺序表的存储结构
typedef int SLDataType;
typedef struct SeqList
{//1.动态顺序的底层使用动态数组实现 ---> 一个SLDataType类型的指针（代表动态数组的首元素地址）//2.记录当前动态顺序中元素的数量 ---> 一个int类型的变量//3.记录动态顺序表的容量 ---> 一个int类型的变量SLDataType* a;int size;int capacity;
}SL;//任务3：声明动态顺表使用的工具函数
//1.扩容函数
void SLCheckCapacity(SL* ps);//任务4：声明顺序表的接口函数/*--------------------- 基础操作 ---------------------*/
//1.顺序表的初始化
//2.顺序表的销毁
//3.顺序表的打印/*--------------------- 插入删除操作 ---------------------*/
//4.顺序表的头插
//5.顺序表的尾插
//6.顺序表的头删
//7.顺序表的尾删/*--------------------- 指定位置操作 ---------------------*/
//8.顺序表的指定位置插入
//9.顺序表的指定位置删除
//10.顺序表的查找某个元素void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL ps);void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

实现文件

-------------------------------SeqList.c--------------------------------#include "SeqList.h"/*--------------------- 工具函数的实现 ---------------------*/
//1.实现：“动态顺序表的扩容”的工具函数
/*** @brief 检查并扩容顺序表* @param ps 指向顺序表结构的指针* @note 当size == capacity时自动扩容*       初始容量为4，后续每次扩容为原来的2倍*/void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){//1.先判断需要扩容的数量int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//2.再使用realloc进行空间的扩容SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SL)); //注意：这里先使用一个临时的指针指向开辟的这片空间，因为开辟空间可能开辟失败//2.1：使用if判断：扩容是否成功if (tmp == NULL){perror("realloc fail");return;}//3.最后更新指针和容量（扩容成功）ps->a = tmp;ps->capacity = newCapacity;}
}/*--------------------- 顺序表接口函数的实现 ---------------------*///1.实现：“顺序表的初始化”操作
/*** @brief 初始化顺序表* @param ps 指向顺序表结构的指针* @note 将顺序表置为空表，a指针置NULL*       size和capacity初始化为0*/
void SLInit(SL* ps)
{assert(ps);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}//2.实现：“顺序表的销毁”操作
/*** @brief 销毁顺序表* @param ps 指向顺序表结构的指针* @note 释放动态分配的数组内存*       并将所有成员重置为初始状态*/
void SLDestroy(SL* ps)
{assert(ps);free(ps->a); //顺序表的销毁相较于初始化唯一的不同在于销毁时需要将ps->a指向的动态开辟的空间释放掉；//同时我们也要注意我们的初始化操作中没有动态开辟空间ps->a = NULL;ps->size = 0;ps->capacity = 0;
}//3.实现：“顺序表的打印”操作
/*** @brief 打印顺序表内容* @param s 顺序表结构（传值）* @note 遍历打印所有有效元素*/
void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.a[i]);}printf("\n");
}//4.实现：“顺序表的尾插”操作
/*** @brief 顺序表尾部插入元素* @param ps 指向顺序表结构的指针* @param x 要插入的元素值* @note 先检查容量，不足则自动扩容*       时间复杂度O(1)（不考虑扩容）*/
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//1.直接在数组的尾部添加要插入的元素ps->a[ps->size] = x;//2.将顺序表中当前元素的数量+1ps->size++;
}//5.实现：“顺序表的头插”操作
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//1.将数组中的所有元素都向后挪动一位（从后向前处理元素）for (int i = ps->size - 1; i >= 0; i--){ps->a[i + 1] = ps->a[i];}//2.直接在数组的头部添加要插入的元素ps->a[0] = x;//3.将顺序表中当前元素的数量+1ps->size++;}//6.实现：“顺序表的尾删”操作
/*** @brief 顺序表尾部删除元素* @param ps 指向顺序表结构的指针* @note 只需减小size，不实际释放内存*       时间复杂度O(1)*/
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);//1.直接顺序表中当前的元素的数量-1ps->size--;
}//7.实现：“顺序表的头删”操作void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);//1.将数组中的所有的元素都向前移动一位（从前往后处理元素）for (int i = 1; i <= ps->size - 1; i++){ps->a[i - 1] = ps->a[i];}//2.将顺序表中当前的元素的数量-1ps->size--;
}//8.实现：“顺序表的指定位置的前面插入”操作
/*** @brief 在指定位置前面插入元素* @param ps 指向顺序表结构的指针* @param pos 插入位置（0-based）* @param x 要插入的元素值* @note 位置必须合法（0 <= pos <= size）*       自动检查扩容，时间复杂度O(n)*/
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//1.将指定位置及其之后的所有的元素都向后挪动一个位置（从后往前处理元素）for (int i = ps->size - 1; i >= pos; i--){ps->a[i + 1] = ps->a[i];}//2.直接在数组的pos位置上添加想要插入的元素ps->a[pos] = x;//3.将顺序表中当前元素的数量+1ps->size++;
}//9.实现：“顺序表的指定位置的删除”操作
/*** @brief 删除指定位置元素* @param ps 指向顺序表结构的指针* @param pos 删除位置（0-based）* @note 位置必须合法（0 <= pos < size）*       时间复杂度O(n)*/void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//1.将指定位置之后的所有的元素都向前挪动一个位置（从前向后处理元素）for (int i = pos + 1; i <= ps->size - 1; i++){ps->a[i - 1] = ps->a[i];}//2.将顺序表中当前元素的数量-1ps->size--;
}//10.实现：“顺序表的查找某个元素”操作
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
} 

测试文件

--------------------------------Test.c---------------------------------#include "SeqList.h"/*** @brief 测试顺序表基础功能* @note 包含初始化、销毁、尾部插入、打印等基础测试*/
void test01()
{SL sl;SLInit(&sl);// 测试头插SLPushFront(&sl, 5);SLPushFront(&sl, 3);printf("头插2个元素后: ");SLPrint(sl);  // 预期输出：3 5// 测试尾插SLPushBack(&sl, 7);SLPushBack(&sl, 9);printf("尾插2个元素后: ");SLPrint(sl);  // 预期输出：3 5 7 9// 测试头删SLPopFront(&sl);printf("头删1次后: ");SLPrint(sl);  // 预期输出：5 7 9// 测试尾删SLPopBack(&sl);printf("尾删1次后: ");SLPrint(sl);  // 预期输出：5 7SLDestroy(&sl);printf("\n");
}/*** @brief 测试顺序表高级功能* @note 测试指定位置插入/删除、查找等功能*       验证边界条件处理是否正确*/
void test02()
{SL sl;                  // 声明顺序表变量SLInit(&sl);            //准备测试数据 SLPushBack(&sl, 1);     SLPushBack(&sl, 2);     SLPushBack(&sl, 3);     SLPushBack(&sl, 4);     printf("初始数据: ");SLPrint(sl);            // 预期输出：1 2 3 4///测试指定位置插入SLInsert(&sl, 1, 99);   SLInsert(&sl, sl.size, 88); printf("插入后数据: ");SLPrint(sl);            // 预期输出：1 99 2 3 4 88//测试指定位置删除 SLErase(&sl, 1);        printf("删除后数据: ");SLPrint(sl);            // 预期输出：1 2 3 4 88///测试查找功能 int find = SLFind(&sl, 40); if (find < 0) {printf("没有找到！\n");  }else {printf("找到了！下标为%d\n", find);}SLDestroy(&sl);      
}int main()
{test01();test02();return 0;
}

运行结果

---------------单链表---------------

无头单向非循环链表的实现

头文件

-----------------------------SingleList.h-------------------------------#pragma once//任务1：包含要使用的头文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//任务2：定义单链表的存储结构
typedef int SLTDataType;typedef struct singleListNode
{//1.记录链表中节点的值 ---> 一个SLTDataType类型的变量//2.记录下一个节点的地址 ---> 一个struct singleListNode*类型的指针SLTDataType data;struct singleListNode* next;
}SLTNode;//任务3：声明单链表使用的工具函数
SLTNode* SLTCreateNode(SLTDataType x);//任务4：声明单链表的接口函数//0.单链表的打印//1.单链表的尾插
//2.单链表的头插
//3.单链表的尾删
//4.单链表的头删//5.单链表的查找
//6.单链表的指定节点的前驱节点插入
//7.单链表的指定节点的后继节点插入
//8.单链表的指定节点的删除
//9.单链表的指定节点的后继节点的删除
//10.单链表的销毁void SLTPrint(SLTNode* phead);void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);SLTNode* 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 SLTDestroy(SLTNode** pphead);   

实现文件

-----------------------------SingleList.c-------------------------------#include "SingleList.h"//0.实现：“单边表的节点创建”工具函数
/*** @brief 动态创建一个新的链表节点并初始化* @param x 要存储在新节点中的数据* @return 返回指向新创建节点的指针* @note 1. 使用malloc动态分配内存*       2. 检查内存分配是否成功*       3. 初始化节点的data和next成员*/SLTNode* SLTCreateNode(SLTDataType x)
{//1.节点空间的创建SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));//1.1：判断空间是否开辟成功if (newNode == NULL){perror("malloc fail");return NULL;}//2.节点参数的初始化newNode->data = x;newNode->next = NULL;//3.节点地址的返回return newNode;
}//1.实现：“单链表的打印”操作
/*** @brief 打印单链表的所有元素* @param phead 指向单链表头节点的指针* @note 遍历链表并打印每个节点的数据，最后以NULL结尾*/
void SLTPrint(SLTNode* phead)
{//1.定义一个临时的指针代替phead指针遍历整个链表SLTNode* pcur = phead;//2.进行循环遍历while (pcur != NULL){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//2.实现：“单链表的尾插”操作
/*** @brief 在单链表的尾部插入新节点* @param pphead 指向头节点指针的指针（二级指针，用于修改头节点）* @param x 要插入的数据* @note 1. 如果链表为空（*pphead == NULL），新节点成为头节点*       2. 如果链表非空，遍历找到尾节点，并在其后插入新节点*/
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead); //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作//1.创建一个新节点并将其初始化SLTNode* newNode = SLTCreateNode(x);//2.情况1：处理单链表是空链表的情况if (*pphead == NULL){//1.1：更新头指针*pphead = newNode;}//3.情况2：处理单链表是非空链表的情况else{//3.1：遍历链表找到尾节点的位置SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//3.2：将新节点链接到链表的尾部ptail->next = newNode;}
}//3.实现：“单链表的头插”操作
/*** @brief 在单链表的头部插入新节点* @param pphead 指向头节点指针的指针（二级指针，用于修改头节点）* @param x 要插入的数据* @note 1. 新节点会成为新的头节点*       2. 无论链表是否为空都适用*/
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead); //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作//1.创建一个新节点并将其初始化SLTNode* newNode = SLTCreateNode(x);//2.将新节点链接到链表的头部    (注意：这里无论链表的是空链表还是非空链表都是符合)newNode->next = *pphead;//3.更新头指针*pphead = newNode;
}//4.实现：“单链表的尾删”操作
/*** @brief 删除单链表的尾节点* @param pphead 指向头节点指针的指针（二级指针）* @note 1. 链表不能为空*       2. 处理单节点和多节点不同情况*       3. 释放尾节点内存并维护链表结构*/void SLTPopBack(SLTNode** pphead)
{assert(pphead);  //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作assert(*pphead); //断言检查2：确保单链表是非空单链表，防止对空链表进行删除节点的操作//情况1：处理单链表中只有一个节点的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//情况2：处理单链表中节点不止一个的情况else{//1.找到尾节点前面的那个节点的位置SLTNode* prev = *pphead;while (prev->next->next != NULL){prev = prev->next;}//2.断开尾节点的链接 + 释放尾节点的内存//2.1：定义指针指向要删除的节点SLTNode* del = prev->next;//2.2：断开要删除的节点的链接prev->next = prev->next->next;//2.3：释放要删除的节点的内存free(del);//2.4：将指向被删除节点的指针都置空del = NULL;}
}//5.实现：“单链表的头删”操作
/*** @brief 删除单链表的头节点* @param pphead 指向头节点指针的指针（二级指针）* @note 1. 链表不能为空*       2. 释放原头节点内存*       3. 更新头指针指向下一个节点*/
void SLTPopFront(SLTNode** pphead)
{assert(pphead);  //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作assert(*pphead); //断言检查2：确保单链表是非空单链表，防止对空链表进行删除节点的操作//1.定义指向头节点的下一个节点的指针SLTNode* next = (*pphead)->next;//2.释放头指针指向的头节点的内存free(*pphead);//3.更新头指针  （注意：这里并没有将指向被删除节点的指针*pphead置空，原因是：*pphead会被更新为next指针所在的位置并未变成野指针）*pphead = next;
}//6.实现：“单链表的查找”操作
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur != NULL){if (pcur->data == x)  return pcur;pcur = pcur->next;}return NULL;
}//7.实现：“单链表的指定节点的前驱节点插入”操作
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);  //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作assert(*pphead); //断言检查2：确保单链表是非空单链表，防止对空链表进行指定节点之前插入的操作assert(pos); //断言检查3：确保pos指针有效，防止对空节点之前插入节点SLTNode* newNode = SLTCreateNode(x);//情况1：处理pos是头节点的情况 --> 相当于头插if (pos == *pphead){SLTPushFront(pphead, x);}//情况2：处理pos不是头节点的情况else{//1.找到pos节点前面那个节点的位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//2.链接新节点：prev -> newNode -> pos （新插入的节点的前后节点有独立的指针指向，所以这里的链接随意）prev->next = newNode;newNode->next = pos;}}//8.实现：“单链表的指定节点的后继节点插入”操作
/*** @brief 在单链表指定节点后插入新节点* @param pos 要在其后插入新节点的目标节点指针* @param x 要插入的新数据* @note 1. 不需要头指针，直接操作pos节点*       2. 时间复杂度O(1)*       3. 新节点插入在pos和原pos->next之间*/void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos); //断言检查1：确保pos指针有效，防止对空节点之后插入节点SLTNode* newNode = SLTCreateNode(x);//链接新节点：pos -> newNode -> pos->next 新插入的节点的后一个节点没有独立的指针指向，所以这里的链接顺序必须是下面的这个顺序//同时这也是为什么我们传参数的时候之传入一个指针即可，因为一个指针就可以管控newNode节点前后的两个节点//1.先链接新节点的下一个节点newNode->next = pos->next;//2.再链接新节点的上一个节点pos->next = newNode;
}//9.实现：“单链表的指定节点的删除”操作
/*** @brief 删除单链表中的指定节点* @param pphead 指向头节点指针的指针（二级指针）* @param pos 要删除的目标节点指针* @note 1. 处理pos是头节点和非头节点两种情况*       2. 需要维护链表结构完整性*       3. 释放被删除节点的内存*/
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);  //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作assert(*pphead); //断言检查2：确保单链表是非空单链表，防止对空链表进行指定节点的删除的操作assert(pos); //断言检查3：确保pos指针有效，防止对空节点进行删除//情况1：处理pos头节点的情况 ---> 相当于头删if (pos == *pphead){SLTPopFront(pphead);}//情况2：处理pos非头节点的情况else{//1.找到要删除节点pos之前的节点位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//2.断开pos节点的链接 + 释放pos节点的内存//2.1：断开链接prev->next = prev->next->next;//2.2：释放内存free(pos);//2.3:将指向被删除节点的指针置为空pos = NULL;}
}//10.实现：“单链表的指定节点的后继节点删除”操作
/*** @brief 删除指定节点后的节点* @param pos 指定节点指针（要删除其后的节点）* @note 1. 直接操作pos节点的next指针*       2. 时间复杂度O(1)*       3. 需要确保pos->next存在（不能是尾节点）*/
void SLTEraseAfter(SLTNode* pos)
{assert(pos); //断言检查1：确保pos指针有效，防止对空节点之后进行删除//1.定义指针指向要删除的节点SLTNode* del = pos->next;//2.断开要删除的节点的链接pos->next = pos->next->next;//3.释放要删除的节点的内存free(del);//4.将指向被删除的节点的中指针置空del = NULL;
}//11.实现：“单链表的销毁”操作
/*** @brief 销毁整个单链表，释放所有节点内存* @param pphead 指向头节点指针的指针（二级指针）* @note 1. 遍历链表逐个释放节点*       2. 最后将头指针置NULL*       3. 时间复杂度O(n)*/
void SLTDestroy(SLTNode** pphead)
{assert(pphead);  //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作//1.定义临时指针代替*pphead进行单链表的遍历SLTNode* pcur = *pphead;while (pcur != NULL){//2.定义指针存储临时指针的下一个遍历的位置SLTNode* next = pcur->next;//3.释放要删除的节点的内存free(pcur);//4.更新临时指针pcur = next; //指针指向空间被释放后并没有进行置空来防止其为野指针，因为我们更新了指针}//5.将链表的头指针置空防止其为野指针*pphead = NULL;
}

测试文件

---------------------------------Test.c----------------------------------#include "SingleList.h"void TestSLT1() 
{printf("\n========== 测试1：创建和打印 ==========\n");SLTNode* plist = NULL;SLTPrint(plist);  // 预期输出：NULL// 测试尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);printf("尾插1,2,3后: ");SLTPrint(plist);  // 预期输出：1->2->3->NULL// 测试头插SLTPushFront(&plist, 0);SLTPushFront(&plist, -1);printf("头插0,-1后: ");SLTPrint(plist);  // 预期输出：-1->0->1->2->3->NULL
}void TestSLT2() 
{printf("\n========== 测试2：删除操作 ==========\n");SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);printf("初始链表: ");SLTPrint(plist);  // 1->2->3->NULL// 测试尾删SLTPopBack(&plist);printf("尾删后: ");SLTPrint(plist);  // 1->2->NULL// 测试头删SLTPopFront(&plist);printf("头删后: ");SLTPrint(plist);  // 2->NULL// 删除最后一个节点SLTPopBack(&plist);printf("删除最后一个节点后: ");SLTPrint(plist);  // NULL
}void TestSLT3() 
{printf("\n========== 测试3：查找和插入 ==========\n");SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 4);printf("初始链表: ");SLTPrint(plist);  // 1->2->4->NULL// 测试查找SLTNode* pos = SLTFind(plist, 2);if (pos) {printf("找到节点2，在其后插入3\n");SLTInsertAfter(pos, 3);SLTPrint(plist);  // 1->2->3->4->NULL}pos = SLTFind(plist, 1);if (pos) {printf("找到节点1，在其前插入0\n");SLTInsert(&plist, pos, 0);SLTPrint(plist);  // 0->1->2->3->4->NULL}
}void TestSLT4() 
{printf("\n========== 测试4：删除指定节点 ==========\n");SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);printf("初始链表: ");SLTPrint(plist);  // 1->2->3->4->NULL// 测试删除中间节点SLTNode* pos = SLTFind(plist, 2);if (pos) {printf("删除节点2\n");SLTErase(&plist, pos);SLTPrint(plist);  // 1->3->4->NULL}// 测试删除后继节点pos = SLTFind(plist, 3);if (pos) {printf("删除节点3的后继\n");SLTEraseAfter(pos);SLTPrint(plist);  // 1->3->NULL}
}void TestSLT5() 
{printf("\n========== 测试5：销毁链表 ==========\n");SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);printf("销毁前: ");SLTPrint(plist);  // 1->2->3->NULLSLTDestroy(&plist);printf("销毁后: ");SLTPrint(plist);  // NULL// 测试销毁后能否继续操作SLTPushBack(&plist, 5);printf("重新插入后: ");SLTPrint(plist);  // 5->NULLSLTDestroy(&plist);
}void TestSLT6() 
{printf("\n========== 测试6：边界测试 ==========\n");SLTNode* plist = NULL;// 测试空链表操作printf("尝试对空链表头删: ");//SLTPopFront(&plist);  // 应该触发断言printf("尝试对空链表尾删: ");//SLTPopBack(&plist);   // 应该触发断言// 测试单节点操作SLTPushFront(&plist, 1);printf("单节点链表: ");SLTPrint(plist);  // 1->NULLSLTPopBack(&plist);printf("删除后: ");SLTPrint(plist);  // NULL
}int main() 
{TestSLT1();  // 基本插入测试TestSLT2();  // 基本删除测试TestSLT3();  // 查找和插入测试TestSLT4();  // 指定位置删除测试TestSLT5();  // 销毁测试//TestSLT6();  // 边界测试printf("\n所有测试完成!\n");return 0;
}

运行结果

心得总结

0.单链表的打印1.单链表的尾插
2.单链表的头插
3.单链表的尾删
4.单链表的头删5.单链表的查找
6.单链表的指定节点的前驱节点插入
7.单链表的指定节点的后继节点插入
8.单链表的指定节点的删除
9.单链表的指定节点的后继节点的删除
10.单链表的销毁

哪些操作使用了断言？都使用了哪些断言？

1. 除了 0.单链表的打印 和 5.单链表的查找 操作没有使用断言，其余的操作都使用了断言
2. 只要是指定节点的操作，都要添加这一条断言：assert(pos); //断言检查1：确保pos指针有效
3. 只要是涉及删除的操作都使用了这一条断言：assert(*pphead); //断言检查2：确保单链表是非空单链表
4. 除了 7.单链表的指定节点的后继节点插入 和 9.单链表的指定节点的后继节点的删除 这两操作的接口函数的形参中没有SLTNode** pphead，导致断言中没有 assert(pphead); //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作，其他有断言的函数中都有这个断言。并且这两个函数中且只有这一个断言：assert(pos); //断言检查1：确保pos指针有效

1.单链表的尾插
2.单链表的头插
assert(pphead); //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作
------------------------------------------------------------------------3.单链表的尾删
4.单链表的头删 
10.单链表的销毁
assert(pphead);  //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作
assert(*pphead); //断言检查2：确保单链表是非空单链表，防止对空链表进行删除节点的操作------------------------------------------------------------------------6.单链表的指定节点的前驱节点插入
assert(pphead);  //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作
assert(*pphead); //断言检查2：确保单链表是非空单链表，防止对空链表进行指定节点之前插入的操作
assert(pos); //断言检查3：确保pos指针有效，防止对空节点之前插入节点8.单链表的指定节点的删除
assert(pphead);  //断言检查1：确保传入的二级指针pphead是有效的，防止对空指针进行解引用的操作
assert(*pphead); //断言检查2：确保单链表是非空单链表，防止对空链表进行指定节点的删除的操作
assert(pos); //断言检查3：确保pos指针有效，防止对空节点进行删除------------------------------------------------------------------------7.单链表的指定节点的后继节点插入
assert(pos); //断言检查1：确保pos指针有效，防止对空节点之后插入节点9.单链表的指定节点的后继节点的删除
assert(pos); //断言检查1：确保pos指针有效，防止对空节点之后进行删除

哪些操作是需要分情况处理的？都分为哪些情况？

1.单链表的尾插

• 情况1：处理单链表是空链表的情况
• 情况2：处理单链表是非空链表的情况

3.单链表的尾删

• 情况1：处理单链表中只有一个节点的情况
• 情况2：处理单链表中节点不止一个的情况

6.单链表的指定节点的前驱节点插入

• 情况1：处理pos是头节点的情况 --> 相当于头插
• 情况2：处理pos不是头节点的情况

8.单链表的指定节点的删除

• 情况1：处理pos头节点的情况 —> 相当于头删
• 情况2：处理pos非头节点的情况

---------------双向链表---------------

带头双向循环链表的实现

头文件

-----------------------------DoubleList.h--------------------------------#pragma once//任务1：包含要使用的头文件
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>//任务2：定义双向链表的存储结构
typedef int DLTDataType;typedef struct DoubleListNode
{//1.存储双向链表中的节点的值 --> 一个DLTDataType类型的变量//2.记录节点的前驱节点的位置 --> 一个struct DoubleListNode*类型的指针//3.记录节点的后继节点的位置 --> 一个struct DoubleListNode*类型的指针DLTDataType data;struct DoubleListNode* prev;struct DoubleListNode* next;
}DLTNode;//任务3：声明双向链表需要使用辅助工具函数
//1.用于创建双向链表的节点
DLTNode* DLTCreateNode(DLTDataType x);//任务4：声明双向链表的接口函数
//1.双向链表的初始化
//2.双向链表的销毁
//3.双向链表打印//3.双向链表的尾插
//4.双向链表的头插
//5.双向链表的尾删
//6.双向链表的头删//7.双向链表的查找
//8.双向链表的指定节点之后插入
//9.双向链表的指定节点的删除//void DLTInit(DLTNode** pphead);
DLTNode* DLTInit();
void DLTDestroy(DLTNode* phead);
void DLTPrint(DLTNode* phead);void DLTPushBack(DLTNode* phead, DLTDataType x);
void DLTPushFront(DLTNode* phead, DLTDataType x);
void DLTPopBack(DLTNode* phead);
void DLTPopFront(DLTNode* phead);DLTNode* DLTFind(DLTNode* phead, DLTDataType x);
void DLTInsert(DLTNode* pos, DLTDataType x);
void DLTErase(DLTNode* pos);

实现文件

-----------------------------DoubleList.c--------------------------------#include "DoubleList.h"//0.实现：“用于创建双向链表的节点”的工具函数
/*** @brief 申请一个新节点并初始化* @param x 节点存储的数据* @return 返回新节点的指针* @note 1. 动态分配内存*       2. 初始化前后指针都指向自己*/
DLTNode* DLTCreateNode(DLTDataType x)
{DLTNode* newNode = (DLTNode*)malloc(sizeof(DLTNode));if (newNode == NULL){perror("malloc fail");return NULL;}newNode->data = x;newNode->prev = newNode;newNode->next = newNode;return newNode;
}//1.实现：“双向链表的初始化”操作
/*** @brief 初始化双向链表* @return 返回哨兵位的指针* @note 创建一个值为-1的哨兵位节点*//*
void DLTInit(DLTNode** pphead)
{//双向链表的初始化本质就是：给双向链表创建一个哨兵节点*pphead = DLTCreateNode(-1);//注意：双向链表的哨兵节点中存储的值并无实际的意义，所以这里我们将其赋值为-1
}*/
//由于双向链表的其他的接口函数的形式参数的中都是使用的一个*的值传递
//为了保持一致性，这里我们重写DLTInint函数
DLTNode* DLTInit()
{DLTNode* phead = DLTCreateNode(-1);return phead;
}//2.实现：“双向链表的销毁”操作
/*** @brief 销毁双向链表* @param phead 哨兵位指针* @note 释放所有节点包括哨兵位*/
void DLTDestroy(DLTNode* phead) //注意：这里我们传参的时候只是用了一个*，是值传递：所以调用完DLTDestroy函数之后我们还要手动的将phead指针置空
{assert(phead); //作用：保证传入的哨兵节点的有效性，防止对空指针进行解引用DLTNode* pcur = phead->next;while (pcur != phead){DLTNode* next = pcur->next;free(pcur);pcur = next;}// 注意：相较于单链表双向链表还需要将哨兵节点置空free(phead);//注意：这里我们并没用将哨兵节点置为空，原因是：此处phead是函数的局部变量，对其置NULL不会影响外部实参//所以：调用者必须自行处理外部指针
}//3.实现：“双向链表的打印”操作
/*** @brief 打印双向链表的所有元素（不打印哨兵位）* @param phead 指向双向链表哨兵位的指针* @note 从哨兵位的下一个节点开始遍历，直到回到哨兵位*/
void DLTPrint(DLTNode* phead)
{assert(phead); //作用：保证传入的哨兵节点的有效性，防止对空指针进行解引用DLTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//4.实现：“双向链表的尾插”操作
/*** @brief 双向链表尾插* @param phead 哨兵位指针* @param x 要插入的数据* @note 将新节点插入到哨兵位之前*/
void DLTPushBack(DLTNode* phead, DLTDataType x)
{assert(phead); //作用：保证传入的哨兵节点的有效性，防止对空指针进行解引用DLTNode* newNode = DLTCreateNode(x);//双向链表的尾插涉及到三个节点：//1.哨兵节点：phead//2.尾节点：phead->prev//3.要插入的节点：newNode//总共要出连接四条线才能完成插入//1.将“要插入的节点”和其他的节点产生联系newNode->prev = phead->prev;newNode->next = phead;//2.将“哨兵节点 + 尾节点”和要插入的节点产生联系phead->prev->next = newNode;phead->prev = newNode;
}//5.实现：“双向链表的头插”操作
/*** @brief 双向链表头插* @param phead 哨兵位指针* @param x 要插入的数据* @note 将新节点插入到哨兵位之后*/
void DLTPushFront(DLTNode* phead, DLTDataType x)
{assert(phead); //作用：保证传入的哨兵节点的有效性，防止对空指针进行解引用DLTNode* newNode = DLTCreateNode(x);//双向链表的头插涉及到三个节点：//1.哨兵节点：phead//2.首元节点：phead->next//3.要插入的节点：newNode//总共要出连接四条线才能完成插入//1.将“要插入的节点”和其他节点建立连接newNode->prev = phead;newNode->next = phead->next;//2.将“哨兵节点 + 首元节点”和要插入的节点之间建立连接phead->next = newNode;phead->next->next->prev = newNode;//这里一般大家会交换一下这两个连接的顺序，这样的话不用写这么多的箭头phead->next->next->prev//又或者有一部分人会将phead->next替换为newNode，这样也可以省去一个箭头//这里我没有：1.交换连接的顺序 2.使用newNode进行替换 //只是为告诉大家：这里的连接正常连就行，仅仅使用phead即可完成}//6.实现：“双向链表的尾删”操作
void DLTPopBack(DLTNode* phead)
{assert(phead);//作用：保证传入的哨兵节点的有效性，防止对空指针进行解引用assert(phead->next != phead); //作用：确保双向链表非空，防止对空链表进行删除操作（双向链表为空的判断依据：phead->next == phead）//双向链表的尾删涉及到三个节点：//1.哨兵节点：phead//2.尾节点的前一个节点：phead->prev->prev//3.要插入的节点（尾节点）：phead->prev//总共要出调整两条线才能完成删除//链表删除一个节点的步骤：//1.定义一个指针指向要删除的节点//2.重新调整节点的连接//3.将要删除的节点的空间释放 + 该指针置空//1.DLTNode* del = phead->prev;//2.phead->prev = phead->prev->prev;phead->prev->next = phead;//注意：上面的这两个连接的顺序交不交换完全没有影响（既不会出现错误，也不会带来简化）//但是绝大多数人在调整节点的连接的时候会使用上之前已经定义的指针del来简化连接的箭头//但是这里我还是没有进行简化，因为还是想明确未删除只是使用phead并且不需要考虑连接的顺序就可以实现//我们定义del指针只是用来释放删除的节点而已//3.free(del);del = NULL;
}//7.实现：“双向链表的头删”操作
/*** @brief 双向链表头删* @param phead 哨兵位指针* @note 删除哨兵位后的一个节点*/
void DLTPopFront(DLTNode* phead)
{assert(phead);//作用：保证传入的哨兵节点的有效性，防止对空指针进行解引用assert(phead->next != phead); //作用：确保双向链表非空，防止对空链表进行删除操作（双向链表为空的判断依据：phead->next == phead）//双向链表的头删涉及到三个节点：//1.哨兵节点：phead//2.首元节点的下一个节点：phead->next->next//3.要插入的节点(首元节点)：phead->next//总共要出调整两条线才能完成删除//链表删除一个节点的步骤：//1.定义一个指针指向要删除的节点//2.重新调整节点的连接//3.将要删除的节点的空间释放 + 该指针置空//1.DLTNode* del = phead->next;//2.phead->next = phead->next->next;phead->next->prev = phead;//3.free(del);del = NULL;
}//8.实现：“双向链表的查找”操作
/*** @brief 在双向链表中查找值为x的节点* @param phead 哨兵位指针* @param x 要查找的值* @return 找到返回节点指针，否则返回NULL*/
DLTNode* DLTFind(DLTNode* phead, DLTDataType x)
{DLTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//9.实现：“双向链表的指定节点之后插入”操作
void DLTInsert(DLTNode* pos, DLTDataType x)
{assert(pos); //作用：保证传入的节点的有效性，防止对空指针进行解引用DLTNode* newNode = DLTCreateNode(x);//双向链表的插入涉及到三个节点：//1.插入节点的前一个节点：pos//2.插入节点的后一个节点：pos->next//3.要插入的节点：newNode//总共要出调整四条线才能完成插入操作//1.将“要插入的节点”和其他节点建立连接newNode->prev = pos;newNode->next = pos->next;//2.将“插入节点的前一个节点 + 插入节点的前一个节点” 和要插入的节点建立连接pos->next = newNode;pos->next->next->prev = newNode;
}//10.实现：“双向链表的指定节点的删除”操作
/*** @brief 删除pos节点* @param pos 要删除的节点指针* @note 不能删除哨兵位*/
void DLTErase(DLTNode* pos)
{assert(pos); //作用：保证传入的节点的有效性，防止对空指针进行解引用//双向链表的删除涉及到三个节点：//1.删除节点的前一个节点：pos->prev//2.删除节点的后一个节点：pos->next//3.要删除的节点：pos//总共要调整两条线才能完成删除//链表删除一个节点的步骤：//1.定义一个指针指向要删除的节点//2.重新调整节点的连接//3.将要删除的节点的空间释放 + 该指针置空//1.//2.pos->prev->next = pos->next;pos->next->prev = pos->prev;//注：交换连接顺序没有任何影响，只能这么写//3.free(pos);//pos = NULL; 外面置空
}    

测试文件

---------------------------------Test.c----------------------------------#include "DoubleList.h"
#include <stdio.h>
#include <assert.h>// 打印分隔线，用于区分不同的测试环节
void print_separator() 
{printf("------------------------\n");
}// 测试双向链表的初始化、尾插、头插和打印功能
void test01() 
{printf("开始测试双向链表的初始化、尾插、头插和打印功能\n");/*第一代双向链表的初始化方式：DLTNode* head = NULL;DLTInit(&head);*/DLTNode* head = DLTInit();printf("双向链表已初始化\n");printf("执行尾插操作，插入 1\n");DLTPushBack(head, 1);printf("当前双向链表内容为：");DLTPrint(head);printf("执行尾插操作，插入 2\n");DLTPushBack(head, 2);printf("当前双向链表内容为：");DLTPrint(head);printf("执行头插操作，插入 3\n");DLTPushFront(head, 3);printf("当前双向链表内容为：");DLTPrint(head);printf("执行头插操作，插入 4\n");DLTPushFront(head, 4);printf("当前双向链表内容为：");DLTPrint(head);DLTDestroy(head);printf("双向链表已销毁\n");print_separator();
}// 测试双向链表的尾删和头删功能
void test02() 
{printf("开始测试双向链表的尾删和头删功能\n");DLTNode* head = DLTInit();printf("执行尾插操作，插入 1\n");DLTPushBack(head, 1);printf("执行尾插操作，插入 2\n");DLTPushBack(head, 2);printf("执行尾插操作，插入 3\n");DLTPushBack(head, 3);printf("插入元素后，当前双向链表内容为：");DLTPrint(head);printf("执行尾删操作\n");DLTPopBack(head);printf("尾删操作后，当前双向链表内容为：");DLTPrint(head);printf("执行头删操作\n");DLTPopFront(head);printf("头删操作后，当前双向链表内容为：");DLTPrint(head);DLTDestroy(head);printf("双向链表已销毁\n");print_separator();
}// 测试双向链表的查找、指定节点后插入和指定节点删除功能
void test03() 
{printf("开始测试双向链表的查找、指定节点后插入和指定节点删除功能\n");DLTNode* head = DLTInit();printf("执行尾插操作，插入 1\n");DLTPushBack(head, 1);printf("执行尾插操作，插入 3\n");DLTPushBack(head, 3);printf("插入元素后，当前双向链表内容为：");DLTPrint(head);printf("查找值为 1 的节点\n");DLTNode* pos = DLTFind(head, 1);if (pos != NULL) {printf("已找到值为 1 的节点，执行在该节点后插入 2 的操作\n");DLTInsert(pos, 2);printf("插入操作后，当前双向链表内容为：");DLTPrint(head);printf("删除值为 1 的节点\n");DLTErase(pos);printf("删除操作后，当前双向链表内容为：");DLTPrint(head);}else {printf("未找到值为 1 的节点\n");}DLTDestroy(head);printf("双向链表已销毁\n");print_separator();
}int main() 
{test01();test02();test03();printf("所有双向链表接口函数测试完成\n");return 0;
}

运行结果

心得总结

链表类型	空链表判断	断言示例
单链表	*pphead == NULL	assert(*pphead);
双向带头链表	phead->next == phead	assert(phead->next != phead);

顺序表和链表的区别有哪些？

对比维度	顺序表（数组实现）	链表
存储结构	物理存储连续	逻辑连续，物理存储不连续（通过指针链接）
随机访问	支持，O(1) 时间复杂度	不支持，需遍历，O(n) 时间复杂度
插入/删除效率	可能需要搬移元素，平均 O(n)	只需修改指针，已知位置时 O(1)
空间开销	只需存储数据，无额外开销	每个结点需额外存储指针（存储密度较低）
扩容方式	动态顺序表需重新分配内存并拷贝数据（代价高）	无容量限制，随时插入新结点
内存碎片	无	可能产生碎片（频繁动态分配释放）
缓存命中率	高（空间局部性好）	低（结点分散存储）
适用场景	1. 频繁访问 2. 数据量可预估 3. 强调存储效率	1. 频繁插入/删除 2. 数据规模变化大 3. 内存灵活性要求高