[教程] 代码优化 #2

[XiaoNiao]

混合列表

混合列表是同时包含多个列表的数组。一个例子可以是一个值数组，通过一个列表排序，用另一个列表链接所有未使用的槽位，这样你就知道可以在哪里添加一个新值。例子（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--;
    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_LIST_DATA_NEXT];
    }
    // 我们在列表中找到了这个槽位吗？
    if (pointer == -1) return 0;
    if (last == -1)
    {
        // 该值是列表中的第一个
        // 在列表中跳过这个槽位
        gListStart = gListData[slot][E_LIST_DATA_NEXT];
    }
    else
    {
        // 该值在列表中
        // 在列表中跳过这个槽位
        gListData[last][E_LIST_DATA_NEXT] = gListData[slot][E_LIST_DATA_NEXT];
    }
    // 将此槽位添加到空闲列表
    // 空闲列表没有特定顺序，所以这没关系
    gListData[slot][E_LIST_DATA_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 大小的二分查找多一次检查，而不是多很多。

如果我们从上面的数据构建一个二叉树，我们得到：



二叉树

如果你从左到右阅读，忽略垂直方面，你可以看到数字是按顺序的。现在我们可以尝试找到 7。

起始数字是 14，7 小于 14，所以我们转到 14 的左分支指向的槽位。这让我们来到 6，7 大于 6，所以我们向右到 9，然后向左到 7。这种方法用了 4 次比较就找到了数字（包括最后确认我们在 7 上），而直接查找需要 5 次。

假设没有 7，我们会得到这个二叉树：


二叉树缺少7

这与上面的例子不同，它有一个单子数字（9），以及 2 个和 0 个子数字。只有当有 (2^n)-1 个数字（0, 1, 3, 7, 15, 31 ...）时，你才能得到完美的树，任何其他数字都会得到一个不完整的树。在这种情况下，当我们到达 9 时，也就是 7 应该在的位置，我们会发现没有左分支，这意味着 7 不存在（它不可能在树中的其他地方，想想看），所以我们返回 -1 表示无效槽位。

平衡与非平衡

上面例子中的树被称为平衡二叉树，这意味着尽可能让所有分支长度相同（显然在第二个例子中，由于数字不足，不可能做到，但已经尽可能平衡了）。构建平衡树并不容易，通常接受的方法是随机顺序放入数字，这可能导致像这样的结果：


不平衡二叉树

显然，这棵树仍然是有效的，但右侧比左侧大得多，然而查找 25 仍然只需要 7 次比较，而在直接列表中需要 12 次。另外，只要你从一个相当中间的数字开始，随机插入方法应该会产生一个相当平衡的树。你能做的最糟糕的事情是按顺序放入数字，因为那样就不会有任何左分支（或者反过来就没有右分支），然而即使在这种最坏的情况下，二叉树的搜索时间也不会比直接列表长。

修改

• 添加
  

向二叉树添加一个值相对容易，你只需沿着树走，使用你想要添加的值作为参考，直到你到达一个空分支，然后在那里添加数字。例如，如果你想向原始平衡树中添加数字 15，它最终会出现在 17 的左分支上。如果我们想向第二个平衡树（没有 7 的那个）添加数字 8，它最终会出现在 9 左边的 7 的旧槽位。

• 删除
  

从二叉树中删除一个数字可能很难，也可能很容易。如果数字在分支的末端（例如原始树中的 1、5、7、12 等），你只需删除它们。如果一个数字只有一个子节点（例如第二个例子中的 9），你只需将该子节点（例如 12）移到它的位置（所以在新的第二个例子中，删除 9 后，6 的子节点将是 2 和 12）。只有当一个节点有两个子节点时，删除才变得有趣。至少有四种方法可以做到这一点：

第一种方法在计算上最简单。基本上你选择一个分支（左或右，假设这里用右），然后用该分支的第一个节点（即被删除节点的右子节点）替换你删除的节点。然后你沿着那个新分支向左走，直到到达末尾，并将左分支放在那里。例如，如果你从原始示例中删除 14，你会得到 25 占据树顶的位置，而 6 连接到 17 的左分支。这种方法很快，但很快就会导致树非常不平衡。

第二种方法是获取你刚刚删除节点的所有子节点，并从它们重新构建一个新的二叉树，然后将该树的顶部放入你刚刚删除的节点中。这能使树保持相当平衡，但显然更慢。

第三种方法是结合上述两种方法，并就地重建树，这编码更复杂，但能保持树平衡，并且比第二种方法更快（尽管远不如第一种快）。

这里列出的最后一种方法是简单地在值上设置一个标志，表示它不再被使用，这甚至比第一种方法更快，并且保持结构，但除非你以后能找到替换它的值，否则你无法重用该槽位。

* * *