1、基本數(shù)據(jù)結(jié)構(gòu)Algorithms+ Data Structures= Programs引言計(jì)算機(jī)和組織數(shù)據(jù)的方式是非常復(fù)雜的，幸運(yùn)的是，往往可以在更高的抽象層次上去考慮這一問(wèn)題數(shù)據(jù)結(jié)構(gòu)（data structure）是由數(shù)據(jù)元素的集合和該集合中元間的關(guān)系所組成的，它并不依賴于某種特定的實(shí)現(xiàn)方法通常，還希望數(shù)據(jù)結(jié)構(gòu)能夠支持某些特定的操作2引言其實(shí)在搜索和排序章節(jié)中一直提到的“序列”也是一種數(shù)據(jù)結(jié)構(gòu)這也是最常用的數(shù)據(jù)結(jié)構(gòu)之一，正式的名稱為線性表（linear list）它擁有最為普遍和簡(jiǎn)單的線性結(jié)構(gòu)，各個(gè)元素是相繼排列的，相鄰元素是直接前驅(qū)和直接后繼的關(guān)系具體在計(jì)算機(jī)中可以使用數(shù)組或鏈表來(lái)實(shí)現(xiàn)，但

2、這并不是所關(guān)心的內(nèi)容3引言常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)操作 數(shù)據(jù)結(jié)構(gòu)的構(gòu)建與銷毀 查找、刪除某個(gè)元素 遍歷整個(gè)數(shù)據(jù)結(jié)構(gòu)并非每種數(shù)據(jù)結(jié)構(gòu)都要支持所有的操作，這與數(shù)據(jù)結(jié)構(gòu)本身的特性以及具體的應(yīng)用場(chǎng)景有關(guān)線性表能夠很容易地實(shí)現(xiàn)以上操作4概要這一節(jié)介紹以下幾個(gè)除普通線性表之外最為經(jīng)典與常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)棧隊(duì)列樹(shù)通過(guò)對(duì)它們的學(xué)習(xí)，會(huì)初步了解如何根據(jù)實(shí)際的需求來(lái)組織和管理數(shù)據(jù)5棧棧其實(shí)是一種特殊的線性表，只是限定了對(duì)它的形式通常，棧（stack）可以定義為只允許在一端進(jìn)行和刪除的線性表6棧把棧的頭部，即允許刪除的一端稱為棧頂（top）；而棧的尾部，即不允許和刪除的另一端叫做棧底（bottom）在棧頂一個(gè)元素的過(guò)程叫做入棧（

3、push），刪除一個(gè)元素的過(guò)程叫做出棧（pop）很容易發(fā)現(xiàn)，按這樣的規(guī)則，棧的元素會(huì)先出棧，稱為后進(jìn)先出（LIFO, Last in out）7棧想，棧的這種后進(jìn)先出的過(guò)程和生活中的哪些場(chǎng)景類似？8棧操作的例子A入棧B入棧C入棧C出棧D入棧CDBBBBAAAAA9棧操作的偽代碼Push(Stack, x)top top + 1 Stacktop xPop(Stack)if Stack is empty then error top top 1return Stacktop+110棧的作用棧所支持的操作看似非常簡(jiǎn)單，但卻能完成你意想不到的重要工作計(jì)算機(jī)程序在管理局部?jī)?nèi)存時(shí)，就是按照棧的模式組織的

4、在前面提到過(guò)的“遞歸”過(guò)程中，同樣會(huì)用到遞歸工作棧，每遞歸調(diào)用一次，棧中就會(huì)分配新的工作單元入棧，防止而在過(guò)程結(jié)束后出棧返回調(diào)用處，11棧的應(yīng)用舉例給定一個(gè)括號(hào)的序列，如果每對(duì)左括號(hào)與右括號(hào)都正確匹配，那么稱之為合法的括號(hào)序列，否則即為的括號(hào)序列。如“()()”即是合法的括號(hào)序列，而“()()(”則是的括號(hào)序列的目的是設(shè)計(jì)一個(gè)算法，能夠檢查括號(hào)序列的，進(jìn)一步的，能夠輸出沒(méi)有正確匹配的括號(hào)12棧的應(yīng)用舉例提示：可以觀察到，如果從左到右掃描，那么每一個(gè)右括號(hào)將與最近遇到的未匹配的左括號(hào)相匹配這個(gè)觀察的結(jié)果使聯(lián)想到可以在從左到右的掃描過(guò)程中把所遇到的左括號(hào)入棧，每遇到一個(gè)右括號(hào)時(shí)，就把它與棧頂?shù)淖?

