1、 .PAGE19 / NUMPAGES19數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納（適于清華嚴(yán)版教材)一、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)與重點(diǎn)構(gòu)成數(shù)據(jù)結(jié)構(gòu)學(xué)科的章節(jié)劃分基本上為：概論，線性表，棧和隊(duì)列，串，多維數(shù)組和廣義表，樹(shù)和二叉樹(shù)，圖，查找，排，外排，文件，動(dòng)態(tài)存儲(chǔ)分配。對(duì)于絕大多數(shù)的學(xué)校而言，“外排，文件，動(dòng)態(tài)存儲(chǔ)分配”三章基本上是不考的，在大多數(shù)高校的計(jì)算機(jī)本科教學(xué)過(guò)程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費(fèi)過(guò)多的精力，只要知道基本的概念即可。但是，對(duì)于報(bào)考名校特別是該校又有在試卷中對(duì)這三章進(jìn)行過(guò)考核的歷史，那么這部分朋友就要留意這三章了。按照以上我們給出的章節(jié)以與對(duì)后三章的介紹，數(shù)據(jù)結(jié)構(gòu)的章

2、節(jié)比重大致為：概論：容很少，概念簡(jiǎn)單，分?jǐn)?shù)大多只有幾分，有的學(xué)校甚至不考。線性表：基礎(chǔ)章節(jié)，必考容之一?？碱}多數(shù)為基本概念題，名校考題中，鮮有大型算法設(shè)計(jì)題。如果有，也是與其它章節(jié)容相結(jié)合。棧和隊(duì)列：基礎(chǔ)章節(jié)，容易出基本概念題，必考容之一。而棧常與其它章節(jié)配合考查，也常與遞歸等概念相聯(lián)系進(jìn)行考查。串 ：基礎(chǔ)章節(jié)，概念較為簡(jiǎn)單。專門(mén)針對(duì)于此章的大型算法設(shè)計(jì)題很少，較常見(jiàn)的是根據(jù)KMP進(jìn)行算法分析。多維數(shù)組與廣義表 ：基礎(chǔ)章節(jié)，基于數(shù)組的算法題也是常見(jiàn)的，分?jǐn)?shù)比例波動(dòng)較大，是出題的“可選單元”或“侯補(bǔ)單元”。一般如果要出題，多數(shù)不會(huì)作為大題出。數(shù)組常與“查找，排序”等章節(jié)結(jié)合來(lái)作為大題考查。樹(shù)和二

3、叉樹(shù) ：重點(diǎn)難點(diǎn)章節(jié)，各校必考章節(jié)。各校在此章出題的不同之處在于，是否在本章中出一到兩道大的算法設(shè)計(jì)題。通過(guò)對(duì)多所學(xué)校的試卷分析，絕大多數(shù)學(xué)校在本章都曾有過(guò)出大型算法設(shè)計(jì)題的歷史。圖 ：重點(diǎn)難點(diǎn)章節(jié)，名校尤愛(ài)考。如果作為重點(diǎn)來(lái)考，則多出現(xiàn)于分析與設(shè)計(jì)題型當(dāng)中，可與樹(shù)一章共同構(gòu)成算法設(shè)計(jì)大題的題型設(shè)計(jì)。查找 ：重點(diǎn)難點(diǎn)章節(jié)，概念較多，聯(lián)系較為緊密，容易混淆。出題時(shí)可以作為分析型題目給出，在基本概念型題目中也較為常見(jiàn)。算法設(shè)計(jì)型題中可以數(shù)組結(jié)合來(lái)考查，也可以與樹(shù)一章結(jié)合來(lái)考查。排序 ：與查找一章類似，本章同屬于重點(diǎn)難點(diǎn)章節(jié)，且概念更多，聯(lián)系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛(ài)考各

4、種排序算法的優(yōu)劣比較此類的題。算法設(shè)計(jì)大題中，如果作為出題，那么常與數(shù)組結(jié)合來(lái)考查。二、數(shù)據(jù)結(jié)構(gòu)各章節(jié)重點(diǎn)勾劃：第0章概述本章主要起到總領(lǐng)作用，為讀者進(jìn)行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)進(jìn)行了一些先期鋪墊。大家主要注意以下幾點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的基本概念，時(shí)間和空間復(fù)雜度的概念與度量方法，算法設(shè)計(jì)時(shí)的注意事項(xiàng)。本章考點(diǎn)不多，只要稍加注意理解即可。第一章線性表作為線性結(jié)構(gòu)的開(kāi)篇章節(jié)，線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。在這一章，第一次系統(tǒng)性地引入鏈?zhǔn)酱鎯?chǔ)的概念，鏈?zhǔn)酱鎯?chǔ)概念將是整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的重中之重，無(wú)論哪一章都涉與到了這個(gè)概念?？傮w來(lái)說(shuō)，線性表一章可供考查的重要考點(diǎn)有以下幾

