《《數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版》知識(shí)點(diǎn)概括》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版》知識(shí)點(diǎn)概括（13頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)概括 第一章 概 論 數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。 數(shù)據(jù)結(jié)構(gòu)的定義： 邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計(jì)算機(jī)。線性結(jié)構(gòu)：一對(duì)一關(guān)系。 線性結(jié)構(gòu)：多對(duì)多關(guān)系。 　　存儲(chǔ)結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。順序存儲(chǔ)結(jié)構(gòu)：如數(shù)組。 　　鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：如鏈表。 　　索引存儲(chǔ)結(jié)構(gòu)：稠密索引：每個(gè)結(jié)點(diǎn)都有索引項(xiàng)。 　　稀疏索引：每組結(jié)點(diǎn)都有索引項(xiàng)。 　　散列存儲(chǔ)結(jié)構(gòu)：如散列表。 數(shù)據(jù)運(yùn)算。 對(duì)數(shù)據(jù)的操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)

2、運(yùn)算集合。 　　常用的有：檢索、插入、刪除、更新、排序。 數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。 　　結(jié)構(gòu)類型：由用戶借助于描述機(jī)制定義，是導(dǎo)出類型。 　 抽象數(shù)據(jù)類型ADT：是抽象數(shù)據(jù)的組織和與之的操作。相當(dāng)于在概念層上描述問(wèn)題。 　　優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。 程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)好的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。 算法是一個(gè)良定義的計(jì)算過(guò)程，以一個(gè)或多個(gè)值輸入，并以一個(gè)或多個(gè)值輸出。 　　評(píng)價(jià)算法的好壞的因素：算法是正確的； 　　執(zhí)行算法的時(shí)間； 執(zhí)行算法的存儲(chǔ)空間（主要是輔助存儲(chǔ)空間

3、）； 算法易于理解、編碼、調(diào)試。 　時(shí)間復(fù)雜度：是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。 　漸近時(shí)間復(fù)雜度：是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。 　　評(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度。 　　算法中語(yǔ)句的頻度不僅與問(wèn)題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。 　　時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O（1）、對(duì)數(shù)階O（log2n）、線性階O（n）、線性對(duì)數(shù)階O（nlog2n）、平方階O（n^2）、立方階O（n^3）、……k次方階O（n^k）、指數(shù)階O（2^n）。 　　空間復(fù)雜度：是某個(gè)算法的空間耗費(fèi)，它是該算法所求解

4、問(wèn)題規(guī)模n的函數(shù)。 　　算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。 第二章 線性表 線性表是由n≥0個(gè)數(shù)據(jù)元素組成的有限序列。 n=0是空表；非空表，只能有一個(gè)開(kāi)始結(jié)點(diǎn)，有且只能有一個(gè)終端結(jié)點(diǎn)。 　　線性表上定義的基本運(yùn)算： 　　構(gòu)造空表：Initlist（L） 　　求表長(zhǎng)：Listlength（L） 　　取結(jié)點(diǎn)：GetNode（L，i） 　　查找：LocateNode（L，x） 　　插入：InsertList（L，x，i） 　　刪除：Delete（L，i） 　　順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲(chǔ)單元中。在存儲(chǔ)單元中的各元素的物理位置和

5、邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系是一致的。地址計(jì)算：LOCa（i）=LOCa（1）+（i-1）*d；（首地址為1） 　在順序表中實(shí)現(xiàn)的基本運(yùn)算： 　　插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為n/2；平均時(shí)間復(fù)雜度均為O（n）。 刪除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為（n-1）/2；平均時(shí)間復(fù)雜度均為O（n）。 　　線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還存儲(chǔ)了其后繼結(jié)點(diǎn)的地址信息（即指針或鏈）。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。 一個(gè)單鏈表由頭指針的名字來(lái)命名。 單鏈表運(yùn)算： 建立單鏈表頭插法：s->next=head；head=s

6、；生成的順序與輸入順序相反。平均時(shí)間復(fù)雜度均為O（n）。 尾插法：head=rear=null；if（head=null） head=s；else r->next=s；r=s； 平均時(shí)間復(fù)雜度均為O（n） 　　加頭結(jié)點(diǎn)的算法：對(duì)開(kāi)始結(jié)點(diǎn)的操作無(wú)需特殊處理，統(tǒng)一了空表和非空表。 　　查找按序號(hào)：與查找位置有關(guān)，平均時(shí)間復(fù)雜度均為O（n）。 　　按值：與輸入實(shí)例有關(guān)，平均時(shí)間復(fù)雜度均為O（n）。 　　插入運(yùn)算：p=GetNode（L，i-1）；s->next=p->next；p->next=s；平均時(shí)間復(fù)雜度均為O（n） 刪除運(yùn)算：p=GetNode（L，i-1）；r=p->next；

7、p->next=r->next；free（r）；平均時(shí)間復(fù)雜度均為O（n） 單循環(huán)鏈表是一種首尾相接的單鏈表，終端結(jié)點(diǎn)的指針域指向開(kāi)始結(jié)點(diǎn)或頭結(jié)點(diǎn)。鏈表終止條件是以指針等于頭指針或尾指針。 　　采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)是查找頭指針和尾指針的時(shí)間都是O（1），不用 遍歷整個(gè)鏈表。 　　雙鏈表就是雙向鏈表，就是在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior，形成兩條不同方 向的鏈。由頭指針head惟一確定。 　　雙鏈表也可以頭尾相鏈接構(gòu)成雙（向）循環(huán)鏈表。 　　雙鏈表上的插入和刪除時(shí)間復(fù)雜度均為O （1）。 　　順序表和鏈表的比較：　　

8、基于空間： 　　 順序表的存儲(chǔ)空間是靜態(tài)分配，存儲(chǔ)密度為1；適于線性表事先確定其大小時(shí)采用。 鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配，存儲(chǔ)密度＜1；適于線性表長(zhǎng)度變化大時(shí)采用。 　　基于時(shí)間： 　　順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時(shí)，宜采用。 　　以插入和刪除操作為主的線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。 若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。 第三章 棧和隊(duì)列 　　棧（Stack）是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無(wú)元素時(shí)為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的，我們又稱棧為L(zhǎng)IFO表（Last

