非常實(shí)用的數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)

1、數(shù)據(jù)結(jié)構(gòu)學(xué)問點(diǎn)概括 第一章 概 論 數(shù)據(jù)就是指能夠被運(yùn)算機(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)的定義： 規(guī)律結(jié)構(gòu)：從規(guī)律結(jié)構(gòu)上描述數(shù)據(jù),獨(dú)立于運(yùn)算機(jī)； 線性結(jié)構(gòu)：一對(duì)一關(guān)系； 線性結(jié)構(gòu)：多對(duì)多關(guān)系； 儲(chǔ)備結(jié)構(gòu)：是規(guī)律結(jié)構(gòu)用運(yùn)算機(jī)語言的實(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ù)的操作；定義在規(guī)律結(jié)構(gòu)上,每種規(guī)律結(jié)構(gòu)都有一個(gè)運(yùn)算集合； 常用的有：檢索、插入、刪除、更新、排

2、序；數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱； 結(jié)構(gòu)類型：由用戶借助于描述機(jī)制定義,是導(dǎo)出類型；抽象數(shù)據(jù)類型 ADT： 是抽象數(shù)據(jù)的組織和與之的操作；相當(dāng)于在概念層上描述問題； 優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱匿；程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問題挑選一種好的數(shù)據(jù)結(jié)構(gòu),設(shè)計(jì)一個(gè)好的算法；算法取決于數(shù)據(jù)結(jié)構(gòu)；算法是一個(gè)良定義的運(yùn)算過程,以一個(gè)或多個(gè)值輸入,并以一個(gè)或多個(gè)值輸出；評(píng)判算法的好壞的因素： 算法是正確的； 執(zhí)行算法的時(shí)間； 執(zhí)行算法的儲(chǔ)備空間（主要是幫忙儲(chǔ)備空間）； 算法易于懂得、編碼、調(diào)試；時(shí)間復(fù)雜度：是某個(gè)算法的時(shí)間耗費(fèi),它是該算法所求解問題規(guī)模 n 的函數(shù)；漸近

3、時(shí)間復(fù)雜度：是指當(dāng)問題規(guī)模趨向無窮大時(shí),該算法時(shí)間復(fù)雜度的數(shù)量級(jí)；評(píng)判一個(gè)算法的時(shí)間性能時(shí),主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度；算法中語句的頻度不僅與問題規(guī)模有關(guān),仍與輸入實(shí)例中各元素的取值相關(guān)；時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O（1）、對(duì)數(shù)階 O（log2n ）、線性階 O（n）、線性對(duì)數(shù)階O（nlog2n ）、平方階 O（n2 ）、立方階 O（n3 ）、 k 次方階 O（nk ）、指數(shù)階 O（2n ）；空間復(fù)雜度：是某個(gè)算法的空間耗費(fèi),它是該算法所求解問題規(guī)模 n 的函數(shù)；1算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度；其次章 線性表 線性表是由 n0 個(gè)數(shù)據(jù)元素組成的有限序列；n=0

4、 是空表；非空表,只能有一個(gè)開頭結(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）次序表是按線性表的規(guī)律結(jié)構(gòu)次序依次存放在一組地址連續(xù)的儲(chǔ)備單元中；在儲(chǔ)備單元中的各元素的物理位置和規(guī)律結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系是一樣的；地址運(yùn)算：在次序表中實(shí)現(xiàn)的基本運(yùn)算：LOCa（i）=LOCa （1）+ （i-1 ）*d ；（首地址為 1） 插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為 n/2 ；平均時(shí)間復(fù)雜

5、度均為 O（n）； 刪除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為（ n-1 ）/2 ；平均時(shí)間復(fù)雜度均為 O（n）；線性表的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)中結(jié)點(diǎn)的規(guī)律次序和物理次序不愿定相同,為了能正確表示結(jié)點(diǎn)間的規(guī)律關(guān)系,在儲(chǔ)備每個(gè)結(jié)點(diǎn)值的同時(shí),仍儲(chǔ)備了其后繼結(jié)點(diǎn)的地址信息（即指針或鏈）一個(gè)單鏈表由頭指針的名字來命名；單鏈表運(yùn)算：；這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)； 建立單鏈表 頭插法：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（

