算法數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

第2章數(shù)據(jù)結(jié)構(gòu)根底2.1線性表將集合中的n個(gè)元素一字排列:a1，a2，…，ai-1，ai，ai+1，…，an↑ ↑

表首

表尾有且僅有一個(gè)元素a1沒(méi)有前驅(qū)，該元素稱為表首；有且僅有一個(gè)元素an沒(méi)有后繼，稱為表尾；此外的所有1<i<n的元素ai均有一個(gè)前驅(qū)ai-1，且有一個(gè)后繼ai+1。以這樣的方式組織起來(lái)的數(shù)據(jù)結(jié)構(gòu)稱為一個(gè)線性表。在計(jì)算機(jī)中，用一個(gè)連續(xù)存儲(chǔ)的數(shù)組來(lái)表示一個(gè)線性表是很自然的，因?yàn)閿?shù)組的下標(biāo)自然地表示出了線性表中元素的前后關(guān)系。線性表的鏈表表示鏈表常用來(lái)表示可變長(zhǎng)線性表。鏈表中為每一個(gè)元素單獨(dú)分配一個(gè)稱為結(jié)點(diǎn)的存儲(chǔ)空間，元素間的前后順序是由指向每個(gè)結(jié)點(diǎn)的指針確定的。帶有哨兵結(jié)點(diǎn)的環(huán)形鏈表在一個(gè)鏈表中，假設(shè)表首的prev域指向表尾，而表尾的next域指向表首，稱為環(huán)形表。此時(shí)表可視為一個(gè)由元素構(gòu)成的環(huán)。這樣，鏈表中任何一個(gè)結(jié)點(diǎn)都有唯一前驅(qū)和后繼。我們?yōu)殒湵鞮添加一個(gè)哨兵結(jié)點(diǎn)nil[L]：它不表示任何數(shù)據(jù)元素，但它是頭結(jié)點(diǎn)的前驅(qū)，尾結(jié)點(diǎn)的后繼。添加了哨兵后，形成了一個(gè)環(huán)形鏈表，其中的每個(gè)結(jié)點(diǎn)都有各自的前驅(qū)和后繼。對(duì)鏈表的掃描LIST-DISPLAY(L)1x

next[nil[L]]

x指向頭結(jié)點(diǎn)2while

x

nil[L]

x指向鏈表中的正常結(jié)點(diǎn)3 doprintkey[x]4 x

next[x]運(yùn)行時(shí)間T(n)=(n)，n為L(zhǎng)的結(jié)點(diǎn)數(shù)。在鏈表中查找LIST-SEARCH(L,k)1x←next[nil[L]]

從表首結(jié)點(diǎn)開(kāi)始2whilex≠nil[L]andkey[x]≠k3 dox←next[x]4returnx運(yùn)行時(shí)間T(n)=O(n)，n為L(zhǎng)的結(jié)點(diǎn)數(shù)。將元素插入到鏈表中LIST-INSERT(L,a,x)

在L的結(jié)點(diǎn)a之前插入新的結(jié)點(diǎn)x1if

x=nil[L]2 thenreturn3b

prev[a]4prev[x]

b5next[x]

a6next[b]

prev[a]

x運(yùn)行時(shí)間T(n)=(1)。從鏈表中刪除元素LIST-DELETE(L,x)1if

x=NIL