9、In First Out）。通常棧有 順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)。 　　棧的基本運(yùn)算有六種： 構(gòu)造空棧：InitStack（S） 　　判?？眨?StackEmpty（S） 　　判棧滿： StackFull（S） 　　進(jìn)棧： Push（S，x） 　　退棧： Pop（S） 　　取棧頂元素：StackTop（S） 　　在順序棧中有“上溢”和“下溢”的現(xiàn)象。 “上溢”是棧頂指針指出棧的外面是出錯(cuò)狀態(tài)。 　　“下溢”可以表示棧為空棧，因此用來(lái)作為控制轉(zhuǎn)移的條件。 　　順序棧中的基本操作有六種：構(gòu)造空棧 判?？? 判棧滿 進(jìn)棧 退棧 取棧頂元素 　　鏈棧則沒(méi)有上溢的限制，因此進(jìn)

10、棧不要判棧滿。鏈棧不需要在頭部附加頭結(jié)點(diǎn)，只要有鏈表的頭指針就可以了。 鏈棧中的基本操作有五種：構(gòu)造空棧 判?？? 進(jìn)棧 退棧 取棧頂元素 隊(duì)列（Queue）是一種運(yùn)算受限的線性表，插入在表的一端進(jìn)行，而刪除在表的另一端進(jìn)行，允許刪除的一端稱 為隊(duì)頭（front），允許插入的一端稱為隊(duì)尾（rear） ，隊(duì)列的操作原則是先進(jìn)先出的，又稱作FIFO表（First In First Out） .隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。 隊(duì)列的基本運(yùn)算有六種：　　置空隊(duì)：InitQueue（Q） 　判隊(duì)空：QueueEmpty（Q） 　判隊(duì)滿：QueueFull（Q）

11、 　入隊(duì)：EnQueue（Q，x） 　出隊(duì)：DeQueue（Q） 　取隊(duì)頭元素：QueueFront（Q） 　　順序隊(duì)列的“假上溢”現(xiàn)象：由于頭尾指針不斷前移，超出向量空間。這時(shí)整個(gè)向量空間及隊(duì)列是空的卻產(chǎn)生了“上 溢”現(xiàn)象。 　為了克服“假上溢”現(xiàn)象引入循環(huán)向量的概念，是把向量空間形成一個(gè)頭尾相接的環(huán)形，這時(shí)隊(duì)列稱循環(huán)隊(duì)列。 判定循環(huán)隊(duì)列是空還是滿，方法有三種： 一種是另設(shè)一個(gè)布爾變量來(lái)判斷； 第二種是少用一個(gè)元素空間，入隊(duì)時(shí)先測(cè)試（（rear+1）%m = front）？ 滿：空； 　　第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列，一

12、個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表。為了便于在表尾進(jìn)行插入（入隊(duì)）的 操作，在表尾增加一個(gè)尾指針，一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì)滿和上溢 的問(wèn)題。在鏈隊(duì)列的出隊(duì)算法中，要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空。 第四章 串 　　串是零個(gè)或多個(gè)字符組成的有限序列。 　　空串：是指長(zhǎng)度為零的串，也就是串中不包含任何字符（結(jié)點(diǎn)）。 　　空白串：指串中包含一個(gè)或多個(gè)空格字符的串。 　　在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。 　　子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置。 　　

13、空串是任意串的子串，任意串是自身的子串。 　　串分為兩種： 串常量在程序中只能引用不能改變； 　　串變量的值可以改變。 　　串的基本運(yùn)算有： 求串長(zhǎng)strlen（char*s） 串復(fù)制strcpy（char*to，char*from） 　串聯(lián)接strcat（char*to，char*from） 　串比較charcmp（char*s1，char*s2） 字符定位strchr（char*s，charc） 　串是特殊的線性表（結(jié)點(diǎn)是字符），所以串的存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。 　順序串又可按存儲(chǔ)分配的不同分為： 靜態(tài)存儲(chǔ)分配：直接用定長(zhǎng)的字符數(shù)

14、組來(lái)定義。優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度 快，但不適合插入、鏈接操作。 　動(dòng)態(tài)存儲(chǔ)分配：是在定義串時(shí)不分配存儲(chǔ)空間，需要使用時(shí)按所需串的長(zhǎng)度分配存儲(chǔ)單元。 　串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。鏈串與單鏈表的差異只是它的 結(jié) 點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。 為了解決“存儲(chǔ)密度”低的狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)的大小。 　　順序串上子串定位的運(yùn)算：又稱串的“模式匹配”或“串匹配”，是在主串中查找出子串出現(xiàn)的位置。在串匹配中，將主串稱為目標(biāo)（串），子串稱為模式（串）。這是比較容易理解的，串匹配問(wèn)題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者

15、是全部有效位移。最壞的情況下時(shí)間復(fù)雜度是O（（n-m+1）m），假如m與n同階 的話則它是O（n^2）。鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址而不是整數(shù) 第五章 多維數(shù)組 數(shù)組一般用順序存儲(chǔ)的方式表示。 存儲(chǔ)的方式有： 行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL、C 　　 列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRAN 　　地址的計(jì)算方法： 按行優(yōu)先順序排列的數(shù)組：LOCa（ij）=LOCa（11）+（（i-1）*n+（j-1））*d. 　　按列優(yōu)先順序排列的數(shù)組：LOCa（ij）=LOCa（11）+（（j-1）*n

16、+（i-1））*d. 矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。 　　特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。 　　稀疏矩陣的概念：一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則該矩陣稱為稀疏矩陣。 　　 特殊矩陣的類型： 對(duì)稱矩陣：滿足a（ij）=a（ji）。元素總數(shù)n（n+1）/2.I=max（i，j），J=min（i，j），LOCa（ij）=LOC（sa[0]）+（I*（I+1）/2+J）*d. 　　三角矩陣： 上三角陣：k=i*（2n-i+1）/2+j-i，LOCa（ij）=LOC（sa[0]）+k*