5、個(gè)方面：線性表的相關(guān)基本概念，如：前驅(qū)、后繼、表長(zhǎng)、空表、首元結(jié)點(diǎn)，頭結(jié)點(diǎn)，頭指針等概念。線性表的結(jié)構(gòu)特點(diǎn)，主要是指：除第一與最后一個(gè)元素外，每個(gè)結(jié)點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼。線性表的順序存儲(chǔ)方式與其在具體語(yǔ)言環(huán)境下的兩種不同實(shí)現(xiàn)：表空間的靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)鏈表與順序表的相似與不同之處。線性表的鏈?zhǔn)酱鎯?chǔ)方式與以下幾種常用鏈表的特點(diǎn)和運(yùn)算：?jiǎn)捂湵怼⒀h(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表與雙向循環(huán)鏈表的插入和刪除算法等都是較為常見(jiàn)的考查方式。此外，近年來(lái)在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單鏈表輸出（可能是順序也可能是倒序）的問(wèn)題。在鏈

6、表的小題型中，經(jīng)?？嫉揭恍┲T如：判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請(qǐng)大家注意。線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)情況下，其不同的優(yōu)缺點(diǎn)比較，即其各自適用的場(chǎng)合。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以與索引存儲(chǔ)結(jié)構(gòu)的各自好處。第二章棧與隊(duì)列棧與隊(duì)列，是很多學(xué)習(xí)DS的同學(xué)遇到第一只攔路虎，很多人從這一章開(kāi)始坐暈車(chē)，一直暈到現(xiàn)在。所以，理解棧與隊(duì)列，是走向DS高手的一條必由之路。學(xué)習(xí)此章前，你可以問(wèn)一下自己是不是已經(jīng)知道了以下幾點(diǎn)：棧、隊(duì)列的定義與其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享?xiàng)?，循環(huán)隊(duì)列，鏈隊(duì)等。棧與隊(duì)列存取數(shù)據(jù)（請(qǐng)注意包括：存和取兩部分）的特點(diǎn)。遞歸

7、算法。棧與遞歸的關(guān)系，以與借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問(wèn)題，fib數(shù)列問(wèn)題，hanoi問(wèn)題，背包問(wèn)題，二叉樹(shù)的遞歸和非遞歸遍歷問(wèn)題，圖的深度遍歷與棧的關(guān)系等。其中，涉與到樹(shù)與圖的問(wèn)題，多半會(huì)在樹(shù)與圖的相關(guān)章節(jié)中進(jìn)行考查。棧的應(yīng)用：數(shù)值表達(dá)式的求解，括號(hào)的配對(duì)等的原理，只作原理性了解，具體要求考查此為題目的算法設(shè)計(jì)題不多。循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件，循環(huán)隊(duì)列中入隊(duì)與出隊(duì)算法。如果你已經(jīng)對(duì)上面的幾點(diǎn)了如指掌，棧與隊(duì)列一章可以不看書(shū)了。注意，我說(shuō)的是可以不看書(shū)，并不是可以不作題哦。第三章串經(jīng)歷了棧一章的痛苦煎熬后，終于迎來(lái)了串一章的柳暗花明。串，在概念上是比較少的一個(gè)章節(jié)，也是最容易

8、自學(xué)的章節(jié)之一，但正如每個(gè)過(guò)來(lái)人所了解的，KMP算法是這一章的重要關(guān)隘，突破此關(guān)隘后，走過(guò)去又是一馬平川的大好DS山河了，呵呵。串一章需要攻破的主要堡壘有：串的基本概念，串與線性表的關(guān)系（串是其元素均為字符型數(shù)據(jù)的特殊線性表），空串與空格串的區(qū)別，串相等的條件2.串的基本操作，以與這些基本函數(shù)的使用，包括：取子串，串連接，串替換，求串長(zhǎng)等等。運(yùn)用串的基本操作去完成特定的算法是很多學(xué)校在基本操作上的考查重點(diǎn)。3.順序串與鏈串與塊鏈串的區(qū)別和聯(lián)系，實(shí)現(xiàn)方式。4.KMP算法思想。KMP中next數(shù)組以與nextval數(shù)組的求法。明確傳統(tǒng)模式匹配算法的不足，明確next數(shù)組需要改進(jìn)之外。其中，理解算法