空結(jié)點(diǎn)2 thenreturn3a←next[x]4b←prev[x]5next[b]←a6prev[a]←b運(yùn)行時(shí)間T(n)=(1)。2.2棧棧是用線性表表示的動(dòng)態(tài)集合，INSERT操作DELETE操作均被限制在表首。在棧中，從集合中刪除的元素是最近才插入其中的：棧實(shí)現(xiàn)的是后進(jìn)先出或LIFO的策略?？梢杂靡粋€(gè)鏈表來(lái)實(shí)現(xiàn)一個(gè)棧S。S有兩個(gè)屬性:一個(gè)是鏈表L[S]，另一個(gè)屬性是棧頂top[S]，它指向最近才插入的元素〔表頭head〕。棧的根本操作STACK-EMPTY(S)1iftop[S]=nil[L[S]]2 thenreturnTRUE3 elsereturnFALSE運(yùn)行時(shí)間T(n)=(1)。PUSH(S,x)1創(chuàng)立一個(gè)以x為關(guān)鍵值的結(jié)點(diǎn)x12LIST-INSERT(L[S],next[nil[L[S]]],x1)3top[S]x1運(yùn)行時(shí)間T(n)=(1)。POP(S)1ifSTACK-EMPTY(S)2 thenerror"underflow"3 elsextop[S]4 top[S]next[x]5 LIST-DELETE(L[S],x)6returnx運(yùn)行時(shí)間T(n)=(1)。2.3隊(duì)列隊(duì)列也是用線性表表示的動(dòng)態(tài)集合，INSERT操作被限制在表尾，而DELETE操作被限制在表首。在隊(duì)列中，刪除的元素總是集合中留駐時(shí)間最長(zhǎng)的：隊(duì)列實(shí)現(xiàn)的是先進(jìn)先出或FIFO的策略。用鏈表表示的隊(duì)列，具有屬性head[Q]，它指向其隊(duì)首。屬性tail[Q]那么指向隊(duì)尾。隊(duì)列根本操作ENQUEUE(Q,x)1LIST-INSERT(Q,nil[L[Q]],x)2if

head[Q]=nil[L[Q]]

原隊(duì)列為空3 then

head[Q]←next[nil[L[Q]]]4tail[Q]←prev[nil[L[Q]]]運(yùn)行時(shí)間T(n)=(1)。DEQUEUE(Q)1if

Q=

2 thenerrounderflow3x←head[Q]4head[Q]←next[x]5LIST-DELETE(Q,x)6returnx運(yùn)行時(shí)間T(n)=(1)。2.4二叉搜索樹(shù)二叉樹(shù)是遞歸定義的。一棵二叉樹(shù)T是一個(gè)定義在有限結(jié)點(diǎn)集合上的結(jié)構(gòu)它不包含結(jié)點(diǎn)，或由三個(gè)不相交的結(jié)點(diǎn)集合組成：一個(gè)根結(jié)點(diǎn)，一棵稱為其左子樹(shù)的二叉樹(shù)，和一棵稱為其右子樹(shù)的二叉樹(shù)。不含結(jié)點(diǎn)的二叉樹(shù)稱為空樹(shù)或零樹(shù)。假設(shè)左子樹(shù)非空，其根稱為整棵樹(shù)的根的左孩子。相仿地，非空右子樹(shù)的根是整棵樹(shù)的根的右孩子。二叉樹(shù)的計(jì)算機(jī)表示在計(jì)算機(jī)中，這樣的一棵樹(shù)可以用鏈接的數(shù)據(jù)結(jié)構(gòu)來(lái)表示。在這個(gè)數(shù)據(jù)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)是一個(gè)對(duì)象。除了關(guān)鍵值域key和衛(wèi)星數(shù)據(jù)外，每個(gè)結(jié)點(diǎn)包含域left、right和p分別指向?qū)?yīng)于左孩子，右孩子和父親的結(jié)點(diǎn)。假設(shè)缺少孩子或父親，那么結(jié)點(diǎn)對(duì)應(yīng)的域包含值NIL。根結(jié)點(diǎn)是樹(shù)中唯一父親域?yàn)镹IL的結(jié)點(diǎn)。二叉樹(shù)的中序遍歷INORDER-TREE-WALK(x)1ifx≠NIL2 thenINORDER-TREE-WALK(left[x])3 printkey[x]4 INORDER-TREE-WALK(right[x])運(yùn)行時(shí)間T(n)=(n)。其中，n為樹(shù)中結(jié)點(diǎn)數(shù)。二叉搜索樹(shù)二叉搜索樹(shù)的一個(gè)關(guān)鍵點(diǎn)是其存儲(chǔ)方式滿足以下的二叉搜索樹(shù)性質(zhì)：設(shè)x為二叉樹(shù)中的一個(gè)結(jié)點(diǎn)。假設(shè)y是x的左子樹(shù)中的一個(gè)結(jié)點(diǎn)，那么key[y]≤key[x]。假設(shè)y是x的右子樹(shù)中的一個(gè)結(jié)點(diǎn)，那么key[x]≤key[y]。查找TREE-SEARCH(x,k)1whilex≠NILandk≠key[x]2 doifk<key[x]3 thenx←left[x]4 elsex←right[x]5returnx運(yùn)行時(shí)間T(n)=O(h)。其中，h為樹(shù)的高度。最小值與最大值TREE-MINIMUM(x)1whileleft[x]≠NIL2 dox←left[x]3returnx運(yùn)行時(shí)間T(n)=O(h)。其中，h為樹(shù)的高度。TREE-MAXIMUM(x)1whileright[x]≠NIL2 dox←right[x]3returnx運(yùn)行時(shí)間T(n)=O(h)。其中，h為樹(shù)的高度。后繼和前驅(qū)TREE-SUCCESSOR(x)1ifright[x]≠NIL2 thenreturnTREE-MINIMUM(right[x])3y←p[x]4whiley≠NILandx=right[y]5 dox←y6 y←p[y]7returny過(guò)程TREE-PREDECESSOR與TREE-SUCCESSOR是對(duì)稱的。運(yùn)行時(shí)間T(n)=O(h)。其中，h為樹(shù)的高度。插入TREE-INSERT(T,z)1y←NIL2x←root[T]3whilex≠NIL4 doy←x5 ifkey[z]<key[x]6 thenx←left[x]7 elsex←right[x]8p[z]←y9ify=NIL10 thenroot[T]←z

