目录
1 链表是什么
1.1 逻辑结构
链表是一种线性数据结构，由一系列结点（Node）组成。每个结点包含两个主要部分：
- 数据域（Data）：存储结点的实际数据。
- 指针域（Next）：存储指向下一个结点的指针。
所有结点通过指针相连，形成一个链式结构。链表中的第一个结点称为头结点（Head Node）。
1.2 物理结构
与数组不同，链表中的结点可以分散在内存的任意位置。每个结点包含两个主要部分：
- 数据域（Data）：存储结点的实际数据。
- 指针域（Next）：存储指向下一个结点的指针。
通过指针将各个结点连接起来，形成一个链式结构。这种方式使得链表的结点无需连续存储，提供了更大的灵活性。
1.3 相关概念
- 结点（Node）：链表的基本单位，包含数据域和指针域。
- 数据域（Data）：存储结点的实际数据。
- 指针域（Next）：存储指向下一个结点的地址。
- 头结点（Head Node）：链表的第一个结点，通常用一个特殊的指针（头指针）指向它。
- 尾结点（Tail Node）：链表的最后一个结点，其指针域通常为 None，表示链表的结束。
- 前驱结点（Predecessor Node）：对于给定结点，其前驱结点是链表中位于该结点之前的结点。
- 后续结点（Successor Node）：对于给定结点，其后续结点是链表中位于该结点之后的结点。
在链表中，n 个结点离散分配，彼此通过指针相连。
确定一个链表只需头指针，通过头指针可以访问和遍历整个链表。
2 链表的分类
链表可以根据其结构和特性分为以下几种类型：
2.1 单链表
- 每个结点包含一个数据域和一个指针域，指针域指向下一个结点。
- 结点只能向前遍历，不能向后遍历。
- 每个结点：只有一个前驱结点和一个后续结点。
- 头结点：没有前驱结点，但有一个后续结点（即第二个结点）。
- 尾结点：没有后续结点，但有一个前驱结点（即倒数第二个结点）。
- 遍历：从头指针开始，通过每个结点的 next 指针逐个访问结点，直到 next 为 NULL。
2.2 双链表
- 每个结点包含一个数据域和两个指针域，一个指向前一个结点，另一个指向后一个结点。
- 支持双向遍历，便于在链表中前后移动。
- 每个结点：有一个前驱结点和一个后续结点。
- 头结点：没有前驱结点，但有一个后续结点（即第二个结点）。
- 尾结点：没有后续结点，但有一个前驱结点（即倒数第二个结点）。
- 遍历：
- 正向遍历：从头指针开始，通过每个结点的 next 指针逐个访问结点，直到 next 为 NULL。
- 反向遍历：从尾结点开始，通过每个结点的 prev 指针逐个访问结点，直到 prev 为 NULL。
2.3 循环单链表
- 单链表的最后一个结点的指针指向头结点，形成一个环。
- 适用于需要从任意位置开始遍历整个链表的场景。
- 每个结点：有一个前驱结点和一个后续结点。
- 头结点：有一个前驱结点（即尾结点）和一个后续结点（即第二个结点）。
- 尾结点：有一个前驱结点（即倒数第二个结点）和一个后续结点（即头结点）。
- 遍历：从头指针开始，通过每个结点的 next 指针逐个访问结点，直到再次回到头结点（即 next 指向头结点）。
2.4 循环双链表
- 双链表的首尾相接，形成一个闭环。
- 支持双向遍历，并且可以从任意位置开始遍历整个链表。
- 每个结点：有一个前驱结点和一个后续结点。
- 头结点：有一个前驱结点（即尾结点）和一个后续结点（即第二个结点）。
- 尾结点：有一个前驱结点（即倒数第二个结点）和一个后续结点（即头结点）。
- 遍历：
- 正向遍历：从头指针开始，通过每个结点的 next 指针逐个访问结点，直到再次回到头结点（即 next 指向头结点）。
- 反向遍历：从尾结点开始，通过每个结点的 prev 指针逐个访问结点，直到再次回到头结点（即 prev 指向头结点）。
2.5 静态链表
- 使用数组来模拟链表的行为，每个数组元素代表一个结点，包含数据和指向下一个结点的索引。
- 适用于内存受限或需要固定大小的链表场景。
- 每个结点：有一个前驱结点和一个后续结点（通过索引表示）。
- 头结点：没有前驱结点，但有一个后续结点（即第二个结点）。
- 尾结点：没有后续结点，但有一个前驱结点（即倒数第二个结点）。
- 遍历：从头指针开始，通过每个结点的 next 索引逐个访问结点，直到 next 为 -1（表示链表结束）。
3 链表的优缺点
3.1 优点
1. 插入和删除操作效率高
在链表中插入和删除结点的时间复杂度为 O(1)，前提是已经找到了要操作的结点位置。这比数组的插入和删除操作（时间复杂度为 O(n)）更高效。
插入操作：
已知位置：假设已经找到了要插入位置的前一个结点（记为 prev_node），只需要执行以下步骤：
- 创建新结点 new_node。
- 将 new_node 的 next 指针指向 prev_node 的下一个结点。
- 将 prev_node 的 next 指针指向 new_node。
- 注意：2 和 3 的顺序不能颠倒。
这些操作都是常数时间内完成的，因此时间复杂度为 O(1)。
删除操作：
已知位置：假设已经找到了要删除的结点（记为 node_to_delete），只需要执行以下步骤：
- 找到 node_to_delete 的前一个结点（记为 prev_node）。
- 将 prev_node 的 next 指针指向 node_to_delete 的下一个结点。
这些操作也是常数时间内完成的，因此时间复杂度为 O(1)。
2. 动态扩展性能好
链表不需要预先指定固定的大小，可以随时动态增长或缩小。这种灵活性使得链表非常适合处理不确定大小的数据集合，避免了数组需要重新分配内存和复制数据的问题。
3.2 缺点
1. 查找效率低
由于链表中的结点不是连续存储的，无法像数组那样通过索引直接访问结点。查找特定结点时，必须从头结点开始逐个遍历，直到找到目标结点。这导致链表的随机访问效率较低，时间复杂度为 O(n)。
- 最坏情况：如果目标结点是链表的最后一个结点，或者目标结点不存在，需要遍历整个链表。在这种情况下，时间复杂度为 O(n)，其中 n 是链表的长度。
- 平均情况：即使在平均情况下，也需要遍历链表的一半结点，时间复杂度仍然为 O(n)。
- 最好情况：如果目标结点恰好是头结点，时间复杂度为 O(1)。但这只是特殊情况，不具有普遍性。
2. 额外的存储空间
每个结点除了存储实际数据外，还需要存储指向下一个结点的指针。这会占用额外的存储空间，使得链表在存储相同数量的数据元素时，需要比数组更多的内存。
3.3 与数组的对比
| 特性 | 链表 | 数组 |
|---|---|---|
| 数据结构 | 非连续存储，通过指针连接 | 连续存储，通过索引访问 |
| 初始化 | 需要手动创建头结点和结点 | 定义时指定大小，自动分配内存 |
| 存储方式 | 分散在内存中，每个结点包含数据和指针 | 连续存储在内存中，每个元素紧邻 |
| 插入操作 | 在已知位置插入结点时间复杂度为 O(1) | 在任意位置插入元素时间复杂度为 O(n)（需要移动元素） |
| 删除操作 | 在已知位置删除结点时间复杂度为 O(1) | 在任意位置删除元素时间复杂度为 O(n)（需要移动元素） |
| 查找操作 | 查找特定元素时间复杂度为 O(n)（需要遍历） | 查找特定元素时间复杂度为 O(1)（通过索引直接访问） |
| 动态扩展 | 可以随时动态增长或缩小，不需要重新分配内存 | 需要预先指定大小，动态扩展需要重新分配内存和复制数据 |
| 内存使用 | 每个结点需要额外的指针空间，总体内存使用较高 | 每个元素只占用数据所需的空间，总体内存使用较低 |
| 访问方式 | 通过指针逐个访问结点 | 通过索引直接访问元素 |
| 适用场景 | 适合频繁插入和删除操作，不确定大小的数据集合 | 适合频繁查找操作，固定大小或预先知道大小的数据集合 |
| 实现复杂度 | 实现较为复杂，需要管理指针和结点 | 实现较为简单，直接使用数组即可 |
| 空间复杂度 | O(n)（每个结点需要额外的指针空间） | O(n)（每个元素只占用数据所需的空间） |
| 时间复杂度 | 插入/删除：O(1)（已知位置），查找：O(n) | 插入/删除：O(n)，查找：O(1) |
4 功能定义
| 功能 | 函数签名 | 描述 |
|---|---|---|
| 初始化链表 | void initLinkedList(LinkedList *list) | 初始化链表，设置头指针为 NULL。 |
| 返回链表的长度 | size_t getLength(const LinkedList *list) | 返回链表的长度。 |
| 在指定位置插入元素 | void insertAt(LinkedList *list, size_t index, int element) | 在指定位置插入元素（假设是 int 类型）。 |
| 在末尾插入元素 | void insertEnd(LinkedList *list, int element) | 在链表末尾插入元素（假设是 int 类型）。 |
| 删除指定位置的元素并返回被删除的元素 | int deleteAt(LinkedList *list, size_t index) | 删除指定位置的元素并返回被删除的元素（假设是 int 类型）。 |
| 删除末尾元素 | int deleteEnd(LinkedList *list) | 删除链表末尾的元素并返回被删除的元素（假设是 int 类型）。 |
| 获取指定位置的元素 | int getElementAt(const LinkedList *list, size_t index) | 获取指定位置的元素（假设是 int 类型）。 |
| 修改指定位置的元素 | void modifyAt(LinkedList *list, size_t index, int newValue) | 修改指定位置的元素（假设是 int 类型）。 |
| 遍历链表 | void printLinkedList(const LinkedList *list) | 遍历链表（打印内容）。 |
| 释放链表内存 | void destroyLinkedList(LinkedList *list) | 释放链表内存。 |
- 上述功能是针对元素类型为 int 的链表定义的。在实际编程中，可以根据具体需求对元素类型进行调整。
5 功能实现
5.1 初始化链表
明确: 在包含虚拟头结点的情况下，首个保存数据的结点的索引为 0！
#include <stdio.h>
// 定义存储数据的结构体
// 存储数据：每个 Node 结构体实例代表链表中的一个结点，包含实际存储的数据（data）。
// 链接结点：每个 Node 结构体包含一个指针 next，用于指向下一个结点，从而形成链表的链接结构。
typedef struct Node
{
int data; // 结点存储的数据，以 int 类型数据为例
struct Node *next; // 指向下一个结点的指针
} Node;
// 定义虚拟头结点的结构体
// 管理链表：LinkedList 结构体用于管理整个链表，包含链表的基本信息。
// 头指针：head 指针指向链表的第一个结点，作为链表的入口点。
// 结点计数：size 字段记录链表中结点的数量，便于快速获取链表长度。
typedef struct
{
size_t size; // 链表中的结点个数（单链表中存储数据的个数）
Node *head; // 链表头结点指针，指向保存数据的首元素。由于上面使用了 typedef 起了别名，所以 Node 前面 可以不加 struct
} LinkedList;
// 明确: 在包含虚拟头结点的情况下，首个保存数据的结点的索引为 0！
/**
* @brief 初始化链表
*
* 设置链表的初始状态，将头指针设置为空，结点个数设置为 0。
*
* @param list 指向 LinkedList 结构体的指针，表示要初始化的链表
*/
void initLinkedList(LinkedList *list)
{
// 可选的对传入的参数做合法性校验
if (list == NULL)
{
puts("Error：无效输入，列表指针为空。");
return;
}
list->size = 0;
list->head = NULL;
puts("Success：初始化链表成功^_^");
}
int main()
{
LinkedList list; // 声明链表
puts("----------------------1.初始化链表----------------------");
initLinkedList(&list); // 初始化链表
initLinkedList(NULL); // 错误测试
return 0;
}输出结果如下所示：
为什么需要两个结构体？
1. 分离职责：
Node结构体专注于表示单个结点，包含数据和指向下一个结点的指针。LinkedList结构体专注于管理整个链表，包括头指针和结点计数。
2. 提高可读性和可维护性：
- 通过分离结点和链表的管理，代码更加清晰和易于理解。
- 维护和扩展链表相关功能时，可以集中在一个结构体中进行，减少代码冗余。
3. 增强功能：
- LinkedList 结构体中的 size 字段提供了一种快速获取链表长度的方法，而不需要每次遍历链表。
- 通过 head 指针，可以方便地进行链表的遍历、插入、删除等操作。
5.2 返回链表的长度
/**
* @brief 获取链表的长度
*
* 返回链表中结点的数量。如果传入的链表指针为 NULL，则返回 0 并打印错误消息。
* 同时，如果成功获取链表长度，还会打印链表的长度信息。
*
* @param list 指向 LinkedList 结构体的指针，表示要获取长度的链表
* @return 返回链表的长度，如果传入的指针为 NULL，则返回 0
*/
size_t getLength(const LinkedList *list)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return 0; // 如果是空指针，则返回 0
}
return list->size;
}5.3 在指定位置插入元素
/**
* @brief 在链表指定位置插入一个新元素。
*
* 此函数接收一个指向 LinkedList 类型的指针、一个索引值和一个要插入的元素。
* 它会在链表的指定位置插入一个新的结点，其中包含提供的元素。
* 如果提供的索引值非法或链表指针为空，函数将输出错误信息并返回。
* 如果一切正常，函数将成功插入新结点，并增加链表的大小。
*
* @param list 指向 LinkedList 类型的指针，表示要操作的链表。
* @param index 要插入的新结点的位置（从 0 开始计数）。
* @param element 要插入的新元素。
*/
void insertAt(LinkedList *list, size_t index, int element)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
// 检查传入的位置是否合法
if (index < 0 || index > list->size)
{
printf("Error: 输入的位置：%zu 非法\n", index);
return; // 如果位置非法，则退出函数
}
// 创建新的结点
Node *newNode = (Node *)malloc(1 * sizeof(Node));
if (newNode == NULL) // 检查内存分配是否成功
{
puts("Error: 内存分配失败");
return;
}
newNode->data = element;
// 插入新结点
if (index == 0)
{
// 插入在第一个位置(虚拟头结点指向的下一个元素的地址，索引为 0)
// 注意：这里的顺序不要搞错了
newNode->next = list->head; // 1. 将原来虚拟头结点指向的下一个元素（即第一个存储数据的元素）的地址给到新结点中的 next
list->head = newNode; // 2. 再将新结点的地址给头虚拟头结点的 head
}
else
{
// 插入中间或尾部
// 需要找到要插入位置的前一个结点
// 1. 从第一个存储数据的元素结点（索引为 0）开始寻找
Node *prevNode = list->head;
// 注意循环次数
for (size_t i = 1; i < index; i++)
{
prevNode = prevNode->next;
}
// 2. 将前面一个结点原本指向的位置给到新结点中的 next
newNode->next = prevNode->next;
// 3. 再将新结点的地址给到前面一个结点的 next
prevNode->next = newNode;
}
list->size++; // 增加链表的大小
printf("Success: 成功在指定位置(%zu)插入元素(%d)\n", index, element);
}5.4 在末尾插入元素
/**
* @brief 在链表末尾插入一个新元素。
*
* 此函数接收一个指向 LinkedList 类型的指针和一个要插入的元素。
* 它会在链表的末尾插入一个新的结点，其中包含提供的元素。
* 如果提供的链表指针为空，函数将输出错误信息并返回。
* 如果一切正常，函数将调用 insertA` 函数在链表末尾插入新结点，并增加链表的大小。
*
* @param list 指向 LinkedList 类型的指针，表示要操作的链表。
* @param element 要插入的新元素。
*/
void insertEnd(LinkedList *list, int element)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
insertAt(list, list->size, element); // 在链表末尾插入元素
}5.5 删除指定位置的元素并返回被删除的元素
/**
* @brief 删除指定位置的元素并返回被删除的元素
*
* 该函数删除链表中指定位置的元素，并返回被删除的元素。如果传入的链表指针为 NULL 或者指定位置非法，
* 则返回错误码 -1008611。
*
* @param list 指向 LinkedList 结构体的指针，表示要操作的链表
* @param index 要删除的元素的索引位置（从 0 开始计数）
* @return 返回被删除的元素，如果操作失败则返回 -1008611
*/
int deleteAt(LinkedList *list, size_t index)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return -1008611; // 如果是空指针，则退出函数
}
// 检查 index 是否合法
if (index >= list->size)
{
printf("Error: 输入的位置：%zu 非法\n", index);
return -1008611; // 退出函数
}
int deletedElement; // 保存要删除的结点中存储的数据
// 删除第一个存储数据的元素结点
if (index == 0)
{
// 1. 定义临时结点将要删除的结点保存起来备用
Node *temp = list->head;
// 2. 再将要删除的结点的下一个结点地址给到虚拟头指针
list->head = temp->next;
// 3. 取到要删除的结点中所保存的数据
deletedElement = temp->data;
// 4. 释放被删除节点的内存
free(temp);
printf("Success: 成功删除指定位置(%zu)的结点\n", index);
}
else
{
// 删除中间或尾部
// 需要找到要删除位置的前一个结点
// 1. 从第一个存储数据的元素结点（索引为 0）开始寻找
Node *prevNode = list->head;
for (size_t i = 1; i < index; i++)
{
prevNode = prevNode->next;
}
// 2. 定义临时结点将要删除的结点保存起来备用
Node *temp = prevNode->next;
// 3. 再将要删除的结点的下一个结点地址给到前一个结点的 next
prevNode->next = temp->next;
// 4. 取到要删除的结点中所保存的数据
deletedElement = temp->data;
// 5. 释放被删除节点的内存
free(temp);
printf("Success: 成功删除指定位置(%zu)的结点\n", index);
}
list->size--; // 更新节点个数
return deletedElement;
}5.6 删除末尾元素
/**
* @brief 删除链表末尾的元素并返回被删除的元素
*
* 该函数删除链表末尾的元素，并返回被删除的元素。如果传入的链表指针为 NULL 或者链表为空，
* 则返回错误码 -1008611。
*
* @param list 指向 LinkedList 结构体的指针，表示要操作的链表
* @return 返回被删除的元素，如果操作失败则返回 -1008611
*/
int deleteEnd(LinkedList *list)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return -1008611; // 如果是空指针，则退出函数
}
return deleteAt(list, list->size - 1); // 删除链表末尾的元素
}5.7 获取指定位置的元素
/**
* @brief 获取链表中指定位置的元素
*
* 该函数返回链表中指定位置的元素。如果传入的链表指针为 NULL 或者指定位置非法，
* 则返回错误码 -1008611。
*
* @param list 指向 LinkedList 结构体的指针，表示要操作的链表
* @param index 要获取的元素的索引位置（从 0 开始计数）
* @return 返回指定位置的元素，如果操作失败则返回 -1008611
*/
int getElementAt(const LinkedList *list, size_t index)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return -1008611; // 如果是空指针，则退出函数
}
// 检查 index 是否合法
if (index >= list->size)
{
return -1008611; // 返回无效的索引
}
// 从第一个元素结点开始找
Node *currentNode = list->head;
// 循环找到指定位置的节点
// 注意这里的循环次数，不是找到前面一个结点，而是当前节点
// 所以相对于前面的插入、删除操作中的循环，这里会多循环一次
for (size_t i = 0; i < index; i++)
{
currentNode = currentNode->next;
}
return currentNode->data; // 返回指定位置的元素
}5.8 修改指定位置的元素
/**
* @brief 修改链表中指定位置的元素
*
* 该函数修改链表中指定位置的元素。如果传入的链表指针为 NULL 或者指定位置非法，
* 则忽略此次修改操作。
*
* @param list 指向 LinkedList 结构体的指针，表示要操作的链表
* @param index 要修改的元素的索引位置（从 0 开始计数）
* @param newValue 新的元素值
*/
void modifyAt(LinkedList *list, size_t index, int newValue)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
// 检查 index 是否合法
if (index >= list->size)
{
return; // 忽略无效的修改位置
}
// 从第一个元素结点开始找
Node *currentNode = list->head;
// 循环找到指定位置的节点
// 注意这里的循环次数，不是找到前面一个结点，而是当前节点
// 所以相对于前面的插入、删除操作中的循环，这里会多循环一次
for (size_t i = 0; i < index; i++)
{
currentNode = currentNode->next;
}
// 修改节点的值
currentNode->data = newValue;
printf("Success：成功修改链表中指定位置(%zu)的元素,新元素为：%d\n", index, newValue);
}5.9 遍历链表
/**
* @brief 遍历链表并打印每个节点的内容
*
* 该函数遍历链表中的每个节点，并打印每个节点的数据。如果传入的链表指针为 NULL，
* 则打印错误消息并退出函数。
*
* @param list 指向 LinkedList 结构体的指针，表示要遍历的链表
*/
void printLinkedList(const LinkedList *list)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
// 从第一个元素结点开始
Node *currentNode = list->head;
puts("开始遍历链表数据：");
// 遍历链表
while (currentNode != NULL)
{
printf("%d ", currentNode->data); // 打印当前节点的数据
currentNode = currentNode->next; // 移动到下一个节点
}
printf("\n");
}5.10 释放链表内存
/**
* @brief 释放链表所占用的内存
*
* 该函数会遍历整个链表，逐个释放每个节点的内存，最后将链表的头指针置为 NULL，
* 并将链表的大小重置为 0。
*
* @param list 指向 LinkedList 结构体的指针，表示需要销毁的链表
*/
void destroyLinkedList(LinkedList *list)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
// 从链表的第一个节点（虚拟头结点指向的下一个元素）开始
Node *currentNode = list->head;
// 循环遍历链表中的所有节点
while (currentNode != NULL)
{
// 保存当前节点的指针
Node *temp = currentNode;
// 移动到下一个节点
currentNode = currentNode->next;
// 释放当前节点的内存
free(temp);
}
// 将链表的头指针置为 NULL，表示链表已被清空
list->head = NULL;
// 将链表的大小重置为 0
list->size = 0;
// 可选：输出销毁成功的消息
puts("Success: 链表已成功销毁");
}5.11 完整代码
#include <stdio.h>
#include <stdlib.h>
// 定义存储数据的结构体
// 存储数据：每个 Node 结构体实例代表链表中的一个结点，包含实际存储的数据（data）。
// 链接结点：每个 Node 结构体包含一个指针 next，用于指向下一个结点，从而形成链表的链接结构。
typedef struct Node
{
int data; // 结点存储的数据，以 int 类型数据为例
struct Node *next; // 指向下一个结点的指针
} Node;
// 定义虚拟头结点的结构体
// 管理链表：LinkedList 结构体用于管理整个链表，包含链表的基本信息。
// 头指针：head 指针指向链表的第一个结点，作为链表的入口点。
// 结点计数：size 字段记录链表中结点的数量，便于快速获取链表长度。
typedef struct
{
size_t size; // 链表中的结点个数（单链表中存储数据的个数）
Node *head; // 链表头结点指针，指向保存数据的首元素。由于上面使用了 typedef 起了别名，所以 Node 前面 可以不加 struct
} LinkedList;
// 明确: 在包含虚拟头结点的情况下，首个保存数据的结点的索引为 0！
/**
* @brief 初始化链表
*
* 设置链表的初始状态，将头指针设置为空，结点个数设置为 0。
*
* @param list 指向 LinkedList 结构体的指针，表示要初始化的链表
*/
void initLinkedList(LinkedList *list)
{
// 可选的对传入的参数做合法性校验
if (list == NULL)
{
puts("Error：无效输入，列表指针为空。");
return;
}
list->size = 0;
list->head = NULL;
puts("Success：初始化链表成功^_^");
}
/**
* @brief 获取链表的长度
*
* 返回链表中结点的数量。如果传入的链表指针为 NULL，则返回 0 并打印错误消息。
* 同时，如果成功获取链表长度，还会打印链表的长度信息。
*
* @param list 指向 LinkedList 结构体的指针，表示要获取长度的链表
* @return 返回链表的长度，如果传入的指针为 NULL，则返回 0
*/
size_t getLength(const LinkedList *list)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return 0; // 如果是空指针，则返回 0
}
return list->size;
}
/**
* @brief 在链表指定位置插入一个新元素。
*
* 此函数接收一个指向 LinkedList 类型的指针、一个索引值和一个要插入的元素。
* 它会在链表的指定位置插入一个新的结点，其中包含提供的元素。
* 如果提供的索引值非法或链表指针为空，函数将输出错误信息并返回。
* 如果一切正常，函数将成功插入新结点，并增加链表的大小。
*
* @param list 指向 LinkedList 类型的指针，表示要操作的链表。
* @param index 要插入的新结点的位置（从 0 开始计数）。
* @param element 要插入的新元素。
*/
void insertAt(LinkedList *list, size_t index, int element)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
// 检查传入的位置是否合法
if (index < 0 || index > list->size)
{
printf("Error: 输入的位置：%zu 非法\n", index);
return; // 如果位置非法，则退出函数
}
// 创建新的结点
Node *newNode = (Node *)malloc(1 * sizeof(Node));
if (newNode == NULL) // 检查内存分配是否成功
{
puts("Error: 内存分配失败");
return;
}
newNode->data = element;
// 插入新结点
if (index == 0)
{
// 插入在第一个位置(虚拟头结点指向的下一个元素的地址，索引为 0)
// 注意：这里的顺序不要搞错了
newNode->next = list->head; // 1. 将原来虚拟头结点指向的下一个元素（即第一个存储数据的元素）的地址给到新结点中的 next
list->head = newNode; // 2. 再将新结点的地址给头虚拟头结点的 head
}
else
{
// 插入中间或尾部
// 需要找到要插入位置的前一个结点
// 1. 从第一个存储数据的元素结点（索引为 0）开始寻找
Node *prevNode = list->head;
// 注意循环次数
for (size_t i = 1; i < index; i++)
{
prevNode = prevNode->next;
}
// 2. 将前面一个结点原本指向的位置给到新结点中的 next
newNode->next = prevNode->next;
// 3. 再将新结点的地址给到前面一个结点的 next
prevNode->next = newNode;
}
list->size++; // 增加链表的大小
printf("Success: 成功在指定位置(%zu)插入元素(%d)\n", index, element);
}
/**
* @brief 在链表末尾插入一个新元素。
*
* 此函数接收一个指向 LinkedList 类型的指针和一个要插入的元素。
* 它会在链表的末尾插入一个新结点，其中包含提供的元素。
* 如果提供的链表指针为空，函数将输出错误信息并返回。
* 如果一切正常，函数将调用 insertA` 函数在链表末尾插入新结点，并增加链表的大小。
*
* @param list 指向 LinkedList 类型的指针，表示要操作的链表。
* @param element 要插入的新元素。
*/
void insertEnd(LinkedList *list, int element)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
insertAt(list, list->size, element); // 在链表末尾插入元素
}
/**
* @brief 删除指定位置的元素并返回被删除的元素
*
* 该函数删除链表中指定位置的元素，并返回被删除的元素。如果传入的链表指针为 NULL 或者指定位置非法，
* 则返回错误码 -1008611。
*
* @param list 指向 LinkedList 结构体的指针，表示要操作的链表
* @param index 要删除的元素的索引位置（从 0 开始计数）
* @return 返回被删除的元素，如果操作失败则返回 -1008611
*/
int deleteAt(LinkedList *list, size_t index)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return -1008611; // 如果是空指针，则退出函数
}
// 检查 index 是否合法
if (index >= list->size)
{
printf("Error: 输入的位置：%zu 非法\n", index);
return -1008611; // 退出函数
}
int deletedElement; // 保存要删除的结点中存储的数据
// 删除第一个存储数据的元素结点
if (index == 0)
{
// 1. 定义临时结点将要删除的结点保存起来备用
Node *temp = list->head;
// 2. 再将要删除的结点的下一个结点地址给到虚拟头指针
list->head = temp->next;
// 3. 取到要删除的结点中所保存的数据
deletedElement = temp->data;
// 4. 释放被删除节点的内存
free(temp);
printf("Success: 成功删除指定位置(%zu)的结点\n", index);
}
else
{
// 删除中间或尾部
// 需要找到要删除位置的前一个结点
// 1. 从第一个存储数据的元素结点（索引为 0）开始寻找
Node *prevNode = list->head;
for (size_t i = 1; i < index; i++)
{
prevNode = prevNode->next;
}
// 2. 定义临时结点将要删除的结点保存起来备用
Node *temp = prevNode->next;
// 3. 再将要删除的结点的下一个结点地址给到前一个结点的 next
prevNode->next = temp->next;
// 4. 取到要删除的结点中所保存的数据
deletedElement = temp->data;
// 5. 释放被删除节点的内存
free(temp);
printf("Success: 成功删除指定位置(%zu)的结点\n", index);
}
list->size--; // 更新节点个数
return deletedElement;
}
/**
* @brief 删除链表末尾的元素并返回被删除的元素
*
* 该函数删除链表末尾的元素，并返回被删除的元素。如果传入的链表指针为 NULL 或者链表为空，
* 则返回错误码 -1008611。
*
* @param list 指向 LinkedList 结构体的指针，表示要操作的链表
* @return 返回被删除的元素，如果操作失败则返回 -1008611
*/
int deleteEnd(LinkedList *list)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return -1008611; // 如果是空指针，则退出函数
}
return deleteAt(list, list->size - 1); // 删除链表末尾的元素
}
/**
* @brief 获取链表中指定位置的元素
*
* 该函数返回链表中指定位置的元素。如果传入的链表指针为 NULL 或者指定位置非法，
* 则返回错误码 -1008611。
*
* @param list 指向 LinkedList 结构体的指针，表示要操作的链表
* @param index 要获取的元素的索引位置（从 0 开始计数）
* @return 返回指定位置的元素，如果操作失败则返回 -1008611
*/
int getElementAt(const LinkedList *list, size_t index)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return -1008611; // 如果是空指针，则退出函数
}
// 检查 index 是否合法
if (index >= list->size)
{
return -1008611; // 返回无效的索引
}
// 从第一个元素结点开始找
Node *currentNode = list->head;
// 循环找到指定位置的节点
// 注意这里的循环次数，不是找到前面一个结点，而是当前节点
// 所以相对于前面的插入、删除操作中的循环，这里会多循环一次
for (size_t i = 0; i < index; i++)
{
currentNode = currentNode->next;
}
return currentNode->data; // 返回指定位置的元素
}
/**
* @brief 修改链表中指定位置的元素
*
* 该函数修改链表中指定位置的元素。如果传入的链表指针为 NULL 或者指定位置非法，
* 则忽略此次修改操作。
*
* @param list 指向 LinkedList 结构体的指针，表示要操作的链表
* @param index 要修改的元素的索引位置（从 0 开始计数）
* @param newValue 新的元素值
*/
void modifyAt(LinkedList *list, size_t index, int newValue)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
// 检查 index 是否合法
if (index >= list->size)
{
return; // 忽略无效的修改位置
}
// 从第一个元素结点开始找
Node *currentNode = list->head;
// 循环找到指定位置的节点
// 注意这里的循环次数，不是找到前面一个结点，而是当前节点
// 所以相对于前面的插入、删除操作中的循环，这里会多循环一次
for (size_t i = 0; i < index; i++)
{
currentNode = currentNode->next;
}
// 修改节点的值
currentNode->data = newValue;
printf("Success：成功修改链表中指定位置(%zu)的元素,新元素为：%d\n", index, newValue);
}
/**
* @brief 遍历链表并打印每个节点的内容
*
* 该函数遍历链表中的每个节点，并打印每个节点的数据。如果传入的链表指针为 NULL，
* 则打印错误消息并退出函数。
*
* @param list 指向 LinkedList 结构体的指针，表示要遍历的链表
*/
void printLinkedList(const LinkedList *list)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
// 从第一个元素结点开始
Node *currentNode = list->head;
puts("开始遍历链表数据：");
// 遍历链表
while (currentNode != NULL)
{
printf("%d ", currentNode->data); // 打印当前节点的数据
currentNode = currentNode->next; // 移动到下一个节点
}
printf("\n");
}
/**
* @brief 释放链表所占用的内存
*
* 该函数会遍历整个链表，逐个释放每个节点的内存，最后将链表的头指针置为 NULL，
* 并将链表的大小重置为 0。
*
* @param list 指向 LinkedList 结构体的指针，表示需要销毁的链表
*/
void destroyLinkedList(LinkedList *list)
{
// 检查传入的指针是否为空
if (list == NULL)
{
puts("Error: 传入的链表指针为 NULL");
return; // 如果是空指针，则退出函数
}
// 从链表的第一个节点（虚拟头结点指向的下一个元素）开始
Node *currentNode = list->head;
// 循环遍历链表中的所有节点
while (currentNode != NULL)
{
// 保存当前节点的指针
Node *temp = currentNode;
// 移动到下一个节点
currentNode = currentNode->next;
// 释放当前节点的内存
free(temp);
}
// 将链表的头指针置为 NULL，表示链表已被清空
list->head = NULL;
// 将链表的大小重置为 0
list->size = 0;
// 可选：输出销毁成功的消息
puts("Success: 链表已成功销毁");
}
int main()
{
LinkedList list; // 声明链表
puts("----------------------1.初始化链表----------------------");
initLinkedList(&list); // 初始化链表
initLinkedList(NULL); // 错误测试
puts("----------------------2.获取链表的长度----------------------");
size_t lenth = getLength(&list);
printf("链表长度为：%zu\n", lenth); // 一开始没有元素，长度为 0
printf("链表长度为：%zu\n", getLength(NULL)); // 为 NULL 时，长度为 0
puts("----------------------3.在指定位置插入元素----------------------");
insertAt(&list, 0, 1); // 在位置 0 插入整形数据 1
insertAt(&list, 1, 2); // 在位置 1 插入整形数据 2
insertAt(&list, 0, 9); // 在位置 0 插入整形数据 9
printf("链表长度为：%zu\n", getLength(&list));
insertAt(&list, 998, 999); // 错误测试，在位置 998 插入整形数据 999
insertAt(NULL, 1, 2); // 错误测试
printf("链表长度为：%zu\n", getLength(&list));
printLinkedList(&list);
puts("----------------------4.在末尾插入元素----------------------");
insertEnd(&list, 66);
insertEnd(&list, 99);
printf("链表长度为：%zu\n", getLength(&list));
printLinkedList(&list);
puts("----------------------5.删除指定位置的元素并返回被删除的元素----------------------");
deleteAt(NULL, 1); // 错误测试
deleteAt(&list, 9999); // 错误测试
int deleteData1 = deleteAt(&list, 2);
printf("删除的内容是：%d\n", deleteData1);
int deleteData2 = deleteAt(&list, 0);
printf("删除的内容是：%d\n", deleteData2);
printf("链表长度为：%zu\n", getLength(&list));
printLinkedList(&list);
puts("----------------------6.删除末尾元素----------------------");
deleteEnd(&list);
printf("链表长度为：%zu\n", getLength(&list));
printLinkedList(&list);
puts("----------------------7.获取指定位置的元素----------------------");
printf("第一个存储数据的元素结点中的内容是：%d\n", getElementAt(&list, 0));
puts("----------------------8.修改指定位置的元素----------------------");
modifyAt(&list, 0, 100);
printLinkedList(&list);
puts("----------------------9.释放链表内存----------------------");
destroyLinkedList(&list);
return 0;
}输出结果如下所示：
6 测试题
1. 比于数组，链表有什么优点和缺点？
【答案】
优点：添加、删除不用移动元素。
缺点：每个节点占用额外空间存储下个节点的地址；查找效率低。
2. 某单向链表中，有三个节点，A -->B-->C，现在需要再 B 和 C 之间插入一个 F 节点，我们需要怎么做？
【答案】
让 F 指向 C；让 B 指向 F。【顺序不能错】
F->next = B->next;
B->next = F;3. 以下代码运行之后，数组会变成什么样子？
int arr[5] = {10, 20, 30, 40, 50};
for (int i = 4; i > 1; i--)
{
arr[i] = arr[i - 1];
}
arr[1] = 250;【答案】
10 250 20 30 40
【解析】
循环过程中：
- arr[4] = 40
- arr[3] = 30
- arr[2] = 20
循环结束后：
- arr[1] = 250
4. 写出下面程序的运行结果。
int num1 = 100, num2 = 200;
int *ptr1 = &num1;
int *ptr2 = ptr1;
ptr1 = &num2;
printf("%d", *ptr2);【答案】
100
【解析】
-
初始状态：
num1的值是 100，地址假设为0x1000。num2的值是 200，地址假设为0x2000。ptr1指向num1，即ptr1 = 0x1000。ptr2指向ptr1所指向的地址，即ptr2 = 0x1000。
-
改变
ptr1的值：ptr1被重新赋值为指向num2，即ptr1 = 0x2000。ptr2仍然指向num1，即ptr2 = 0x1000。
-
解引用
ptr2：*ptr2解引用ptr2，获取num1的值，即 100。