9、是核心，會(huì)求數(shù)組是得分點(diǎn)。不用我多說(shuō)，這一節(jié)容是本章的重中之重?？赡苓M(jìn)行的考查方式是：求next和nextval數(shù)組值，根據(jù)求得的next或nextval數(shù)組值給出運(yùn)用KMP算法進(jìn)行匹配的匹配過(guò)程。第四章數(shù)組與廣義表學(xué)過(guò)程序語(yǔ)言的朋友，數(shù)組的概念我們已經(jīng)不是第一次見(jiàn)到了，應(yīng)該已經(jīng)“一回生，二回熟”了，所以，在概念上，不會(huì)存在太大障礙。但作為考研課程來(lái)說(shuō)，本章的考查重點(diǎn)可能與大學(xué)里的程序語(yǔ)言所關(guān)注的不太一樣，下面會(huì)作介紹。廣義表的概念，是數(shù)據(jù)結(jié)構(gòu)里第一次出現(xiàn)的。它是線性表或表元素的有限序列，構(gòu)成該結(jié)構(gòu)的每個(gè)子表或元素也是線性結(jié)構(gòu)的，所以，這一章也歸入線性結(jié)構(gòu)中。本章的考查重點(diǎn)有：多維數(shù)組中某數(shù)組

10、元素的position求解。一般是給出數(shù)組元素的首元素地址和每個(gè)元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。明確按行存儲(chǔ)和按列存儲(chǔ)的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲(chǔ)方式求解1中類型的題。將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對(duì)稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。廣義表的概念，特別應(yīng)該明確表頭與表尾的定義。這一點(diǎn)，是理解整個(gè)廣義表一節(jié)算法的基礎(chǔ)。近來(lái)，在一些學(xué)校中，出現(xiàn)了這樣一種題目類型：

11、給出對(duì)某個(gè)廣義表L若干個(gè)求了若干次的取頭和取尾操作后的串值，要求求出原廣義表L。大家要留意。與廣義表有關(guān)的遞歸算法。由于廣義表的定義就是遞歸的，所以，與廣義表有關(guān)的算法也常是遞歸形式的。比如：求表深度，復(fù)制廣義表等。這種題目，可以根據(jù)不同角度廣義表的表現(xiàn)形式運(yùn)用兩種不同的方式解答：一是把一個(gè)廣義表看作是表頭和表尾兩部分，分別對(duì)表頭和表尾進(jìn)行操作；二是把一個(gè)廣義表看作是若干個(gè)子表，分別對(duì)每個(gè)子表進(jìn)行操作。第五章樹(shù)與二叉樹(shù)從對(duì)線性結(jié)構(gòu)的研究過(guò)度到對(duì)樹(shù)形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變，此次躍變完成的好壞，將直接關(guān)系到你到實(shí)際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業(yè)課總分

12、。所以，樹(shù)這一章的重要性，已經(jīng)不說(shuō)自明了。總體來(lái)說(shuō)，樹(shù)一章的知識(shí)點(diǎn)包括：二叉樹(shù)的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)遍歷的三種算法（遞歸與非遞歸），在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹(shù)的其它算法，線索二叉樹(shù)的概念和線索化算法以與線索化后的查找算法，最優(yōu)二叉樹(shù)的概念、構(gòu)成和應(yīng)用，樹(shù)的概念和存儲(chǔ)形式，樹(shù)與森林的遍歷算法與其與二叉樹(shù)遍歷算法的聯(lián)系，樹(shù)與森林和二叉樹(shù)的轉(zhuǎn)換。下面我們看一下圖這一章的主要考點(diǎn)以與這些考點(diǎn)的考查方式：考查有關(guān)圖的基本概念問(wèn)題：這些概念是進(jìn)行圖一章學(xué)習(xí)的基礎(chǔ)，這一章的概念包括：圖的定義和特點(diǎn)，無(wú)向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長(zhǎng)度，回路，（強(qiáng)）連通圖，（強(qiáng)）連通分量等

13、概念。與這些概念相聯(lián)系的相關(guān)計(jì)算題也應(yīng)該掌握?？疾閳D的幾種存儲(chǔ)形式：圖的存儲(chǔ)形式包括：鄰接矩陣，（逆）鄰接表，十字鏈表與鄰接多重表。在考查時(shí)，有的學(xué)校是給出一種存儲(chǔ)形式，要求考生用算法或手寫(xiě)出與給定的結(jié)構(gòu)相對(duì)應(yīng)的該圖的另一種存儲(chǔ)形式。考查圖的兩種遍歷算法：深度遍歷和廣度遍歷深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個(gè)算法對(duì)圖一章的重要性等同于“先序、中序、后序遍歷”對(duì)于二叉樹(shù)一章的重要性。在考查時(shí)，圖一章的算法設(shè)計(jì)題常常是基于這兩種基本的遍歷算法而設(shè)計(jì)的，比如：“求最長(zhǎng)的最短路徑問(wèn)題”和“判斷兩頂點(diǎn)間是否存在長(zhǎng)為K的簡(jiǎn)單路徑問(wèn)題”，就分別用到了廣度遍歷和深度遍歷算法。生成樹(shù)、最小生成樹(shù)的