6、n） 加頭結(jié)點(diǎn)的算法：對(duì)開頭結(jié)點(diǎn)的操作無需特殊處理,統(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；p-next=r-next；free （r）；平均時(shí)間復(fù)雜度均為 O（n）單循環(huán)鏈表是一種首尾相接的單鏈表,終端結(jié)點(diǎn)的指針域指向開頭結(jié)點(diǎn)或頭結(jié)點(diǎn)；鏈表終止條件是以指針等于頭指針或尾指針；接受單循環(huán)鏈表在有用中多接受尾指針表

7、示單循環(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）；次序表和鏈表的比較： 基于空間： 次序表的儲(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í),宜接受； 以插入和刪除操作為主的線性表宜接受鏈

8、表做儲(chǔ)備結(jié)構(gòu)； 如插入和刪除主要發(fā)生在表的首尾兩端,就宜接受尾指針表示的單循環(huán)鏈表；第三章 棧和隊(duì)列 棧（Stack ）是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表,稱插入、刪除這一端為棧頂,另一端稱為棧底；表中無元素時(shí)為空棧；棧的修改是按后進(jìn)先出的原就進(jìn)行的,我們又稱棧為L(zhǎng)IFO 表（Last In First Out）；通常棧有次序棧和鏈棧兩種儲(chǔ)備結(jié)構(gòu)；棧的基本運(yùn)算有六種： 構(gòu)造空棧：InitStack （S） 判?？眨篠tackEmpty （S） 判棧滿：StackFull （S） 進(jìn)棧：Push （S,x） 退棧：Pop （S） 取棧頂元素：StackTop （S）在次序棧中有“ 上溢

9、” 和“ 下溢” 的現(xiàn)象；“ 上溢” 是棧頂指針指出棧的外面是出錯(cuò)狀態(tài)；“ 下溢” 可以表示棧為空棧,因此用來作為把握轉(zhuǎn)移的條件；次序棧中的基本操作有六種： 構(gòu)造空棧 判?？?判棧滿 進(jìn)棧 退棧 取棧頂元素 鏈棧就沒有上溢的限制,因此進(jìn)棧不要判棧滿；鏈棧不需要在頭部附加頭結(jié)點(diǎn),只要有鏈表的頭指針就可以了；鏈棧中的基本操作有五種： 構(gòu)造空棧 判棧空 進(jìn)棧 退棧 取棧頂元素 隊(duì)列（ Queue ）是一種運(yùn)算受限的線性表,插入在表的一端進(jìn)行,而刪除在表的另一端進(jìn)行,答應(yīng)刪除的一端稱為隊(duì)頭（ front ）,答應(yīng)插入的一端稱為隊(duì)尾（rear ） ,隊(duì)列的操作原就是先進(jìn)先出的,又稱作FIFO 表（ Fi

10、rst In First Out ） . 隊(duì)列也有次序儲(chǔ)備和鏈?zhǔn)絻?chǔ)備兩種儲(chǔ)備結(jié)構(gòu)；隊(duì)列的基本運(yùn)算有六種： 置空隊(duì)：InitQueue （Q） 判隊(duì)空：QueueEmpty（Q） 判隊(duì)滿：QueueFull （Q）3 入隊(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è)布爾變

11、量來判定； 其次種是少用一個(gè)元素空間,入隊(duì)時(shí)先測(cè)試（rear+1 ）%m = front）？ 滿：空； 第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)；隊(duì)列的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)稱為鏈隊(duì)列,一個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表；為了便于在表尾進(jìn)行插入（入隊(duì)）的 操作,在表尾增加一個(gè)尾指針,一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針唯獨(dú)地確定；鏈隊(duì)列不存在隊(duì)滿和上溢 的問題；在鏈隊(duì)列的出隊(duì)算法中,要留意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí),出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空；第四章 串 串是零個(gè)或多個(gè)字符組成的有限序列； 空串：是指長(zhǎng)度為零的串,也就是串中不包含任何字符（結(jié)點(diǎn)） ； 空白串：指串中包含一個(gè)或多個(gè)空格字符的串；

12、 在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串,包含子串的串就稱為主串； 子串在主串中的序號(hào)就是指子串在主串中首次顯現(xiàn)的位置； 空串是任意串的子串,任意串是自身的子串；串分為兩種： 串常量在程序中只能引用不能轉(zhuǎn)變； 串變量的值可以轉(zhuǎ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 （char*s ,charc ）串是特殊的線性表（結(jié)點(diǎn)是字符） ,所以串的儲(chǔ)備結(jié)構(gòu)與線性表

13、的儲(chǔ)備結(jié)構(gòu)類似；串的次序儲(chǔ)備結(jié)構(gòu)簡(jiǎn)稱為次序串；次序串又可按儲(chǔ)備支配的不同分為： 靜態(tài)儲(chǔ)備支配：直接用定長(zhǎng)的字符數(shù)組來定義；優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度快,但不適合插入、鏈接操作； 動(dòng)態(tài)儲(chǔ)備支配：是在定義串時(shí)擔(dān)憂排儲(chǔ)備空間,需要使用時(shí)按所需串的長(zhǎng)度支配儲(chǔ)備單元；4串的鏈?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)（串）,子串稱為模式

14、（串）；這是比較簡(jiǎn)潔懂得的,串匹配問題就是找出給定模式串 P 在給定目標(biāo)串 T 中首次顯現(xiàn)的有效位移或者是全 部有效位移；最壞的情形下時(shí)間復(fù)雜度是 O（n-m+1 ）m ）,假如 m 與 n 同階 的話就它是 O（n2 ）；鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址而不是整數(shù)第五章 多維數(shù)組 數(shù)組一般用次序儲(chǔ)備的方式表示；儲(chǔ)備的方式有： 行優(yōu)先次序,也就是把數(shù)組逐行依次排列； PASCAL、C 列優(yōu)先次序,就是把數(shù)組逐列依次排列； FORTRAN 地址的運(yùn)算方法： 按行優(yōu)先次序排列的數(shù)組：LOCa（ij ）=LOCa （11）+ （i-1 ）*n+ （j-1 ）*d. 按列優(yōu)先次序排列的數(shù)組：LOCa