5、括號(hào)（如果存在）相匹配，同時(shí)該左括號(hào) 出棧13隊(duì)列隊(duì)列（queue）是另一種限定存取位置的線性表，它只允許在表的一端端刪除，在另一14隊(duì)列把允許的一端叫做隊(duì)尾（rear），允許刪除的一端叫做隊(duì)頭（front）在隊(duì)列中一個(gè)元素的過(guò)程稱為入隊(duì)（EnQueue），在隊(duì)列中刪除一個(gè)元素的過(guò)程稱為出隊(duì)（DeQueue）與棧不同的是，在這樣的設(shè)定下，先進(jìn)隊(duì)列的元素會(huì)先從隊(duì)列中刪除，稱為先進(jìn)先出（FIFO,out）in15隊(duì)列隊(duì)列，顧名思義就是描繪了人們排隊(duì)的過(guò)程16隊(duì)列操作的例子B、C入隊(duì)D、E、F入隊(duì)A入隊(duì)A出隊(duì)B出隊(duì)FEDCCCCBBAA17隊(duì)列操作的偽代碼EnQueue(Queue, x)Queue

6、rear x rear rear + 1DeQueue(Queue) x Queuefront front front + 1return x18隊(duì)列的作用在操作系統(tǒng)中，作業(yè)調(diào)度和輸入輸出管理都有一個(gè)排隊(duì)問(wèn)題作業(yè)調(diào)度策略中很常用的一個(gè)策略就是“先來(lái)先服務(wù)”，這通常都用隊(duì)列來(lái)實(shí)現(xiàn)等待輸出的作業(yè)排成隊(duì)，先提出請(qǐng)求的作業(yè)排面，一個(gè)作業(yè)完成并輸出后出隊(duì)，在隊(duì)列的下一個(gè)作業(yè)再利用資源進(jìn)行操作，依此類推19雙端隊(duì)列雙端隊(duì)列（Double-ended queue, Deque）是對(duì)隊(duì)列概念的一種擴(kuò)展普通隊(duì)列只允許在一端刪除而在另一端插入，而雙端隊(duì)列可以在隊(duì)列的兩端進(jìn)行插入和刪除雙端隊(duì)列的結(jié)構(gòu)與隊(duì)列類似，可以

7、嘗試自己寫(xiě)出其入隊(duì)和出隊(duì)（注意現(xiàn)在有兩種情況）的偽代碼20樹(shù)前面講過(guò)的棧和隊(duì)列等數(shù)據(jù)結(jié)構(gòu)，從本質(zhì)上說(shuō)是線性的它們從時(shí)間和空間上來(lái)說(shuō)都是依次緊密排列的，如果希望表達(dá)更復(fù)雜的關(guān)系，比如層次化的組織形式，就需要更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)了這種能夠表達(dá)層次關(guān)系的分支數(shù)據(jù)結(jié)構(gòu)被稱為樹(shù)（tree）21樹(shù)從圖論的角度來(lái)說(shuō)，樹(shù)指沒(méi)有回路的圖，這會(huì)在后面的章節(jié)中再做闡述這里所說(shuō)的樹(shù)是指具有層次結(jié)構(gòu)的有根樹(shù)（rooted tree）22樹(shù)樹(shù)中的每一個(gè)位置稱為一個(gè)結(jié)點(diǎn)（node）樹(shù)根部的結(jié)點(diǎn)稱為根結(jié)點(diǎn)（root node）端點(diǎn)處的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)（terminal node），也叫做葉子結(jié)點(diǎn)（leaf node）通常把從根

8、結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長(zhǎng)路徑上的結(jié)點(diǎn)數(shù)稱為樹(shù)的深度（depth），比如上圖中的樹(shù)深度為523樹(shù)的例子銷售副財(cái)務(wù)副服務(wù)副A地區(qū)銷售經(jīng)理B地區(qū)銷售經(jīng)理C地區(qū)銷售經(jīng)理A地區(qū)服務(wù)經(jīng)理B地區(qū)服務(wù)經(jīng)理24樹(shù)有時(shí)候，會(huì)把樹(shù)看作這樣的結(jié)構(gòu)：是由每個(gè)節(jié)點(diǎn)派生出其直接下層的節(jié)點(diǎn)，就像（英語(yǔ)中的family tree）的家譜25樹(shù)此時(shí)，稱一個(gè)結(jié)點(diǎn)的直接后代為子結(jié)點(diǎn)（child），稱其直接祖先為父結(jié)點(diǎn)（parent），而將有同一個(gè)父節(jié)點(diǎn)的那些結(jié)點(diǎn)稱之為兄弟節(jié)點(diǎn)（sibling）對(duì)于樹(shù)中任意一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)與其下層的結(jié)點(diǎn)也樹(shù)結(jié)構(gòu)，稱為（subtree）每個(gè)子節(jié)點(diǎn)就是父節(jié)點(diǎn)下的根節(jié)點(diǎn)，這樣的稱為父節(jié)點(diǎn)的一個(gè)分支（branch

