《數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)》知識(shí)點(diǎn)概括

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

1、精選優(yōu)質(zhì)文檔-----傾情為你奉上 數(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)

2、算。 ·對(duì)數(shù)據(jù)的操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。 　　·常用的有：檢索、插入、刪除、更新、排序。 數(shù)據(jù)類(lèi)型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱(chēng)。 　　·結(jié)構(gòu)類(lèi)型：由用戶借助于描述機(jī)制定義，是導(dǎo)出類(lèi)型。 　 抽象數(shù)據(jù)類(lèi)型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à)算法的好壞的因素：·算法是正

3、確的； 　　·執(zhí)行算法的時(shí)間； ·執(zhí)行算法的存儲(chǔ)空間（主要是輔助存儲(chǔ)空間）； ·算法易于理解、編碼、調(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）、

4、指數(shù)階O（2^n）。 　　空間復(fù)雜度：是某個(gè)算法的空間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。 　　算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱(chēng)算法復(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） 　　順序表是按線

5、性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲(chǔ)單元中。在存儲(chǔ)單元中的各元素的物理位置和 邏輯結(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è)單鏈表由頭

6、指針的名字來(lái)命名。 單鏈表運(yùn)算： ·建立單鏈表·頭插法：s->next=head；head=s；生成的順序與輸入順序相反。平均時(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-

7、>next=s；平均時(shí)間復(fù)雜度均為O（n） ·刪除運(yùn)算：p=GetNode（L，i-1）；r=p->next；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惟一確定。 　　雙鏈表也可以頭尾相

8、鏈接構(gòu)成雙（向）循環(huán)鏈表。 　　雙鏈表上的插入和刪除時(shí)間復(fù)雜度均為O （1）。 　　順序表和鏈表的比較：　　·基于空間： 　　 ·順序表的存儲(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)算的線性表，稱(chēng)插

9、入、刪除這一端為棧頂，另一端稱(chēng)為棧底。表中無(wú)元素時(shí)為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的，我們又稱(chēng)棧為L(zhǎng)IFO表（Last 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)作為控

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

11、和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。 隊(duì)列的基本運(yùn)算有六種：　　·置空隊(duì)：InitQueue（Q） 　·判隊(duì)空：QueueEmpty（Q） 　·判隊(duì)滿：QueueFull（Q） 　·入隊(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ì)列稱(chēng)循環(huán)隊(duì)列。 判定循環(huán)隊(duì)列是空還是滿，方法有三種： ·一種是另設(shè)一個(gè)布爾變量來(lái)判斷； ·

12、第二種是少用一個(gè)元素空間，入隊(duì)時(shí)先測(cè)試（（rear+1）%m = front）？ 滿：空； 　　·第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為鏈隊(duì)列，一個(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)）。 　　·空白串：

13、指串中包含一個(gè)或多個(gè)空格字符的串。 　　·在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱(chēng)為該串的子串，包含子串的串就稱(chēng)為主串。 　　·子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置。 　　·空串是任意串的子串，任意串是自身的子串。 　　串分為兩種： ·串常量在程序中只能引用不能改變； 　　·串變量的值可以改變。 　　串的基本運(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（ch

14、ar*s，charc） 　串是特殊的線性表（結(jié)點(diǎn)是字符），所以串的存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類(lèi)似。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為順序串。 　順序串又可按存儲(chǔ)分配的不同分為： ·靜態(tài)存儲(chǔ)分配：直接用定長(zhǎng)的字符數(shù)組來(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)稱(chēng)為鏈串。鏈串與單鏈表的差異只是它的 結(jié) 點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。 為了解決“存儲(chǔ)密度”低的狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)的大小。 　　順序串上子串定位的運(yùn)算

15、：又稱(chēng)串的“模式匹配”或“串匹配”，是在主串中查找出子串出現(xiàn)的位置。在串匹配中，將主串稱(chēng)為目標(biāo)（串），子串稱(chēng)為模式（串）。這是比較容易理解的，串匹配問(wèn)題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時(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ì)算方法：

16、·按行優(yōu)先順序排列的數(shù)組：LOCa（ij）=LOCa（11）+（（i-1）*n+（j-1））*d. 　　·按列優(yōu)先順序排列的數(shù)組：LOCa（ij）=LOCa（11）+（（j-1）*n+（i-1））*d. 矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。 　　特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。 　　稀疏矩陣的概念：一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則該矩陣稱(chēng)為稀疏矩陣。 　　 特殊矩陣的類(lèi)型： ·對(duì)稱(chēng)矩陣：滿足a（ij）=a（ji）。元素總數(shù)n（n+1）/2.I=ma

17、x（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*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ǔ)功能。加入行表記

18、錄每行的非零元素在三元組表中的 起始位置，即帶行表的三元組表。 第六章 樹(shù) 　　樹(shù)是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有一個(gè)稱(chēng)為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱(chēng) 根的子樹(shù)。 　　根是開(kāi)始結(jié)點(diǎn)；結(jié)點(diǎn)的子樹(shù)數(shù)稱(chēng)度；度為0的結(jié)點(diǎn)稱(chēng)葉子（終端結(jié)點(diǎn)）；度不為0的結(jié)點(diǎn)稱(chēng)分支結(jié)點(diǎn)（非終端結(jié) 點(diǎn)）；除根外的分支結(jié)點(diǎn)稱(chēng)內(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è)

19、根結(jié)點(diǎn)及兩棵互不相交的分別稱(chēng)作這個(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的二叉樹(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ù)的所

20、有結(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類(lèi)型的結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)的BinTree型頭指針就構(gòu)成了二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱(chēng)為二叉鏈表。它就是由根指針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)的指針，

21、這些附加的指針就稱(chēng)為“線索”，加上線索的二叉鏈表就稱(chēng)為線索鏈表。線索使得查找中序前趨和中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié) 點(diǎn)的前序前趨和后序后繼并沒(méi)有什么作用。 樹(shù)和森林及二叉樹(shù)的轉(zhuǎn)換是唯一對(duì)應(yīng)的。 轉(zhuǎn)換方法： ·樹(shù)變二叉樹(shù)：兄弟相連，保留長(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，并

22、將data | firstchild存放在一個(gè)向量中。 　·雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。 　·孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的 指針域。 　　樹(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ù)就稱(chēng)為最優(yōu)二叉樹(shù) （即哈夫曼樹(shù)）。 　　在葉子的權(quán)值相同的二叉樹(shù)中，完全二叉樹(shù)的路徑長(zhǎng)度最短。 　　哈夫曼樹(shù)有n個(gè)葉結(jié)點(diǎn)，共有2n-1個(gè)結(jié)點(diǎn)，

23、沒(méi)有度為1的結(jié)點(diǎn)，這類(lèi)樹(shù)又稱(chēng)為嚴(yán)格二叉樹(shù)。 　　變長(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長(zhǎng)，但是變長(zhǎng)編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個(gè)碼無(wú)法在解碼時(shí)確定是哪一個(gè)，所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的 前綴，這種碼稱(chēng)為前綴碼（其實(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)特征就是

24、其結(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)有方向。 有向完全圖：具有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ú)向圖：鄰接矩陣

25、是對(duì)稱(chēng)的。 　　·有向圖：行是出度，列是入度。 建立鄰接矩陣算法的時(shí)間是O（n+n^2+e），其時(shí)間復(fù)雜度為O（n^2） 　　·鄰接表表示法：用頂點(diǎn)表和鄰接表構(gòu)成不是唯一的，適合稀疏圖。 ·頂點(diǎn)表結(jié)構(gòu) vertex | firstedge，指針域存放鄰接表頭指針。 ·鄰接表：用頭指針確定。 ·無(wú)向圖稱(chēng)邊表； ·有向圖又分出邊表和逆鄰接表； ·鄰接表結(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ì)列保

26、存已訪問(wèn)結(jié)點(diǎn)。 　　生成樹(shù)的定義：若從圖的某個(gè)頂點(diǎn)出發(fā)，可以系統(tǒng)地訪問(wèn)到圖中所有頂點(diǎn)，則遍歷時(shí)經(jīng)過(guò)的邊和圖的所有頂點(diǎn) 構(gòu)成的子圖稱(chēng)作該圖的生成樹(shù)。 　　最小生成樹(shù)：圖的生成樹(shù)不唯一，從不同的頂點(diǎn)出發(fā)可得到不同的生成樹(shù)，把權(quán)值最小的生成樹(shù)稱(chēng)為最小生成樹(shù) （MST）。 　　構(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）?！ゎ?lèi)似于prim算法。 　　拓?fù)渑判颍菏菍⒂邢驘o(wú)環(huán)圖G中所有頂點(diǎn)排成一

