高级数据结构

数组操作

正确查找空闲槽位

本示例演示如何使用标准编码规范在数组中查找空闲槽位。

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，调用方需进行有效性校验。更常见的做法是直接使用找到的索引：

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]"替换为具体的槽位占用标识（如自定义的枚举值或状态标记）。

列表

引言

列表是一种极为实用的数据结构，其本质是一个数组，其中每个元素都指向下一个相关数据。

示例：

假设我们有以下数组：

3, 1, 64, 2, 4, 786, 2, 9

若对数组进行排序，结果将是：

1, 2, 2, 3, 4, 9, 64, 786

然而，若希望保留数据的原始顺序，同时又能按某种逻辑（如数字大小）获取顺序，列表便派上了用场。构建列表时，需将数组转换为二维数组，其中第二维包含两个元素：第一个元素存储原始数据，第二个元素指向下一个更大数据的索引。此外，还需一个独立变量来记录最小值的索引。因此，新数组如下所示：

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 添加到数组末尾，并修改列表中的一个值即可：

start = 1
3, 1, 64, 2, 4, 786, 2, 9, 3
8, 3, 5,  6, 7, -1,  0, 2, 4
^ 修改此值        ^ 下一个更大值的索引

其他元素的位置未变，因此无需更新其索引，只需让前一个元素指向新元素，并让新元素指向原前一个元素所指向的元素。删除元素则更为简单：

start = 1
3, 1, 64, X, 4, 786, 2, 9, 3
8, 6, 5,  6, 7, -1,  0, 2, 4
   ^ 跳过被删除的值

在此例中，第一个 2 被删除，指向它的元素（1）被更新为指向被删除元素原本指向的元素。虽然被删除元素的指针和值未被移除，但由于无法通过列表访问该位置，因此它实际上已被删除。

类型

上述示例中的列表为单向列表，此外还有双向列表，其中每个元素既指向下一个元素，也指向上一个元素。双向列表通常还包含一个指向列表末尾的指针，以便反向遍历（例如，获取降序排列的数字）：

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

使用双向列表时需格外小心，尤其是当存在重复值时，需确保上一个指针指向的元素的下一个指针能正确返回。例如，以下示例是错误的：

2,  3, 3
1,  2, -1
-1, 2, 0

其中，2 的下一个指针指向第一个 3，但该 3 的上一个指针并未指向 2。虽然两个列表各自有序，但组合在一起则存在问题。正确的版本应为：

2,  3, 3
1,  2, -1
-1, 0, 2

这两个列表均以最后两个数字为起点和终点，而错误示例中的反向列表则以中间数字为起点。

另一种类型为循环列表，其中最后一个元素指向第一个元素。其优势在于可以从任意元素访问其他元素，而无需预先知道目标元素的位置。但需注意避免无限循环，因为循环列表没有显式的结束标志。循环列表仍具有起点。此外，还可以创建双向循环列表，其中下一个和上一个指针均循环：

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 表示未使用的槽位）：

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

显然，这两个列表互不干扰，因此它们可以使用相同的槽位作为下一个值：

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

代码实现

在编写代码之前，需根据应用场景选择最合适的列表类型。以下示例展示了如何实现一个按数字升序排序的列表。

#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 个子节点。它并非用于排序数据，而是用于高效搜索。其基本原理是从有序列表的中间位置开始，将目标值与当前节点进行比较。若相等，则找到目标；若更大，则向右移动；若更小，则向左移动，并重复此过程。

示例：

1 2 5 6 7 9 12 14 17 19 23 25 28 33 38

假设我们有一个有序数组，希望找到数字 7 的位置（若存在）。在此例中，直接遍历数组可能更为高效，但这不是重点。直接搜索的时间随数组大小线性增长，而二分搜索的时间则随数组大小呈对数增长。例如，一个 128 大小的数组直接搜索所需时间是 64 大小数组的两倍，而二分搜索仅需多一次比较。

若从上述数据构建二叉树，结果如下：

从左到右阅读，忽略垂直结构，可见数字按顺序排列。现在，我们尝试找到 7。

起始数字为 14，7 小于 14，因此向左移动到 6。7 大于 6，因此向右移动到 9，再向左移动到 7。此过程共进行了 4 次比较（包括最后的确认），而直接搜索则需要 5 次。

假设数组中没有 7，二叉树将如下所示：

与上例不同，此树有一个单子节点（9），以及 2 和 0 子节点。只有当数组大小为(2^n)-1（如 0, 1, 3, 7, 15, 31 等）时，才能构建完美的二叉树。在此例中，当到达 9 时，发现没有左分支，这意味着 7 不存在（它不可能在树的其他位置），因此返回-1 表示无效槽位。

平衡与不平衡

上例中的树称为平衡二叉树，即尽可能使所有分支长度相同（尽管在第二个例子中因数字不足而无法完全实现）。构建平衡树并非易事，通常采用随机插入数字的方法来构建近似平衡的树。例如，以下是一个不平衡的二叉树：

显然，此树仍然有效，但右侧分支比左侧长得多。然而，在此树中查找 25 仅需 7 次比较，而直接搜索则需要 12 次。此外，只要从中间数字开始插入，随机插入方法通常能生成较为平衡的树。最糟糕的情况是按顺序插入数字，这将导致没有左分支（或右分支），但即使如此，二叉树的搜索时间也不会比直接搜索更长。

修改

添加

向二叉树添加一个值相对简单，只需遍历树，以目标值为参考，直到找到空分支并插入新值。例如，若想将 15 添加到原始平衡树中，它将位于 17 的左分支。若想将 8 添加到第二个平衡树（无 7）中，它将位于 9 的左分支。

删除

从二叉树中删除一个值可能简单，也可能复杂。若值位于分支末端（如原始树中的 1、5、7、12 等），只需删除即可。若节点只有一个子节点（如第二个例子中的 9），只需将该子节点（如 12）移动到被删除节点的位置。删除操作在节点有两个子节点时变得复杂，至少有四种处理方法：

1. 简单替换法：选择其中一个分支（如右分支），用被删除节点的第一个子节点替换被删除节点，然后将左分支附加到新分支的末端。此方法速度快，但容易导致树不平衡。

2. 重建子树法：将被删除节点的所有子节点重新构建为一棵新的二叉树，并将其插入被删除节点的位置。此方法保持树的平衡，但速度较慢。

3. 内联重建法：结合前两种方法，内联重建子树。此方法编码复杂，但既能保持树的平衡，又比第二种方法更快。

4. 标记删除法：简单标记被删除节点为“未使用”。此方法速度最快，且保持树的结构，但无法重用槽位，除非后续能找到替换值。