14、概念以與最小生成樹(shù)的構(gòu)造：PRIM算法和KRUSKAL算法?？疾闀r(shí)，一般不要求寫(xiě)出算法源碼，而是要求根據(jù)這兩種最小生成樹(shù)的算法思想寫(xiě)出其構(gòu)造過(guò)程與最終生成的最小生成樹(shù)。拓?fù)渑判騿?wèn)題：拓?fù)渑判蛴袃煞N方法，一是無(wú)前趨的頂點(diǎn)優(yōu)先算法，二是無(wú)后繼的頂點(diǎn)優(yōu)先算法。換句話說(shuō)，一種是“從前向后”的排序，一種是“從后向前”排。當(dāng)然，后一種排序出來(lái)的結(jié)果是“逆拓?fù)溆行颉钡?。關(guān)鍵路徑問(wèn)題：這個(gè)問(wèn)題是圖一章的難點(diǎn)問(wèn)題。理解關(guān)鍵路徑的關(guān)鍵有三個(gè)方面：一是何謂關(guān)鍵路徑，二是最早時(shí)間是什么意思、如何求，三是最晚時(shí)間是什么意思、如何求。簡(jiǎn)單地說(shuō)，最早時(shí)間是通過(guò)“從前向后”的方法求的，而最晚時(shí)間是通過(guò)“從后向前”的方法求解的

15、，并且，要想求最晚時(shí)間必須是在所有的最早時(shí)間都已經(jīng)求出來(lái)之后才能進(jìn)行。這個(gè)問(wèn)題拿來(lái)直接考算法源碼的不多，一般是要求按照書(shū)上的算法描述求解的過(guò)程和步驟。在實(shí)際設(shè)計(jì)關(guān)鍵路徑的算法時(shí)，還應(yīng)該注意以下這一點(diǎn)：采用鄰接表的存儲(chǔ)結(jié)構(gòu)，求最早時(shí)間和最晚時(shí)間要采用不同的處理方法，即：在算法初始時(shí)，應(yīng)該首先將所有頂點(diǎn)的最早時(shí)間全部置為0。關(guān)鍵路徑問(wèn)題是工程進(jìn)度控制的重要方法，具有很強(qiáng)的實(shí)用性。最短路徑問(wèn)題：與關(guān)鍵路徑問(wèn)題并稱為圖一章的兩只攔路虎。概念理解是比較容易的，關(guān)鍵是算法的理解。最短路徑問(wèn)題分為兩種：一是求從某一點(diǎn)出發(fā)到其余各點(diǎn)的最短路徑；二是求圖中每一對(duì)頂點(diǎn)之間的最短路徑。這個(gè)問(wèn)題也具有非常實(shí)用的背景特

16、色，一個(gè)典型的應(yīng)該就是旅游景點(diǎn)與旅游路線的選擇問(wèn)題。解決第一個(gè)問(wèn)題用DIJSKTRA算法，解決第二個(gè)問(wèn)題用FLOYD算法。注意區(qū)分。第七章查找在不少數(shù)據(jù)結(jié)構(gòu)的教材中，是把查找與排序放入高級(jí)數(shù)據(jù)結(jié)構(gòu)中的。應(yīng)該說(shuō)，查找和排序兩章是前面我們所學(xué)的知識(shí)的綜合運(yùn)用，用到了樹(shù)、也用到了鏈表等知識(shí)，對(duì)這些數(shù)據(jù)結(jié)構(gòu)某一方面的運(yùn)用就構(gòu)成了查找和排序?，F(xiàn)實(shí)生活中，search幾乎無(wú)處不在，特別是現(xiàn)在的網(wǎng)絡(luò)時(shí)代，萬(wàn)事離不開(kāi)search，小到文檔文字的搜索，大到INTERNET上的搜索，search占據(jù)了我們上網(wǎng)的大部分時(shí)間。在復(fù)習(xí)這一章的知識(shí)時(shí)，你需要先弄清楚以下幾個(gè)概念：關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義；靜態(tài)查找

17、與動(dòng)態(tài)查找的含義與區(qū)別；平均查找長(zhǎng)度ASL的概念與在各種查找算法中的計(jì)算方法和計(jì)算結(jié)果，特別是一些典型結(jié)構(gòu)的ASL值，應(yīng)該記住。在DS的教材中，一般將search分為三類：1st，在順序表上的查找；2nd，在樹(shù)表上的查找；3rd，在哈希表上的查找。下面詳細(xì)介紹其考查知識(shí)點(diǎn)與考查方式：線性表上的查找：主要分為三種線性結(jié)構(gòu)：順序表，有序順序表，索引順序表。對(duì)于第一種，我們采用傳統(tǒng)查找方法，逐個(gè)比較。對(duì)于與有序順序表我們采用二分查找法。對(duì)于第三種索引結(jié)構(gòu)，我們采用索引查找算法?？忌枰⒁膺@三種表下的ASL值以與三種算法的實(shí)現(xiàn)。其中，二分查找還要特別注意適用條件以與其遞歸實(shí)現(xiàn)方法。樹(shù)表上的查找：這是