15、（ij ）=LOCa （11）+ （j-1 ）*n+ （i-1 ）*d. 矩陣的壓縮儲(chǔ)備：為多個(gè)相同的非零元素支配一個(gè)儲(chǔ)備空間；對(duì)零元素?fù)?dān)憂排空間；特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有確定規(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（sa0 ）+ （I* （I+1 ）/2+J ）*d. 三角矩陣： 上三角陣：k=i* （2n-i+1 ）/2+j-i ,LOCa

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

17、；度為 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)；有序樹是子樹有左,右之分的樹；無序樹是子樹沒有左,右之分的樹；森林是m 個(gè)互不相交的樹的集合；樹的四種不同表示方法： 樹形表示法； 嵌套集合表示法； 凹入表示法 廣義表表示法；二叉樹的定義：是 n0 個(gè)結(jié)點(diǎn)的有限集,它是空集（n=0 ）或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成；二叉樹不是樹的特殊情形,與度數(shù)為 2 的有序樹不同；二叉樹的 4 個(gè)重要性質(zhì)： 二叉樹上第i 層上的結(jié)點(diǎn)數(shù)目最多為 2 （i-1 ）（i1）； 深度為k 的二叉樹至多有（ 2k

18、）-1 個(gè)結(jié)點(diǎn)（ k1）； 在任意一棵二叉樹中,如終端結(jié)點(diǎn)的個(gè)數(shù)為 n0 ,度為 2 的結(jié)點(diǎn)數(shù)為 n2,就 n0=n2+1； 具有n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 int （log2n ）+1. 滿二叉樹是一棵深度為 k,結(jié)點(diǎn)數(shù)為（ 2k ）-1 的二叉樹；完全二叉樹是滿二叉樹在最下層自右向左去處部分結(jié)點(diǎn)；二叉樹的次序儲(chǔ)備結(jié)構(gòu)就是把二叉樹的全部結(jié)點(diǎn)依據(jù)層次次序儲(chǔ)備到連續(xù)的儲(chǔ)備單元中；二叉樹）（儲(chǔ)備前先將其畫成完全樹的儲(chǔ)備結(jié)構(gòu)多用的是鏈?zhǔn)絻?chǔ)備；BinTNode的結(jié)構(gòu)為 lchild|data|rchild,把全部 BinTNode類型的結(jié)點(diǎn),加上一個(gè)指向根結(jié)點(diǎn)的BinTree 型頭指針就構(gòu)成了二叉

19、樹的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu),稱為二叉鏈表；它就是由根指針 共有 2n 個(gè)指針域, n+1 個(gè)空指針；root 唯獨(dú)確定的；依據(jù)拜望結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷（前序遍歷或先根遍歷）,中序遍歷（或中根遍歷） 、后序遍歷（或 后根遍歷）；時(shí)間復(fù)雜度為 O（n）；利用二叉鏈表中的 n+1 個(gè)空指針域來存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針,這些附加的指針就稱為“ 線索”,加上線 索的二叉鏈表就稱為線索鏈表；線索使得查找中序前趨和中序后繼變得簡(jiǎn)潔有效,但對(duì)于查找指定結(jié) 點(diǎn)的前序前趨和后序后繼并沒有什么作用；樹和森林及二叉樹的轉(zhuǎn)換是唯獨(dú)對(duì)應(yīng)的；轉(zhuǎn)換方法： 樹變二叉樹：兄弟相連,保留長(zhǎng)子的連線；

20、二叉樹變樹：結(jié)點(diǎn)的右孩子與其雙親連； 森林變二叉樹：樹變二叉樹,各個(gè)樹的根相連；樹的儲(chǔ)備結(jié)構(gòu)： 有雙親鏈表表示法：結(jié)點(diǎn) data | parent 點(diǎn)的孩子及后代；,對(duì)于求指定結(jié)點(diǎn)的雙親或祖先特殊便利,但不適于求指定結(jié) 孩子鏈表表示法：為樹中每個(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)的最左孩子和右鄰兄弟的樹的前序遍歷與相對(duì)應(yīng)的二叉

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

22、地是在編碼技術(shù)上,它能夠簡(jiǎn)潔地求出給定字符集及其概率分布的最優(yōu)前綴碼；哈夫曼編碼的構(gòu)造很簡(jiǎn)潔,只要畫好了哈夫曼樹,按分支情形在左路徑上寫代碼0,右路徑上寫代碼1,然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼；第七章 圖圖的規(guī)律結(jié)構(gòu)特點(diǎn)就是其結(jié)點(diǎn)（頂點(diǎn)）的前趨和后繼的個(gè)數(shù)都是沒有限制的,即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)；圖 GraphG= （V,E）,V 是頂點(diǎn)的有窮非空集合,E 是頂點(diǎn)偶對(duì)的有窮集；有向圖 Digraph ：每條邊有方向；無向圖 Undigraph ：每條邊沒有方向；有向完全圖：具有 n* （n-1 ）條邊的有向圖；無向完全圖：具有 n* （n-1 ）/2