樹(shù)T是空的11 elseifkey[z]<key[y]12 thenleft[y]←z13 elseright[y]←z運(yùn)行時(shí)間T(n)=O(h)。其中，h為樹(shù)的高度。刪除TREE-DELETE(T,z)1ifleft[z]=NILorright[z]=NIL2 theny←z3 elsey←TREE-SUCCESSOR(z)4ifleft[y]≠NIL5 thenx←left[y]6 elsex←right[y]7ifx≠NIL8 thenp[x]←p[y]9ifp[y]=NIL10 thenroot[T]←x11 elseify=left[p[y]]12 thenleft[p[y]]←x13 elseright[p[y]]←x14ify≠z15 thenkey[z]←key[y]16 將y的衛(wèi)星數(shù)據(jù)拷貝到z中17returny運(yùn)行時(shí)間T(n)=O(h)。其中，h為樹(shù)的高度。紅-黑樹(shù)一棵二叉搜索樹(shù)為紅-黑樹(shù)，假設(shè)其滿足以下的紅-黑樹(shù)性質(zhì)：1．每個(gè)結(jié)點(diǎn)非紅即黑。2．根是黑色的。3．每一片葉子是黑色的。4．假設(shè)一結(jié)點(diǎn)是紅色的，那么其孩子是黑色的。5．對(duì)每個(gè)結(jié)點(diǎn)而言，所有從該結(jié)點(diǎn)起到后代葉子的路徑含有同樣多的黑色結(jié)點(diǎn)。紅-黑樹(shù)圖例紅-黑樹(shù)的特性把從一個(gè)結(jié)點(diǎn)x起，但不包含此結(jié)點(diǎn)，向下到一片葉子的路徑中所含的黑色結(jié)點(diǎn)數(shù)稱為該結(jié)點(diǎn)的黑色高度，記為bh(x)。引理2-1

紅-黑樹(shù)中以任何結(jié)點(diǎn)x為根的子樹(shù)至少包含2bh(x)–1個(gè)內(nèi)結(jié)點(diǎn)。引理2-2一棵具有n個(gè)內(nèi)結(jié)點(diǎn)的紅-黑樹(shù)其高度至多為2lg(n+1)。旋轉(zhuǎn)搜索樹(shù)操作TREE-INSERT和TREE-DELETE對(duì)一棵紅-黑樹(shù)運(yùn)行時(shí)，耗時(shí)O(lgn)。由于改變了樹(shù)的結(jié)構(gòu)，結(jié)果就可能違背紅-黑樹(shù)性質(zhì)。為恢復(fù)這些性質(zhì)，必須改變樹(shù)中某些結(jié)點(diǎn)的顏色還要改變指針結(jié)構(gòu)。通過(guò)旋轉(zhuǎn)來(lái)改變指針結(jié)構(gòu)，這是在搜索樹(shù)中的保存二叉搜索樹(shù)性質(zhì)的局部操作。左旋轉(zhuǎn)LEFT-ROTATE(T,x)1y←right[x]

