具有偏移

Question

下面陣列的聯接元件是從「算法+數據結構=程序」，由尼克勞斯·維爾特，章的摘錄「1.7記錄結構。」：

在一個進一步的例子中，我們假設（可能爲了更快地找到它們）將數組a中的某些人連接在一起。鏈接信息由記錄結構的附加組件人表示，其名稱爲鏈接。這些鏈接將記錄鏈接成一個線性鏈，這樣每個人的後繼者和前任都可以很容易找到。這種鏈接技術的有趣特性是鏈可以在每個記錄中存儲的單個數字的基礎上在兩個方向上遍歷。該技術的工作原理如下。

假設鏈的三個連續的成員的指數我 _K-1，我_ķ，我 _{K +我}。所述ķ個構件的鏈接值被選擇爲我 _{K + 1} - 我 _K-1。遍歷在向前方向上的鏈，我 _{K + 1}從兩個電流索引變量確定X = I _K-1，和Y = 1 _ķ爲：

我 _{K + 1} = X + A [Y]。鏈路

而在向後的方向上穿過所述鏈，我一個[Y]。鏈路 -

我 _K-1 = X：K-1從X = I _{K + 1}，和Y = 1 _ķ所確定

一個例子連結同性別的所有人員在一個表：

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。例如，遍歷所述女性：

遍歷向前，從卡羅琳...

我_ķ = Y = 1

我 _K-1 = X = 1（用於初始猜測x是相同的爲y）

我 _{K + 1} = X + A [Y]。鏈路= 1 + 2 = 3

...在索引3的人是錫一個。成功！

向後遍歷與安開始...

我_ķ = Y = 9

我 _K-1 = X = 9（對於x的初始猜測是一樣的y）的

我 _{K + 1} = X - 一個[Y]。鏈路= 9 - 1 = 8

...在索引8的人是瑪麗。成功！

我不認爲你可以從這個方法的表中間的任意位置開始。你只能從一開始往前走，或者從結尾往後走。

---

編輯：爲了完整起見，小夥子：

遍歷向前，從克里斯...

我_ķ = Y = 2

我K- = x = 2（x的初始猜測與y相同）

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

...索引4處的人是羅伯特。

向後遍歷，具有的Mathias開始...

我_ķ = Y = 10

我 _K-1 = X = 10（對於x的初始猜測是一樣的y）的

我 _{K + 1} = X - 一個[Y]。鏈路= 10 - 3 = 7

...該人在索引7是Raytheon公司。