17、d. 　　 下三角陣：k=i*（i+1）/2+j，LOCa（ij）=LOC（sa[0]）+k*d. 　　對(duì)角矩陣：k=2i+j，LOCa（ij）=LOC（sa[0]）+k*d. 　　稀疏矩陣的壓縮存儲(chǔ)方式用三元組表把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起，用這些結(jié)點(diǎn)組成的一個(gè)線性表來(lái)表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行的非零元素在三元組表中的 起始位置，即帶行表的三元組表。 第六章 樹(shù) 　　樹(shù)是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有一個(gè)稱為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱 根的子樹(shù)。 　　根是開(kāi)始結(jié)點(diǎn)；結(jié)點(diǎn)的子樹(shù)

18、數(shù)稱度；度為0的結(jié)點(diǎn)稱葉子（終端結(jié)點(diǎn)）；度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn)（非終端結(jié) 點(diǎn)）；除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn)； 　有序樹(shù)是子樹(shù)有左，右之分的樹(shù)；無(wú)序樹(shù)是子樹(shù)沒(méi)有左，右之分的樹(shù)；森林是m個(gè)互不相交的樹(shù)的集合； 　　樹(shù)的四種不同表示方法：樹(shù)形表示法；嵌套集合表示法；凹入表示法廣義表表示法。 　　二叉樹(shù)的定義：是n≥0個(gè)結(jié)點(diǎn)的有限集，它是空集（n=0）或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的 左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。 　　二叉樹(shù)不是樹(shù)的特殊情形，與度數(shù)為2的有序樹(shù)不同。 　　二叉樹(shù)的4個(gè)重要性質(zhì)： 二叉樹(shù)上第i層上的結(jié)點(diǎn)數(shù)目最多為2^（i-1）（i≥1）。； 　　深度為k的

19、二叉樹(shù)至多有（2^k）-1個(gè)結(jié)點(diǎn)（k≥1）； 　　在任意一棵二叉樹(shù)中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1； 　　具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為int（log2n）+1. 　滿二叉樹(shù)是一棵深度為k，結(jié)點(diǎn)數(shù)為（2^k）-1的二叉樹(shù)；完全二叉樹(shù)是滿二叉樹(shù)在最下層自右向左去處部分結(jié)點(diǎn)； 　二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹(shù)的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。（存儲(chǔ)前先將其畫(huà)成完全 二叉樹(shù)） 　樹(shù)的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。BinTNode的結(jié)構(gòu)為lchild|data|rchild，把所有BinTNode類型的結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)的BinTree型

20、頭指針就構(gòu)成了二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。 共有2n個(gè)指針域，n+1個(gè)空指針。 根據(jù)訪問(wèn)結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷（前序遍歷或先根遍歷），中序遍歷（或中根遍歷）、后序遍歷（或 后根遍歷）。時(shí)間復(fù)雜度為O（n）。 利用二叉鏈表中的n+1個(gè)空指針域來(lái)存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié) 點(diǎn)的前序前趨和后序后繼并沒(méi)有什么作用。 樹(shù)和森林及二叉樹(shù)的轉(zhuǎn)換是唯一對(duì)應(yīng)的。 轉(zhuǎn)換方法： 樹(shù)變二叉樹(shù)：兄弟相連，

21、保留長(zhǎng)子的連線。 　二叉樹(shù)變樹(shù)：結(jié)點(diǎn)的右孩子與其雙親連。 　　森林變二叉樹(shù)：樹(shù)變二叉樹(shù)，各個(gè)樹(shù)的根相連。 樹(shù)的存儲(chǔ)結(jié)構(gòu)：有雙親鏈表表示法：結(jié)點(diǎn)data | parent，對(duì)于求指定結(jié)點(diǎn)的雙親或祖先十分方便，但不適于求指定結(jié) 點(diǎn)的孩子及后代。 　孩子鏈表表示法：為樹(shù)中每個(gè)結(jié)點(diǎn)data | next設(shè)置一個(gè)孩子鏈表firstchild，并將data | firstchild存放在一個(gè)向量中。 　雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。 　孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的