23、 條邊的無向圖；有根圖：有一個(gè)頂點(diǎn)有路徑到達(dá)其它頂點(diǎn)的有向圖；簡(jiǎn)潔路徑：是經(jīng)過頂點(diǎn)不同的路徑；簡(jiǎn)潔回路是開頭和終端重的簡(jiǎn)潔路徑；網(wǎng)絡(luò)：是帶權(quán)的圖；圖的儲(chǔ)備結(jié)構(gòu)： 鄰接矩陣表示法：用一個(gè) n 階方陣來表示圖的結(jié)構(gòu)是唯獨(dú)的,適合稠密圖； 無向圖：鄰接矩陣是對(duì)稱的； 有向圖：行是出度,列是入度；建立鄰接矩陣算法的時(shí)間是O（n+n2+e）,其時(shí)間復(fù)雜度為O（n2 ） 鄰接表表示法：用頂點(diǎn)表和鄰接表構(gòu)成不是唯獨(dú)的,適合稀疏圖； 頂點(diǎn)表結(jié)構(gòu)vertex | firstedge,指針域存放鄰接表頭指針； 鄰接表：用頭指針確定； 無向圖稱邊表； 有向圖又分出邊表和逆鄰接表； 鄰接表結(jié)點(diǎn)結(jié)構(gòu)為 adjvex |

24、 next,時(shí)間復(fù)雜度為 O（n+e ）；,空間復(fù)雜度為 O（n+e ）；圖的遍歷： 深度優(yōu)先遍歷：借助于鄰接矩陣的列；使用棧儲(chǔ)存已拜望結(jié)點(diǎn)； 廣度優(yōu)先遍歷：借助于鄰接矩陣的行；使用隊(duì)列儲(chǔ)存已拜望結(jié)點(diǎn)；生成樹的定義：如從圖的某個(gè)頂點(diǎn)動(dòng)身,可以系統(tǒng)地拜望到圖中全部頂點(diǎn),就遍歷時(shí)經(jīng)過的邊和圖的全部頂點(diǎn)構(gòu)成的子圖稱作該圖的生成樹；7最小生成樹：圖的生成樹不唯獨(dú),從不同的頂點(diǎn)動(dòng)身可得到不同的生成樹,把權(quán)值最小的生成樹稱為最小生成樹（MST ）；構(gòu)造最小生成樹的算法：Prim 算法的時(shí)間復(fù)雜度為 O（n2 ）與邊數(shù)無關(guān)適于稠密圖；Kruskal 算法的時(shí)間復(fù)雜度為 O（lge ）,主要取決于邊數(shù),較適合

25、于稀疏圖；最短路徑的算法：Dijkstra 算法,時(shí)間復(fù)雜度為 O （n2 ）； 類似于prim 算法；拓?fù)渑判颍菏菍⒂邢驘o環(huán)圖 G 中全部頂點(diǎn)排成一個(gè)線性序列,如 E（G）,就在線性序列 u 在 v 之前,這種線性序列稱為拓?fù)湫蛄校煌負(fù)渑判蛞灿袃煞N方法： 無前趨的頂點(diǎn)優(yōu)先,每次輸出一個(gè)無前趨的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其出邊,最終得到的序列即拓?fù)湫蛄校?無后繼的結(jié)點(diǎn)優(yōu)先：每次輸出一個(gè)無后繼的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其入邊,最終得到的序列是逆拓?fù)湫蛄?；第八?排序記錄中可用某一項(xiàng)來標(biāo)識(shí)一個(gè)記錄,就稱為關(guān)鍵字項(xiàng),該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字；排序是使文件中的記錄按關(guān)鍵字遞增（或遞減）次序排列起來； 基本操作：比較關(guān)

26、鍵字大小；轉(zhuǎn)變指向記錄的指針或移動(dòng)記錄； 儲(chǔ)備結(jié)構(gòu)：次序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)；經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變,就稱這種排序方法是穩(wěn)固的,否就排序算法是不穩(wěn)固的；排序過程中不涉及數(shù)據(jù)的內(nèi)、外存交換就稱之為“ 內(nèi)部排序”（內(nèi)排序）,反之,如存在數(shù)據(jù)的內(nèi)外存交換,就稱之為外排序；內(nèi)部排序方法可分五類：插入排序、挑選排序、交換排序、歸并排序和支配排序；評(píng)判排序算法好壞的標(biāo)準(zhǔn)主要有兩條：執(zhí)行時(shí)間和所需的幫忙空間,另外算法的復(fù)雜程序也是要考慮的一個(gè)因素；插入排序： 直接插入排序： 逐個(gè)向前插入到合適位置； 哨兵（監(jiān)視哨）有兩個(gè)作用： 作為臨變量存放Ri 是在查找循環(huán)中用來監(jiān)視