18、本章的重點(diǎn)和難點(diǎn)。由于這一節(jié)介紹的容是使用樹(shù)表進(jìn)行的查找，所以很容易與樹(shù)一間的某些概念相混淆。本節(jié)容與樹(shù)一章的容有聯(lián)系，但也有很多不同，應(yīng)注意規(guī)納。樹(shù)表主要分為以下幾種：二叉排序樹(shù)，平衡二叉樹(shù)，B樹(shù)，鍵樹(shù)。其中，尤以前兩種結(jié)構(gòu)為重，也有部分名校偏愛(ài)考B樹(shù)的。由于二叉排序樹(shù)與平衡二叉樹(shù)是一種特殊的二叉樹(shù)，所以與二叉樹(shù)的聯(lián)系就更為緊密，二叉樹(shù)一章學(xué)好了，這里也就不難了。二叉排序樹(shù)，簡(jiǎn)言之，就是“左小右大”，它的中序遍歷結(jié)果是一個(gè)遞增的有序序列。平衡二叉樹(shù)是二叉排序樹(shù)的優(yōu)化，其本質(zhì)也是一種二叉排序樹(shù)，只不過(guò)，平衡二叉樹(shù)對(duì)左右子樹(shù)的深度有了限定：深度之差的絕對(duì)值不得大于1。對(duì)于二叉排序樹(shù)，“判斷某棵二

19、叉樹(shù)是否二叉排序樹(shù)”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹(shù)的建立也是一個(gè)常考點(diǎn)，但該知識(shí)點(diǎn)歸根結(jié)底還是關(guān)注的平衡二叉樹(shù)的四種調(diào)整算法，所以應(yīng)該掌握平衡二叉樹(shù)的四種調(diào)整算法，調(diào)整的一個(gè)參照是：調(diào)整前后的中序遍歷結(jié)果一樣。B樹(shù)是二叉排序樹(shù)的進(jìn)一步改進(jìn)，也可以把B樹(shù)理解為三叉、四叉排序樹(shù)。除B樹(shù)的查找算法外，應(yīng)該特別注意一下B樹(shù)的插入和刪除算法。因?yàn)檫@兩種算法涉與到B樹(shù)結(jié)點(diǎn)的分裂和合并，是一個(gè)難點(diǎn)。B樹(shù)是報(bào)考名校的同學(xué)應(yīng)該關(guān)注的焦點(diǎn)之一。鍵樹(shù)也稱字符樹(shù)，特別適用于查找英文單詞的場(chǎng)合。一般不要求能完整描述算法源碼，多是根據(jù)算法思想建立鍵樹(shù)與描述其大致查找過(guò)程?；竟１淼牟檎宜惴ǎ汗?/p>

20、希一詞，是外來(lái)詞，譯自“hash”一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據(jù)當(dāng)前待查找數(shù)據(jù)的特征，以記錄關(guān)鍵字為自變量，設(shè)計(jì)一個(gè)function，該函數(shù)對(duì)關(guān)鍵字進(jìn)行轉(zhuǎn)換后，其解釋結(jié)果為待查的地址?；诠１淼目疾辄c(diǎn)有：哈希函數(shù)的設(shè)計(jì)，沖突解決方法的選擇與沖突處理過(guò)程的描述。第八章部排序排是DS課程中最后一個(gè)重要的章節(jié)，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型算法題。但是，歸結(jié)到一點(diǎn)，就是考查你對(duì)書(shū)本上的各種排序算法與其思想以與其優(yōu)缺點(diǎn)和性能指標(biāo)（時(shí)間復(fù)雜度）能否了如指掌。這一章，我們對(duì)重點(diǎn)的規(guī)納將跟以上各章不同。我們將從以下幾個(gè)側(cè)面來(lái)對(duì)排序一章進(jìn)行不同的規(guī)納

21、，以期能更全面的理解排序一章的總體結(jié)構(gòu)與各種算法。從排序算法的種類來(lái)分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸并、計(jì)數(shù)等五種排序方法。其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點(diǎn)，說(shuō)到底就是根據(jù)什么規(guī)則尋找新元素的插入點(diǎn)。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過(guò)控制每次參與排序的數(shù)的總圍“由小到大”的增量來(lái)實(shí)現(xiàn)排序效率提高的目的。交換排序，又稱冒泡排序，在交換排序的基礎(chǔ)上改進(jìn)又可以得到快速排序?？焖倥判虻乃枷?，一語(yǔ)以敝之：用中間數(shù)將待排數(shù)據(jù)組一分為二?？焖倥判颍谔幚淼摹皢?wèn)題規(guī)?！边@個(gè)概念上，與希爾有點(diǎn)相反

