數據結構復習重點(diǎn)歸納（適于清華嚴版教材）
近來(lái)，被不少朋友問(wèn)起關(guān)于各門(mén)學(xué)科的復習重點(diǎn)問(wèn)題，我想這正在成為越來(lái)越多的同學(xué)共同關(guān)注的一個(gè)焦點(diǎn)問(wèn)題，所以，從數據結構學(xué)科開(kāi)始，本版將陸續推出這一系列的復習重點(diǎn)的歸納。
既然作為某一門(mén)學(xué)科的重點(diǎn)歸納，不可避免地就要牽涉到我們歸納時(shí)所參照的教材。關(guān)于這一點(diǎn)，作個(gè)說(shuō)明。我們在作這些學(xué)科的歸納時(shí)，都會(huì )指明我們主要用的是哪本教材作為參照的。比如，數據結構，由于嚴老師的教材在國內是最為常用的，所以我們采用嚴蔚敏的教材。而如編譯原理，我們可能會(huì )采用陳火旺的；操作系統則采用湯子灜的?？傊?，我們采用是國內普遍采用的教材以及質(zhì)量和內容都相對更好的教材。
由于時(shí)間關(guān)系，這些復習重點(diǎn)，我們不可能一次全部給出，我們會(huì )陸續給出?，F在下面的各個(gè)系列回貼里給出數據結構的前面幾個(gè)章節的復習重要知識點(diǎn)歸納。
一、 數據結構的章節結構及重點(diǎn)構成
數據結構學(xué)科的章節劃分基本上為：概論，線(xiàn)性表，棧和隊列，串，多維數組和廣義表，樹(shù)和二叉樹(shù)，圖，查找，內排，外排，文件，動(dòng)態(tài)存儲分配。
對于絕大多數的學(xué)校而言，“外排，文件，動(dòng)態(tài)存儲分配”三章基本上是不考的，在大多數高校的計算機本科教學(xué)過(guò)程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費過(guò)多的精力，只要知道基本的概念即可。但是，對于報考名校特別是該校又有在試卷中對這三章進(jìn)行過(guò)考核的歷史，那么這部分朋友就要留意這三章了。
按照以上我們給出的章節以及對后三章的介紹，數據結構的章節比重大致為：
概論：內容很少，概念簡(jiǎn)單，分數大多只有幾分，有的學(xué)校甚至不考。
線(xiàn)性表：基礎章節，必考內容之一?？碱}多數為基本概念題，名?？碱}中，鮮有大型算法設計題。如果有，也是與其它章節內容相結合。
棧和隊列：基礎章節，容易出基本概念題，必考內容之一。而棧常與其它章節配合考查，也常與遞歸等概念相聯(lián)系進(jìn)行考查。
串 ：基礎章節，概念較為簡(jiǎn)單。專(zhuān)門(mén)針對于此章的大型算法設計題很少，較常見(jiàn)的是根據KMP進(jìn)行算法分析。
多維數組及廣義表 ：基礎章節，基于數組的算法題也是常見(jiàn)的，分數比例波動(dòng)較大，是出題的“可選單元”或“侯補單元”。一般如果要出題，多數不會(huì )作為大題出。數組常與“查找，排序”等章節結合來(lái)作為大題考查。
樹(shù)和二叉樹(shù) ：重點(diǎn)難點(diǎn)章節，各校必考章節。各校在此章出題的不同之處在于，是否在本章中出一到兩道大的算法設計題。通過(guò)對多所學(xué)校的試卷分析，絕大多數學(xué)校在本章都曾有過(guò)出大型算法設計題的歷史。
圖 ：重點(diǎn)難點(diǎn)章節，名校尤愛(ài)考。如果作為重點(diǎn)來(lái)考，則多出現于分析與設計題型當中，可與樹(shù)一章共同構成算法設計大題的題型設計。
查找 ：重點(diǎn)難點(diǎn)章節，概念較多，聯(lián)系較為緊密，容易混淆。出題時(shí)可以作為分析型題目給出，在基本概念型題目中也較為常見(jiàn)。算法設計型題中可以數組結合來(lái)考查，也可以與樹(shù)一章結合來(lái)考查。
排序 ：與查找一章類(lèi)似，本章同屬于重點(diǎn)難點(diǎn)章節，且概念更多，聯(lián)系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛(ài)考各種排序算法的優(yōu)劣比較此類(lèi)的題。算法設計大題中，如果作為出題，那么常與數組結合來(lái)考查。
二、 數據結構各章節重點(diǎn)勾劃：
第0章 概述
本章主要起到總領(lǐng)作用，為讀者進(jìn)行數據結構的學(xué)習進(jìn)行了一些先期鋪墊。大家主要注意以下幾點(diǎn)：數據結構的基本概念，時(shí)間和空間復雜度的概念及度量方法，算法設計時(shí)的注意事項。本章考點(diǎn)不多，只要稍加注意理解即可。
第一章 線(xiàn)性表
作為線(xiàn)性結構的開(kāi)篇章節，線(xiàn)性表一章在線(xiàn)性結構的學(xué)習乃至整個(gè)數據結構學(xué)科的學(xué)習中，其作用都是不可低估的。在這一章，第一次系統性地引入鏈式存儲的概念，鏈式存儲概念將是整個(gè)數據結構學(xué)科的重中之重，無(wú)論哪一章都涉及到了這個(gè)概念。
總體來(lái)說(shuō)，線(xiàn)性表一章可供考查的重要考點(diǎn)有以下幾個(gè)方面：
1.線(xiàn)性表的相關(guān)基本概念，如：前驅、后繼、表長(cháng)、空表、首元結點(diǎn)，頭結點(diǎn)，頭指針等概念。
2.線(xiàn)性表的結構特點(diǎn)，主要是指：除第一及最后一個(gè)元素外，每個(gè)結點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼。
3.線(xiàn)性表的順序存儲方式及其在具體語(yǔ)言環(huán)境下的兩種不同實(shí)現：表空間的靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處。
4.線(xiàn)性表的鏈式存儲方式及以下幾種常用鏈表的特點(diǎn)和運算：?jiǎn)捂湵?、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見(jiàn)的考查方式。此外，近年來(lái)在不少學(xué)校中還多次出現要求用遞歸算法實(shí)現單鏈表輸出（可能是順序也可能是倒序）的問(wèn)題。
在鏈表的小題型中，經(jīng)?？嫉揭恍┲T如：判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請大家注意。
5.線(xiàn)性表的順序存儲及鏈式存儲情況下，其不同的優(yōu)缺點(diǎn)比較，即其各自適用的場(chǎng)合。單鏈表中設置頭指針、循環(huán)鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處。
第二章 棧與隊列
棧與隊列，是很多學(xué)習DS的同學(xué)遇到第一只攔路虎，很多人從這一章開(kāi)始坐暈車(chē)，一直暈到現在。所以，理解棧與隊列，是走向DS高手的一條必由之路， 。
學(xué)習此章前，你可以問(wèn)一下自己是不是已經(jīng)知道了以下幾點(diǎn)：
1.棧、隊列的定義及其相關(guān)數據結構的概念，包括：順序棧，鏈棧，共享棧，循環(huán)隊列，鏈隊等。棧與隊列存取數據（請注意包括：存和取兩部分）的特點(diǎn)。
2.遞歸算法。棧與遞歸的關(guān)系，以及借助棧將遞歸轉向于非遞歸的經(jīng)典算法：n!階乘問(wèn)題，fib數列問(wèn)題，hanoi問(wèn)題，背包問(wèn)題，二叉樹(shù)的遞歸和非遞歸遍歷問(wèn)題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹(shù)與圖的問(wèn)題，多半會(huì )在樹(shù)與圖的相關(guān)章節中進(jìn)行考查。
3.棧的應用：數值表達式的求解，括號的配對等的原理，只作原理性了解，具體要求考查此為題目的算法設計題不多。
4.循環(huán)隊列中判隊空、隊滿(mǎn)條件，循環(huán)隊列中入隊與出隊算法。
如果你已經(jīng)對上面的幾點(diǎn)了如指掌，棧與隊列一章可以不看書(shū)了。注意，我說(shuō)的是可以不看書(shū)，并不是可以不作題哦。
第三章 串
經(jīng)歷了棧一章的痛苦煎熬后，終于迎來(lái)了串一章的柳暗花明。
串，在概念上是比較少的一個(gè)章節，也是最容易自學(xué)的章節之一，但正如每個(gè)過(guò)來(lái)人所了解的，KMP算法是這一章的重要關(guān)隘，突破此關(guān)隘后，走過(guò)去又是一馬平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡壘有：
1.串的基本概念，串與線(xiàn)性表的關(guān)系（串是其元素均為字符型數據的特殊線(xiàn)性表），空串與空格串的區別，串相等的條件
2.串的基本操作，以及這些基本函數的使用，包括：取子串，串連接，串替換，求串長(cháng)等等。運用串的基本操作去完成特定的算法是很多學(xué)校在基本操作上的考查重點(diǎn)。
3.順序串與鏈串及塊鏈串的區別和聯(lián)系，實(shí)現方式。
4.KMP算法思想。KMP中next數組以及nextval數組的求法。明確傳統模式匹配算法的不足，明確next數組需要改進(jìn)之外。其中，理解算法是核心，會(huì )求數組是得分點(diǎn)。不用我多說(shuō)，這一節內容是本章的重中之重?？赡苓M(jìn)行的考查方式是：求next和nextval數組值，根據求得的next或nextval數組值給出運用KMP算法進(jìn)行匹配的匹配過(guò)程。
第四章 數組與廣義表
學(xué)過(guò)程序語(yǔ)言的朋友，數組的概念我們已經(jīng)不是第一次見(jiàn)到了，應該已經(jīng)“一回生，二回熟”了，所以，在概念上，不會(huì )存在太大障礙。但作為考研課程來(lái)說(shuō)，本章的考查重點(diǎn)可能與大學(xué)里的程序語(yǔ)言所關(guān)注的不太一樣，下面會(huì )作介紹。
廣義表的概念，是數據結構里第一次出現的。它是線(xiàn)性表或表元素的有限序列，構成該結構的每個(gè)子表或元素也是線(xiàn)性結構的，所以，這一章也歸入線(xiàn)性結構中。
本章的考查重點(diǎn)有：
1.多維數組中某數組元素的position求解。一般是給出數組元素的首元素地址和每個(gè)元素占用的地址空間并組給出多維數組的維數，然后要求你求出該數組中的某個(gè)元素所在的位置。
2.明確按行存儲和按列存儲的區別和聯(lián)系，并能夠按照這兩種不同的存儲方式求解1中類(lèi)型的題。
3.將特殊矩陣中的元素按相應的換算方式存入數組中。這些矩陣包括：對稱(chēng)矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉換的算法。
4.廣義表的概念，特別應該明確表頭與表尾的定義。這一點(diǎn)，是理解整個(gè)廣義表一節算法的基礎。近來(lái)，在一些學(xué)校中，出現了這樣一種題目類(lèi)型：給出對某個(gè)廣義表L若干個(gè)求了若干次的取頭和取尾操作后的串值，要求求出原廣義表L。大家要留意。
5.與廣義表有關(guān)的遞歸算法。由于廣義表的定義就是遞歸的，所以，與廣義表有關(guān)的算法也常是遞歸形式的。比如：求表深度，復制廣義表等。這種題目，可以根據不同角度廣義表的表現形式運用兩種不同的方式解答：一是把一個(gè)廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進(jìn)行操作；二是把一個(gè)廣義表看作是若干個(gè)子表，分別對每個(gè)子表進(jìn)行操作。
第五章 樹(shù)與二叉樹(shù)
從對線(xiàn)性結構的研究過(guò)度到對樹(shù)形結構的研究，是數據結構課程學(xué)習的一次躍變，此次躍變完成的好壞，將直接關(guān)系到你到實(shí)際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專(zhuān)業(yè)課總分。所以，樹(shù)這一章的重要性，已經(jīng)不說(shuō)自明了。
總體來(lái)說(shuō)，樹(shù)一章的知識點(diǎn)包括：
二叉樹(shù)的概念、性質(zhì)和存儲結構，二叉樹(shù)遍歷的三種算法（遞歸與非遞歸），在三種基本遍歷算法的基礎上實(shí)現二叉樹(shù)的其它算法，線(xiàn)索二叉樹(shù)的概念和線(xiàn)索化算法以及線(xiàn)索化后的查找算法，最優(yōu)二叉樹(shù)的概念、構成和應用，樹(shù)的概念和存儲形式，樹(shù)與森林的遍歷算法及其與二叉樹(shù)遍歷算法的聯(lián)系，樹(shù)與森林和二叉樹(shù)的轉換。
下面我們來(lái)看考試中對以上知識的主要考查方法：
1.二叉樹(shù)的概念、性質(zhì)和存儲結構
考查方法可有：直接考查二叉樹(shù)的定義，讓你說(shuō)明二叉樹(shù)與普通雙分支樹(shù)的區別；考查滿(mǎn)二叉樹(shù)和完全二叉樹(shù)的性質(zhì)，普通二叉樹(shù)的五個(gè)性質(zhì)：第i層的最多結點(diǎn)數，深度為k的二叉樹(shù)的最多結點(diǎn)數，n0=n2+1的性質(zhì)，n個(gè)結點(diǎn)的完全二叉樹(shù)的深度，順序存儲二叉樹(shù)時(shí)孩子結點(diǎn)與父結點(diǎn)之間的換算關(guān)系（左為：2*i，右為：2*i+1）。
二叉樹(shù)的順序存儲和二叉鏈表存儲的各自?xún)?yōu)缺點(diǎn)及適用場(chǎng)合，二叉樹(shù)的三叉鏈表表示方法。
2.二叉樹(shù)的三種遍歷算法
這一知識點(diǎn)掌握的好壞，將直接關(guān)系到樹(shù)一章的算法能否理解，進(jìn)而關(guān)系到樹(shù)一章的算法設計題能否順利完成。二叉樹(shù)的遍歷算法有三種：先序，中序和后序。其劃分的依據是視其每個(gè)算法中對根結點(diǎn)數據的訪(fǎng)問(wèn)順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執行的實(shí)際步驟，并且應該熟練掌握三種遍歷的非遞歸算法。由于二叉樹(shù)一章的很多算法，可以直接根據三種遞歸算法改造而來(lái)（比如：求葉子個(gè)數），所以，掌握了三種遍歷的非遞歸算法后，對付諸如：“利用非遞歸算法求二叉樹(shù)葉子個(gè)數”這樣的題目就下筆如有神了。我會(huì )在另一篇系列文章（http://bbs.kaoyan.com/ibbs.dll?bbsdisp?t_id=301583&bp=2&bt=0）里給出三種遍歷的遞歸和非遞歸算法的背記版，到時(shí)請大家一定熟記。
3.可在三種遍歷算法的基礎上改造完成的其它二叉樹(shù)算法：
求葉子個(gè)數，求二叉樹(shù)結點(diǎn)總數，求度為1或度為2的結點(diǎn)總數，復制二叉樹(shù)，建立二叉樹(shù)，交換左右子樹(shù)，查找值為n的某個(gè)指定結點(diǎn)，刪除值為n的某個(gè)指定結點(diǎn)，諸如此類(lèi)等等等等。如果你可以熟練掌握二叉樹(shù)的遞歸和非遞歸遍歷算法，那么解決以上問(wèn)題就是小菜一碟了。
4.線(xiàn)索二叉樹(shù)：
線(xiàn)索二叉樹(shù)的引出，是為避免如二叉樹(shù)遍歷時(shí)的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內存資源，如果遞歸層次一多，勢必帶來(lái)資源耗盡的危險，為了避免此類(lèi)情況，線(xiàn)索二叉樹(shù)便堂而皇之地出現了。對于線(xiàn)索二叉樹(shù)，應該掌握：線(xiàn)索化的實(shí)質(zhì)，三種線(xiàn)索化的算法，線(xiàn)索化后二叉樹(shù)的遍歷算法，基本線(xiàn)索二叉樹(shù)的其它算法問(wèn)題（如：查找某一類(lèi)線(xiàn)索二叉樹(shù)中指定結點(diǎn)的前驅或后繼結點(diǎn)就是一類(lèi)?？碱}）。
5.最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）：
最優(yōu)二叉樹(shù)是為了解決特定問(wèn)題引出的特殊二叉樹(shù)結構，它的前提是給二叉樹(shù)的每條邊賦予了權值，這樣形成的二叉樹(shù)按權相加之和是最小的。最優(yōu)二叉樹(shù)一節，直接考查算法源碼的很少，一般是給你一組數據，要求你建立基于這組數據的最優(yōu)二叉樹(shù)，并求出其最小權值之和，此類(lèi)題目不難，屬送分題。
6.樹(shù)與森林：
二叉樹(shù)是一種特殊的樹(shù)，這種特殊不僅僅在于其分支最多為2以及其它特征，一個(gè)最重要的特殊之處是在于：二叉樹(shù)是有序的！即：二叉樹(shù)的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹(shù)，這樣交換之后的二叉樹(shù)與原二叉樹(shù)我們認為是不相同的兩棵二叉樹(shù)。但是，對于普通的雙分支樹(shù)而言，不具有這種性質(zhì)。
樹(shù)與森林的遍歷，不像二叉樹(shù)那樣豐富，他們只有兩種遍歷算法：先根與后根（對于森林而言稱(chēng)作：先序與后序遍歷）。在難度比較大的考試中，也有基于此二種算法的基礎上再進(jìn)行擴展要求你利用這兩種算法設計其它算法的，但一般院校很少有這種考法，最多只是要求你根據先根或后根寫(xiě)出他們的遍歷序列。此二者的先根與后根遍歷與二叉樹(shù)中的遍歷算法是有對應關(guān)系的：先根遍歷對應二叉樹(shù)的先序遍歷，而后根遍歷對應二叉樹(shù)的中序遍歷。這一點(diǎn)成為很多學(xué)校的考點(diǎn)，考查的方式不一而足，有的直接考此句話(huà)，有的是先讓你求解遍歷序列然后回答這個(gè)問(wèn)題。二叉樹(shù)、樹(shù)與森林之所以能有以上的對應關(guān)系，全拜二叉鏈表所賜。二叉樹(shù)使用二叉鏈表分別存放他的左右孩子，樹(shù)利用二叉鏈表存儲孩子及兄弟（稱(chēng)孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。
樹(shù)一章，處處是重點(diǎn)，道道是考題，大家務(wù)必個(gè)個(gè)過(guò)關(guān)。
第六章 圖
如果說(shuō)，從線(xiàn)性結構向樹(shù)形結構研究的轉變，是數據結構學(xué)科對數據組織形式研究的一次升華，那么從樹(shù)形結構的研究轉到圖形結構的研究，則進(jìn)一步讓我們看到了數據結構對于解決實(shí)際問(wèn)題的重大推動(dòng)作用。
圖這一章的特點(diǎn)是：概念繁多，與離散數學(xué)中圖的概念聯(lián)系緊密，算法復雜，極易被考到，且容易出大題，尤其是名校，作為考研課程，如果不考查樹(shù)與圖兩章的知識，幾乎是不可想像的。
下面我們看一下圖這一章的主要考點(diǎn)以及這些考點(diǎn)的考查方式：
1.考查有關(guān)圖的基本概念問(wèn)題：
這些概念是進(jìn)行圖一章學(xué)習的基礎，這一章的概念包括：圖的定義和特點(diǎn)，無(wú)向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長(cháng)度，回路，（強）連通圖，（強）連通分量等概念。與這些概念相聯(lián)系的相關(guān)計算題也應該掌握。
2.考查圖的幾種存儲形式：
圖的存儲形式包括：鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。在考查時(shí)，有的學(xué)校是給出一種存儲形式，要求考生用算法或手寫(xiě)出與給定的結構相對應的該圖的另一種存儲形式。
3.考查圖的兩種遍歷算法：深度遍歷和廣度遍歷
深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個(gè)算法對圖一章的重要性等同于“先序、中序、后序遍歷”對于二叉樹(shù)一章的重要性。在考查時(shí)，圖一章的算法設計題常常是基于這兩種基本的遍歷算法而設計的，比如：“求最長(cháng)的最短路徑問(wèn)題”和“判斷兩頂點(diǎn)間是否存在長(cháng)為K的簡(jiǎn)單路徑問(wèn)題”，就分別用到了廣度遍歷和深度遍歷算法。
4.生成樹(shù)、最小生成樹(shù)的概念以及最小生成樹(shù)的構造：PRIM算法和KRUSKAL算法。
考查時(shí)，一般不要求寫(xiě)出算法源碼，而是要求根據這兩種最小生成樹(shù)的算法思想寫(xiě)出其構造過(guò)程及最終生成的最小生成樹(shù)。
5.拓撲排序問(wèn)題：
拓撲排序有兩種方法，一是無(wú)前趨的頂點(diǎn)優(yōu)先算法，二是無(wú)后繼的頂點(diǎn)優(yōu)先算法。換句話(huà)說(shuō)，一種是“從前向后”的排序，一種是“從后向前”排。當然，后一種排序出來(lái)的結果是“逆拓撲有序”的。
6.關(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ò)“從后向前”的方法求解的，并且，要想求最晚時(shí)間必須是在所有的最早時(shí)間都已經(jīng)求出來(lái)之后才能進(jìn)行。這個(gè)問(wèn)題拿來(lái)直接考算法源碼的不多，一般是要求按照書(shū)上的算法描述求解的過(guò)程和步驟。
在實(shí)際設計關(guān)鍵路徑的算法時(shí)，還應該注意以下這一點(diǎn)：采用鄰接表的存儲結構，求最早時(shí)間和最晚時(shí)間要采用不同的處理方法，即：在算法初始時(shí)，應該首先將所有頂點(diǎn)的最早時(shí)間全部置為0。關(guān)鍵路徑問(wèn)題是工程進(jìn)度控制的重要方法，具有很強的實(shí)用性。
7.最短路徑問(wèn)題：
與關(guān)鍵路徑問(wèn)題并稱(chēng)為圖一章的兩只攔路虎。概念理解是比較容易的，關(guān)鍵是算法的理解。最短路徑問(wèn)題分為兩種：一是求從某一點(diǎn)出發(fā)到其余各點(diǎn)的最短路徑；二是求圖中每一對頂點(diǎn)之間的最短路徑。這個(gè)問(wèn)題也具有非常實(shí)用的背景特色，一個(gè)典型的應該就是旅游景點(diǎn)及旅游路線(xiàn)的選擇問(wèn)題。解決第一個(gè)問(wèn)題用DIJSKTRA算法，解決第二個(gè)問(wèn)題用FLOYD算法。注意區分。
第七章 查找
在不少數據結構的教材中，是把查找與排序放入高級數據結構中的。應該說(shuō)，查找和排序兩章是前面我們所學(xué)的知識的綜合運用，用到了樹(shù)、也用到了鏈表等知識，對這些數據結構某一方面的運用就構成了查找和排序。
現實(shí)生活中，search幾乎無(wú)處不在，特別是現在的網(wǎng)絡(luò )時(shí)代，萬(wàn)事離不開(kāi)search，小到文檔內文字的搜索，大到INTERNET上的搜索，search占據了我們上網(wǎng)的大部分時(shí)間。
在復習這一章的知識時(shí)，你需要先弄清楚以下幾個(gè)概念：
關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義；靜態(tài)查找與動(dòng)態(tài)查找的含義及區別；平均查找長(cháng)度ASL的概念及在各種查找算法中的計算方法和計算結果，特別是一些典型結構的ASL值，應該記住。
在DS的教材中，一般將search分為三類(lèi)：1st，在順序表上的查找；2nd，在樹(shù)表上的查找；3rd，在哈希表上的查找。下面詳細介紹其考查知識點(diǎn)及考查方式：
1.線(xiàn)性表上的查找：
主要分為三種線(xiàn)性結構：順序表，有序順序表，索引順序表。對于第一種，我們采用傳統查找方法，逐個(gè)比較。對于及有序順序表我們采用二分查找法。對于第三種索引結構，我們采用索引查找算法?？忌枰⒁膺@三種表下的ASL值以及三種算法的實(shí)現。其中，二分查找還要特別注意適用條件以及其遞歸實(shí)現方法。
2.樹(shù)表上的查找：
這是本章的重點(diǎn)和難點(diǎn)。由于這一節介紹的內容是使用樹(shù)表進(jìn)行的查找，所以很容易與樹(shù)一間的某些概念相混淆。本節內容與樹(shù)一章的內容有聯(lián)系，但也有很多不同，應注意規納。樹(shù)表主要分為以下幾種：二叉排序樹(shù)，平衡二叉樹(shù)，B樹(shù)，鍵樹(shù)。其中，尤以前兩種結構為重，也有部分名校偏愛(ài)考B樹(shù)的。由于二叉排序樹(shù)與平衡二叉樹(shù)是一種特殊的二叉樹(shù)，所以與二叉樹(shù)的聯(lián)系就更為緊密，二叉樹(shù)一章學(xué)好了，這里也就不難了。
二叉排序樹(shù)，簡(jiǎn)言之，就是“左小右大”，它的中序遍歷結果是一個(gè)遞增的有序序列。平衡二叉樹(shù)是二叉排序樹(shù)的優(yōu)化，其本質(zhì)也是一種二叉排序樹(shù)，只不過(guò)，平衡二叉樹(shù)對左右子樹(shù)的深度有了限定：深度之差的絕對值不得大于1。對于二叉排序樹(shù)，“判斷某棵二叉樹(shù)是否二叉排序樹(shù)”這一算法經(jīng)常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹(shù)的建立也是一個(gè)?？键c(diǎn)，但該知識點(diǎn)歸根結底還是關(guān)注的平衡二叉樹(shù)的四種調整算法，所以應該掌握平衡二叉樹(shù)的四種調整算法，調整的一個(gè)參照是：調整前后的中序遍歷結果相同。
B樹(shù)是二叉排序樹(shù)的進(jìn)一步改進(jìn)，也可以把B樹(shù)理解為三叉、四叉....排序樹(shù)。除B樹(shù)的查找算法外，應該特別注意一下B樹(shù)的插入和刪除算法。因為這兩種算法涉及到B樹(shù)結點(diǎn)的分裂和合并，是一個(gè)難點(diǎn)。B樹(shù)是報考名校的同學(xué)應該關(guān)注的焦點(diǎn)之一。
鍵樹(shù)也稱(chēng)字符樹(shù)，特別適用于查找英文單詞的場(chǎng)合。一般不要求能完整描述算法源碼，多是根據算法思想建立鍵樹(shù)及描述其大致查找過(guò)程。
3.基本哈希表的查找算法：
哈希一詞，是外來(lái)詞，譯自“hash”一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據當前待查找數據的特征，以記錄關(guān)鍵字為自變量，設計一個(gè)function，該函數對關(guān)鍵字進(jìn)行轉換后，其解釋結果為待查的地址?；诠１淼目疾辄c(diǎn)有：哈希函數的設計，沖突解決方法的選擇及沖突處理過(guò)程的描述。
第八章 內部排序
內排是DS課程中最后一個(gè)重要的章節，建立在此章之上的考題可以有多種類(lèi)型：填空，選擇，判斷乃至大型算法題。但是，歸結到一點(diǎn)，就是考查你對書(shū)本上的各種排序算法及其思想以及其優(yōu)缺點(diǎn)和性能指標（時(shí)間復雜度）能否了如指掌。
這一章，我們對重點(diǎn)的規納將跟以上各章不同。我們將從以下幾個(gè)側面來(lái)對排序一章進(jìn)行不同的規納，以期能更全面的理解排序一章的總體結構及各種算法。
從排序算法的種類(lèi)來(lái)分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸并、計數等五種排序方法。
其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序算法的最根本的不同點(diǎn)，說(shuō)到底就是根據什么規則尋找新元素的插入點(diǎn)。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過(guò)控制每次參與排序的數的總范圍“由小到大”的增量來(lái)實(shí)現排序效率提高的目的。
交換排序，又稱(chēng)冒泡排序，在交換排序的基礎上改進(jìn)又可以得到快速排序?？焖倥判虻乃枷?，一語(yǔ)以敝之：用中間數將待排數據組一分為二?？焖倥判?，在處理的“問(wèn)題規模”這個(gè)概念上，與希爾有點(diǎn)相反，快速排序，是先處理一個(gè)較大規模，然后逐漸把處理的規模降低，最終達到排序的目的。
選擇排序，相對于前面幾種排序算法來(lái)說(shuō)，難度大一點(diǎn)。具體來(lái)說(shuō)，它可以分為：簡(jiǎn)單選擇、樹(shù)選擇、堆排。這三種方法的不同點(diǎn)是，根據什么規則選取最小的數。簡(jiǎn)單選擇，是通過(guò)簡(jiǎn)單的數組遍歷方案確定最小數；樹(shù)選擇，是通過(guò)“錦標賽”類(lèi)似的思想，讓兩數相比，不斷淘汰較大（?。┱?，最終選出最?。ù螅?；而堆排序，是利用堆這種數據結構的性質(zhì)，通過(guò)堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序中的堆建立、堆調整是重要考點(diǎn)。樹(shù)選擇排序，也曾經(jīng)在一些學(xué)校中的大型算法題中出現，請大家注意。
歸并排序，故名思義，是通過(guò)“歸并”這種操作完成排序的目的，既然是歸并就必須是兩者以上的數據集合才可能實(shí)現歸并。所以，在歸并排序中，關(guān)注最多的就是2路歸并。算法思想比較簡(jiǎn)單，有一點(diǎn)，要銘記在心：歸并排序是穩定排序。
基數排序，是一種很特別的排序方法，也正是由于它的特殊，所以，基數排序就比較適合于一些特別的場(chǎng)合，比如撲克牌排序問(wèn)題等?；鶖蹬判?，又分為兩種：多關(guān)鍵字的排序（撲克牌排序），鏈式排序（整數排序）?；鶖蹬判虻暮诵乃枷胍彩抢?#8220;基數空間”這個(gè)概念將問(wèn)題規模規范、變小，并且，在排序的過(guò)程中，只要按照基排的思想，是不用進(jìn)行關(guān)鍵字比較的，這樣得出的最終序列就是一個(gè)有序序列。
本章各種排序算法的思想以及偽代碼實(shí)現，及其時(shí)間復雜度都是必須掌握的，學(xué)習時(shí)要多注意規納、總結、對比。此外，對于教材中的10.7節，要求必須熟記，在理解的基礎上記憶，這一節幾乎成為很多學(xué)校每年的必考點(diǎn)。
本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請
點(diǎn)擊舉報。