27、個(gè)線性序列，若∈E（G），則在線性序列u在v之前， 這種線性序列稱(chēng)為拓?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)及其入邊，最后得到的序列是逆拓?fù)湫蛄小? 第八章 排序 　　記錄中可用某一項(xiàng)來(lái)標(biāo)識(shí)一個(gè)記錄，則稱(chēng)為關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱(chē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)

28、過(guò)排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，則稱(chēng)這種排序方法是穩(wěn)定的，否則排序算法是不穩(wěn)定的。 　　排序過(guò)程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱(chēng)之為“內(nèi)部排序”（內(nèi)排序），反之，若存在數(shù)據(jù)的內(nèi)外存交換，則稱(chēng)之為外排序。 內(nèi)部排序方法可分五類(lèi)：插入排序、選擇排序、交換排序、歸并排序和分配排序。 　　評(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是否越界。 　　·直接

29、插入排序是就地的穩(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^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； 　　·快速排序：

30、·以第一個(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ù)為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），不適

31、宜于記錄數(shù)較少的文件。 　　歸并排序： ·先兩個(gè)一組排序，形成（n+1）/2組，再將兩組并一組，直到剩下一組為止。 　　·歸并排序是非就地穩(wěn)定排序，時(shí)間復(fù)雜度是O（nlog2n）， 　　分配排序：·箱排序： ·按關(guān)鍵字的取值范圍確定箱子數(shù)，按關(guān)鍵字投入箱子，鏈接所有非空箱。 　　·箱排序的平均時(shí)間復(fù)雜度是線性的O（n）。 　·基數(shù)排序：·從低位到高位依次對(duì)關(guān)鍵字進(jìn)行箱排序。 ·基數(shù)排序是非就穩(wěn)定的排序，時(shí)間復(fù)雜度是O（d*n+d*rd）。 　　各種排序方法的比較和選擇： ·待排序的記錄數(shù)目n；n較大的要用時(shí)間復(fù)雜度為O（nlog2n）的排序方法； 　　·記錄的大?。ㄒ?guī)模）；記錄

32、大最好用鏈表作為存儲(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)的表稱(chēng)之為動(dòng)態(tài)查找表，否則稱(chēng)之為靜態(tài)查找表。 　　衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)（即平均查找長(zhǎng)度ASL）。 　　線性表查找的方法： ·順序查找：逐個(gè)查找，ASL=（n+1）/2； 　　·二分查找：取中點(diǎn)int（n/2）比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹(shù)表示。ASL=（∑（每

