arrays - 使用偏移量链接数组的元素

Question

以下摘自 Niklaus Wirth 的“算法 + 数据结构 = 程序”，“1.7. 记录结构”一章:

在另一个示例中，我们假设(可能是为了更快地找到他们)数组 a 中的某些人组链接在一起。链接信息由记录结构 Person 的附加组件表示，名为 link。这些链接将记录连接成线性链，以便可以轻松找到每个人的继任者和前任。这种链接技术的有趣特性是，可以根据存储在每个记录中的单个数字在两个方向上遍历链。该技术的工作原理如下。

假设链上三个连续成员的索引分别为i_k-1, i_k , i_k+i。第k个成员的链接值被选择为i_k+1—i_{k -1。正向遍历链，ik+1由当前两个索引变量x = ik-1确定，y = ik 为:}

i_k+1 = x+a[y].link

而在向后方向遍历链时，i_k-1 由 x = i_k+1 确定/em>，并且 y = i_k 为:

i_k-1 = x - a[y].link

一个例子是在一个表中链接所有同性的人:

Index  First Name Sex  Link
-----  ---------- ---  ----
1      Carolyn    F    2
2      Chris      M    2
3      Tina       F    5
4      Robert     M    3
5      Jonathan   M    3
6      Jennifer   F    5
7      Raytheon   M    5
8      Mary       F    3
9      Anne       F    1
10     Mathias    M    3

我无法理解链接的工作原理。假设我们要从 y = i_k = a[1] 开始向前遍历链。由于我们没有前面的i_k-1元素，x的起始值是多少？我试过从 x = 0 或 x = 1 开始，但两者都会导致错误的序列。如果我们想反向遍历链怎么办？

Answer 1

如果向前遍历，它假定您从链中索引最低的元素开始，如果向后遍历，则假定您从链中索引最高的元素开始。这些元素设置了它们的链接值，以便 x 的初始值等于当前索引 y。比如遍历雌性:

向前遍历，从 Carolyn 开始......

我<子>k = y = 1

i_k-1 = x = 1(x 的初始猜测与 y 相同)

i_k+1 = x + a[y].link = 1 + 2 = 3

...索引 3 处的人是 Tina。成功!

向后遍历，从 Anne 开始......

我<子>k = y = 9

i_k-1 = x = 9(x 的初始猜测与 y 相同)

i_k+1 = x - a[y].link = 9 - 1 = 8

...索引 8 处的人是玛丽。成功!

我不认为你可以用这种方法从 table 中间的任意位置开始。只能从头向前遍历，或从末尾向后遍历。

---

编辑:为了完整起见，伙计们:

向前穿越，从克里斯开始……

我<子>k = y = 2

i_k-1 = x = 2(x 的初始猜测与 y 相同)

i_k+1 = x + a[y].link = 2 + 2 = 4

...索引 4 处的人是罗伯特。

向后遍历，从 Mathias 开始......

我<子>k = y = 10

i_k-1 = x = 10(x 的初始猜测与 y 相同)

i_k+1 = x - a[y].link = 10 - 3 = 7

...索引 7 的人是 Raytheon。