說(shuō)明：該系列博客整理自《算法導(dǎo)論(原書第二版)》，但更偏重于實(shí)用菜谣，所以晦澀偏理論的內(nèi)容未整理珠漂，請(qǐng)見諒。另外本人能力有限尾膊，如有問題媳危，懇請(qǐng)指正！
? ? 基本數(shù)據(jù)結(jié)構(gòu)包括：棧冈敛、隊(duì)列待笑、鏈表、有根樹抓谴。
1暮蹂、棧
????棧和隊(duì)列都是動(dòng)態(tài)集合寞缝。棧實(shí)現(xiàn)了一種 后進(jìn)先出(LIFO)?的策略，隊(duì)列實(shí)現(xiàn)了一種 先進(jìn)先出(FIFO)?的策略仰泻。棧操作的時(shí)間復(fù)雜度為O?(1)荆陆。
????作用于棧上的?INSERT?操作稱為?壓入?（?PUSH?），而無(wú)參的?DELETE?操作常稱為?彈出?（?POP?）集侯”惶洌可以使用一個(gè)數(shù)組?S?[ 1 ..?n?]來(lái)實(shí)現(xiàn)一個(gè)至多有?n?個(gè)元素的棧。數(shù)組?S?有個(gè)屬性?S.top?棠枉，它指向最近插入的元素浓体。由S 實(shí)現(xiàn)的棧包含元素S[1...S.top]，其中S[1]是棧底元素辈讶，S[S.top]是棧頂元素命浴。當(dāng)S.top=0時(shí)棧中不包含任何元素，此時(shí)棧為空棧荞估。如果試圖對(duì)一個(gè)空棧做彈出操作咳促，則稱棧“下溢”勘伺。如果S.top>n跪腹，則稱棧“上溢”飞醉。
STACK-EMPTY(S)
1 if S.top == 0//注意S.top的值是從1開始的
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]
2冲茸、隊(duì)列
????棧和隊(duì)列都是動(dòng)態(tài)集合。棧實(shí)現(xiàn)了一種 后進(jìn)先出(LIFO)的策略缅帘，隊(duì)列實(shí)現(xiàn)了一種 先進(jìn)先出(FIFO)的策略轴术。隊(duì)列操作的時(shí)間復(fù)雜度為O(1)。
? ??我們把作用于隊(duì)列上的?INSERT?操作稱為?入隊(duì)?（?ENQUEUE?）钦无，把作用于隊(duì)列上的?DELETE?操作稱為?出隊(duì)?（?DEQUEUE?）逗栽。隊(duì)列有?頭?和?尾?。當(dāng)一個(gè)元素入隊(duì)時(shí)失暂，將排在隊(duì)尾彼宠，而出隊(duì)的元素總是隊(duì)首元素。
????用一個(gè)數(shù)組?Q?[ 1 ..?n?]來(lái)實(shí)現(xiàn)一個(gè)至多含?n?- 1 個(gè)元素的隊(duì)列弟塞。隊(duì)列具有屬性?Q.head?凭峡，它指向隊(duì)列的頭，另一個(gè)屬性為?Q.tail?决记，它指向新元素將會(huì)被插入的地方摧冀。隊(duì)列需要在最后一個(gè)位置進(jìn)行“卷繞”，即隊(duì)列中的n個(gè)元素形成環(huán)形巢价，位置1接在位置n之后彤委。當(dāng)Q.head?=?Q.tail時(shí)隊(duì)列為空娶聘，當(dāng)Q.head?=?Q.tail+1時(shí)隊(duì)列為滿借卧。下面列出隊(duì)列的常用操作，但是省略了溢出檢查部分馆截。
ENQUEUE(Q, x)
1 Q[Q.tail] = x? //Q.tail?指向新元素將會(huì)被插入的地方
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
3锣笨、無(wú)哨兵鏈表
????在?鏈表?中，各對(duì)象按線性順序排序框产。其順序由各對(duì)象中的指針決定。本節(jié)介紹的是無(wú)序的雙鏈表错洁。?雙鏈表?的每一個(gè)元素都是一個(gè)對(duì)象秉宿，每個(gè)對(duì)象包含一個(gè)關(guān)鍵字域和兩個(gè)指針域：?next?和?prev?。對(duì)鏈表中的某個(gè)元素?x?屯碴，?x.next?指向鏈表中?x?的后繼元素描睦，而?x.prev?則指向鏈表中?x?的前驅(qū)元素。如果x.prev=nil导而，則它是鏈表的第一個(gè)元素忱叭；如果x.next=nil，則它是鏈表的最后一個(gè)元素今艺。L.head指向鏈表的第一個(gè)元素韵丑，如果L.head=nil，則鏈表為空虚缎。下面給出的是鏈表的基本操作撵彻。
? ? 查找操作的最壞時(shí)間復(fù)雜度為Θ(n)，插入操作運(yùn)行時(shí)間為O?(1)实牡，刪除操作運(yùn)行時(shí)間為O(1)陌僵。
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
4、哨兵鏈表=對(duì)無(wú)哨兵鏈表的改進(jìn)
? ? 哨兵可以簡(jiǎn)化邊界條件创坞。例如碗短，假設(shè)有鏈表L和一個(gè)對(duì)象L.nil，后者表示NIL题涨，但也包含和其他元素一樣的各個(gè)域偎谁。將鏈表算法中出現(xiàn)的每次對(duì)NIL的引用，用哨兵元素L.nil的引用來(lái)代替携栋，這樣搭盾，就可以將一個(gè)一般的雙向鏈表變成一個(gè)帶哨兵的環(huán)形雙向鏈表，哨兵元素L.nil介于頭和尾之間婉支。L.nil.next指向鏈表的頭鸯隅，L.nil.prev指向鏈表的尾，因?yàn)長(zhǎng).nil.next指向鏈表的頭，所以去掉了L.head屬性蝌以。一個(gè)空鏈表僅包含哨兵元素炕舵，此時(shí)L.nil.next=nil，且L.nil.prev=nil跟畅。
LIST-DELETE(L, x)
1 x.prev.next = x.next
2?x.next.prev = x.prev ??
LIST-SEARCH(L, k)
1 x = L.nil.next
2 while x != L.nil and x.key != k
3? ? x = x.next
4 return x
LIST-INSERT(L, x)
1 x.next = L.nil.next
2 L.nil.next.prev = x
3?L.nil.next = x ??
4 x.prev =?L.nil
? ? 哨兵元素基本上不能降低施于有關(guān)數(shù)據(jù)結(jié)構(gòu)上的各種操作的漸近時(shí)間界咽筋，但他們可以降低常數(shù)因子。在循環(huán)結(jié)構(gòu)中使用哨兵的好處主要有兩方面：一是使得代碼更加簡(jiǎn)潔徊件，但對(duì)于速度則沒有什么幫助奸攻；二是可以使循環(huán)部分的代碼更加緊湊，因而可以降低運(yùn)行時(shí)間中項(xiàng)n或項(xiàng)n2的系數(shù)虱痕。
? ? 要注意不能不加區(qū)別的使用哨兵睹耐。如果有很多較短的鏈表，則使用哨兵后就會(huì)造成存儲(chǔ)的浪費(fèi)部翘。在本書中硝训，當(dāng)哨兵真正能簡(jiǎn)化代碼時(shí)，我們才加以采用新思。
5窖梁、有根樹的表示
? ? 在這一節(jié)中，我們來(lái)討論用鏈接數(shù)據(jù)結(jié)構(gòu)表示有根樹的問題夹囚。首先纵刘，要討論二叉樹，然后提出一種適用于結(jié)點(diǎn)子女?dāng)?shù)任意的有根樹表示方法崔兴。
? ? 我們用一個(gè)對(duì)象來(lái)表示樹的一個(gè)結(jié)點(diǎn)彰导。對(duì)鏈表，假設(shè)每個(gè)結(jié)點(diǎn)都有一個(gè)關(guān)鍵字域敲茄，其余域包括指向指向其他結(jié)點(diǎn)的指針位谋，而且要根據(jù)不同類型的樹而發(fā)生變化。
? ? 1）堰燎、二叉樹
????如下圖所示掏父，用域?p?，?left?秆剪，?right?來(lái)存放指向二叉樹?T?中的父親赊淑，左兒子和右兒子的指針。如果?x.p?=?NIL?仅讽，則?x?為根陶缺。如果結(jié)點(diǎn)?x?無(wú)左兒子，則?x.left?=?NIL?洁灵，對(duì)右兒子也類似饱岸。整個(gè)樹?T?的根由屬性?T.root?指向掺出。如果?T.root?=?NIL?，則樹為空苫费。
????2）汤锨、分支數(shù)無(wú)限的有根樹
? ? 上面二叉樹的表示方法可以推廣至每個(gè)結(jié)點(diǎn)的子女?dāng)?shù)至多為常數(shù)k的任意種類的樹：用chaild1...childk來(lái)取代left和right域。如果樹中結(jié)點(diǎn)的子女?dāng)?shù)是無(wú)限制的百框，那么這種方法就不適用了闲礼，因?yàn)槲覀儫o(wú)法事先知道有多少域需要分配。此外铐维，即使結(jié)點(diǎn)子女?dāng)?shù)k以一個(gè)很大的常數(shù)為界柬泽，但多數(shù)結(jié)點(diǎn)只有少數(shù)子女，則會(huì)浪費(fèi)大量的存儲(chǔ)空間方椎。
? ? 值得慶幸的是聂抢，可以用二叉樹很方便地表示具有任意子女?dāng)?shù)的樹。該方法的優(yōu)點(diǎn)是對(duì)任意含?n?個(gè)結(jié)點(diǎn)的有根樹僅用?O?(?n?)空間棠众。這種?左孩子?，?右兄弟?的表示如下圖所示有决。每個(gè)結(jié)點(diǎn)都包含一個(gè)父親指針?p?闸拿，?T.root?指向樹?T?的根。每個(gè)結(jié)點(diǎn)?x?不再包含指向每個(gè)孩子結(jié)點(diǎn)的指針书幕，而僅包含兩個(gè)指針：
? ? ? ? ? ? a新荤、x.left-child?指向結(jié)點(diǎn)?x?的最左孩子。
? ? ? ? ? ? b台汇、x.right-sibling?指向結(jié)點(diǎn)?x?緊右邊的兄弟苛骨。
????如果?x?沒有孩子，則?x.left-child?=?NIL?苟呐；如果?x?是其父結(jié)點(diǎn)的最右孩子痒芝，則?x.right-sibling?=?NIL?。
? ? 3牵素、樹的其他表示
? ? 有時(shí)严衬，可以用另外一些方法來(lái)表示有根樹。例如笆呆，在第6章中请琳，我們用了一個(gè)數(shù)組加上下標(biāo)的形式來(lái)表示基于完全二叉樹的堆。將在21章中出現(xiàn)的樹只可由頁(yè)向根的方向遍歷赠幕，故只用到父指針俄精，而沒有指向子女的指針。另外榕堰，還有很多其他的方法竖慧，哪一種最好要視具體的應(yīng)用而定。