33、層結(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ù)。 　　二叉排序樹(shù)的插入、建立、刪除的算法平均時(shí)間性能是O（nlog2n）。 　二叉排序樹(shù)的刪除操作可分三種情況進(jìn)行處理： ·*P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可。

34、 　·*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ò)程稱(chēng)為散列。散列函數(shù)的選擇有兩條標(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

35、（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)放定址法類(lèi)型： ·線性探查法：address=（hash（x）+i）%m； ·二次探查法：address=（hash（x）+i^2）%m； 　　 ·雙重散列法：address=（hash（x）+i*hash（y））%m； 　　 ·拉鏈法： ·是將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。 　　 ·拉鏈法的優(yōu)點(diǎn)：

36、·拉鏈法處理沖突簡(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.3 選擇排序 10.4 交換排序 本章主要知識(shí)點(diǎn)： 排序的基本概念和衡量排序算法優(yōu)劣的標(biāo)準(zhǔn)，其中衡量標(biāo)準(zhǔn)有算法的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性 直接插入排序

37、，希爾排序 直接選擇排序，堆排序 冒泡排序，快速排序 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)鍵字稱(chēng)為主關(guān)鍵字。不滿足主關(guān)鍵字定義的關(guān)鍵字稱(chēng)為次關(guān)鍵字。 4.排序的種類(lèi)：分為內(nèi)部排序和外部排序兩大類(lèi)。 若待排序記錄都在內(nèi)存中，稱(chēng)為內(nèi)部排序；若待排序記錄一部分在內(nèi)存，一部分在外存，則稱(chēng)為外部排序。

38、 注：外部排序時(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的先后次序保持不變，則稱(chēng)這種排序算法是穩(wěn)定的。 10.2 插入排序 插入排序的基本思想是：每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。 簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排

39、好序的。 常用的插入排序有：直接插入排序和希爾排序兩種。 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 第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11 第三次排序：

40、 【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) [ ]中為已排序記錄的關(guān)鍵字，下劃?rùn)M線的 關(guān)鍵字 表示它對(duì)應(yīng)的記錄后移一個(gè)位置。 2.直接插入排序算法 public static void insertSort(int[]

41、 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 + 1] = temp; } } 初始關(guān)鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序： 【6, 13】, 3, 3

