跳到主要内容

Advanced Structures

数组操作​

正确查找空槽​

此示例展示了如何使用标准编码实践在数组中查找空槽.

new
    gMyArray[10];

stock FindEmptySlot()
{
    new
        i = 0;
    while (i < sizeof (gMyArray) && gMyArray[i])
    {
        i++;
    }
    if (i == sizeof (gMyArray)) return -1;
    return i;
}

这个基本示例假设如果数组槽的值为0, 则该槽为空. 循环会遍历数组中的所有值（也可以使用常量）, 只要这些值不是0. 当它遇到一个值为0的槽时, while 条件将失败, 循环结束. 在这种情况下, 通常避免使用 break, 而是直接通过条件结束循环. 这个函数还会返回 -1, 如果未找到空槽, 需要在其他地方进行检查. 更常见的做法是直接使用找到的ID. :

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）已经更新为指向被移除的数字原本指向的数字. 在这个示例中, 虽然被移除数字的指针和数字本身并没有被实际删除, 但你无法通过列表访问到那个槽位, 因此它实际上是被移除了.

Types​

上述示例中的列表只是基本的单向列表, 你也可以使用双向列表, 其中每个值都指向下一个值和上一个值, 这些列表通常还会有一个指向列表末尾的指针, 以便可以向后遍历（例如, 以降序获取数字）:

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的下一个指针指向槽位1中的3, 但那个3的上一个指针没有回到2, 两种列表在各自的顺序上都是正确的（因为两个3可以交换位置）, 但结合在一起时是错误的. 正确的版本应如下所示:

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

这两种列表都以末尾的两个数字开始和结束, 而错误示例中的反向列表是从中间的数字开始的.

另一种类型的列表是循环列表, 其中最后一个值指向第一个值. 这样做的明显好处是你可以从任何一个值访问到其他任何值, 而不需要事先知道目标是在起点之前还是之后, 你只需要小心不要陷入无限循环, 因为没有显式的-1结束点. 这些列表仍然有起点. 你还可以创建双向循环列表, 其中有一个下一个列表和一个上一个列表, 它们都进行循环:

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个是/否的问题, 你可以处理超过1048576个项. 顾名思义, 二叉树是一种树结构, 类似于家谱, 其中每个项有0、1或2个子节点. 它们不是用来像列表那样排序数据, 而是用于非常高效的搜索数据. 基本上, 你从有序列表中的中间某个项开始（例如, 排序数组中的中间数字）, 并将其与要查找的值进行比较. 如果相同, 则找到目标项；如果大于目标值, 则移动到右边的项（不是紧挨着的右边, 而是中间项右侧的三分之一处）, 如果小于目标值, 则移动到左边, 然后重复这个过程.

例如

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

你有一个排好序的数组, 想要查找数字7所在的槽位（如果它存在的话）. 在这个例子中, 直接遍历数组来查找可能更高效, 但这并不是重点. 线性查找的时间随着数组大小的增加而线性增长, 而二叉搜索的时间随着数组大小的指数增长而增加. 也就是说, 一个128大小的数组直接查找需要的时间将是64大小数组的两倍, 但一个128大小的数组的二叉搜索比64大小的数组只多检查一次, 这个增加是非常小的.

如果我们从上述数据构造一个二叉树, 我们得到的结构如下: Binarytree

如果你从左到右读取二叉树, 忽略垂直结构, 你会发现数字是有序的. 现在我们可以尝试找到数字7.

  • 开始节点：14

    • 由于7小于14, 我们转到14的左侧分支.

  • 下一个节点：6

    • 由于7大于6, 我们转到6的右侧分支.

  • 下一个节点：9

    • 由于7小于9, 我们转到9的左侧分支.

  • 下一个节点：7

    • 7等于7, 所以我们找到了目标值.

这个方法总共进行了4次比较（包括最后一次确认我们在7上）. 如果使用线性搜索, 最多需要进行5次比较, 因此二叉树的查找效率更高.

如果我们假设二叉树中没有数字7, 我们将会得到一个如下的二叉树结构: Binarytree-7-less

这与上面的示例不同, 它只有一个子节点（9）, 以及2和0个子节点. 只有在节点数量为(2^n)-1 的情况下（例如 0、1、3、7、15、31 等）, 你才能得到一个完美的二叉树. 任何其他数量的节点都会导致树不完全. 在这个例子中, 当我们到达9时, 如果7存在, 它应该在9的左侧分支上. 然而, 实际情况是9没有左侧分支, 这意味着7不存在（它不可能出现在树的其他地方, 仔细想一想）. 因此, 我们返回-1, 表示无效的槽位

平衡与不平衡的二叉树​

上面例子中的树称为平衡二叉树, 这意味着尽可能地所有的分支长度相同（显然在第二棵树中, 由于数量不足, 不能完全平衡, 但已经尽可能接近）. 构建平衡树并不容易, 通常接受的构建几乎平衡树的方法是以随机顺序插入数字, 这可能会导致如下结果: Binarytree-uneven

显然, 这棵树仍然是有效的, 但右侧远大于左侧. 然而, 找到 25 仍然只需 7 次比较, 而在直线列表中则需要 12 次比较. 此外, 只要从一个相对中间的数字开始, 随机插入方法通常会产生一个相对平衡的树. 最糟糕的情况是按顺序插入数字, 这样将完全没有左分支（如果按相反的顺序则会没有右分支）. 然而, 即使在这种最坏情况下, 二叉树的搜索时间也不会比直线列表更长.

修改

添加​

向二叉树中添加一个值相对简单, 你只需通过树进行遍历, 使用你想添加的值作为参考, 直到你到达一个空分支并将该值添加到那里. 例如, 如果你想向我们最初的平衡树中添加数字 15, 它将最终位于 17 的左分支上. 如果我们想向第二棵平衡树（没有 7 的那棵）中添加数字 8, 它将最终位于 9 的左侧, 即原来 7 的位置.

删除​

从二叉树中删除一个数字可以很简单, 也可以很复杂. 如果数字位于分支的末端（例如原始树中的 1、5、7、12 等）, 你只需将它们删除. 如果一个数字只有一个子节点（例如第二个示例中的 9）, 你只需将那个子节点（例如 12）移动到它的位置（在删除 9 后, 6 的子节点将是 2 和 12）. 当一个节点有两个子节点时, 删除操作才变得有趣. 处理这种情况的方法至少有四种：

第一种方法在计算上是最简单的. 基本上, 你选择一个分支（左或右, 假设为右分支）, 用该分支的第一个节点（即你删除的节点的右子节点）替换你删除的节点. 然后你沿着新分支向左遍历, 直到到达末尾, 并将左分支放在那里. 例如, 如果你从原始示例中删除 14, 你将会让 25 取代它在树顶的位置, 而 6 则附加到 17 的左分支上. 这种方法很快, 但会很快产生非常不平衡的树.

第二种方法是获取你刚刚删除的节点的所有子节点, 并从这些子节点中重建一个新的二叉树, 然后将新树的顶部放入你刚刚删除的节点的位置. 这保持了树的相对平衡, 但显然速度较慢.

第三种方法是结合前两种方法, 在内联重建树, 这种方法编程更复杂, 但保持了树的平衡, 速度比第二种方法快（虽然没有第一种方法快）.

最后一种方法是简单地在一个值上设置一个标志, 表示它不再使用, 这种方法比第一种方法更快, 并且保持了结构, 但这意味着你不能重新使用槽位, 除非你以后找到一个值来替换它.