Skip pointers / Skip lists

先前第一章有提到兩個串列的AND合併，這個章節是要討論能夠在比較次數最少的時候，做出兩串列的合併，所使用到的是跳躍指標(Skip pointers)，另外必須注意一點是串列必須是有序的，也就是要先排序過。

Exercise2-1:

這題會給定一個數列，並依照題意算出找尋該數的次數

L1: 4 6 10 12 14 16 18 20 22 32 47 81 120 122 157 180

(1): 47 using the standard posting list.

solution:

    這題是要你使用最簡單的方法逐一的從頭開始搜尋47所要的次數
    4->6->10->12->14->16->18->20-22->32->47

                                                        Ans : 11次

(2): 47 using skipped pointer skip length.

solution:

    這題是要你使用跳躍指標搜尋47所要的次數，其中跳耀的長度使用均等空間√P
(P代表串列的總長，故skip length=4)。走訪方式就一直跳躍當該數小於要被搜尋
的數值到大於時就往回到上一個節點逐一搜尋，如圖:。
    
    4->14->22->120->32->47

                                                        Ans : 6次

各位可以試試使用skip pointer搜尋76和100這兩個數字，發現答案都是7次。

Exercise2-2:

藉由上面例題各位應該熟知跳躍指標了用法，以下就使用該方法AND合併兩串列吧!

L1: 3 5 9 15 24 39 60 68 78 81 84 89 92 96 97 100 115
L2: 3 5 89 95 97 99 100 101

solution:

    兩兩從第一個開始比較較小的一方往前一步，遇到節點指標就使用指標跳躍
skip length = √17 = 4

        (3,3)✓
        (5,5)✓
        (9,89)
        (15,89)
        (24,89)
        (75,89)
        (92,89)△
        (81,89)
        (84,89)
        (89,89)✓
        (92,95)
        (115,95)△
        (96,95)X
        (96,97)
        (97,97)
        (100,99)X
        (100,100)✓
        (105,101)X

                                                    Ans: 共18次