--- title: "高级数据结构 | open.mp" description: "数组操作" canonical: https://omp.itsneufox.com/zh-CN/docs/tutorials/AdvancedStructures language: zh-CN --- # 高级数据结构 ## 数组操作 ### 正确查找空闲槽位 本示例演示如何使用标准编码规范在数组中查找空闲槽位。 ```pawn new gMyArray[10]; stock FindEmptySlot() { new i = 0; while (i < sizeof (gMyArray) && gMyArray[i]) { i++; } if (i == sizeof (gMyArray)) return -1; return i; } ``` 此基础示例假设数组元素的零值表示槽位空闲。循环遍历数组元素（也可通过常量实现），当检测到非零值时持续遍历。遇到零值后循环终止，无需使用 break 语句（在此类场景中通常不推荐使用 break）。若未找到空闲槽位则返回-1，调用方需进行有效性校验。更常见的做法是直接使用找到的索引： ```pawn MyFunction() { new i = 0; while (i < sizeof (gMyArray) && gMyArray[i]) { i++; } if (i == sizeof (gMyArray)) { printf("错误：未找到空闲槽位"); return 0; } printf("成功：槽位%d空闲", i); // 在此处使用找到的槽位索引 return 1; } ``` 注意：实际应用中应将"gMyArray\[i\]"替换为具体的槽位占用标识（如自定义的枚举值或状态标记）。 ### 列表 #### 引言 列表是一种极为实用的数据结构，其本质是一个数组，其中每个元素都指向下一个相关数据。 **示例：** 假设我们有以下数组： ```pawn 3, 1, 64, 2, 4, 786, 2, 9 ``` 若对数组进行排序，结果将是： ```pawn 1, 2, 2, 3, 4, 9, 64, 786 ``` 然而，若希望保留数据的原始顺序，同时又能按某种逻辑（如数字大小）获取顺序，列表便派上了用场。构建列表时，需将数组转换为二维数组，其中第二维包含两个元素：第一个元素存储原始数据，第二个元素指向下一个更大数据的索引。此外，还需一个独立变量来记录最小值的索引。因此，新数组如下所示： ```pawn start = 1 3, 1, 64, 2, 4, 786, 2, 9 4, 3, 5, 6, 7, -1, 0, 2 ``` 其中，786 的下一个索引为-1，表示列表结束。两个 2 的顺序可以互换，但通常数组中的第一个 2 也会是列表中的第一个，因为它更可能首先被访问。 列表的另一大优势是添加新元素的速度更快。例如，若想在排序后的数组中插入数字 3，需将至少 4 个元素向右移动以腾出空间，这在小型数组中尚可接受，但在大型数组中则效率低下。而使用列表，只需将 3 添加到数组末尾，并修改列表中的一个值即可： ```pawn start = 1 3, 1, 64, 2, 4, 786, 2, 9, 3 8, 3, 5, 6, 7, -1, 0, 2, 4 ^ 修改此值 ^ 下一个更大值的索引 ``` 其他元素的位置未变，因此无需更新其索引，只需让前一个元素指向新元素，并让新元素指向原前一个元素所指向的元素。删除元素则更为简单： ```pawn start = 1 3, 1, 64, X, 4, 786, 2, 9, 3 8, 6, 5, 6, 7, -1, 0, 2, 4 ^ 跳过被删除的值 ``` 在此例中，第一个 2 被删除，指向它的元素（1）被更新为指向被删除元素原本指向的元素。虽然被删除元素的指针和值未被移除，但由于无法通过列表访问该位置，因此它实际上已被删除。 #### 类型 上述示例中的列表为单向列表，此外还有双向列表，其中每个元素既指向下一个元素，也指向上一个元素。双向列表通常还包含一个指向列表末尾的指针，以便反向遍历（例如，获取降序排列的数字）： ```pawn start = 1 end = 5 value: 3, 1, 64, 2, 4, 786, 2, 9, 3 next: 8, 3, 5, 6, 7, -1, 0, 2, 4 last: 6, -1, 7, 1, 8, 2, 3, 4, 0 ``` 使用双向列表时需格外小心，尤其是当存在重复值时，需确保上一个指针指向的元素的下一个指针能正确返回。例如，以下示例是错误的： ```pawn 2, 3, 3 1, 2, -1 -1, 2, 0 ``` 其中，2 的下一个指针指向第一个 3，但该 3 的上一个指针并未指向 2。虽然两个列表各自有序，但组合在一起则存在问题。正确的版本应为： ```pawn 2, 3, 3 1, 2, -1 -1, 0, 2 ``` 这两个列表均以最后两个数字为起点和终点，而错误示例中的反向列表则以中间数字为起点。 另一种类型为循环列表，其中最后一个元素指向第一个元素。其优势在于可以从任意元素访问其他元素，而无需预先知道目标元素的位置。但需注意避免无限循环，因为循环列表没有显式的结束标志。循环列表仍具有起点。此外，还可以创建双向循环列表，其中下一个和上一个指针均循环： ```pawn start = 1 end = 5 3, 1, 64, 2, 4, 786, 2, 9, 3 8, 3, 5, 6, 7, 1, 0, 2, 4 6, 5, 7, 1, 8, 2, 3, 4, 0 ``` #### 混合列表 混合列表是同时包含多个列表的数组。例如，一个按列表排序的值数组，另一个列表则链接所有未使用的槽位，以便在添加新值时快速定位可用位置。示例如下（X 表示未使用的槽位）： ```pawn sortedStart = 3 unusedStart = 1 value: 34, X, X, 6, 34, 46, X, 54, 23, 25, X, 75, X, 45 sort: 4, 8, 13, 7, 11, 9, 0, -1, 5 free: 2, 6, 10, 12, -1 ``` 显然，这两个列表互不干扰，因此它们可以使用相同的槽位作为下一个值： ```pawn sortedStart = 3 unusedStart = 1 value: 34, X, X, 6, 34, 46, X, 54, 23, 25, X, 75, X, 45 next: 4, 2, 6, 8, 13, 7, 10, 11, 9, 0, 12, -1, -1, 5 ``` #### 代码实现 在编写代码之前，需根据应用场景选择最合适的列表类型。以下示例展示了如何实现一个按数字升序排序的列表。 ```pawn #define NUMBER_OF_VALUES (10) enum E_DATA_LIST { E_DATA_LIST_VALUE, E_DATA_LIST_NEXT } new gListData[NUMBER_OF_VALUES][E_DATA_LIST], gUnusedStart = 0, gListStart = -1; // 初始时列表为空 // 初始化列表 List_Setup() { new i, size = NUMBER_OF_VALUES; size--; for (i = 0; i < size; i++) { // 初始时所有槽位均未使用 gListData[i][E_DATA_LIST_NEXT] = i + 1; } // 结束列表 gListData[size][E_DATA_LIST_NEXT] = -1; } // 向列表中添加一个值（使用基本排序） List_Add(value) { // 检查数组中是否有空闲槽位 if (gUnusedStart == -1) return -1; new pointer = gListStart, last = -1, slot = gUnusedStart; // 将值添加到数组 gListData[slot][E_DATA_LIST_VALUE] = value; // 更新空闲列表 gUnusedStart = gListData[slot][E_DATA_LIST_NEXT]; // 遍历列表，直到找到更大或相等的值 while (pointer != -1 && gListData[pointer][E_DATA_LIST_VALUE] < value) { // 保存上一个值的位置 last = pointer; // 移动到下一个槽位 pointer = gListData[pointer][E_DATA_LIST_NEXT]; } // 若到达此处，说明已遍历完列表或找到更大的值 // 检查是否遍历了任何数字 if (last == -1) { // 第一个数字更大或列表为空 // 将新值添加到列表开头 gListData[slot][E_DATA_LIST_NEXT] = gListStart; gListStart = slot; } else { // 将新值插入列表中 gListData[slot][E_DATA_LIST_NEXT] = pointer; gListData[last][E_DATA_LIST_NEXT] = slot; } return slot; } // 从数组中删除指定槽位的值（由List_Add返回） List_Remove(slot) { // 检查槽位是否有效 if (slot < 0 || slot >= NUMBER_OF_VALUES) return 0; // 首先找到前一个槽位 new pointer = gListStart, last = -1; while (pointer != -1 && pointer != slot) { last = pointer; pointer = gListData[pointer][E_DATA_LIST_NEXT]; } // 检查是否找到槽位 if (pointer == -1) return 0; if (last == -1) { // 该值为列表中的第一个 // 跳过此槽位 gListStart = gListData[slot][E_DATA_LIST_NEXT]; } else { // 该值在列表中 // 跳过此槽位 gListData[last][E_DATA_LIST_NEXT] = gListData[slot][E_DATA_LIST_NEXT]; } // 将此槽位添加到空闲列表 // 空闲列表无需排序，因此顺序无关紧要 gListData[slot][E_DATA_LIST_NEXT] = gUnusedStart; gUnusedStart = slot; return 1; } ``` ### 二叉树 #### 引言 二叉树是一种通过特殊列表系统在数组中快速搜索数据的方法。最著名的二叉树应用或许是“20 个问题”游戏，仅需 20 个是/否问题，便可识别超过 100 万个项目。二叉树，顾名思义，是一种树形结构，类似于家谱，其中每个节点有 0、1 或 2 个子节点。它并非用于排序数据，而是用于高效搜索。其基本原理是从有序列表的中间位置开始，将目标值与当前节点进行比较。若相等，则找到目标；若更大，则向右移动；若更小，则向左移动，并重复此过程。 **示例：** ```pawn 1 2 5 6 7 9 12 14 17 19 23 25 28 33 38 ``` 假设我们有一个有序数组，希望找到数字 7 的位置（若存在）。在此例中，直接遍历数组可能更为高效，但这不是重点。直接搜索的时间随数组大小线性增长，而二分搜索的时间则随数组大小呈对数增长。例如，一个 128 大小的数组直接搜索所需时间是 64 大小数组的两倍，而二分搜索仅需多一次比较。 若从上述数据构建二叉树，结果如下： ![Binarytree](https://sampwiki.blast.hk/wroot/images2/f/fe/Binarytree.GIF) 从左到右阅读，忽略垂直结构，可见数字按顺序排列。现在，我们尝试找到 7。 起始数字为 14，7 小于 14，因此向左移动到 6。7 大于 6，因此向右移动到 9，再向左移动到 7。此过程共进行了 4 次比较（包括最后的确认），而直接搜索则需要 5 次。 假设数组中没有 7，二叉树将如下所示： ![Binarytree-7-less](https://sampwiki.blast.hk/wroot/images2/e/e5/Binarytree-7-less.GIF) 与上例不同，此树有一个单子节点（9），以及 2 和 0 子节点。只有当数组大小为(2^n)-1（如 0, 1, 3, 7, 15, 31 等）时，才能构建完美的二叉树。在此例中，当到达 9 时，发现没有左分支，这意味着 7 不存在（它不可能在树的其他位置），因此返回-1 表示无效槽位。 #### 平衡与不平衡 上例中的树称为平衡二叉树，即尽可能使所有分支长度相同（尽管在第二个例子中因数字不足而无法完全实现）。构建平衡树并非易事，通常采用随机插入数字的方法来构建近似平衡的树。例如，以下是一个不平衡的二叉树： ![Binarytree-uneven](https://sampwiki.blast.hk/wroot/images2/a/a2/Binarytree-uneven.GIF) 显然，此树仍然有效，但右侧分支比左侧长得多。然而，在此树中查找 25 仅需 7 次比较，而直接搜索则需要 12 次。此外，只要从中间数字开始插入，随机插入方法通常能生成较为平衡的树。最糟糕的情况是按顺序插入数字，这将导致没有左分支（或右分支），但即使如此，二叉树的搜索时间也不会比直接搜索更长。 **修改** #### 添加 向二叉树添加一个值相对简单，只需遍历树，以目标值为参考，直到找到空分支并插入新值。例如，若想将 15 添加到原始平衡树中，它将位于 17 的左分支。若想将 8 添加到第二个平衡树（无 7）中，它将位于 9 的左分支。 #### 删除 从二叉树中删除一个值可能简单，也可能复杂。若值位于分支末端（如原始树中的 1、5、7、12 等），只需删除即可。若节点只有一个子节点（如第二个例子中的 9），只需将该子节点（如 12）移动到被删除节点的位置。删除操作在节点有两个子节点时变得复杂，至少有四种处理方法： 1. **简单替换法**：选择其中一个分支（如右分支），用被删除节点的第一个子节点替换被删除节点，然后将左分支附加到新分支的末端。此方法速度快，但容易导致树不平衡。 2. **重建子树法**：将被删除节点的所有子节点重新构建为一棵新的二叉树，并将其插入被删除节点的位置。此方法保持树的平衡，但速度较慢。 3. **内联重建法**：结合前两种方法，内联重建子树。此方法编码复杂，但既能保持树的平衡，又比第二种方法更快。 4. **标记删除法**：简单标记被删除节点为“未使用”。此方法速度最快，且保持树的结构，但无法重用槽位，除非后续能找到替换值。