1、 線性表的鏈式儲存結構

1、線性表的鏈式儲存結構—連結串列

（1）如果每個結點只設置一個指向其後繼結點的指標成員，這樣的連結串列稱為線性單向連結表，簡稱單鏈表。

（2）如果每個結點中設定兩個指標成員，分別用以指向其前驅結點和後繼結點，這樣的連結串列稱之為線性雙向連結表，簡稱雙鏈表。

2、單鏈表

每個結點為LinkNode類物件，包括儲存元素的資料列表data和儲存後繼結點的指標屬性next。

單鏈表類LinkList

結點引用方式：

插入結點操作：將結點s插入到單鏈表中p結點的後面。

整體建立單鏈表

透過一個含有n個元素的a陣列來建立單鏈表。

建立單鏈表的常用方法有兩種：頭插法和尾插法。

頭插法建表

從一個空表開始，依次讀取陣列a中的元素。

生成新結點s，將讀取的資料存放到新結點的資料成員中。

將新結點s插入到當前連結串列的表頭上。

頭插法建立的單鏈表中資料結點的次序與a陣列中的次序正好相反

尾插法建表

從一個空表開始，依次讀取陣列a中的元素。

生成新結點s，將讀取的資料存放到新結點的資料成員中。

將新結點s插入到當前連結串列的表尾上。

頭插法建立的單鏈表中資料結點的次序與a陣列中的次序正好相同

3、線性表基本運算在單鏈表中的實現

查詢序號為i（0≤i≤n-1，n為單鏈表中資料結點個數）的結點

將元素e新增的線性表末尾Add(e)

求線性表的長度getsize()

求線性表中序號為i的元素GetElem(i)

設定線性表中序號為i的元素SetElem(i，e)

求線性表中第一個值為e的元素的邏輯序號GetNo(e)

線上性表中插入e作為第i個元素Insert(i，e)

輸出線性表所有元素display()

4、基於單鏈表基本操作的演算法設計

練習1：有一個長度大於2的整數單鏈表L，設計一個演算法查詢L中中間位置的元素。

例如，L=（1，2，3），返回元素為2；L=（1，2，3，4），返回元素為2。

計數法：計算出L的長度n，假設首結點的編號為1，則滿足題目要求的結點的編號為(n-1)/2+1（這裡的除法為整除）。置j=1，指標p指向首結點，讓其後移(n-1)/2-1個結點即可。

快慢指標法：設定快慢指標fast和slow，首先均指向首結點，當fast結點後面至少存在兩個結點時，讓慢指標slow每次後移動一個結點，讓快指標fast每次後移動兩個結點。否則slow指向的結點就是滿足題目要求的結點。

練習2有一個整數單鏈表L，其中可能存在多個值相同的結點，設計一個演算法查詢L中最大值結點的個數。

解：先讓p指向首結點，用maxe記錄首結點值，將其看成是最大值結點，cnt置為1。按以下方式迴圈直到p指向尾結點為止：

（1）若p.next.data>maxe，將p.next看成新的最大值結點，置maxe=p.next.data，cnt=1。

（2）若p.next.data==maxe，maxe仍為最大結點值，置cnt++。

（3）p後移一個結點。

最後返回cnt即為最大值結點個數。

解：過程如下：

先遍歷L的所有結點，求出最大結點值maxe。

練習4有一個整數單鏈表L，設計一個演算法逆置L中的所有結點。例如L=(1，2，3，4，5)，逆置後L=(5，4，3，2，1)。

練習5有一個含2n個整數的單鏈表L=（a0，b0，a1，b1，…，an-1，bn-1），設計一個演算法將其拆分成兩個帶頭結點的單鏈表A和B。

其中A=（a0，a1，…，an-1），B=（bn-1，bn-2，…，b0）。

練習6有兩個遞增有序整數單鏈表A和B，設計一個演算法採用二路歸併方法將A和B的所有資料結點合併到遞增有序單鏈表C中。

要求演算法的空間複雜度為O(1)。

練習7有兩個遞增有序整數單鏈表A和B，假設每個單鏈表中沒有值相同的結點，但兩個單鏈表中存在相同值的結點，設計一個儘可能高效的演算法建立一個新的遞增有序整數單鏈表C，其中包含A和B相同值的結點，要求演算法執行後不改變單鏈表A和B。

本演算法的時間複雜度為O(n+m)。

空間複雜度為O(MIN(n，m))。

其中m、n分別為A、B單鏈表中的資料結點個數，MIN為取最小值函式，因為單鏈表C中最多隻有MIN(n，m)個結點。