27、下標(biāo)變量 j 是否越界； 直接插入排序是就地的穩(wěn)固排序；時(shí)間復(fù)雜度為O（n2 ）,比較次數(shù)為（ n+2 ）（n-1 ）/2 ；移動(dòng)次數(shù)為（ n+4 ）（n-1 ）/2 ； 希爾排序： 等間隔的數(shù)據(jù)比較并按要求次序排列,最終間隔為 1. 希爾排序是就地的不穩(wěn)固排序；時(shí)間復(fù)雜度為 O（n1.25 ）,比較次數(shù)為（ n1.25 ）；移動(dòng)次數(shù)為（ 1.6n1.25）；交換排序： 冒泡排序： 自下向上確定最輕的一個(gè)； 自上向下確定最重的一個(gè)； 自下向上確定最輕的一個(gè),后自上向下確定最重的一個(gè)； 冒泡排序是就地的穩(wěn)固排序；時(shí)間復(fù)雜度為O（n2 ）,比較次數(shù)為 n（n-1 ）/2 ；移動(dòng)次數(shù)為 3n （n-

28、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（n2 ）；比較次數(shù)為 n（n-1 ）/2 ； 堆排序 建堆：按層次將數(shù)據(jù)填入完全二叉樹,從int （n/2 ）處向前逐個(gè)調(diào)整位置； 然后將樹根與最終一個(gè)葉子交換值并斷開與樹的連接并重建堆,直到全斷開； 堆排序是就地不穩(wěn)固的排序,時(shí)間復(fù)雜度為O（nlog2n ）,不相宜于記錄

29、數(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ī)模）；記錄大最好用鏈表作為儲(chǔ)備結(jié)構(gòu),而快速排序和堆排序在鏈表上難

30、于實(shí)現(xiàn)； 對(duì)穩(wěn)固性的要求； 關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)； 語言工具的條件； 儲(chǔ)備結(jié)構(gòu)； 時(shí)間和幫忙空間復(fù)雜度；第九章 查找 查找的同時(shí)對(duì)表做修改操作（如插入或刪除）就相應(yīng)的表稱之為動(dòng)態(tài)查找表,否就稱之為靜態(tài)查找表；衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)（即平均查找長(zhǎng)度 ASL）；線性表查找的方法： 次序查找：逐個(gè)查找,ASL= （n+1 ）/2 ；ASL= （每層結(jié)點(diǎn)數(shù) *層數(shù)）/N. 二分查找：取中點(diǎn)int （n/2 ）比較,如小就比左區(qū)間,大就比右區(qū)間；用二叉判定樹表示； 分塊查找；要求“ 分塊有序” ,將表分成如干塊內(nèi)部不愿定有序,并抽取各塊中的最大關(guān)鍵字及

31、其位置建立有序索引表；二叉排序樹（ BST）定義是：二叉排序樹是空樹或者中意如下性質(zhì)的二叉樹：根結(jié)點(diǎn)的值； 如它的右子樹非空,就右子樹上全部結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； 左、右子樹本身又是一棵二叉排序樹；二叉排序樹的插入、建立、刪除的算法平均時(shí)間性能是 O（nlog2n ）； 如它的左子樹非空,就左子樹上全部結(jié)點(diǎn)的值均小于二叉排序樹的刪除操作可分三種情形進(jìn)行處理：*P 是葉子,就直接刪除 *P,即將 *P 的雙親 *parent 中指向 *P 的指針域置空即可；*P 只有一個(gè)孩子 *child ,此時(shí)只需將 *child 和*p 的雙親直接連接就可刪去 *p. *p 有兩個(gè)孩子,就先將 *p 結(jié)

32、點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù)據(jù)到 *p ,刪除中序后繼結(jié)點(diǎn)；關(guān)于 B- 樹（多路平穩(wěn)查找樹） ；它適合在磁盤等直接存取設(shè)備上組織動(dòng)態(tài)的查找表,是一種外查找算法；建立的方式是從下向上拱起；散列技術(shù)：將結(jié)點(diǎn)按其關(guān)鍵字的散列地址儲(chǔ)備到散列表的過程稱為散列；散列函數(shù)的挑選有兩條標(biāo)準(zhǔn)：簡(jiǎn)潔和勻稱；常見的散列函數(shù)構(gòu)的造方法： 平方取中法：hash=int （x2 ）%100 ）9 除余法：表長(zhǎng)為m ,hash=x%m 相乘取整法：hash=int（m* （x*A-int （x*A）；A=0.618 隨機(jī)數(shù)法：hash=random（x）；處理沖突的方法： 開放定址法： 一般形式為hi= （h（key ）+di ）