42、1, 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 希爾（shell）排序 （又稱(chēng)縮小增量排序） 1、基本思想：把整個(gè)待排序的數(shù)據(jù)元素分成若干個(gè)小組，對(duì)同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個(gè)數(shù)逐次縮小，當(dāng)完成了

43、所有數(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，56，46，14，77，92，23），請(qǐng)寫(xiě)出希爾排序的具體實(shí)現(xiàn)過(guò)程。 public static void shellSort(int[] a, int[] d, int

44、 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 + span){ temp = a[i+span]; j = i; while(j > -1 && temp < a[j]){

45、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) 空間效率：O（1）——因?yàn)閮H占用1個(gè)緩沖單元 算法的穩(wěn)定性：不穩(wěn)定 練習(xí)： 1. 欲將序列（Q, H, C, Y, P, A, M,

46、 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í)，關(guān)鍵字序列的狀態(tài)。 解：原始序列: 256，301，751，129，937，863，742，694，076，438 希爾排序第一趟d=5 256 301 69

47、4 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)鍵字最小（或最大）的數(shù)據(jù)元素放到數(shù)據(jù)元素集合的最前（或最后），數(shù)據(jù)元素集合不斷縮小，當(dāng)數(shù)據(jù)元素集合為空時(shí)選擇排序結(jié)束。 常用的選擇排序算法： （1）直接選擇排序

48、（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í)現(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ò)程。 原始

49、序列： 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, j, small; int temp; int n = a.Length; for(i = 0; i < n - 1; i ++){ small

50、 = 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]; a[i] = a[small]; a[small] = temp; } } } 3、算法分析 時(shí)間效率： O(n2)

51、——雖移動(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，49 ，25 * 第3趟08，16, 21，25，49 ，25 * 第4趟08，16, 21，25，49 ，25 * 第5趟08，16, 21，25，2

52、5 * ，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] < a[small]) small = j; //記住最小元素的下標(biāo) } if(small != i){ temp = a[small

53、]; 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，…，kn-1，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱(chēng)之為堆。 解釋?zhuān)喝绻対M足以上條件的元素序列 （k０，k１，…，kn－１）順次排成一棵完全二叉樹(shù)，則此樹(shù)的特點(diǎn)是： 樹(shù)

54、中所有結(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= (21，25，49，25*，16，08），請(qǐng)建最大堆。 解：為便于理解，先將原始序列畫(huà)成完全二叉樹(shù)的形式： 這樣可以很清晰地從(n-1-1)/2開(kāi)始調(diào)整。

55、 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 && flag != 1){ //尋找左右孩子結(jié)點(diǎn)中的較大者,j為其下標(biāo) if(j < n - 1 && a[j] < a[j + 1]) j++; if (t

56、emp >= 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)始，到根結(jié)點(diǎn)a[0]為止，循環(huán)調(diào)用createHeap（a,n,h）的過(guò)程。 初始化創(chuàng)建最大堆算法如下： public static void initCreateH

57、eap(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ì)象，使用堆的調(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è)

58、對(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]元素和當(dāng)前最大堆的最后一個(gè)元素交換 temp = a[0]; a[0] = a[i]; a[i] = temp; createHeap(a,i,

59、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. {75,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,

60、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 交換排序 交換排序的基本思想是：利用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法。 交換排序的主要算法有： 1) 冒泡排序 2) 快速排序

61、 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，25*，16， 08 ， 49 第2趟21，25， 16， 08 ，25*，49 第3趟21，16， 08 ，25， 25*，49 第4趟16，08 ，21， 25，

62、 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++){ if(a[j] > a[j+1]){ flag = 1; temp = a[j]; a[j] = a[j+1];

63、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)按從小到大的順序，寫(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

64、 第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ù)組中的元素以標(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)

65、行方法類(lèi)同的遞歸快速排序。算法的遞歸出口條件是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 = low; j = high; temp = a[low]; //取第一個(gè)元素為標(biāo)準(zhǔn)數(shù)據(jù)元素 while(i < j){

66、 //在數(shù)組的右端掃描 while(i < j && temp <= a[j]) j--; if(i < j){ a[i] = a[j]; i++; } //在數(shù)組的左端掃描 while(i < j && a[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)元素都把