22、 指針域。 　　樹(shù)的前序遍歷與相對(duì)應(yīng)的二叉樹(shù)的前序遍歷一致；樹(shù)的后序遍歷與相對(duì)應(yīng)的二叉樹(shù)的中序遍歷一致。 　　樹(shù)的帶權(quán)路徑長(zhǎng)度是樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。樹(shù)的帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)就稱為最優(yōu)二叉樹(shù) （即哈夫曼樹(shù)）。 　　在葉子的權(quán)值相同的二叉樹(shù)中，完全二叉樹(shù)的路徑長(zhǎng)度最短。 　　哈夫曼樹(shù)有n個(gè)葉結(jié)點(diǎn)，共有2n-1個(gè)結(jié)點(diǎn)，沒(méi)有度為1的結(jié)點(diǎn)，這類樹(shù)又稱為嚴(yán)格二叉樹(shù)。 　　變長(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長(zhǎng)，但是變長(zhǎng)編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個(gè)碼無(wú)法在解碼時(shí)確定是哪一個(gè)，所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的

23、前綴，這種碼稱為前綴碼（其實(shí)是非前綴碼）。 　　哈夫曼樹(shù)的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易，只要畫(huà)好了哈夫曼樹(shù)，按分支情況在左路徑上寫(xiě)代碼0，右路徑上寫(xiě)代碼1，然后從上到下到葉結(jié) 點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。 第七章 圖 圖的邏輯結(jié)構(gòu)特征就是其結(jié)點(diǎn)（頂點(diǎn)）的前趨和后繼的個(gè)數(shù)都是沒(méi)有限制的，即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。 圖GraphG=（V，E），V是頂點(diǎn)的有窮非空集合，E是頂點(diǎn)偶對(duì)的有窮集。 有向圖Digraph：每條邊有方向；無(wú)向圖Undigraph：每條邊沒(méi)有方向。 有向完全圖：

24、具有n*（n-1）條邊的有向圖；無(wú)向完全圖：具有n*（n-1）/2條邊的無(wú)向圖； 有根圖：有一個(gè)頂點(diǎn)有路徑到達(dá)其它頂點(diǎn)的有向圖；簡(jiǎn)單路徑：是經(jīng)過(guò)頂點(diǎn)不同的路徑；簡(jiǎn)單回路是開(kāi)始和終端重 的簡(jiǎn)單路徑； 網(wǎng)絡(luò)：是帶權(quán)的圖。 圖的存儲(chǔ)結(jié)構(gòu)： 　　鄰接矩陣表示法：用一個(gè)n階方陣來(lái)表示圖的結(jié)構(gòu)是唯一的，適合稠密圖。 　　無(wú)向圖：鄰接矩陣是對(duì)稱的。 　　有向圖：行是出度，列是入度。 建立鄰接矩陣算法的時(shí)間是O（n+n^2+e），其時(shí)間復(fù)雜度為O（n^2） 　　鄰接表表示法：用頂點(diǎn)表和鄰接表構(gòu)成不是唯一的，適合稀疏圖。 頂點(diǎn)表結(jié)構(gòu) vertex | firstedge，指針域存放鄰接表頭指

25、針。 鄰接表：用頭指針確定。 無(wú)向圖稱邊表； 有向圖又分出邊表和逆鄰接表； 鄰接表結(jié)點(diǎn)結(jié)構(gòu)為 adjvex | next， 　　時(shí)間復(fù)雜度為O（n+e）。，空間復(fù)雜度為O（n+e）。。 　　圖的遍歷： 深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問(wèn)結(jié)點(diǎn)。 　　廣度優(yōu)先遍歷：借助于鄰接矩陣的行。使用隊(duì)列保存已訪問(wèn)結(jié)點(diǎn)。 　　生成樹(shù)的定義：若從圖的某個(gè)頂點(diǎn)出發(fā)，可以系統(tǒng)地訪問(wèn)到圖中所有頂點(diǎn)，則遍歷時(shí)經(jīng)過(guò)的邊和圖的所有頂點(diǎn) 構(gòu)成的子圖稱作該圖的生成樹(shù)。 　　最小生成樹(shù)：圖的生成樹(shù)不唯一，從不同的頂點(diǎn)出發(fā)可得到不同的生成樹(shù)，把權(quán)值最小的生成樹(shù)稱為最小生成樹(shù) （MST）。 　　

26、構(gòu)造最小生成樹(shù)的算法： Prim算法的時(shí)間復(fù)雜度為O（n^2）與邊數(shù)無(wú)關(guān)適于稠密圖。 　　Kruskal算法的時(shí)間復(fù)雜度為O（lge），主要取決于邊數(shù)，較適合于稀疏圖。 　　最短路徑的算法：Dijkstra算法，時(shí)間復(fù)雜度為O（n^2）。類似于prim算法。 　　拓?fù)渑判颍菏菍⒂邢驘o(wú)環(huán)圖G中所有頂點(diǎn)排成一個(gè)線性序列，若∈E（G），則在線性序列u在v之前， 這種線性序列稱為拓?fù)湫蛄小? 拓?fù)渑判蛞灿袃煞N方法： 無(wú)前趨的頂點(diǎn)優(yōu)先，每次輸出一個(gè)無(wú)前趨的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其出邊，最后得到的序列即拓?fù)湫蛄小? 　　無(wú)后繼的結(jié)點(diǎn)優(yōu)先：每次輸出一個(gè)無(wú)后繼的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其入邊，最后得

27、到的序列是逆拓?fù)湫蛄小? 第八章 排序 　　記錄中可用某一項(xiàng)來(lái)標(biāo)識(shí)一個(gè)記錄，則稱為關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字。 　　排序是使文件中的記錄按關(guān)鍵字遞增（或遞減）次序排列起來(lái)。 　　基本操作：比較關(guān)鍵字大??；改變指向記錄的指針或移動(dòng)記錄。 　　存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。 　　經(jīng)過(guò)排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，則稱這種排序方法是穩(wěn)定的，否則排序算法是不穩(wěn)定的。 　　排序過(guò)程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為“內(nèi)部排序”（內(nèi)排序），反之，若存在數(shù)據(jù)的內(nèi)外存交換，則稱之為外排序。 內(nèi)部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配

28、排序。 　　評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條：執(zhí)行時(shí)間和所需的輔助空間，另外算法的復(fù)雜程序也是要考慮的一個(gè)因素。 　　插入排序：直接插入排序： 逐個(gè)向前插入到合適位置。 　　哨兵（監(jiān)視哨）有兩個(gè)作用： 作為臨變量存放R[i] 　　是在查找循環(huán)中用來(lái)監(jiān)視下標(biāo)變量j是否越界。 　　直接插入排序是就地的穩(wěn)定排序。時(shí)間復(fù)雜度為O（n^2），比較次數(shù)為（n+2）（n-1）/2；移動(dòng)次數(shù)為（n+4）（n-1）/2； 　希爾排序： 等間隔的數(shù)據(jù)比較并按要求順序排列，最后間隔為1. 　　希爾排序是就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為O（n^1.25），比較次數(shù)為（n^1.25）；移動(dòng)次數(shù)為（1.6n^

29、1.25）； 　　交換排序：冒泡排序：自下向上確定最輕的一個(gè)。自上向下確定最重的一個(gè)。自下向上確定最輕的一個(gè)，后自上向下確定最重的一個(gè)。 　　冒泡排序是就地的穩(wěn)定排序。時(shí)間復(fù)雜度為O（n^2），比較次數(shù)為n（n-1）/2；移動(dòng)次數(shù)為3n（n-1）/2； 　　快速排序：以第一個(gè)元素為參考基準(zhǔn)，設(shè)定、動(dòng)兩個(gè)指針，發(fā)生交換后指針交換位置，直到指針重合。重復(fù)直到排序完成。 　　快速排序是非就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為O（nlog2n），比較次數(shù)為n（n-1）/2； 　　選擇排序：直接選擇排序： 選擇最小的放在比較區(qū)前。 　　直接選擇排序就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為O（n^2）。比較次數(shù)