22、，快速排序，是先處理一個(gè)較大規(guī)模，然后逐漸把處理的規(guī)模降低，最終達(dá)到排序的目的。選擇排序，相對(duì)于前面幾種排序算法來(lái)說(shuō)，難度大一點(diǎn)。具體來(lái)說(shuō)，它可以分為：簡(jiǎn)單選擇、樹(shù)選擇、堆排。這三種方法的不同點(diǎn)是，根據(jù)什么規(guī)則選取最小的數(shù)。簡(jiǎn)單選擇，是通過(guò)簡(jiǎn)單的數(shù)組遍歷方案確定最小數(shù)；樹(shù)選擇，是通過(guò)“錦標(biāo)賽”類似的思想，讓兩數(shù)相比，不斷淘汰較大（?。┱?，最終選出最?。ù螅?shù)；而堆排序，是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，通過(guò)堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點(diǎn)。樹(shù)選擇排序，也曾經(jīng)在一些學(xué)校中的大型算法題中出現(xiàn)，請(qǐng)大家注意。歸并排序，故名思義，是通過(guò)“歸并”這種操作完成

23、排序的目的，既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可能實(shí)現(xiàn)歸并。所以，在歸并排序中，關(guān)注最多的就是2路歸并。算法思想比較簡(jiǎn)單，有一點(diǎn)，要銘記在心：歸并排序是穩(wěn)定排序。基數(shù)排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數(shù)排序就比較適合于一些特別的場(chǎng)合，比如撲克牌排序問(wèn)題等?；鶖?shù)排序，又分為兩種：多關(guān)鍵字的排序（撲克牌排序），鏈?zhǔn)脚判颍ㄕ麛?shù)排序）?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個(gè)概念將問(wèn)題規(guī)模規(guī)、變小，并且，在排序的過(guò)程中，只要按照基排的思想，是不用進(jìn)行關(guān)鍵字比較的，這樣得出的最終序列就是一個(gè)有序序列。本章各種排序算法的思想以與偽代碼實(shí)現(xiàn)，與其時(shí)間復(fù)雜度都是必須掌握的，學(xué)習(xí)時(shí)

24、要多注意規(guī)納、總結(jié)、對(duì)比。此外，對(duì)于教材中的10.7節(jié)，要求必須熟記，在理解的基礎(chǔ)上記憶，這一節(jié)幾乎成為很多學(xué)校每年的必考點(diǎn)。數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納數(shù)據(jù)結(jié)構(gòu)大學(xué)教程The Complete Data Structure Training Course第一章 數(shù)據(jù)結(jié)構(gòu)與其基本概念Chapter 1 Data Structure and Its Basic Concepts1什么是數(shù)據(jù)結(jié)構(gòu)(What is Data Structure)如果你問(wèn)一個(gè)木匠學(xué)徒：你工作的工具要用什么，他可能會(huì)回答你：“我只要一把錘子和一個(gè)鋸”。但是如果你去問(wèn)一個(gè)老木工或者是大師級(jí)的建筑師，他會(huì)告訴你“我需要一些精確的工具

25、”。由于計(jì)算機(jī)所解決的問(wèn)題都是從生活中抽象出來(lái)的問(wèn)題，其復(fù)雜性不言而喻，所以我們需要這樣精確有效的工具去解決現(xiàn)實(shí)生活中的復(fù)雜問(wèn)題。算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)語(yǔ)言都是這樣的工具。數(shù)據(jù)結(jié)構(gòu)是信息的組織方式。對(duì)于一樣的算法，用不同的數(shù)據(jù)結(jié)構(gòu)表示其中的抽象數(shù)據(jù)類型會(huì)造成不同的執(zhí)行效率。這就有必要研究各種抽象數(shù)據(jù)類型用不同的數(shù)據(jù)結(jié)構(gòu)表示的效率差異，以與其適用場(chǎng)合。一何謂數(shù)據(jù)結(jié)構(gòu)（What is Data Structure）數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語(yǔ)。它用來(lái)反映一個(gè)數(shù)據(jù)的部構(gòu)成，即一個(gè)數(shù)據(jù)由哪些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)

26、構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)部的存儲(chǔ)安排。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，好的數(shù)據(jù)結(jié)構(gòu)可以提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過(guò)這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。從學(xué)科角度來(lái)講，數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以與它們之間的關(guān)系和操作等等的學(xué)科。二數(shù)據(jù)結(jié)構(gòu)學(xué)科的研究對(duì)象 (The Object of Data Structure Research)數(shù)據(jù)結(jié)構(gòu)作為一門(mén)學(xué)科，主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以與對(duì)數(shù)據(jù)的各種操作。因此，主要有三個(gè)方面的容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存

