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

Question

以下摘自 Niklaus Wirth "Algorithms + Data Structures = Programs" 的“1.7. 记录结构”一章：

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

假设链上连续三个成员的索引为i_k-1,i_k, i_k+i。第 k 个成员的 link 值被选择为 i_k+1 —i_k-1。正向遍历链，i_k+1由当前两个索引变量x = i_k-1，并且 y = i_k 如：

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

而向后遍历链，i_k-1 由 x = i_k+1，并且 y = i_k 如：

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

一个例子是 link 在 table:

中所有同性的人

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

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

Answer 1

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

向前移动，从 Carolyn 开始...

i_k = y = 1

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

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

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

向后遍历，从安妮开始...

i_k = y = 9

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

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

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

我认为您不能使用此方法从 table 中间的任意位置开始。只能从头向前遍历，或从末尾向后遍历。

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

向前移动，从克里斯开始...

i_k = y = 2

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

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

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

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

i_k = y = 10

i_k-1 = x = 10（x 的初始猜测与 y 相同）

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

...索引7的人是雷神

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

Linking elements of an array with an offset

arrays

algorithm

traversal