30、為n（n-1）/2； 　　堆排序 建堆：按層次將數(shù)據(jù)填入完全二叉樹(shù)，從int（n/2）處向前逐個(gè)調(diào)整位置。 　　然后將樹(shù)根與最后一個(gè)葉子交換值并斷開(kāi)與樹(shù)的連接并重建堆，直到全斷開(kāi)。 　　堆排序是就地不穩(wěn)定的排序，時(shí)間復(fù)雜度為O（nlog2n），不適宜于記錄數(shù)較少的文件。 　　歸并排序： 先兩個(gè)一組排序，形成（n+1）/2組，再將兩組并一組，直到剩下一組為止。 　　歸并排序是非就地穩(wěn)定排序，時(shí)間復(fù)雜度是O（nlog2n）， 　　分配排序：箱排序： 按關(guān)鍵字的取值范圍確定箱子數(shù)，按關(guān)鍵字投入箱子，鏈接所有非空箱。 　　箱排序的平均時(shí)間復(fù)雜度是線性的O（n）。 　基數(shù)排序：從低位到高

31、位依次對(duì)關(guān)鍵字進(jìn)行箱排序。 基數(shù)排序是非就穩(wěn)定的排序，時(shí)間復(fù)雜度是O（d*n+d*rd）。 　　各種排序方法的比較和選擇： 待排序的記錄數(shù)目n；n較大的要用時(shí)間復(fù)雜度為O（nlog2n）的排序方法； 　　記錄的大?。ㄒ?guī)模）；記錄大最好用鏈表作為存儲(chǔ)結(jié)構(gòu)，而快速排序和堆排序在鏈表上難于實(shí)現(xiàn)； 　　關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；　　對(duì)穩(wěn)定性的要求； 　　語(yǔ)言工具的條件； 　　存儲(chǔ)結(jié)構(gòu)；　　時(shí)間和輔助空間復(fù)雜度。 第九章 查找 　　查找的同時(shí)對(duì)表做修改操作（如插入或刪除）則相應(yīng)的表稱之為動(dòng)態(tài)查找表，否則稱之為靜態(tài)查找表。 　　衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的

32、平均比較次數(shù)（即平均查找長(zhǎng)度ASL）。 　　線性表查找的方法： 順序查找：逐個(gè)查找，ASL=（n+1）/2； 　　二分查找：取中點(diǎn)int（n/2）比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹(shù)表示。ASL=（∑（每層結(jié)點(diǎn)數(shù)*層數(shù)））/N. 　　分塊查找。要求“分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中的最大關(guān)鍵字及其位置建立有序索引表。 　　二叉排序樹(shù)（BST）定義是：二叉排序樹(shù)是空樹(shù)或者滿足如下性質(zhì)的二叉樹(shù)： 若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 　　若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； 左、右子樹(shù)本身又是一棵二叉排序樹(shù)。

33、 　　二叉排序樹(shù)的插入、建立、刪除的算法平均時(shí)間性能是O（nlog2n）。 　二叉排序樹(shù)的刪除操作可分三種情況進(jìn)行處理： *P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可。 　*P只有一個(gè)孩子*child，此時(shí)只需將*child和*p的雙親直接連接就可刪去*p. 　　*p有兩個(gè)孩子，則先將*p結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù)據(jù)到*p，刪除中序后繼結(jié)點(diǎn)。 　關(guān)于B-樹(shù)（多路平衡查找樹(shù)）。它適合在磁盤(pán)等直接存取設(shè)備上組織動(dòng)態(tài)的查找表，是一種外查找算法。建立的方式是從下向上拱起。 　散列技術(shù)：將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表的過(guò)程稱為散列。散列函數(shù)的選擇有兩

34、條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻。 常見(jiàn)的散列函數(shù)構(gòu)的造方法： 平方取中法：hash=int（（x^2）%100） 除余法：表長(zhǎng)為m，hash=x%m 　　相乘取整法：hash=int（m*（x*A-int（x*A））；A=0.618 　　 隨機(jī)數(shù)法：hash=random（x）。 處理沖突的方法：開(kāi)放定址法： 一般形式為hi=（h（key）+di）%m1≤i≤m-1，開(kāi)放定址法要求散列表的裝填因子α≤1. 　　開(kāi)放定址法類型： 線性探查法：address=（hash（x）+i）%m； 二次探查法：address=（hash（x）+i^2）%m； 　　 雙重散列法：ad

35、dress=（hash（x）+i*hash（y））%m； 　　 拉鏈法： 是將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。 　　 拉鏈法的優(yōu)點(diǎn)： 拉鏈法處理沖突簡(jiǎn)單，且無(wú)堆積現(xiàn)象； 　　 鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的適于無(wú)法確定表長(zhǎng)的情況； 　　 拉鏈法中α可以大于1，結(jié)點(diǎn)較大時(shí)其指針域可忽略，因此節(jié)省空間； 拉鏈法構(gòu)造的散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)。 　　拉鏈法也有缺點(diǎn)：當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，用拉鏈法中的指針域也要占用額外空間，還是開(kāi)放定址法省空間。 第十章 排序 10.1 排序的基本概念 10.2 插入排序 10

36、.3 選擇排序 10.4 交換排序 本章主要知識(shí)點(diǎn)： 排序的基本概念和衡量排序算法優(yōu)劣的標(biāo)準(zhǔn)，其中衡量標(biāo)準(zhǔn)有算法的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性 直接插入排序，希爾排序 直接選擇排序，堆排序 冒泡排序，快速排序 10.1排序的基本概念 1.排序是對(duì)數(shù)據(jù)元素序列建立某種有序排列的過(guò)程。 2.排序的目的：便于查找。 3.關(guān)鍵字是要排序的數(shù)據(jù)元素集合中的一個(gè)域，排序是以關(guān)鍵字為基準(zhǔn)進(jìn)行的。 關(guān)鍵字分主關(guān)鍵字和次關(guān)鍵字兩種。對(duì)要排序的數(shù)據(jù)元素集合來(lái)說(shuō)，如果關(guān)鍵字滿足數(shù)據(jù)元素值不同時(shí)該關(guān)鍵字的值也一定不同，這樣的關(guān)鍵字稱為主關(guān)鍵字。不滿足主關(guān)鍵字定義的關(guān)鍵字稱為