27、儲(chǔ)結(jié)構(gòu)；對(duì)數(shù)據(jù)的操作（即算法）。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉與到計(jì)算機(jī)硬件的研究，比如存儲(chǔ)裝置和存取方法，而且解決編譯原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)元素在存儲(chǔ)器中的分配問(wèn)題的重要基礎(chǔ)。1.2 基本概念與學(xué)科術(shù)語(yǔ)(Basic Concepts and Terminologies)數(shù)據(jù)（Data）:是一個(gè)集合的概念，是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能被輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)處理的符號(hào)的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。數(shù)據(jù)元素（Data Element）:是數(shù)據(jù)的基本單位，數(shù)據(jù)中的一個(gè)“個(gè)體”。又

28、稱為“記錄”或者“表目”。數(shù)據(jù)項(xiàng)（Data Item）：數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合。數(shù)據(jù)對(duì)象（Data Object）：是性質(zhì)一樣的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集?？偨Y(jié)數(shù)據(jù)項(xiàng)組成數(shù)據(jù)元素，數(shù)據(jù)元素組成數(shù)據(jù)對(duì)象，數(shù)據(jù)對(duì)象組成數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)（Data Structure）：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。它包括三個(gè)方面：數(shù)據(jù)元素的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相適應(yīng)的運(yùn)算（操作）。數(shù)據(jù)元素之間的邏輯關(guān)系被稱為數(shù)據(jù)元素的邏輯結(jié)構(gòu)，可以用一個(gè)二元組表示：Data_Structure = (D, S) / Data_Structure= (Data-part, Logic-

29、Structure-Part)這里D是數(shù)據(jù)元素的集合，S是定義在D（或其他集合）上的關(guān)系的集合，S = R R : DD.。數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:（1）集合結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外別無(wú)其他關(guān)系（2）線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的前趨后繼關(guān)系在此種結(jié)構(gòu)下：有且僅有一個(gè)元素?zé)o前趨元素有且僅有一個(gè)元素?zé)o后繼元素其余任何一個(gè)元素均有且僅有一個(gè)前趨有且僅有一個(gè)后繼元素。（3）樹(shù)形結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系任何一個(gè)節(jié)點(diǎn)最多有一個(gè)前趨，可以有多個(gè)后繼，是一種典型的非線性結(jié)構(gòu)（4）圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系這

30、種結(jié)構(gòu)的特征是任何一個(gè)元素可以有多個(gè)前趨，也可以有多個(gè)后繼，是一種多對(duì)多的前趨后繼關(guān)系表和樹(shù)是最常用的兩種高效數(shù)據(jù)結(jié)構(gòu)，許多高效的算法可以用這兩種數(shù)據(jù)結(jié)構(gòu)來(lái)設(shè)計(jì)實(shí)現(xiàn)。表是線性結(jié)構(gòu)的（全序關(guān)系），樹(shù)(偏序或?qū)哟侮P(guān)系)和圖（局部有序(weak/local orders)）是非線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱為映像）稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)的存儲(chǔ)映像(image)。數(shù)據(jù)結(jié)構(gòu) DS 的物理結(jié)構(gòu) P 對(duì)應(yīng)于從 DS 的數(shù)據(jù)元素到存儲(chǔ)區(qū)M（維護(hù)著邏輯結(jié)構(gòu)S）的一個(gè)映射：PD,S) - M存儲(chǔ)器模型：一個(gè)存儲(chǔ)器 M 是一系列固定大小的存儲(chǔ)單元，每個(gè)單元 U 有一個(gè)

31、唯一的地址 A(U)，該地址被連續(xù)地編碼。每個(gè)單元 U 有一個(gè)唯一的后繼單元 U=succ(U)。P 的四種基本映射模型：順序（sequential）、（linked）、索引（indexed）和散列（hashing）映射。因此，我們至少可以得到44種可能的物理數(shù)據(jù)結(jié)構(gòu)：sequential (sets)linked listsindexed treeshashinggraphs需要指出的是：并不是所有的可能組合都合理。數(shù)據(jù)結(jié)構(gòu)DS上的操作：所有的定義在DS上的操作在改變數(shù)據(jù)元素（節(jié)點(diǎn)）或節(jié)點(diǎn)的域時(shí)必須保持DS的邏輯和物理結(jié)構(gòu)。DS上的基本操作：任何其他對(duì)DS的高級(jí)操作都可以用這些基本操作來(lái)實(shí)現(xiàn)

