Связывание элементов массива со смещением

Question

Ниже приводится выдержка из «Структуры Алгоритмы + Данные = Программы» по Никлаус Вирт, глава «1.7 Структура записи.»:

В следующем примере мы предполагаем, что (возможно, чтобы быстрее их найти) некоторые группы лиц в массиве a связаны между собой. Информация связывания представлена ​​дополнительным компонентом структуры записи Лицо, названное link. Связи соединяют записи в линейную цепочку, чтобы можно было легко найти преемника и предшественника каждого человека. Интересным свойством этого метода связывания является то, что цепь может проходить по обоим направлениям на основе одного числа, сохраненного в каждой записи. Техника работает следующим образом.

Предположим, что индексы трех последовательных членов цепочки я _к-1, я _к, я _{K + I}. Значение звено-го элемента к выбирается так, чтобы быть я _{к + 1} - я _к-1. Обход цепь в прямом направлении, я _{к + 1} определяется из двух текущих переменных индекса х = я _к-1 и у = я _к как:

я _{к + 1} = х + а [у] .link

тогда пересекая цепь в обратном направлении, I _к-1 определяется из х = I _{к + 1} и у = я _к как:

я _к-1 = х - а [у] .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. Например, пересекая самка:

пересекающие вперед, начиная с Каролин ...

я _к = у = 1

я _к-1 = х = 1 (начальное приближение для х такое же, как у)

я _{к + 1} = х + а [у] .link = 1 + 2 = 3

... человек с индексом 3, является Олово а. Успех!

обход в обратном направлении, начиная с Энн ...

я _к = у = 9

я _к--= х = 9 (начальное приближение для й такого же, как у)

я _{к + 1 =} х - а [у] .link = 9 - 1 = 8

... человек с индексом 8 Мэри. Успех!

Я не думаю, что вы можете начать с произвольного положения в середине таблицы с помощью этого метода. Вы можете перемещаться вперед только с самого начала или назад с конца.

---

Edit: Для полноты: парни

обходе вперед, начиная с Крисом ...

я _к = у = 2

я _{k- 1} = x = 2 (начальное предположение для x совпадает с y)

i _{k + 1} = x + a [y] .link = 2 + 2 = 4

... Человек с индексом 4 - это Роберт.

обход в обратном направлении, начиная с Mathias ...

я _к = у = 10

я _к-1 = х = 10 (начальное приближение для й такого же, как у)

я _{к + 1 =} х - а [у] .link = 10 - 3 = 7

... человек с индексом 7 является Raytheon.