37、次關(guān)鍵字。 4.排序的種類：分為內(nèi)部排序和外部排序兩大類。 若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。 注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來(lái)排序，中間結(jié)果還要及時(shí)放入外 存，顯然外部排序要復(fù)雜得多。 5.排序算法好壞的衡量標(biāo)準(zhǔn)： (1)時(shí)間復(fù)雜度—— 它主要是分析記錄關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)。 (2)空間復(fù)雜度——算法中使用的內(nèi)存輔助空間的多少。 (3)穩(wěn)定性——若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。 10.2 插入排序 插入排序的基本

38、思想是：每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。 簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。 常用的插入排序有：直接插入排序和希爾排序兩種。 10.2.1 直接插入排序 1、其基本思想是： 順序地把待排序的數(shù)據(jù)元素按其關(guān)鍵字值的大小插入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。 例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11）， 請(qǐng)寫(xiě)出直接插入排序的中間過(guò)程序列。 初始關(guān)鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序： 【

39、6, 13】, 3, 31, 9, 27, 5, 11 第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11 第三次排序： 【3, 6, 13，31】, 9, 27, 5, 11 第四次排序： 【3, 6, 9, 13，31】, 27, 5, 11 第五次排序： 【3, 6, 9, 13，27, 31】, 5, 11 第六次排序： 【3, 5, 6, 9, 13，27, 31】, 11 第七次排序： 【3, 5, 6, 9, 11，13，27, 31】 注：方括號(hào) [ ]中為

40、已排序記錄的關(guān)鍵字，下劃?rùn)M線的 關(guān)鍵字 表示它對(duì)應(yīng)的記錄后移一個(gè)位置。 2.直接插入排序算法 public static void insertSort(int[] a){ int i, j, temp; int n = a.Length; for(i = 0; i < n - 1; i ++){ temp = a[i + 1]; j = i; while(j > -1 && temp < a[j]){ a[j + 1] = a[j]; j --; } a[j +

41、1] = temp; } } 初始關(guān)鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11 3、直接插入排序算法分析 (1)時(shí)間效率：當(dāng)數(shù)據(jù)有序時(shí)，執(zhí)行效率最好，此時(shí)的時(shí)間復(fù)雜度為O(n)；當(dāng)數(shù)據(jù)基本反序時(shí)，執(zhí)行效率最差，此時(shí)的時(shí)間復(fù)雜度為O(n2)。所以當(dāng)數(shù)據(jù)越接近有序，直接插入排序算法的性能越好。 (2)空間效率：僅占用1個(gè)緩沖單元——O（1） (3)算法的穩(wěn)定性：穩(wěn)定 8.2.2

42、 希爾（shell）排序 （又稱縮小增量排序） 1、基本思想：把整個(gè)待排序的數(shù)據(jù)元素分成若干個(gè)小組，對(duì)同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個(gè)數(shù)逐次縮小，當(dāng)完成了所有數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序后排序過(guò)程結(jié)束。 2、技巧：小組的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)增量d的記錄組成一個(gè)小組,讓增量d逐趟縮短（例如依次取5,3,1），直到d＝1為止。 3、優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。 例2：設(shè)待排序的序列中有12個(gè)記錄，它們的關(guān)鍵字序列 T=(65，34，25，87，12，38，5

43、6，46，14，77，92，23），請(qǐng)寫(xiě)出希爾排序的具體實(shí)現(xiàn)過(guò)程。 public static void shellSort(int[] a, int[] d, int numOfD){ int i, j, k, m, span; int temp; int n = a.Length; for(m = 0; m < numOfD; m ++){ //共numOfD次循環(huán) span = d[m]; //取本次的增量值 for(k = 0; k < span; k ++){ //共span個(gè)小組 for(i = k; i < n-span; i = i

44、+ span){ temp = a[i+span]; j = i; while(j > -1 && temp < a[j]){ a[j + span] = a[j]; j = j - span; } a[j + span] = temp; } } } } 算法分析：開(kāi)始時(shí)d 的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，d 值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)記錄已基本有序，所以排序速度仍然很快。 時(shí)間效率：O(n(log2n)2)

45、 空間效率：O（1）——因?yàn)閮H占用1個(gè)緩沖單元 算法的穩(wěn)定性：不穩(wěn)定 練習(xí)： 1. 欲將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按字母升序重排，則初始d為4的希爾排序一趟的結(jié)果是？ 答： 原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后： P,A,C,S,Q,D,F,X,R,H,M,Y 2. 以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫(xiě)出執(zhí)行希爾排序（取d=5,3,1）算法的各趟排序結(jié)束時(shí)

46、，關(guān)鍵字序列的狀態(tài)。 解：原始序列: 256，301，751，129，937，863，742，694，076，438 希爾排序第一趟d=5 256 301 694 076 438 863 742 751 129 937 第二趟d=3 076 301 129 256 438 694 742 751 863 937 第三趟d=1 076 129 256 301 438 694 742 751 863 937 10.3 選擇排序 選擇排序的基本思想是：每次從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最?。ɑ蜃畲螅?/p>

47、的數(shù)據(jù)元素放到數(shù)據(jù)元素集合的最前（或最后），數(shù)據(jù)元素集合不斷縮小，當(dāng)數(shù)據(jù)元素集合為空時(shí)選擇排序結(jié)束。 常用的選擇排序算法： （1）直接選擇排序 （2）堆排序 10.3.1直接選擇排序 1、其基本思想 每經(jīng)過(guò)一趟比較就找出一個(gè)最小值，與待排序列最前面的位置互換即可。 （即從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個(gè)數(shù)據(jù)元素交換位置；然后從不包括第一個(gè)位置的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)集合中的第二個(gè)數(shù)據(jù)元素交換位置；如此重復(fù)，直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。） 2、優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：實(shí)

