深度理解链表：使用C++数组与下标的模拟

文章目录

• 1. 概述
• 2. 数据结构设计
• 3. 初始化数组
• 4. 插入节点
  • 插入操作流程图
  • 插入操作示例说明
• 5. 删除节点
  • 删除操作流程图
  • 删除操作示例说明
• 6. 遍历链表
  • 遍历操作流程图
  • 遍历操作示例说明
• 7. 查找节点
  • 查找操作流程图
  • 查找操作示例说明
• 8. 示例代码
  • 运行示例说明
• 9. 时间复杂度和空间复杂度分析
  • 时间复杂度
  • 空间复杂度
• 10. 总结

1. 概述

链表是一种由节点组成的线性数据结构，每个节点包含数据部分和指向下一个节点的指针。传统上，链表通过动态内存分配和指针操作来实现。然而，通过使用数组来模拟内存，用下标来模拟指针，可以简化实现过程，避免复杂的指针操作。

本文将详细讲解如何使用数组模拟内存和下标模拟指针来实现链表，并通过具体示例说明每个操作的过程，包括插入、删除、遍历和查找操作。同时，每种操作都配以流程图，帮助读者更好地理解。

2. 数据结构设计

为了模拟链表，我们需要两个数组：

1. 数据数组 (data[]) ：存储链表节点的数据。
2. 指针数组 (next[]) ：存储每个节点的下一个节点的下标（即指针）。

此外，还需要一个变量 head 来表示链表的头节点的下标。初始时，head 设置为 -1，表示链表为空。

#defineMAX_SIZE100// 预先定义数组的最大大小int data[MAX_SIZE];// 存储节点的数据int next[MAX_SIZE];// 存储指向下一个节点的索引int head =-1;// 链表的头节点索引，初始为-1表示空链表

3. 初始化数组

初始化时，将数据数组的所有元素设置为 -1 表示空闲，指针数组的所有元素也设置为 -1 表示没有下一个节点。

voidinitialize(){for(int i =0; i < MAX_SIZE; i++){ data[i]=-1; next[i]=-1;} head =-1;}

4. 插入节点

插入节点时，需要找到一个空闲的位置（即数据数组中值为 -1 的位置），然后将新节点的数据存储在该位置，并更新指针数组中的指针，使其指向原来的头节点。最后，更新头节点为新节点的下标。

插入操作流程图

开始 | |--- 遍历 data 数组，寻找 data[i] == -1 的位置 | |--- 如果找到空闲位置： | | | |--- 存储 value 到 data[i] | | | |--- 更新 next[i] 为 head | | | |--- 更新 head 为 i | | | |--- 返回 1（插入成功） | |--- 如果未找到空闲位置： | | | |--- 返回 -1（插入失败） | 结束 

插入操作示例说明