33、%m1 im-1 ,開放定址法要求散列表的裝填因子 1. 開放定址法類型： 線性探查法：address= （hash （x）+i ）%m ； 二次探查法：address= （hash （x）+i2 ）%m ； 雙重散列法：address= （hash （x）+i*hash （y）%m ； 拉鏈法： 是將全部關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中； 拉鏈法的優(yōu)點(diǎn)： 拉鏈法處理沖突簡(jiǎn)潔,且無積存現(xiàn)象； 鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的適于無法確定表長(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í),用拉鏈法

34、中的指針域也要占用額外空間,仍是開放定址法省空間；第十章 排序 10.1 排序的基本概念 10.2 插入排序 10.3 挑選排序 10.4 交換排序 本章主要學(xué)問點(diǎn)：排序的基本概念和衡量排序算法優(yōu)劣的標(biāo)準(zhǔn),其中衡量標(biāo)準(zhǔn)有算法的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)固性 直接插入排序,希爾排序 直接挑選排序,堆排序 冒泡排序,快速排序 10.1 排序的基本概念 1.排序是對(duì)數(shù)據(jù)元素序列建立某種有序排列的過程；2.排序的目的：便于查找；3.關(guān)鍵字是要排序的數(shù)據(jù)元素集合中的一個(gè)域,排序是以關(guān)鍵字為基準(zhǔn)進(jìn)行的；關(guān)鍵字分主關(guān)鍵字和次關(guān)鍵字兩種； 對(duì)要排序的數(shù)據(jù)元素集合來說, 假如關(guān)鍵字中意數(shù)據(jù)元素值不同時(shí)該關(guān)鍵字的

35、值也確定不同,這樣的關(guān)鍵字稱為主關(guān)鍵字；不中意主關(guān)鍵字定義的關(guān)鍵字稱為次關(guān)鍵字；4.排序的種類：分為內(nèi)部排序和外部排序兩大類；如待排序記錄都在內(nèi)存中,稱為內(nèi)部排序；如待排序記錄一部分在內(nèi)存,一部分在外存,就稱為外部排序；10注：外部排序時(shí),要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序,中間結(jié)果仍要準(zhǔn)時(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 插入排序 插入排序的基本思想

36、是：每步將一個(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)寫出直接插入排序的中間過程序列；初始關(guān)鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序：【6, 13 】, 3, 31, 9, 27, 5, 11 關(guān)鍵字

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

38、 i, j, temp; int n = a.Length; fori = 0; i -1 & temp aj aj + 1 = aj; j -; aj + 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ù)雜度為On ；當(dāng)數(shù)據(jù)基本反序時(shí), 執(zhí)行效率最差, 此時(shí)的時(shí)間復(fù)雜度為On2 ；所以當(dāng)數(shù)據(jù)越接近有序,直接插入排序算法的性能越

39、好；2空間效率：僅占用 1 個(gè)緩沖單元 O （1）3算法的穩(wěn)固性：穩(wěn)固 8.2.2 希爾（ shell ）排序 （又稱縮小增量排序）1、基本思想：把整個(gè)待排序的數(shù)據(jù)元素分成如干個(gè)小組,對(duì)同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個(gè)數(shù)逐次縮小,當(dāng)完成了全部數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序后排序過程終止；隔某個(gè)增量 d 的記錄組成一個(gè)小組 ,讓增量 d 逐趟縮短（例如依次取2、技巧：小組的構(gòu)成不是簡(jiǎn)潔地“ 逐段分割” ,而是將相 5,3,1）,直到 d1 為止；3、優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移,且序列如基本有序時(shí),再用直接插入排序處理,時(shí)間效率會(huì)高許多；例 2：設(shè)待排序的序列中有12 個(gè)記錄,它

40、們的關(guān)鍵字序列T=65 ,34 ,25 ,87 ,12 ,38,56,46,14 ,77 ,92 ,23）,請(qǐng)寫出希爾排序的詳細(xì)實(shí)現(xiàn)過程；public static void shellSortint a, int d, int numOfD int i, j, k, m, span; int temp; int n = a.Length; form = 0; m numOfD; m + / 共 numOfD 次循環(huán)span = dm; / 取本次的增量值 fork = 0; k span; k + / 共 span 個(gè)小組 fori = k; i -1 & temp aj aj + span

41、 = aj; j = j - span; aj + span = temp; 算法分析：開頭時(shí) d 的值較大,子序列中的對(duì)象較少,排序速度較快；隨著排序進(jìn)展,于前面工作的基礎(chǔ),大多數(shù)記錄已基本有序,所以排序速度仍舊很快；時(shí)間效率： Onlog2n2 空間效率： O（1）由于僅占用 1 個(gè)緩沖單元 算法的穩(wěn)固性：不穩(wěn)固練習(xí)：d 值逐步變小,子序列中對(duì)象個(gè)數(shù)逐步變多,由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,