48、現(xiàn)簡(jiǎn)單 缺點(diǎn)：每趟只能確定一個(gè)元素，表長(zhǎng)為n時(shí)需要n-1趟 例3：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)給出直接選擇排序的具體實(shí)現(xiàn)過(guò)程。 原始序列： 21，25，49，25*，16，08 第1趟 08，25，49，25*，16，21 第2趟 08，16, 49，25*，25，21 第3趟 08，16, 21，25*，25，49 第4趟 08，16, 21，25*，25，49 第5趟 08，16, 21，25*，25，49 public static void selectSort(int[] a){ int i,

49、j, small; int temp; int n = a.Length; for(i = 0; i < n - 1; i ++){ small = i; //設(shè)第i個(gè)數(shù)據(jù)元素最小 for(j = i + 1; j < n; j ++) //尋找最小的數(shù)據(jù)元素 if(a[j] < a[small]) small = j; //記住最小元素的下標(biāo) if(small != i){ //當(dāng)最小元素的下標(biāo)不為i時(shí)交換位置 temp = a[i];

50、 a[i] = a[small]; a[small] = temp; } } } 3、算法分析 時(shí)間效率： O(n2)——雖移動(dòng)次數(shù)較少，但比較次數(shù)仍多。 空間效率：O（1）——沒(méi)有附加單元（僅用到1個(gè)temp) 算法的穩(wěn)定性：不穩(wěn)定 4、穩(wěn)定的直接選擇排序算法 例：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)給出穩(wěn)定的直接選擇排序的具體實(shí)現(xiàn)過(guò)程。 原始序列： 21，25，49，25*，16，08 第1趟08, 21 , 25 , 49 , 25 *, 16 第2趟08，16, 21，25，

51、49 ，25 * 第3趟08，16, 21，25，49 ，25 * 第4趟08，16, 21，25，49 ，25 * 第5趟08，16, 21，25，25 * ，49 public static void selectSort2(int [] a){ int i,j,small; int temp; int n = a.Length; for(i = 0; i < n-1; i++){ small = i; for(j = i+1; j < n; j++){ //尋找最小的數(shù)據(jù)元素 if(a[j] <

52、a[small]) small = j; //記住最小元素的下標(biāo) } if(small != i){ temp = a[small]; for(j = small; j > i; j--) //把該區(qū)段尚未排序元素依次后移 a[j] = a[j-1]; a[i] = temp; //插入找出的最小元素 } } } 8.3.2 堆排序 1. 什么是堆？ 2. 怎樣建堆？ 3. 怎樣堆排序？ 堆的定義：設(shè)有n個(gè)數(shù)據(jù)元素的序列 k0，k1，…，k

53、n-1，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。 解釋：如果讓滿足以上條件的元素序列 （k０，k１，…，kn－１）順次排成一棵完全二叉樹(shù)，則此樹(shù)的特點(diǎn)是： 樹(shù)中所有結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹(shù)的根結(jié)點(diǎn)（即堆頂）必最大（或最?。?。 例4：有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判斷它們是否 “堆”？ 2. 怎樣建堆？ 步驟：從第一個(gè)非終端結(jié)點(diǎn)開(kāi)始往前逐步調(diào)整，讓每個(gè)雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。 終端結(jié)點(diǎn)（即葉子）沒(méi)有任何子女，無(wú)需單獨(dú)調(diào)整 例：關(guān)鍵字序列T= (

54、21，25，49，25*，16，08），請(qǐng)建最大堆。 解：為便于理解，先將原始序列畫(huà)成完全二叉樹(shù)的形式： 這樣可以很清晰地從(n-1-1)/2開(kāi)始調(diào)整。 public static void createHeap(int[] a, int n, int h){ int i, j, flag; int temp; i = h; j = 2 * i + 1; // j為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的下標(biāo) temp = a[i]; flag = 0; while(j < n &&

55、flag != 1){ //尋找左右孩子結(jié)點(diǎn)中的較大者,j為其下標(biāo) if(j < n - 1 && a[j] < a[j + 1]) j++; if (temp >= a[j]) //a[i]>=a[j] flag = 1; //標(biāo)記結(jié)束篩選條件 else{ //否則把a(bǔ)[j]上移 a[i] = a[j]; i = j; j = 2 * i + 1; } } a[i] = temp; } 利用上述createHeap（a,n,h）函數(shù)，初始化創(chuàng)建最大堆的過(guò)程就是從第一個(gè)非葉子結(jié)點(diǎn)a[i]開(kāi)

56、始，到根結(jié)點(diǎn)a[0]為止，循環(huán)調(diào)用createHeap（a,n,h）的過(guò)程。 初始化創(chuàng)建最大堆算法如下： public static void initCreateHeap(int[] a){ int n = a.Length; for(int i = (n-1-1) / 2; i >= 0; i --) createHeap(a, n, i); } 3. 怎樣進(jìn)行整個(gè)序列的堆排序？ *基于初始堆進(jìn)行堆排序的算法步驟： 堆的第一個(gè)對(duì)象a[0]具有最大的關(guān)鍵碼，將a[0]與a[n-1]對(duì)調(diào)，把具有最大關(guān)鍵碼的對(duì)象交換到最后; 再對(duì)前面的n-1個(gè)對(duì)象，使

57、用堆的調(diào)整算法，重新建立堆（調(diào)整根結(jié)點(diǎn)使之滿足最大堆的定義）。結(jié)果具有次最大關(guān)鍵碼的對(duì)象又上浮到堆頂，即a[0]位置; 再對(duì)調(diào)a[0]和a[n-2]，然后對(duì)前n-2個(gè)對(duì)象重新調(diào)整，…如此反復(fù)，最后得到全部排序好的對(duì)象序列。 例5：對(duì)剛才建好的最大堆進(jìn)行排序： public static void heapSort(int[] a){ int temp; int n = a.Length; initCreateHeap(a); //初始化創(chuàng)建最大堆 for(int i = n - 1; i > 0; i --){ //當(dāng)前最大堆個(gè)數(shù)每次遞減1 //把堆頂a[0]

58、元素和當(dāng)前最大堆的最后一個(gè)元素交換 temp = a[0]; a[0] = a[i]; a[i] = temp; createHeap(a,i, 0); //調(diào)整根結(jié)點(diǎn)滿足最大堆 } } 4、堆排序算法分析： 時(shí)間效率：O(nlog2n)。 空間效率：O(1)。 穩(wěn)定性： 不穩(wěn)定。 練習(xí)1：以下序列是堆的是（ ） {75,65,30,15,25,45,20,10} B. {75,65,45,10,30,25,20,15} C. {75,45,65,30,15,25,20,10} D. {7

59、5,45,65,10,25,30,20,15} 練習(xí)2：有一組數(shù)據(jù){15,9,7,8,20,1,7*,4}，建成的最小堆為（ ）。 A.{1,4,8,9,20,7,15,7*} B.{1,7,15,7*,4,8,20,9} C.{1,4,7,8,20,15,7*,9} D.以上都不對(duì) 練習(xí)3：已知序列{503，87，512，61，908，170，897，275，653，462}，寫(xiě)出采用堆排序?qū)υ撔蛄凶鞣沁f減排列時(shí)的排序過(guò)程。 排序好的序列為：61，87，170，275，462，503，512，653，897，908 10.4

60、交換排序 交換排序的基本思想是：利用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法。 交換排序的主要算法有： 1) 冒泡排序 2) 快速排序 10.4.1 冒泡排序 1、基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。 2、優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒(méi)有交換發(fā)生，還可以提前結(jié)束排序。 例：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)按從小到大的順序，寫(xiě)出冒泡排序的具體實(shí)現(xiàn)過(guò)程。 初態(tài)：21，25，49， 25*，16， 08 第1趟21，25，2

