Chap 4 鏈結串列 Linked Lists

回顧 在先前章節中已介紹利用陣列與循序表示法來表示簡單的資料結構。這些表示法的特性是資料物件的後繼節點會儲存在固定間隔的位置中。 若循序表示法被應用在有序串列上，那插入或刪除任意的元素等運算的代價將會很高。 若資料具有不同的資料量時使用循序表示法時空間效率較低。

鏈結串列(Linked List) 在先前所提的問題中，鏈結串列提供比循序表示法更好的解決方式。 在鏈結串列中資料並非以循序的方式儲存在記憶體中，相反的它可能儲存在記憶體的任何一個地方。資料間的串連藉由紀錄資料存放的位址即可。每個資料必須負責記錄相鄰資料的存放位址。 一個鏈結串列包含一個 head 指標，此指標負責指向此鏈結串列的第一個資料。 從鏈結串列的第一個資料開始，經由第一個資料、第二個資料、第三個資料…等一個接著一個的方式循序搜尋整個資料串列。

鏈結串列的插入操作 在鏈結串列中在FAT與HAT之間插入資料物件 GAT，步驟如下: 找一個未被使用的節點 x. 將這個節點的 data 欄位設成 GAT. 將 x 的link 欄位設成指向FAT的下一個節點，也就是包含HAT的節點. 將包含FAT的節點的 link 欄位設成指向 x.

鏈結串列的插入和刪除 first BAT CAT EAT FAT HAT GAT first BAT CAT EAT FAT GAT HAT

Program 4.1 Composite Classes class ThreeLetterList; // forward delcarion class ThreeLetterNode { friend class ThreeLetterList; private: char data[3]; ThreeLetterNode * link; }; class ThreeLetterList { public: // List Manipulation operations . ThreeLetterNode *first;

Nested Classes The Three Letter List problem can also use nested classes to represent its structure. class ThreeLetterList { public: // List Manipulation operations . private: class ThreeLetterNode { // nested class char data[3]; ThreeLetterNode *link; }; ThreeLetterNode *first;

在串列後端插入新節點 Template <class Type> Void List<Type>::Attach(Type k) { ListNode<Type>*newnode = new ListNode<Type>(k); if (first == 0) first = last =newnode; else { last->link = newnode; last = newnode; } };

串接兩個串列 Template <class Type> void List<Type>:: Concatenate(List<Type> b) // this = (a1, …, am) and b = (b1, …, bn) m, n ≥ , // produces the new chain z = (a1, …, am, b1, bn) in this. { if (!first) { first = b.first; return;} if (b.first) { for (ListNode<Type> *p = first; p->link; p = p->link); // no body p->link = b.first; }

將串列倒轉 Template <class Type> void List<Type>:: Reverse( ) // List is reversed so that (a1, …, am) becomes (am, …, a1) . { ListNode <Type> *current = first; *previous = 0; //previous trails current while (current) { ListNode <Type> *r = previous; previous = current; current = current -> link; previous->link = r; } first = previous;

環狀串列 將串列的最後一個節點指向第一個節點即形成環狀串列. 在進行此步驟前須先確定目前的節點為最後一個節點. 在環狀串列中進行插入以及刪除時須注意不要破壞環狀串列的結構.

環狀串列示意圖 first last

鏈結堆疊與佇列 top front rear Linked Queue Linked Stack

多項式表示法 14 3 2 8 1 a.first 14 8 -3 10 6 b.first

多項式類別定義 struct Term // all members of Terms are public by default { int coef; // coefficient int exp; // exponent void Init(int c, int e) {coef = c; exp = e;}; }; class Polynomial friend Polynomial operator+(const Polynomial&, const Polynomial&); private: List<Term> poly;

多項式運算(相加) 在鏈結串列上進行多項式運算較為容易， 例如兩個多項式的相加 a.first b.first 3 14 2 8 1 p b.first 8 14 -3 10 10 6 q (i) p->exp == q->exp c.first 11 14

多項式運算(相加) a.first b.first c.first (ii) p->exp < q->exp p q 3 14 2 8 1 p b.first 8 14 -3 10 10 6 q c.first 11 14 -3 10 (ii) p->exp < q->exp

多項式運算(相加) a.first b.first c.first (iii) p->exp > q->exp p q 3 14 2 8 1 p b.first 8 14 -3 10 10 6 q c.first 11 14 -3 10 2 8 (iii) p->exp > q->exp

串列解構子 Template <class Type> List<Type>::~List() // Free all nodes in the chain { ListNode<Type>* next; for (; first; first = next) { next = first->link; delete first; }

可用空間串列 在建立或刪除串列時，如果一次建立一個節點或一次刪除一個節點，那麼它所需要的時間將和串列的長度呈線性正比. 如果能夠自行維護一個自由節點的鏈結串列，那麼這些建構子或解構子的執行時間將可以降到 O(1). 當需要一個新的節點時，先檢查自由節點鏈。若這個鏈不是空的可以拿這個鏈中的一個節點來用。只有當這個鏈是空的時候才需要再呼叫 new 來產生一個新的節點.

可用空間串列使用 使用環狀鏈結串列來實作多項式表示與可用空間串列時，刪除多項式的時間將可在一固定時間內完成，此時間和多項式的項目數量或長度無關。

可用空間串列使用-刪除多項式 av 3 a.first 3 14 2 8 1 1 2 second av

等價類 對任一個多邊形 x, x ≡ x代表它自己本身是電路等價. 因此, ≡ 具反射性 (reflexive). 對任兩個多邊形 x 與 y, 假如 x ≡ y, 則 y ≡ x. 因此, ≡ 具對稱性 (symetric). 對任三個多邊形 x, y,與 z, 假如 x ≡ y 且 y ≡ z, 則 x ≡ z. ≡ 具遞移性 (transitive).

等價類 定義: 若一個作用在集合 S 上的一個關係 ≡, 我們稱 ≡ 為 S 的等價關係若且為若此關係具有反射性, 對稱性和遞移性. Example: Supposed 12 polygons 0 ≡ 4, 3 ≡ 1, 6 ≡ 10, 8 ≡ 9, 7 ≡ 4, 6 ≡ 8, 3 ≡ 5, 2 ≡ 11, and 11 ≡ 0. Then they are partitioned into three equivalence classes: {0, 2, 4, 7, 11}; {1 , 3, 5}; {6, 8, 9 , 10}

等價類 決定等價關係的演算法有兩階段 接下來針對還未被印出的元素，重複上述步驟，直至所有元素均找到對應的等價類別. 第一階段， 讀取並儲存每一等價序對 (i, j). 第二階段， 由 0 開始， 並找出所有 (0, j) ， 其中 0 和 j 同屬一個等價類。根據遞移性可以找到所有 (j, k) 隱含 k 和 0 屬同一等價類別。 持續此動作直到所有和 0 屬同一等價類別的元素均被找出. 接下來針對還未被印出的元素，重複上述步驟，直至所有元素均找到對應的等價類別.

等價類別鏈結串列表示法 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] data 11 link data 4 1 10 9 2 link