9、）26二叉樹(shù)二叉樹(shù)（binary tree）是一種特殊的有根樹(shù)，要求二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)，分別稱為左兒子和右兒子這樣名也就意味著對(duì)于二叉樹(shù)來(lái)說(shuō)，其左、右因此其的地位是需要加以區(qū)別的，的次序不能顛倒二叉樹(shù)由于其結(jié)構(gòu)定義良好，具有不錯(cuò)的時(shí)間與空間性能，因此使用最為頻繁27二叉樹(shù)的轉(zhuǎn)換由于二叉樹(shù)擁有這樣的優(yōu)勢(shì)，通常希望能將一般的樹(shù)轉(zhuǎn)換為二叉樹(shù)，同時(shí)能保持原樹(shù)的性質(zhì)，如下圖所示28二叉樹(shù)的轉(zhuǎn)換轉(zhuǎn)換是根據(jù)“左兒子，右兄弟”這樣的原則完成的具體可以簡(jiǎn)述為以下的過(guò)程父節(jié)點(diǎn)只保留第一個(gè)兒子為左兒子結(jié)點(diǎn)，去除與其它兒子節(jié)點(diǎn)之間的聯(lián)系每個(gè)結(jié)點(diǎn)將在原來(lái)樹(shù)中與自己最靠近的右兄弟結(jié)點(diǎn)作為自己的右兒子大家

10、可以自行驗(yàn)證這一算法的正確性29二叉樹(shù)的轉(zhuǎn)換這樣的轉(zhuǎn)化算法是非常高效的，而且原樹(shù)與轉(zhuǎn)換后的二叉樹(shù)是一一的（想想怎樣在二叉樹(shù)中找到父結(jié)點(diǎn)所有的兒子）30二叉搜索樹(shù)面介紹搜索時(shí)，提到過(guò)，二分搜索無(wú)法高效地處理有實(shí)時(shí)數(shù)據(jù)除的情況或是刪對(duì)于這樣的情形，二叉搜索樹(shù)（binary search tree）就是一種能滿足這種需求的更好的選擇了二叉搜索樹(shù)在形式上就是一棵二叉樹(shù)，但同時(shí)又保持了特殊的性質(zhì)31二叉搜索樹(shù)二叉搜索樹(shù)的每個(gè)結(jié)點(diǎn)都附有一個(gè)（key），一般要求互不相同樹(shù)（如果存在）上所有結(jié)點(diǎn)的都小于根節(jié)點(diǎn)的右（如果存在）上所有結(jié)點(diǎn)的都大于根節(jié)點(diǎn)的樹(shù)和右樹(shù)的性質(zhì)同時(shí)也滿足以上二叉搜索32二叉搜索樹(shù)的例子83

11、101614471333二叉搜索樹(shù)的查詢?cè)诙嫠阉鳂?shù)中查詢的過(guò)程可以概括為如果查詢 布查找成功如果查詢等于當(dāng)前結(jié)點(diǎn)的，則宣小于當(dāng)前結(jié)點(diǎn)的，則查找其 如果查詢找其右樹(shù)大于當(dāng)前結(jié)點(diǎn)的，則查 如果已沒(méi)有兒子節(jié)點(diǎn)，則宣布查找失敗這樣查找次數(shù)最大不會(huì)超過(guò)樹(shù)的深度34查詢的例子83101614471335查詢的偽代碼Tree-Search(x, k)if x = NILthen return “not found”if k = keyxthen return xif k keyxthen return Tree-Search(leftx, k)else return Tree-Search(rightx,

12、 k)36二叉搜索樹(shù)的能夠動(dòng)態(tài)添加數(shù)據(jù)是二叉搜索樹(shù)的主要特 性，由于二叉搜索樹(shù)的結(jié)構(gòu)有一定的要求，的過(guò)程應(yīng)保持二叉搜索樹(shù)的性質(zhì)的過(guò)程與查詢類似，可以理解為對(duì)待的首先做一次查詢，然后再將這個(gè)元素到搜索操作停止的地方，因?yàn)椴樵冊(cè)诖酥袛嘁馕吨@里就是元素“應(yīng)該”所在的位置37的例子831016140471338的偽代碼Tree-Insert(T, z)y NILx rootTwhile (x NIL) doy xif (keyzkeyx)then x leftxelse x rightxparentz yif (keyzkeyy)then lefty zelse righty z39二叉搜索樹(shù)的刪除二叉搜索樹(shù)的刪除較為復(fù)雜，因?yàn)橥枰跇?shù)中找到一個(gè)能夠“代替”被刪除結(jié)點(diǎn)的元素涉及到二叉樹(shù)中結(jié)點(diǎn)的前驅(qū)（sucsor）和后繼（predesor）的概念根據(jù)擬刪除結(jié)點(diǎn)分情況葉子結(jié)點(diǎn)只有單個(gè)分支同時(shí)含有兩個(gè)子結(jié)點(diǎn)40二叉搜索樹(shù)的刪除41進(jìn)階內(nèi)容一般來(lái)說(shuō)，由于二叉搜索樹(shù)會(huì)在每一步都“忽略”兩棵中的一棵，與二分搜索的情況類似，因此執(zhí)行效率是很高的但也存在著這樣的情況：整棵二叉搜索樹(shù)可能會(huì)為一條長(zhǎng)長(zhǎng)的線性鏈。此時(shí)，樹(shù)的深度即為結(jié)點(diǎn)的總數(shù)，這樣搜索比較的次數(shù)就會(huì)從log2n的級(jí)別其中n為結(jié)點(diǎn)總數(shù)為n的級(jí)別，