42、 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 ）為例,寫出執(zhí)行希爾排序（取 d=5,3,1 ）算法的各趟排序終止時(shí),關(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 93

43、7 第三趟 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í)挑選排序終止；常用的挑選排序算法：（1）直接挑選排序（2）堆排序10.3.1 直接挑選排序131、其基本思想每經(jīng)過一趟比較就找出一個(gè)最小值,與待排序列最前面的位置互換即可；（即從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個(gè)數(shù)據(jù)元素交換位置；然后從不包括第一個(gè)位置的數(shù)據(jù)元素集合中選取關(guān)

44、鍵字最小的數(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)給出直接挑選排序的詳細(xì)實(shí)現(xiàn)過程；原始序列：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 趟 0

45、8,16, 21 ,25* ,25,49 public static void selectSortint a int i, j, small; int temp; int n = a.Length; fori = 0; i n - 1; i + small = i; / 設(shè)第 i 個(gè)數(shù)據(jù)元素最小forj = i + 1; j n; j + / 查找最小的數(shù)據(jù)元素ifaj asmall small = j; / 記住最小元素的下標(biāo)ifsmall .= i / 當(dāng)最小元素的下標(biāo)不為 i 時(shí)交換位置temp = ai; ai = asmall; asmall = temp; 3、算法分析時(shí)間效率：

46、On2 雖移動(dòng)次數(shù)較少,但比較次數(shù)仍多；14空間效率： O（1）沒有附加單元（僅用到 1 個(gè) temp 算法的穩(wěn)固性：不穩(wěn)固4、穩(wěn)固的直接挑選排序算法例：關(guān)鍵字序列 T= （21 ,25,49 ,25* ,16,08）,請(qǐng)給出穩(wěn)固的直接挑選排序的詳細(xì)實(shí)現(xiàn)過程；原始序列：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 ,25

47、* ,49 public static void selectSort2int a int i,j,small; int temp; int n = a.Length; fori = 0; i n-1; i+ small = i; forj = i+1; j n; j+ / 查找最小的數(shù)據(jù)元素ifaj i; j- aj = aj-1; / 把該區(qū)段尚未排序元素依次后移ai = temp; / 插入找出的最小元素 8.3.2 堆排序1. 什么是堆？2. 怎樣建堆？3. 怎樣堆排序？堆的定義：設(shè)有 n 個(gè)數(shù)據(jù)元素的序列 k0 ,k1 , ,kn-1 ,當(dāng)且僅當(dāng)中意下述關(guān)系之一時(shí),稱之為堆；說明：假

48、如讓中意以上條件的元素序列（k,k, ,kn ）順次排成一棵完全二叉樹,就此樹的特點(diǎn)是：樹中全部結(jié)點(diǎn)的值均大于（或小于）其左右孩子,此樹的根結(jié)點(diǎn)（即堆頂）必最大（或最?。?5例 4：有序列 T1= （08, 25, 49, 46, 58, 67）和序列 T2= （91, 85, 76, 66, 58, 67, 55）,判定它們是否“ 堆” ？2. 怎樣建堆？步驟：從第一個(gè)非終端結(jié)點(diǎn)開頭往前逐步調(diào)整,讓每個(gè)雙親大于（或小于）子女,直到根結(jié)點(diǎn)為止；終端結(jié)點(diǎn)（即葉子）沒有任何子女,無需單獨(dú)調(diào)整 例：關(guān)鍵字序列 T= 21 ,25 ,49 ,25* ,16,08 ）,請(qǐng)建最大堆；解：為便于懂得,先將

49、原始序列畫成完全二叉樹的形式：這樣可以很清楚地從 n-1-1/2 開頭調(diào)整；public static void createHeapint 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 = ai; flag = 0; whilej n & flag .= 1 / 查找左右孩子結(jié)點(diǎn)中的較大者 ,j 為其下標(biāo) ifj n - 1 & aj = aj /ai=aj flag = 1; / 標(biāo)記終止挑選條件 else / 否就把 aj 上移 ai = aj; i = j

50、; j = 2 * i + 1; ai = temp; 利用上述 createHeap （a,n,h ）函數(shù),初始化創(chuàng)建最大堆的過程就是從第一個(gè)非葉子結(jié)點(diǎn) ai 開頭,到根結(jié)點(diǎn) a0 為止,循環(huán)調(diào) 用 createHeap （a,n,h ）的過程；初始化創(chuàng)建最大堆算法如下：public static void initCreateHeapint a int n = a.Length; 16forint i = n-1-1 / 2; i = 0; i - createHeapa, n, i; 3. 怎樣進(jìn)行整個(gè)序列的堆排序？*基于初始堆進(jìn)行堆排序的算法步驟：; 堆的第一個(gè)對(duì)象 a0 具有最大的關(guān)