以鏈結串列表示稀疏矩陣 稀疏矩陣的循序表示法會遭遇類似多項式表示法的缺點. 利用環狀鏈結串列來表示稀疏矩陣，其中節點部分分成兩類: 標頭節點 (head node): tag, down, right, and next 元素節點 (entry node): tag, down, row, col, right, value 列 i 的標頭節點同時也是行 i 的標頭節點. 每一個標頭節點會出現在三個串列中: 列串列、行串列和標頭串列. 若要表示一個具有numTerms非零項的 n x m 稀疏矩陣, 需要 max{n, m} + numTerms + 1 個節點.

稀疏矩陣相關的節點結構 f i j Head node Typical node Setup for aij down tag right down tag row col right f i j next value Head node Typical node Setup for aij A 4x4 sparse matrix

稀疏矩陣的鏈結表示 H0 H1 H2 H3 Matrix head 4 H0 2 11 H1 1 12 H2 2 1 -4 H3 3 -15

雙向鏈結串列 使用單項鏈結串列的缺點在於單項鏈結僅能順著鏈結的方向移動，因此若目前指向節點 ptr, 但目標為ptr的前一個節點時， 唯一的方法就是從串列的起始節點開始尋找. 在刪除節點的過程中必須找到前一個節點， 因此雙向鏈結提供較有效率的結構. 一個雙向鏈結串列的節點至少有三個欄位： 左鏈結欄位 (llink), 資料欄位 (item), 以及右鏈結欄位 (rlink).

雙向鏈結串列 一個雙向鏈結串列可以是環狀的，也可以不是；而且可能有一個標頭節點，也可能沒有. Empty List llink item rlink Head Node llink item rlink Empty List

x -> left -> right = x -> right 從雙向鏈結環狀串列中刪除節點 llink item rlink Head Node x -> left -> right = x -> right x -> right -> left = x -> left

插入節點至雙向鏈結環狀串列 p -> left = x; p -> right = x -> right; node node x x p newnode p p -> left = x; p -> right = x -> right; x -> right -> left = p; x -> right = p;

廣義串列(Generalized list) 定義: 一個廣義串列是一個包含 n 個元素的有限序列, α0, α1, α2, …, αn-1, n ≥ 0, 其中 αi (0≤ i ≤ n – 1)可以是一個基本元素, 也可以是一個串列. 如果 αi, 不是基本元素 (atom), 那麼便稱之為子串列 (sublists). 令 A = (α0, …, αn-1 ) 是一個串列, 其中 n 代表串列的長度. 依慣例, 所有串列名稱都以大寫字母表示, 小寫字母則用來表示串列中的基本元素. α0 是串列 A 的頭(head), 而 (α1, …, αn-1) 則是串列的尾 (tail).