61、5*，16， 08 ， 49 第2趟21，25， 16， 08 ，25*，49 第3趟21，16， 08 ，25， 25*，49 第4趟16，08 ，21， 25， 25*，49 第5趟08，16， 21， 25， 25*，49 3、冒泡排序算法 public static void bubbleSort(int[] a){ int i, j, flag=1; int temp; int n = a.Length; for(i = 1; i < n && flag == 1; i++){ flag = 0; for(j = 0; j < n-i; j+

62、+){ if(a[j] > a[j+1]){ flag = 1; temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } 4、冒泡排序的算法分析 時(shí)間效率：O（n2) —因?yàn)橐紤]最壞情況（數(shù)據(jù)元素全部逆序），當(dāng)然最好情況是數(shù)據(jù)元素已全部排好序，此時(shí)循環(huán)n-1次，時(shí)間復(fù)雜度為O（n) 空間效率：O（1） —只在交換時(shí)用到一個(gè)緩沖單元 穩(wěn) 定 性： 穩(wěn)定 —25和25*在排序前后的次序未改變 練習(xí)：關(guān)鍵字序列 T=(31，15，9，25，16，28），請(qǐng)按從小到大的順序

63、，寫(xiě)出冒泡排序的具體實(shí)現(xiàn)過(guò)程。 初態(tài)：31，15，9， 25，16， 28 第1趟15，9，25，16， 28， 31 第2趟9，15， 16， 25，28，31 第3趟9，15， 16，25， 28，31 1、基本思想：設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，low為數(shù)組的低端下標(biāo)，high為數(shù)組的高端下標(biāo)，從數(shù)組a中任取一個(gè)元素（通常取a[low]）做為標(biāo)準(zhǔn)元素，以該標(biāo)準(zhǔn)元素調(diào)整數(shù)組a中其他各個(gè)元素的位置，使排在標(biāo)準(zhǔn)元素前面的元素均小于標(biāo)準(zhǔn)元素，排在標(biāo)準(zhǔn)元素后面的均大于或等于標(biāo)準(zhǔn)元素。這樣一次排序過(guò)程結(jié)束后，一方面將標(biāo)準(zhǔn)元素放在了未來(lái)排好序的數(shù)組中該標(biāo)準(zhǔn)元素應(yīng)位于的位置上，另一方面將數(shù)組

64、中的元素以標(biāo)準(zhǔn)元素為中心分成了兩個(gè)子數(shù)組，位于標(biāo)準(zhǔn)元素左邊子數(shù)組中的元素均小于標(biāo)準(zhǔn)元素，位于標(biāo)準(zhǔn)元素右邊子數(shù)組中的元素均大于等于或標(biāo)準(zhǔn)元素。對(duì)這兩個(gè)子數(shù)組中的元素分別再進(jìn)行方法類同的遞歸快速排序。算法的遞歸出口條件是low≥high。 例、關(guān)鍵字序列 T=(60，55，48，37，10，90，84，36），請(qǐng)按從小到大的順序，寫(xiě)出快速排序的具體實(shí)現(xiàn)過(guò)程。 快速排序算法各次快速排序過(guò)程 3、快速排序算法 public static void quickSort(int[] a, int low, int high){ int i, j; int temp; i = lo

65、w; j = high; temp = a[low]; //取第一個(gè)元素為標(biāo)準(zhǔn)數(shù)據(jù)元素 while(i < j){ //在數(shù)組的右端掃描 while(i < j && temp <= a[j]) j--; if(i < j){ a[i] = a[j]; i++; } //在數(shù)組的左端掃描 while(i < j && a[

66、i] < temp) i++; if(i < j){ a[j] = a[i]; j--; } } a[i] = temp; if(low < i) quickSort(a, low, i-1); //對(duì)左端子集合遞歸 if(i < high) quickSort(a, j+1, high); //對(duì)右端子集合遞歸 } 4、快速排序算法分析： 時(shí)間效率：一般情況下時(shí)間復(fù)雜度為O(nlog2n)，最壞情況是數(shù)據(jù)元素已全部正序或反序有序，此時(shí)每次標(biāo)準(zhǔn)元素都把當(dāng)前數(shù)組分成一個(gè)大小比當(dāng)前數(shù)組小1的子