設(shè)置y2right[x]←left[y]

將y的左子樹(shù)轉(zhuǎn)換成x的右子樹(shù)3p[left[y]]←x4p[y]←p[x]

將x的父親鏈接到y(tǒng)的父親.5ifp[x]=nil[T]6 thenroot[T]←y7 elseifx=left[p[x]]8 thenleft[p[x]]←y9 elseright[p[x]]←y10left[y]←x

將x置于y的左孩子.11p[x]←yRIGHT-ROTATE的代碼是與LEFT-ROTATE對(duì)稱的。運(yùn)行時(shí)間T(n)=(1)。左旋轉(zhuǎn)圖例插入RB-INSERT(T,z)1y←nil[T]2x←root[T]3whilex≠nil[T]4 doy←x5 ifkey[z]<key[x]6 thenx←left[x]7 elsex←right[x]8p[z]←y9ify=nil[T]10 thenroot[T]←z11 elseifkey[z]<key[y]12 thenleft[y]←z13 elseright[y]←z14left[z]←nil[T]15right[z]←nil[T]16color[z]←RED17RB-INSERT-FIXUP(T,z)運(yùn)行時(shí)間T(n)=O(h)。其中，h為樹(shù)的高度。RB-INSERT-FIXUP(T,z)1whilecolor[p[z]]=RED2doifp[z]=left[p[p[z]]]3theny←right[p[p[z]]]4ifcolor[y]=RED5thencolor[p[z]]←BLACK

情形16 color[y]←BLACK

情形17 color[p[p[z]]]←RED

情形18 z←p[p[z]]

情形19 elseifz=right[p[z]]10 thenz←p[z]

情形211 LEFT-ROTATE(T,z)

情形212 color[p[z]]←BLACK

情形313 color[p[p[z]]]←RED

情形314 RIGHT-ROTATE(T,p[p[z]])

情形315 else(與then短語(yǔ)一樣但交換"right"和"left")16color[root[T]]←BLACK

RB-INSERT-FIXUP的操作刪除RB-DELETE(T,z)1ifleft[z]=nil[T]orright[z]=nil[T]2 theny←z3 elsey←TREE-SUCCESSOR(z)4ifleft[y]≠nil[T]5 thenx←left[y]6 elsex←right[y]7p[x]←p[y]8ifp[y]=nil[T]9 thenroot[T]←x10 elseify=left[p[y]]11 thenleft[p[y]]←x12 elseright[p[y]]←x13ify≠z14 thenkey[z]←key[y]15 copyy'ssatellitedataintoz16ifcolor[y]=BLACKandx

nil[T]17 thenRB-DELETE-FIXUP(T,x)18returny運(yùn)行時(shí)間T(n)=O(h)。其中，h為樹(shù)的高度。RB-DELETE-FIXUP(T,x)1whilex≠root[T]andcolor[x]=BLACK2doifx=left[p[x]]3 thenw←right[p[x]]4 ifcolor[w]=RED5 thencolor[w]←BLACK

情形16 color[p[x]]←RED

情形17 LEFT-ROTATE(T,p[x])

情形18 w←right[p[x]]

情形19 ifcolor[left[w]]=BLACKandcolor[right[w]]=BLACK10 thencolor[w]←RED

情形211 x←p[x]

情形212 elseifcolor[right[w]]=BLACK13 thencolor[left[w]]←BLACK

情形314 color[w]←RED

情形315 RIGHT-ROTATE(T,w)

情形316 w←right[p[x]]

情形317 color[w]←color[p[x]]

情形418 color[p[x]]←BLACK

情形419 color[right[w]]←BLACK

情形420 LEFT-ROTATE(T,p[x])

情形421 x←root[T]

情形