廣義串列範例 D = ( ): 零或空的串列; 長度為 0. A = (a, (b, c)): 長度為二的串列; 第一個元素為基本元素 a, 第二個元素則是線性串列 (b, c). B = (A, A, ( )):長度為三的串列; 前兩個元素為串列 A, 第三個元素是空串列. C = (a, C):長度為二的遞迴串列; C 代表一個無限串列 (a, (a, (a, …))). head(A) = ‘a’, tail(A) = (b, c), head(tail(A) ) = (b, c), tail(tail(A)) = (). 串列可以跟其它串列共用. 串列可以是遞迴的.

廣義串列應用範例 第一種表示法: P的每一項均可用一個包含四個欄位的結構來表示(coef、expx、expy、expz) 。採用這方式需為單變數多項式定義出一個結構、雙變數多項式又定義另一個結構… 。 第二種表示法:定義一種擁有大量指數欄位的結構，視需要便使用多少個指數欄位。此方式浪費空間。

廣義串列應用範例 P(x, y, z) 可表示為: 上述多項式可表示成 Cz2 + Dz. 其中 C 和 D 也是多項式, 但他們是變數 x 與 y 的多項式. 觀察 C, 其形式為 Ey3 + Fy2, 其中 E 和 F 為變數 x 的多項式. 重複此方法, 可發現每個多項式都包含一個變數加上一個係數和指數. 每一個係數本身也是一個多項式.

廣義串列的節點型態 enum Triple{ var, ptr, no }; class PolyNode { PolyNode *link; int exp; Triple trio; union { char vble; PolyNode *dlink; int coef; };

廣義串列的節點型態 trio == var: 代表此節點為串列的標頭節點. vble 用以儲存變數名稱, 此時 exp 欄位的內容為0. 如果將所有變數均儲存於一個表格內且 vble 儲存的內容為表格的索引值, 此時 vble 為整數型態. trio == ptr: 此時係數本身就是一個串列且由 dlink 欄位指到它. exp 則代表這個串列上的變數的指數. trio == no, 此時系數是一個整數而且被儲存於欄位 coef 中. exp 則代表這個串列上的變數的指數.

3x2y 表示法 trio vble exp link trio vble exp link var y ptr 1 var x no 3 ptr 1 var x no 3 2 P

P(x, y, z) 表示法 P(x, y, z) v z p 2 p 1 v y p 3 p 2 v y p 4 p 1 v x n 2 p 2 p 1 v y p 3 p 2 v y p 4 p 1 v x n 2 v x n 3 8 v x n 1 10 n 2 8 v x n 1 4 n 6 3

串列的遞迴演算法 遞迴演算法通常包含兩個元件: 遞迴函數本身 (主函式); 宣告為私有函式 在程式頂層呼叫這個遞迴函式的另一個函式 (驅動函式); 宣告為公用函式.

程式(複製一個串列) void GenList::Copy(const GenList& l) { first = Copy(l.first); } GenListNode* GenList::Copy(GenListNode *p) // Copy the nonrecursive list with no shared sublists pointed at by p GenListNode *q = 0; if (p) { q = new GenListNode; q->tag = p->tag; if (!p->tag) q->data = p->data; else q->dlink = Copy(p->dlink); q->link = Copy(p->link); return q;

A 的鏈結表示 A=((a, b), ((c, d), e)) r b t t t u v s f a f b t f e w x f c t u v s f a f b t f e w x f c f d

串列表示法 D = 0 Empty list A=(a, (b, c)) A f a t f b t c B t t f b t c B t t B=(A, A, ()) C f a t C=(a, C)

執行複製程式時的參數值 Level of recursion Value of p Continuing level p 1 b 2 r 3 4 v t w 5 x 6

Important List Functions List Equality (Program 4.37) List Depth (Program 4.38) An empty list has depth 0.

Reference Counts, Shared and Recursive Lists Lists may be shared by other lists for the purpose of space saving. Lists that are shared by other lists create problems when performing add or delete functions. For example, let’s look at the previous A, B, C, D example. When deleting the front node of list A would requires List B to update its pointers. The use of the data field of a head node to record the reference count can resolve the aforementioned problem. The list can not be deleted unless the reference count is 0.

Example of Reference Counts, Shared and Recursive Lists 1 A=(a, (b, c)) Y f 3 f a t f 1 f b f c Z f 1 t t t B=(A, A, ()) W f 2 f a t f 1 C=(a, C)

Erasing A List Recursively // Driver GenList::~GenList() // Each head node has a reference count. We assume first ≠ 0. { Delete(first); first = 0; } // Workhorse void GenList::Delete(GenListNode* x) x->ref--; // decrement reference coutn of head node. if (!x->ref) GenListNode *y = x; // y traverses top-level of x. while (y->link) { y= y->link; if (y->tag == 1) Delete (y->dlink);} y->link = av; // Attach top-level nodes to av list av = x;

Issue In Erasing Recursive Lists When erasing a recursive list (either direct recursive or indirect recursive), the reference count does not become 0. Then the nodes are not returned to available list. This will cause memory leak issue.