51、鍵碼,將 a0 與 an-1 對(duì)調(diào),把具有最大關(guān)鍵碼的對(duì)象交換到最終 再對(duì)前面的 n-1 個(gè)對(duì)象,使用堆的調(diào)整算法,重新建立堆（調(diào)整根結(jié)點(diǎn)使之中意最大堆的定義）；結(jié)果具有次最大關(guān)鍵碼的對(duì)象又上 浮到堆頂,即 a0 位置 ; 再對(duì)調(diào) a0 和 an-2 ,然后對(duì)前 n-2 個(gè)對(duì)象重新調(diào)整, 如此反復(fù),最終得到全部排序好的對(duì)象序列；例 5：對(duì)剛才建好的最大堆進(jìn)行排序：public static void heapSortint a int temp; int n = a.Length; initCreateHeapa; / 初始化創(chuàng)建最大堆1 forint i = n - 1; i 0; i -

52、/ 當(dāng)前最大堆個(gè)數(shù)每次遞減/ 把堆頂 a0 元素和當(dāng)前最大堆的最終一個(gè)元素交換 temp = a0; a0 = ai; ai = temp; createHeapa,i, 0; / 調(diào)整根結(jié)點(diǎn)中意最大堆 4、堆排序算法分析：時(shí)間效率： Onlog2n ；空間效率： O1 ；穩(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 ,建

53、成的最小堆為（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ì)17練習(xí) 3：已知序列 503 ,87,512 ,61 ,908 ,170 ,897 ,275 ,653 ,462 ,寫出接受堆排序?qū)υ撔蛄凶鞣沁f減排列時(shí)的排序過程；排序好的序列為： 61 ,87,170 ,275 ,462 ,503 ,512 ,653 ,897 ,908 10.4 交換排序交換排序的基本思想是：利用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法；交換排序的主要算法有：1 冒泡排序 2 快速排序 10.4.1 冒泡排序 1、基本思路：每趟

54、不斷將記錄兩兩比較,并按“ 前小后大” （或“ 前大后小” ）規(guī)章交換；2、優(yōu)點(diǎn)：每趟終止時(shí),不僅能擠出一個(gè)最大值到最終面位置,仍能同時(shí)部分理順其他元素；一旦下趟沒有交換發(fā)生,仍可以提前終止排序；例：關(guān)鍵字序列 T=21 ,25 ,49 ,25* ,16,08 ）,請(qǐng)按從小到大的次序,寫出冒泡排序的詳細(xì)實(shí)現(xiàn)過程；初態(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 , 2

55、5* ,49 第 5 趟 08,16, 21 , 25 , 25* ,49 3、冒泡排序算法 public static void bubbleSortint a int i, j, flag=1; int temp; int n = a.Length; fori = 1; i n & flag = 1; i+ flag = 0; forj = 0; j aj+1 flag = 1; temp = aj; aj = aj+1; aj+1 = temp; 18 4、冒泡排序的算法分析時(shí)間效率： O（n2 由于要考慮最壞情形（數(shù)據(jù)元素全部逆序）,當(dāng)然最好情形是數(shù)據(jù)元素已全部排好序,此時(shí)循環(huán)n-1

56、次,時(shí)間復(fù)雜度為 O （n 空間效率： O（1） 只在交換時(shí)用到一個(gè)緩沖單元 穩(wěn) 定 性： 穩(wěn)固 25 和 25* 在排序前后的次序未轉(zhuǎn)變練習(xí)：關(guān)鍵字序列 T=31 ,15,9,25,16,28 ）,請(qǐng)按從小到大的次序,寫出冒泡排序的詳細(xì)實(shí)現(xiàn)過程；初態(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è)元素（通常取al

57、ow ）做為標(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)元素；這樣一次排序過程終止后,一方面將標(biāo)準(zhǔn)元素放在了將來排好序的數(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)行方法類同的遞歸快速排序；算法的遞歸出口條件是low high；例、關(guān)鍵字序列 T=60 ,55 ,48 ,37 ,10,90 ,84,36）,請(qǐng)按從小到大的次序,寫出快速排序的

58、詳細(xì)實(shí)現(xiàn)過程；快速排序算法各次快速排序過程 3、快速排序算法 public static void quickSortint a, int low, int high int i, j; int temp; i = low; j = high; temp = alow; / 取第一個(gè)元素為標(biāo)準(zhǔn)數(shù)據(jù)元素 whilei j / 在數(shù)組的右端掃描 whilei j & temp = aj j-; ifi j 19ai = aj; i+; / 在數(shù)組的左端掃描 whilei j & ai temp i+; ifi j aj = ai; j-; ai = temp; iflow i quickSorta, low, i-1; / 對(duì)左端子集合遞歸 ifi high quickSorta, j+1, high; / 對(duì)右端子集合遞歸 4、快速排序算法分析：時(shí)間效率：一般情形下時(shí)間復(fù)雜度為 Onlog2n ,最壞情形是數(shù)據(jù)元素已全部正序或反序有序,此時(shí)每次標(biāo)準(zhǔn)元素都把當(dāng)前數(shù)組分成一 個(gè)大小比當(dāng)前數(shù)組小 1 的子數(shù)組,此時(shí)時(shí)間復(fù)雜度為 On2 空間效率： O（log2n ）由于遞歸要用棧穩(wěn) 定 性： 不 穩(wěn) 定 由于有跳動(dòng)式交換；練習(xí)：