算法導論讀書筆記（10）
目錄
- 棧和隊列
- 棧
- 隊列
- 連結清單
- 有根樹的表示
- 二叉樹
- 分支數無限的有根樹
棧和隊列
棧和隊列都是動态集合。棧實作了一種 先進先出 的政策。類似地，隊列實作了一種 後進先出 的政策。
棧
作用于棧上的
INSERT
操作稱為 壓入 （
PUSH
），而無參的
DELETE
操作常稱為 彈出 （
POP
）。可以使用一個數組 S [ 1 .. n ]來實作一個至多有 n 個元素的棧。如下圖所示，數組 S 有個屬性 S.top ，它指向最近插入的元素。
STACK-EMPTY(S)
1 if S.top == 0
2 return TRUE
3 else
4 return FALSE
PUSH(S, x)
1 S.top = S.top + 1
2 S[S.top] = x
POP(S)
1 if STACK-EMPTY(S)
2 error "underflow"
3 else
4 S.top = S.top - 1
5 return S[S.top + 1]
隊列
我們把作用于隊列上的
INSERT
操作稱為 入隊 （
ENQUEUE
），把作用于隊列上的
DELETE
操作稱為 出隊 （
DEQUEUE
）。隊列有 頭 和 尾 。當一個元素入隊時，将排在隊尾，而出隊的元素總是隊首元素。下圖說明了用一個數組 Q [ 1 .. n ]來實作一個至多含 n - 1 個元素的隊列的方法。隊列具有屬性 Q.head ，它指向隊列的頭，另一個屬性為 Q.tail ，它指向新元素将會被插入的地方。
ENQUEUE(Q, x)
1 Q[Q.tail] = x
2 if Q.tail == Q.length
3 Q.tail = 1
4 else
5 Q.tail = Q.tail + 1
DEQUEUE(Q)
1 x = Q[Q.head]
2 if Q.head == Q.length
3 Q.head = 1
4 else
5 Q.head = Q.head + 1
6 return x
連結清單
在 連結清單 中，各對象按線性順序排序。其順序由各對象中的指針決定。本節介紹的是無序的雙連結清單。 雙連結清單 的每一個元素都是一個對象，每個對象包含一個關鍵字域和兩個指針域： next 和 prev 。對連結清單中的某個元素 x ， x.next 指向連結清單中 x 的後繼元素，而 x.prev 則指向連結清單中 x 的前驅元素。下面給出的是連結清單的基本操作。
LIST-SEARCH(L, k)
1 x = L.head
2 while x != NIL and x.key != k
3 x = x.next
4 return x
LIST-INSERT(L, x)
1 x.next = L.head
2 if L.head != NIL
3 L.head.prev = x
4 L.head = x
5 x.prev = NIL
LIST-DELETE(L, x)
1 if x.prev != NIL
2 x.prev.next = x.next
3 else
4 L.head = x.next
5 if x.next != NIL
6 x.next.prev = x.prev
有根樹的表示
用連結清單表示有根樹
二叉樹
如下圖所示，用域 p ， left ， right 來存放指向二叉樹 T 中的父親，左兒子和右兒子的指針。如果 x.p =
NIL
，則 x 為根。如果結點 x 無左兒子，則 x.left =
NIL
，對右兒子也類似。整個樹 T 的根由屬性 T.root 指向。如果 T.root =
NIL
，則樹為空。
分支數無限的有根樹
可以用二叉樹很友善地表示具有任意子女數的樹。該方法的優點是對任意含 n 個結點的有根樹僅用 O ( n )空間。這種 左孩子 ， 右兄弟 的表示如下圖所示。每個結點都包含一個父親指針 p ， T.root 指向樹 T 的根。每個結點 x 不再包含指向每個孩子結點的指針，而僅包含兩個指針：
- x.left-child 指向結點 x 的最左孩子。
- x.right-sibling 指向結點 x 緊右邊的兄弟。
如果 x 沒有孩子，則 x.left-child =
NIL
；如果 x 是其父結點的最右孩子，則 x.right-sibling =
NIL
。
轉載于:https://www.cnblogs.com/sungoshawk/p/3649004.html