intinsert(int value){for(int i =0; i < MAX_SIZE; i++){if(data[i]==-1){// 找到一个空闲的位置 data[i]= value;// 存储数据 next[i]= head;// 当前节点的下一个节点指向原来的头节点 head = i;// 更新头节点为当前节点return1;// 插入成功}}return-1;// 插入失败，数组已满}

示例说明：

• 初始化后，data 和 next 数组全为 -1，head 为 -1。
• 调用 insert(5)，找到第一个空闲位置（假设为下标 0），将数据 5 存储在 data[0]，并将 next[0] 设置为原来的头节点（-1），更新 head 为 0。
• 插入成功后，链表中只有一个节点，数据为 5。

5. 删除节点

删除节点时，需要遍历链表，找到要删除的节点，并将其前驱节点的指针指向被删除节点的下一个节点。最后，将被删除节点的数据和指针重置为初始值。

删除操作流程图

开始 | |--- 如果 head == -1，返回 -1（删除失败） | |--- 如果头节点 data[head] == value： | | | |--- 保存头节点的下标 temp = head | | | |--- 更新 head 为 next[head] | | | |--- 重置 data[temp] 和 next[temp] 为 -1 | | | |--- 返回 1（删除成功） | |--- 否则： | | | |--- 从头节点开始，遍历链表，寻找 data[next[current]] == value | | | |--- 如果找到目标节点： | | | | | |--- 保存目标节点的下标 temp = next[current] | | | | | |--- 更新 current 的 next 指针为 next[temp] | | | | | |--- 重置 data[temp] 和 next[temp] 为 -1 | | | | | |--- 返回 1（删除成功） | | | |--- 如果未找到目标节点： | | | | | |--- 返回 -1（删除失败） | 结束 

删除操作示例说明

intdelete(int value){if(head ==-1){return-1;// 链表为空，删除失败}if(data[head]== value){// 头节点即为目标节点int temp = head; head = next[head]; data[temp]=-1; next[temp]=-1;return1;// 删除成功}int current = head;while(next[current]!=-1&& data[next[current]]!= value){ current = next[current];}if(next[current]!=-1){// 找到目标节点int temp = next[current]; next[current]= next[temp]; data[temp]=-1; next[temp]=-1;return1;// 删除成功}return-1;// 删除失败，未找到目标节点}

示例说明：

• 假设链表中有节点 5（下标 0）、3（下标 1）、8（下标 2），头节点为 2。
• 调用 delete(8)，遍历链表，找到节点 8 的位置（下标 2）。
• 将前驱节点（下标 1）的 next 指针指向节点 8 的下一个节点（-1）。
• 将节点 8 的数据和指针重置为 -1，删除成功。

6. 遍历链表

遍历链表时，从头节点开始，依次访问每个节点的指针，直到指针为 -1 表示链表结束。

遍历操作流程图

开始 | |--- 初始化 current = head | |--- 如果 current == -1，输出 "null"，结束 | |--- 否则： | | | |--- 输出 data[current] | | | |--- current = next[current] | | | |--- 重复直到 current == -1 | 结束 

遍历操作示例说明

voidtraverse(){int current = head;while(current !=-1){printf("%d -> ", data[current]); current = next[current];}printf("null\n");}

示例说明：

• 假设链表中有节点 1（下标 0）、3（下标 1）、5（下标 2），头节点为 0。
• 调用 traverse()，输出链表的所有节点数据，格式为：1 -> 3 -> 5 -> null。

7. 查找节点

查找节点时，从头节点开始，依次访问每个节点的数据，直到找到目标值或遍历完整个链表。

查找操作流程图

开始 | |--- 初始化 current = head | |--- 如果 current == -1，返回 -1（未找到） | |--- 检查 data[current] 是否等于 value | | | |--- 是：返回 current | | | |--- 否：current = next[current] | |--- 重复直到 current == -1 | 结束 

查找操作示例说明

intfind(int value){int current = head;while(current !=-1){if(data[current]== value){return current;// 找到目标节点，返回其下标} current = next[current];}return-1;// 未找到目标节点}

示例说明：

• 假设链表中有节点 1（下标 0）、3（下标 1）、5（下标 2），头节点为 0。
• 调用 find(3)，从 head（0）开始，检查 data[0]（1），不匹配。
• 访问 next[0]（1），检查 data[1]（3），匹配，返回下标 1。

8. 示例代码

以下是一个完整的示例代码，展示了如何使用数组模拟内存和下标模拟指针来实现链表，包括插入、删除、遍历和查找操作：

#include<stdio.h>#defineMAX_SIZE100// 预先定义数组的最大大小int data[MAX_SIZE];// 存储节点的数据int next[MAX_SIZE];// 存储指向下一个节点的索引int head =-1;// 链表的头节点索引，初始为-1表示空链表voidinitialize(){for(int i =0; i < MAX_SIZE; i++){ data[i]=-1; next[i]=-1;} head =-1;}intinsert(int value){for(int i =0; i < MAX_SIZE; i++){if(data[i]==-1){// 找到一个空闲的位置 data[i]= value;// 存储数据 next[i]= head;// 当前节点的下一个节点指向原来的头节点 head = i;// 更新头节点为当前节点return1;// 插入成功}}return-1;// 插入失败，数组已满}intdelete(int value){if(head ==-1){return-1;// 链表为空，删除失败}if(data[head]== value){// 头节点即为目标节点int temp = head; head = next[head]; data[temp]=-1; next[temp]=-1;return1;// 删除成功}int current = head;while(next[current]!=-1&& data[next[current]]!= value){ current = next[current];}if(next[current]!=-1){// 找到目标节点int temp = next[current]; next[current]= next[temp]; data[temp]=-1; next[temp]=-1;return1;// 删除成功}return-1;// 删除失败，未找到目标节点}voidtraverse(){int current = head;while(current !=-1){printf("%d -> ", data[current]); current = next[current];}printf("null\n");}intfind(int value){int current = head;while(current !=-1){if(data[current]== value){return current;// 找到目标节点，返回其下标} current = next[current];}return-1;// 未找到目标节点}intmain(){initialize();// 插入节点insert(5);insert(3);insert(8);insert(1);// 遍历链表traverse();// 输出: 1 -> 8 -> 3 -> 5 -> null// 查找节点int foundIndex =find(8);if(foundIndex !=-1){printf("找到节点，下标为：%d，数据为：%d\n", foundIndex, data[foundIndex]);}else{printf("未找到目标节点\n");}// 删除节点delete(8);traverse();// 输出: 1 -> 3 -> 5 -> nulldelete(5);traverse();// 输出: 1 -> 3 -> nullreturn0;}

运行示例说明

1. 初始化链表：
   • 调用 initialize() 函数，将 data 和 next 数组初始化为 -1，并将 head 设为 -1，表示链表为空。
2. 插入节点：
   • 调用 insert(5)、insert(3)、insert(8) 和 insert(1)，依次插入节点 5、3、8 和 1。
   • 插入成功后，链表的顺序为：1 -> 8 -> 3 -> 5 -> null。
3. 遍历链表：
   • 调用 traverse() 函数，输出链表的所有节点数据，格式为：1 -> 8 -> 3 -> 5 -> null。
4. 查找节点：
   • 调用 find(8)，查找值为 8 的节点。
   • 如果找到，输出节点的下标和数据；如果未找到，输出未找到提示。
5. 删除节点：
   • 调用 delete(8)，删除值为 8 的节点。
   • 删除成功后，链表的顺序为：1 -> 3 -> 5 -> null。
   • 再次调用 delete(5)，删除值为 5 的节点。
   • 删除成功后，链表的顺序为：1 -> 3 -> null。
6. 再次遍历链表：
   • 调用 traverse() 函数，输出链表的最终状态：1 -> 3 -> null。

9. 时间复杂度和空间复杂度分析

时间复杂度

空间复杂度

10. 总结

通过使用数组模拟内存和下标模拟指针，可以实现链表的基本功能，包括插入、删除、遍历和查找操作。这种方法虽然在某些方面不如传统指针实现的链表高效，但它具有代码简洁、易于理解和实现的优点。对于教学和基础理解来说，这是一种非常有效的方法。在实际应用中，可以根据具体需求选择合适的实现方式。