32、。最好將DS和他的所有基本操作看作一個(gè)整體稱之為模塊（model）。我們可以進(jìn)一步將該模塊抽象為數(shù)據(jù)類型（其中DS的存儲(chǔ)結(jié)構(gòu)被表示為私有成員，基本操作被表示為公共方法），稱之為ADT（即是抽象數(shù)據(jù)類型AbstractData Type，指一個(gè)數(shù)學(xué)模型以與定義在該模型上的一組操作）。ADT按照其值的不同特性分為下列三種類型：原子類型（Atomic Data Type）：變量是不帶結(jié)構(gòu)的，不可分解的。固定聚合類型（Fixed-aggregate Data Type）：其值由確定數(shù)目的成分按照某種結(jié)構(gòu)組成可變聚合類型（Variable-Aggregate Data Type）：值的成分的數(shù)目不確定抽

33、象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為基本操作名（參數(shù)表）初始條件：初始條件描述操作結(jié)果：操作結(jié)果描述基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭， 除可提供輸入值外，還將返回操作結(jié)果?！俺跏紬l件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！安僮鹘Y(jié)果”說(shuō)明了操作正常完成

34、之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則將其省略。需要注意的是：抽象數(shù)據(jù)類型需要通過(guò)固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來(lái)實(shí)現(xiàn)。順便提一句，多形數(shù)據(jù)類型（Polymorphic Data Type）是指值的成分不確定的數(shù)據(jù)類型，不過(guò)這個(gè)不太多見(jiàn)，或者是可以用ADT表示，所以我們?cè)诮窈蟮恼鹿?jié)再論述。好的和壞的DS：如果一個(gè)DS可以通過(guò)某種“線性規(guī)則”被轉(zhuǎn)化為線性的DS（例如線性表），則稱它為好的DS。好的DS通常對(duì)應(yīng)于好的（高效的）算法。這是由計(jì)算機(jī)的計(jì)算能力決定的，因?yàn)橛?jì)算機(jī)本質(zhì)上只能存取邏輯連續(xù)的存單元，因此如何沒(méi)有線性化的結(jié)構(gòu)邏輯上是不可計(jì)算的。比如對(duì)一個(gè)圖進(jìn)行

35、操作，要訪問(wèn)圖的所有結(jié)點(diǎn)，則必須按照某種順序來(lái)依次訪問(wèn)所有節(jié)點(diǎn)（要形成一個(gè)偏序），必須通過(guò)某種方式將圖固有的非線性結(jié)構(gòu)轉(zhuǎn)化為線性結(jié)構(gòu)才能對(duì)圖進(jìn)行操作。樹(shù)是好的DS它有非常簡(jiǎn)單而高效的線性化規(guī)則，因此可以利用樹(shù)設(shè)計(jì)出許多非常高效的算法。樹(shù)的實(shí)現(xiàn)和使用都很簡(jiǎn)單，但可以解決大量特殊的復(fù)雜問(wèn)題，因此樹(shù)是實(shí)際編程中最重要和最有用的一種數(shù)據(jù)結(jié)構(gòu)。樹(shù)的結(jié)構(gòu)本質(zhì)上有遞歸的性質(zhì)每一個(gè)葉節(jié)點(diǎn)可以被一棵子樹(shù)所替代，反之亦然。實(shí)際上，每一種遞歸的結(jié)構(gòu)都可以被轉(zhuǎn)化為（或等價(jià)于）樹(shù)形結(jié)構(gòu)。說(shuō)到遞歸在大學(xué)的數(shù)據(jù)結(jié)構(gòu)課程里面有個(gè)老師經(jīng)常說(shuō)“不懂遞歸就不算北大計(jì)算機(jī)系的學(xué)生”，這樣看來(lái)足以從側(cè)面說(shuō)明書(shū)的結(jié)構(gòu)的重要性。1.3 算

36、法和算法分析Algorithms and Algorithm Analysis1.3.1算法所謂算法（Algorithm）是對(duì)問(wèn)題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。在CLRS中是這樣給出算法的定義的：Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input andproduces some value, or set of values, as output. An algori

37、thm is thus a sequence ofcomputational steps that transform the input into the output.一個(gè)算法必須滿足以下五個(gè)重要特性：1有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間完成；2確定性 對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義與如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；3可行性 算法中描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4有輸入 作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有

38、些輸入量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒(méi)有輸入，實(shí)際上已被嵌入算法之中；5有輸出 它是一組與輸入有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果。1.3.2算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)我們應(yīng)當(dāng)嚴(yán)格考慮：1正確性（Correctness）首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說(shuō)明”方式給出的需求。對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a程序中不含語(yǔ)法錯(cuò)誤；b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的輸出結(jié)果；c程序?qū)τ诰倪x擇的、典型、苛刻的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；通常以第c層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。因?yàn)樽鳛檩斎?，我們有時(shí)候不可能提前做出所有的預(yù)期?？勺x性(Readability)算法