第 六 章 鏈結串列(Link List) 課程名稱：資料結構 授課老師：________ 2019/1/2
本章學習目標 1.讓讀者了解動態記憶體的配置方法及釋回記憶體空間。 2.介紹陣列與鏈結串列的差異。 3.介紹鏈結串列的運作原理。 4.介紹鏈結串列的應用。例如：多項式加法。 2019/1/2
本章內容 6-1 線性串列(Linear List) 6-2 陣列(Array)與鏈結串列(Link List)比較 6-3 動態記憶體配置(Dynamical Memory Allocation) 6-4 鏈結串列 6-5 單向鏈結串列(Singly Linked List) 6-6 鏈結堆疊與鏈結佇列 6-7 認識環狀鏈結串列(Circular Linked List) 6-8 雙向鏈結串列(Double Linked List) 6-9 多項式串列表示法 2019/1/2
6-1 線性串列(Linear List) 線性串列(Linear List)又稱有序串列(Ordered List)或循序串列(Sequential List)。它由許多元素A(1) 、A(2) 、…、A(n); n>0所組成，元素與元素之間有線性的相對關係，並且以循序方式儲存，因此，我們也可以將有次序排列之資料稱為串列(List)。例如：陣列。 2019/1/2
在日常生活中，有許多事物都是有次序性的關係。 例如： 1. 數字(0~9) 2. 英文字(A~Z) 3. 學生的座號(1,2,3,...,50) 4. 一年有四季(春、夏、秋、冬) 2019/1/2
優點： (1)資料的搜尋方便，可隨機讀取資料。 (2)設計時，資料結構簡單。 缺點： (1)事先需宣告固定記憶空間，彈性小。 (2)刪除或加入資料需移動大量資料。 2019/1/2
6-2 陣列(Array)與鏈結串列(Link List)比較 一般而言，串列可分為有序串列與無序串列。而有序串列便是指「陣列」，其資料儲存在連續記憶空間；而無序串列則是透過指標Pointer，資料乃是儲存在非連續性的記憶空間，如此可以彈性的在串列上增減元素。 基本上它是以變更鏈結指標的方式達成，允許資料在串列中的任一位置加入資料，刪除資料等動作。而在實際需要時才配置記憶體空間。 2019/1/2
本結構的範例以單一鏈結線性串列為例。如圖6-1所示。 利用變更鏈結指標達成鏈結串列元素的增減，允許在串列中的任何位置進行資料的調整與操作。 2019/1/2
6-3 鏈結串列 【定義】 鏈結串列是由一個或一個以上動態記憶體分配的「節點」 (node)所組成，每一個節點至少會有兩個或兩個以上的欄位，分別存放資料及指標，此指標稱為鏈結(link)。若某節點無下一個節點，則此節點的連結為空指標(Null)。如圖6-2所示： 2019/1/2
【特性】 1. 各節點不一定要佔用連續的記憶體空間。 2. 各節點之資料型態不一定要相同。 3. 插入／刪除節點方便。 鏈結串列各元素在記憶體之位置是不連續的。它是由動態記憶體分配的節點(Node)串接而成。 (相形之下，陣列為一個循序(Sequential)之記憶體結構)。 2019/1/2
表6-1 Array 與 Link List 的比較 2019/1/2
6-4 單向鏈結串列(Singly Linked List) 【定義】 單向鏈結串列是串列中最常用的一種，它像火車一般，所有節點串成一列，而且指標所指的方向一樣。 【節點結構】 每一個節點不必儲存於連讀記憶位址，並且包含下面兩個基本欄位： 2019/1/2
節點結構可定義如下： class node //以結構來表示節點 { int data; // data儲存節點資料項目 node link; // link儲存下一個節點的位址 public node(int data) this.data=data; this.link=Null; } 2019/1/2
【圖示】單向鏈結串列之結構 其中 list：指向串列前端之指標 2019/1/2
為了往後方便解說，我們通常在串列前端加入一個首節點(Head Node)， 它是用來指向串列的第一個節點，而首節點並沒有任何資料。 因此，上列單向鏈結串列亦可表示為： 2019/1/2
6-4.1 LinkedList類別的方法 由於VB程式語言中，沒有結構可以直接來宣告資料型態，還好，在VB物件導向程式語言中，它提供了LinkedList類別來使用，因此，我們就可以直接使用此類別中的所有方法，例如：鏈結串列的建立、插入及刪除等操作動作都可以非常容易的撰寫程式碼。 2019/1/2
LinkedList( )：指建立一個空的鏈結串列，亦即串列的初始化。 二、屬性 1.Count：指取得鏈結串列中的節數總數。 一、建構函數 LinkedList( )：指建立一個空的鏈結串列，亦即串列的初始化。 二、屬性 1.Count：指取得鏈結串列中的節數總數。 2.First：指取得鏈結串列中的第一個節點。 3.Last：指取得鏈結串列中的最後一個節點。 2019/1/2
1.AddFirst(Object newnode)： 指在鏈結串列中的開頭，加入某一新元素(節點或值)。 三、方法 1.AddFirst(Object newnode)： 指在鏈結串列中的開頭，加入某一新元素(節點或值)。 2.AddLast(Object newnode)： 指在鏈結串列中的結尾，加入某一新元素(節點或值)。 3.Clear()： 指將全部的鏈結串列之節點移除。 2019/1/2
4.Contains(Object oldnode)： 指判斷現有的鏈結串列中是否有包含某一個舊元素(節點或值)。 5. Remove(int index )： 指移除鏈結串列中指定索引位置的元素(節點或值)。 6. RemoveFirst( )： 指移除鏈結串列之開頭的元素(節點或值)。 7. RemoveLast( )： 指移除鏈結串列之結尾的元素(節點或值)。 2019/1/2
6-4.2 單向鏈結串列的建立 如果需要的節點是兩個或兩個以上時，常見的作法就是先建立一個指向鏈結串列首的指標，再利用迴圈結構將其餘節點一個一個加入到串列的尾端。 2019/1/2
【舉例】請製作兩個或兩個以上的節點之鏈結串列 【執行結果】 2019/1/2
6-4.3 單向鍵結串列中節點的刪除 討論鏈結串列內的節點刪除時，依據所刪除節點的位置會有三種不同的情形： 1.刪除串列的第一個節點 6-4.3 單向鍵結串列中節點的刪除 討論鏈結串列內的節點刪除時，依據所刪除節點的位置會有三種不同的情形： 1.刪除串列的第一個節點 2.刪除串列內的中間節點 3.刪除串列後的最後一個節點 2019/1/2
1.刪除串列的第一個節點 只要把串列首指標指向第二個節點即可。 2019/1/2
2019/1/2
2.刪除串列內的中間節點 只要將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可。 2019/1/2
2019/1/2
3.刪除串列後的最後一個節點 只要指向最後一個節點的指標，直接指向NULL即可。 2019/1/2
2019/1/2
6-4.4 單向鏈結串列的插入節點 討論在鏈結串列內的插入節點時，依據所插入節點的位置會有三種不同的情形： 1.在串列的第一個節點前插入節點 6-4.4 單向鏈結串列的插入節點 討論在鏈結串列內的插入節點時，依據所插入節點的位置會有三種不同的情形： 1.在串列的第一個節點前插入節點 2.在串列的最後一個節點後面插入節點 3.在串列的中間位置插入節點 2019/1/2
1.在串列的第一個節點前插入節點 只需把新節點的指標指向串列首，再把串列首移到新節點上即可。 2019/1/2
2.在串列的最後一個節點後面插入節點 把串列的最後一個節點的指標指向新節點，新節點再指向NULL即可。 2019/1/2
3.在串列的中間位置插入節點 如果插入的節點是在P與Q之間，只要將P節點的指標指向新節點R，新節點的指標指向Q節點即可。 2019/1/2
6-4.5 鏈結串列的反轉 一般而言，單向鏈結串列都是由左至右的方向來鏈結，亦即串列中每一節點的指標欄都可以知道下一個節點的位置，但是，如果我們所需的情況是反轉列印資料時，就必須要將單向鏈結串列反轉過來。 例如：輸入ABCD，而輸出DCBA諸如此類的問題。如圖6-3所示。 2019/1/2
6-4.6 鏈結串列的連結 對於兩個或兩個以上鏈結串列的連結(Concatenation)，其實作法也很容易；只要將串列的首尾相連即可。如圖6-4所示。 2019/1/2
6-4.7 鏈結串列的長度 一般而言，串列的長度是指串列中節點的個數，但不包括首節點。 如下圖中串列的長度為4。 6-4.7 鏈結串列的長度 一般而言，串列的長度是指串列中節點的個數，但不包括首節點。 如下圖中串列的長度為4。 因此，我們可以撰寫一個演算法來計算串列的長度，從首節點的下一個節點開始，由左至右依序拜訪，直到最後一個節點向指Null即可。 2019/1/2
6-5 認識環狀鏈結串列 (Circular Linked List) 【定義】 將鏈結串列的最後一個節點的指標指向鏈結串列結構的第一個節點，我們就稱此串列為環狀鏈結串列。如圖6-7所示。 說明：環狀鏈結串列的建立只需將最後1個節點的next指標指向第1個節 點，即可完成環狀鏈結串列的建立。 2019/1/2
6-5.1 環狀鏈結串列-插入節點 一、加入新資料項目到環狀鏈結串列的前端 2019/1/2
2019/1/2
2019/1/2
如果插入的節點是在P與Q之間，只要將P節點的指標指向新節點R，新節點的指標指向Q節點即可。 二、加入新資料項目到環狀鏈結串列的中間 如果插入的節點是在P與Q之間，只要將P節點的指標指向新節點R，新節點的指標指向Q節點即可。 2019/1/2
三、加入新資料項目到環狀鏈結串列的尾端 2019/1/2
2019/1/2
2019/1/2
6-5.2 環狀鏈結串列-刪除節點 一、刪除環狀串列的第一個節點： 2019/1/2
2019/1/2
只要將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可 二、刪除串列內的中間節點 只要將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可 2019/1/2
2019/1/2
6-6 雙向鏈結串列 (Double Linked List) 由於單向鏈結串列只能一個方向來進行，而無法往回走。因此，本單元中將介紹雙向鏈結串列來解決此一問題，其定義如下： 每一個節點具有三個欄位，中間為資料欄位。左右各有兩個指標欄 位，分別為Llink及Rlink。其中Llink指向上一個節點，而Rlink指向下一個 節點。 2. 建立雙向鏈結串列的方法，首先就是宣告每個節點有三個欄位。 由於雙向鏈結串列的加入與刪除動作與單向鏈結串列相同，因此， 筆者就不在此多加介紹。但雙向鏈結串列也有許多優缺點，請讀者 在實務的應用上，可依照情況來選擇。 2019/1/2
雙向鏈結串列的優缺點如下說明： 【優點】 1. 雙向鏈結串列有兩個指標節點，在處理加入或刪除節點動作時， 速度比較快。 2.若雙向鏈結串列有任一端的指標連結錯誤或脫落，它可以快速進行 修補錯誤或脫落的連結節點。 【缺點】 1. 由於雙向鏈結串列有兩個指標節點，所以比較浪費記憶體空間。 2. 雙向鏈結串列的加入或刪除時，必須要有較多的連結節點。 2019/1/2
6-7 多項式串列表示法 多項式的鏈結串列表示法主要是儲存非零項目，並且每一項均符合以下資料結構： 2019/1/2
6-7.1 多項式串列的資料結構 假設有n個非零項，則可以表示如圖6-8所示： 2019/1/2
雖然在第三章已經介紹利用陣列來處理多項式，但是，鏈結串列在 處理多項式具有以下兩項優點： 1. 當多項式的內容變動(加入或刪除)時，則比較容易處理。 2. 鏈結串列可以動態的配置記憶體，因此，比較有彈性。 2019/1/2
6-7.2 多項式的相加 了解多項式串列的資料結構之後，接下來，我們來實際完成多項式的相加，其方法為逐一比較兩個多項式的項次，當指數相同時，則可以直接相加，而當指數較大者，則可以直接照抄下來，直到兩個多項時比較完畢為止。 2019/1/2
2019/1/2
2019/1/2
2019/1/2
2019/1/2
2019/1/2