復(fù)旦大學(xué)軟件工程考研(mse)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

1、數(shù)據(jù)結(jié)構(gòu)2016MSE考研沖刺,,課程安排,課程介紹棧、隊(duì)列和向量 樹(shù)查找排序圖,課程目的,（以最小代價(jià)）通過(guò)考試！不是成為專(zhuān)家不是初學(xué)授課,試題結(jié)構(gòu),考試滿分60分考試題型：?jiǎn)柎?、分析、編?樣題－問(wèn)答和編程題,插入排序、選擇排序、冒泡排序、快速排序中最快的排序方法是________試論述什么叫Hash沖突及有那些處理方法編程實(shí)現(xiàn)對(duì)二叉樹(shù)所有節(jié)點(diǎn)的統(tǒng)計(jì),課程安排,課程介紹棧、隊(duì)列和向量 樹(shù)查找排

2、序圖,鏈表、棧和隊(duì)列,大綱描述：?jiǎn)捂湵?雙向鏈表,環(huán)形鏈表,帶哨兵節(jié)點(diǎn)的鏈表?xiàng)５幕靖拍詈托再|(zhì),棧ADT及其順序,鏈接實(shí)現(xiàn);棧的應(yīng)用;棧與遞歸;隊(duì)列的基本概念和性質(zhì),隊(duì)列ADT及其順序,鏈接實(shí)現(xiàn);隊(duì)列的應(yīng)用;向量基本概念和性質(zhì);向量ADT及其數(shù)組、鏈接實(shí)現(xiàn);,線性表基本概念和性質(zhì),線性表是n個(gè)數(shù)據(jù)元素的有限序列常見(jiàn)線性表包括數(shù)組、鏈表、棧、隊(duì)列等線性表的兩種實(shí)現(xiàn)方式順序鏈?zhǔn)綄?duì)比：插入（有序、無(wú)序）、刪除、查找、讀取

3、,環(huán)形鏈表,環(huán)形鏈表又稱(chēng)循環(huán)列表，是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)元素的指針域指向頭結(jié)點(diǎn),棧的基本概念和性質(zhì),棧：棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表后進(jìn)先出特性（LIFO）棧頂、棧底、出棧、入棧,例題,設(shè)有一個(gè)棧S，元素S1, S2, S3, S4, S5, S6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)镾2, S3, S4, S6, S5, S1，則棧的容量至少應(yīng)為多少？ 答案：3,棧的基本概念和性質(zhì),設(shè)

4、計(jì)遞歸問(wèn)題的非遞歸算法一般需要用到棧機(jī)制三個(gè)數(shù)a、b、c進(jìn)棧，不可能出現(xiàn)c、a、b順序出棧,例題,若某棧的輸入序列為a、b、c，則所有可能的出棧序列有___種，所有不可能的出棧序列有____種。答案：5，1,例題,若棧的輸入序列為1,2,3,4，則——是不可能的棧輸出序列之一。答案：4，3，1，2,習(xí)題,若某棧的輸入序列為a、b、c、d，則所有可能的出棧序列有___種，所有不可能的出棧序列有____種。請(qǐng)寫(xiě)出所有可能的序列

5、和不可能的序列。,棧的應(yīng)用,數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)字與d進(jìn)制數(shù)字的轉(zhuǎn)換N = ( N div d) × d + N mod d其中div為整除，mod為求余。算法：將算法3.1中8換成d,例題,十進(jìn)制數(shù)1167等于八進(jìn)制數(shù)——？答案： 2217思路：計(jì)算方法：除余倒排法驗(yàn)證方法：指數(shù)相加法,習(xí)題,十進(jìn)制數(shù)1167等于七進(jìn)制數(shù)——？,棧的應(yīng)用,表達(dá)式求值：中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式后綴表達(dá)式求值三種表達(dá)式：前綴

6、表達(dá)式 + a b中綴表達(dá)式 a + b后綴表達(dá)式 a b +,例題,中綴表達(dá)式a + b × c – d轉(zhuǎn)為后綴表達(dá)式是————？答案： a b c×＋d－,例題,中綴表達(dá)式（a + b） × c – d轉(zhuǎn)為后綴表達(dá)式是————？答案： a b ＋ c×d－思路：數(shù)字位序不變，運(yùn)算符位置改變后綴表達(dá)式無(wú)括號(hào)，運(yùn)算順序同中綴表達(dá)式,習(xí)題,中綴表達(dá)式A-(B+C)*D/

7、E的后綴形式是_________________。,練習(xí),中綴表達(dá)式a * ( b + c ) / d轉(zhuǎn)為后綴表達(dá)式是————？,例題,計(jì)算后綴表達(dá)式1 2 + 4 * 2 /的值為——？答案：6思路：順序計(jì)算或 轉(zhuǎn)換為中綴表達(dá)式計(jì)算,習(xí)題,計(jì)算后綴表達(dá)式3 2 － 4 * 2 / 3＋的值為——？,遞歸,一個(gè)直接調(diào)用自己或通過(guò)一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù)，稱(chēng)為遞歸函數(shù)優(yōu)點(diǎn)：結(jié)構(gòu)清晰、程序易讀、正確性容易得到證明缺

8、點(diǎn)：效率相對(duì)較低,隊(duì)列的基本概念和性質(zhì),隊(duì)列：隊(duì)列是限定僅在表的一頭進(jìn)行插入、另一頭進(jìn)行刪除操作的線性表先進(jìn)先出特性（FIFO）隊(duì)尾、隊(duì)頭、入隊(duì)、出隊(duì),例題,在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)頭元素是——，隊(duì)尾元素是————。答案：c，d,雙向隊(duì)列,雙向隊(duì)列：亦稱(chēng)雙端隊(duì)列（Deque）是限定插入和刪除操作在表的兩端進(jìn)行的線性表可以用于包裝產(chǎn)生棧和隊(duì)列,課程安排,課程介紹棧、隊(duì)

9、列和向量 樹(shù)查找排序圖,樹(shù),大綱描述：樹(shù)的基本概念和術(shù)語(yǔ)；樹(shù)的前序、中序、后序、層次序遍歷；二叉樹(shù)及其性質(zhì)；普通樹(shù)與二叉樹(shù)的轉(zhuǎn)換；樹(shù)的存儲(chǔ)結(jié)構(gòu),標(biāo)準(zhǔn)形式;完全樹(shù)(complete tree)的數(shù)組形式存儲(chǔ);樹(shù)的應(yīng)用，Huffman樹(shù) 。,樹(shù)的基本概念和術(shù)語(yǔ),樹(shù)：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集在任意一棵非空樹(shù)中：有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可以分為m（m>0）個(gè)互不相交的有限集，其中

10、每個(gè)集合本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)樹(shù)屬于層次結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu),樹(shù)的基本概念和術(shù)語(yǔ),節(jié)點(diǎn)標(biāo)簽父節(jié)點(diǎn)、子節(jié)點(diǎn)、兄弟節(jié)點(diǎn)、祖先節(jié)點(diǎn)、子孫節(jié)點(diǎn)路徑、樹(shù)枝,根、葉子次數(shù)內(nèi)部節(jié)點(diǎn)、外部節(jié)點(diǎn)樹(shù)的次數(shù)、K次樹(shù)節(jié)點(diǎn)層次、樹(shù)的高度和深度子樹(shù)有序樹(shù)、無(wú)序樹(shù)森林、果園,例題,例題,列出如上圖所示樹(shù)的所有葉子結(jié)點(diǎn)答案：K,L,F,G,M,I,J列出如上圖所示樹(shù)的所有分支結(jié)點(diǎn)答案：A,B,C,D,E,H樹(shù)A為幾次樹(shù)？子樹(shù)B呢？答案

11、：3，2前頁(yè)圖所示樹(shù)的高度為多少？答案：4,樹(shù)的基本概念和術(shù)語(yǔ),如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看作從左到右有序的,則該樹(shù)為有序樹(shù)(ordered tree),否則為無(wú)序樹(shù)。森林(forest)是m棵互不相交的樹(shù)的集合。如果把一棵樹(shù)的根砍去，剩下的部分就是森林。如果原來(lái)的樹(shù)是有序的,則砍去根后的森林也是有序的,此時(shí)稱(chēng)該森林為有序森林或果園。,二叉樹(shù)及其性質(zhì),二叉樹(shù)（Binary Tree）另一種樹(shù)形結(jié)構(gòu)，特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)

12、，且子樹(shù)有左右之分，其次序不能任意顛倒二叉樹(shù)可能的五種基本形態(tài),二叉樹(shù)及其性質(zhì),在二叉樹(shù)的第i層上至多有2i－1個(gè)結(jié)點(diǎn)（i≥1）,例題,一棵二叉樹(shù)第五層上至多有多少個(gè)結(jié)點(diǎn)？至少多少？答案：16，1,二叉樹(shù)及其性質(zhì),深度為k的二叉樹(shù)至多有2k－1個(gè)結(jié)點(diǎn)（k≥1）,例題,深度為n(n>0)的二叉樹(shù)最多有_____個(gè)結(jié)點(diǎn)。答案：2n-1,例題,一棵深度為5的二叉樹(shù)至多有多少個(gè)結(jié)點(diǎn)？至少多少？答案：31，5,例題,高度為h(

13、h>0)的二叉樹(shù)最少有________個(gè)結(jié)點(diǎn)？答案：h,二叉樹(shù)及其性質(zhì),對(duì)于任何二叉樹(shù),如果葉子節(jié)點(diǎn)數(shù)為n0,度為2的節(jié)點(diǎn)數(shù)為n2,則n0=n2+1,例題,在一棵二叉樹(shù)中有n0個(gè)葉結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，則n2=________。答案： n0 －1,例題,若一棵二叉樹(shù)有10個(gè)葉結(jié)點(diǎn)，則該二叉樹(shù)中度為2的結(jié)的點(diǎn)個(gè)數(shù)為_(kāi)_____________。答案：9,例題,若一二叉樹(shù)有2度結(jié)點(diǎn)100個(gè)，則其葉結(jié)點(diǎn)有多少個(gè)？答

14、案：101,例題,若二叉樹(shù)中度為2的結(jié)點(diǎn)有15個(gè)，度為1的結(jié)點(diǎn)有10個(gè)，共有多少個(gè)結(jié)點(diǎn)？答案：41,例題,在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)有2個(gè)，度為2的結(jié)點(diǎn)有1個(gè)，度為1的結(jié)點(diǎn)有2個(gè)，那么，該樹(shù)有__________個(gè)葉結(jié)點(diǎn)。答案：6構(gòu)造法,二叉樹(shù)及其性質(zhì),滿二叉樹(shù)：一棵深度為k且有2k－1個(gè)結(jié)點(diǎn)的二叉樹(shù)可以對(duì)滿二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定編號(hào)從根開(kāi)始，自上而下，自左而右。完全二叉樹(shù)：深度為k的，有n個(gè)結(jié)點(diǎn)的二

15、叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)為完全二叉樹(shù)。,二叉樹(shù)及其性質(zhì),完全二叉樹(shù)特點(diǎn)：葉子結(jié)點(diǎn)只可能出現(xiàn)在層次最大的兩層上對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，其左下分支的子孫的最大層次必為l或者l＋1。深度為k的完全二叉樹(shù)第k層最少1個(gè)結(jié)點(diǎn)，最多2k-1-1個(gè)結(jié)點(diǎn)；整棵樹(shù)最少2k-1個(gè)結(jié)點(diǎn)，最多2k-2個(gè)結(jié)點(diǎn),例題,若某完全二叉樹(shù)的深度為h，則該完全二叉樹(shù)中至少有______個(gè)

16、結(jié)點(diǎn)。答案：2h-1,例題,若深度為6的完全二叉樹(shù)的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹(shù)一共有______個(gè)結(jié)點(diǎn)。答案：25-1+3＝34,例題,一個(gè)具有767個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其葉子結(jié)點(diǎn)個(gè)數(shù)為_(kāi)___。 答案：384分析：可以根據(jù)公式進(jìn)行推導(dǎo)，假設(shè)n0是度為0的結(jié)點(diǎn)總數(shù)（即葉子結(jié)點(diǎn)數(shù)），n1是度為1的結(jié)點(diǎn)總數(shù)，n2是度為2的結(jié)點(diǎn)總數(shù)，由二叉樹(shù)的性質(zhì)可知：n0＝n2＋1，則n= n0＋n1＋n2（其中n為完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)）

17、，由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)只有兩種可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一個(gè)公式：n0＝[（n＋1）/2 ]，就可根據(jù)完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)計(jì)算出葉子結(jié)點(diǎn)數(shù)。本題計(jì)算得：384。,二叉樹(shù)及其性質(zhì),具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1,例題,具有2000個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為_(kāi)________。答案：11,二叉樹(shù)及其性質(zhì),如果含有n ?1個(gè)

18、節(jié)點(diǎn)的二叉樹(shù)的高度為[log2n]＋1,將其所有結(jié)點(diǎn)按層次序編號(hào),則對(duì)于任一節(jié)點(diǎn)j(1?j ? n),有如果j=1,則節(jié)點(diǎn)j是樹(shù)的根,無(wú)雙親;如果j>1,則其父節(jié)點(diǎn)parent(j)是節(jié)點(diǎn)[j/2]如果2j>n,則節(jié)點(diǎn)j無(wú)左子節(jié)點(diǎn);否則其左子節(jié)點(diǎn)為2j如果2j+1>n,則節(jié)點(diǎn)j無(wú)右子節(jié)點(diǎn);否則其右子節(jié)點(diǎn)為2j+1證明,完全樹(shù)的數(shù)組形式存儲(chǔ),完全樹(shù)的數(shù)組形式存儲(chǔ)算法將其編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組下標(biāo)為i－

19、1的分量中,例題,已知數(shù)組[20,30,19,87,30,40]表示一棵完全二叉樹(shù)，請(qǐng)畫(huà)出該樹(shù)。,練習(xí)答案,樹(shù)的遍歷,樹(shù)的遍歷 按某種搜索路徑巡訪樹(shù)中每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次僅且一次二叉樹(shù)的遍歷可分為前序、中序、后序、層次序等普通樹(shù)的遍歷可以分為先根、后根、層次序等,樹(shù)的遍歷,二叉樹(shù)的遍歷前序、中序、后序定義層次序：從上而下，從左至右常見(jiàn)問(wèn)題已知樹(shù)寫(xiě)遍歷結(jié)果已知遍歷結(jié)果畫(huà)樹(shù)依據(jù)：二叉樹(shù)的前序和中序遍歷可以唯一確

20、定一棵二叉樹(shù)思路：前序定根，中序定左右遞歸和非遞歸算法實(shí)現(xiàn),例題,寫(xiě)出左圖所示二叉樹(shù)的前序、中序、后序、層次序遍歷結(jié)果,例題答案,前序：ABDCEFG中序：DBAECFG后序：DBEGFCA層次序：ABCDEFG,例題,假設(shè)一棵二叉樹(shù)的前序遍歷為EBADCHGFIKJ，中序遍歷為ABCDEFGHIJK，請(qǐng)畫(huà)出該樹(shù)。,例題答案,樹(shù)的遍歷,普通樹(shù)的遍歷前根：先遍歷根結(jié)點(diǎn)，再依次前根遍歷各棵子樹(shù)后根：先后根遍歷各課子樹(shù)，再遍歷根

21、結(jié)點(diǎn)已知樹(shù)寫(xiě)遍歷結(jié)果已知遍歷結(jié)果畫(huà)樹(shù)思路：先根定根，后根定子樹(shù),例題,寫(xiě)出如右圖所示樹(shù)的先根、后根、層次序遍歷結(jié)果,例題答案,前序： ABECFGHD后序：EBFHGCDA層次序：ABCDEFGH,練習(xí),給出如圖所示樹(shù)的先根、后根和層次序遍歷結(jié)果,練習(xí)答案,前根：ABEFHIGCJKLDMNOQP后根：EHIFGBKLJCNQOPMDA層次序：ABCDEFGJMHIKLNOPQ,例題,畫(huà)出和下列已知序列對(duì)應(yīng)的樹(shù)T：樹(shù)的

22、先根次序訪問(wèn)序列為GFKDAIEBCHJ樹(shù)的后根次序訪問(wèn)序列為DIAEKFCJHBG,例題答案,普通樹(shù)與二叉樹(shù)的轉(zhuǎn)換,對(duì)于任意k次樹(shù)到相應(yīng)二叉樹(shù)的轉(zhuǎn)換算法對(duì)于具有子節(jié)點(diǎn)n1,n2…nk的節(jié)點(diǎn)n,將n1作為其左子節(jié)點(diǎn),且kj+1作為kj(1 ?j ? k-1)的右子節(jié)點(diǎn)思路：“不同層在左，同層在右”,普通樹(shù)與二叉樹(shù)的轉(zhuǎn)換,對(duì)于任意森林到相應(yīng)二叉樹(shù)的轉(zhuǎn)換算法為 設(shè)T=(T1,T2…..Tm)為m(m?0)棵樹(shù)的序列,而B(niǎo)T (T

23、1,T2…..Tm)為相應(yīng)的二叉樹(shù),則如果m=0,則BT為空樹(shù)如果m>0,則T1的根節(jié)點(diǎn)就是BT的根節(jié)點(diǎn),而B(niǎo)T的左子樹(shù)是T1的子樹(shù)T11,T12…T1K轉(zhuǎn)換成的BTl(T11,T12…T1K),其右子樹(shù)為BTr(T2…..Tm),例題,將下頁(yè)圖所示森林轉(zhuǎn)換為等價(jià)的二叉樹(shù),例題,例題答案,練習(xí),將如圖所示樹(shù)轉(zhuǎn)換為二叉樹(shù),練習(xí)答案,Huffman樹(shù),Huffman樹(shù)：又稱(chēng)最優(yōu)樹(shù)，是一類(lèi)帶權(quán)路徑長(zhǎng)度最短的樹(shù)基本概念：樹(shù)的路徑

24、長(zhǎng)度：從根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記做WPL。,Huffman樹(shù),基本概念：假設(shè)有n個(gè)權(quán)值wi，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子的結(jié)點(diǎn)帶權(quán)為wi，則其中WPL最小的二叉樹(shù)稱(chēng)為最優(yōu)二叉樹(shù)或赫夫曼樹(shù)算法見(jiàn)下頁(yè),Huffman算法,(1) 由給定的n個(gè)權(quán)值{w0, w1, w2, …, wn-1}，

25、構(gòu)造具有n棵二叉樹(shù)的集合F = {T0, T1, T2, …, Tn-1}，其中每一棵二叉樹(shù)Ti只有一個(gè)帶有權(quán)值wi的根結(jié)點(diǎn)，其左、右子樹(shù)均為空。(2) 在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹(shù), 做為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)。置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。(3) 在F中刪去這兩棵二叉樹(shù)，加入新得的樹(shù)。(4) 重復(fù)(2) (3)，直到F只含一棵樹(shù)為止。這棵樹(shù)就是赫夫曼樹(shù),Step 1,2Z,7K

26、,24F,32C,37U,42D,42L,120E,9,,,33,,,,,Round 1,Round 2,例題,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,Round 3,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,79,,,Round 4,2Z,7K,24F,32C,37U,42D,42

27、L,120E,9,,,33,,,65,,,79,,,107,,,Round 5,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,79,,,107,,,186,,,Round 6,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,79,,,107,,,186,,,306,,,Round 7 (final),Huffman編碼

28、,編碼：等長(zhǎng)編碼/不等長(zhǎng)編碼前綴編碼：若要設(shè)計(jì)長(zhǎng)短不等的編碼，則必須是任一個(gè)字符的編碼抖不是另一個(gè)字符編碼的前綴，這種編碼叫做前綴編碼Huffman編碼：以n種字符出現(xiàn)的頻率做權(quán)，設(shè)計(jì)一棵赫夫曼樹(shù)，由此得到的前綴編碼稱(chēng)為Huffman編碼,例題,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,79,,,107,,,186,,,306,,,0,0,0,0,0,1,1,1,1,1

29、,1,0,0,1,,習(xí)題,某通訊系統(tǒng)只使用8種字符a、b、c、d、e、f、g、h，其使用頻率是0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11。構(gòu)造以字符使用頻率為權(quán)值的Huffman樹(shù)，并給出相應(yīng)的Huffman編碼。,習(xí)題答案,習(xí)題答案,A：0110B：10C：1110D：1111,E：110F：00G：0111H：010,課程安排,課程介紹棧、隊(duì)列和向量 樹(shù)查找排序圖,查找,大綱

30、描述：查找的基本概念；對(duì)線性關(guān)系結(jié)構(gòu)的查找，順序查找，二分查找；Hash查找法,常見(jiàn)的Hash函數(shù)(直接定址法,隨機(jī)數(shù)法),hash沖突的概念, 解決沖突的方法(開(kāi)散列方法/拉鏈法,閉散列方法/開(kāi)址定址法),二次聚集現(xiàn)象;BST樹(shù)定義,性質(zhì),ADT及其實(shí)現(xiàn),BST樹(shù)查找,插入,刪除算法;平衡樹(shù) (AVL) 的定義,性質(zhì),ADT及其實(shí)現(xiàn),平衡樹(shù)查找,插入算法,平衡因子的概念;優(yōu)先隊(duì)列與堆,堆的定義,堆的生成,調(diào)整算法;范圍查詢(xún);

31、,查找的基本概念,查找表(search table)：具有同一類(lèi)型數(shù)據(jù)元素(經(jīng)常稱(chēng)為記錄)的集合查找表的基本操作有：查找某個(gè)“特定”記錄是否在表中查找到后取出某個(gè)“特定”記錄的各個(gè)數(shù)據(jù)項(xiàng)向表中插入記錄從表中刪除記錄,查找的基本概念,靜態(tài)查找表(static search table)：僅用于查詢(xún)的查找表。動(dòng)態(tài)查找表(dynamic search table):若在查找過(guò)程中需同時(shí)插入表中不存在的記錄;或者需要?jiǎng)h除記錄,

32、則稱(chēng)之為動(dòng)態(tài)查找表。關(guān)鍵字/鍵值(key) ：記錄某個(gè)數(shù)據(jù)項(xiàng)的值,用其可以標(biāo)示該記錄當(dāng)記錄只有一個(gè)數(shù)據(jù)項(xiàng)時(shí),其關(guān)鍵字即為該記錄的值如果一個(gè)key可以唯一標(biāo)示一個(gè)就,則稱(chēng)之為主關(guān)鍵字(primary key),否則稱(chēng)之為次關(guān)鍵字(secondary key),查找的基本概念,查找(search)：在一個(gè)查找表中找出具有“特定”鍵值的那些記錄所謂查找成功是指在查找表中找到了滿足條件的記錄,此時(shí)一般會(huì)返回找到的記錄,或者返回記錄的

33、位置信息,或者僅僅返回找到(true)否則稱(chēng)為查找失敗,此時(shí)一般返回空指針,或特殊值,或者僅僅返回沒(méi)有找到(false),有時(shí)也會(huì)就此插入這個(gè)元素,BST樹(shù)定義，性質(zhì)， 實(shí)現(xiàn),二叉排序樹(shù)(Binary Sorted Tree)又稱(chēng)二叉搜索樹(shù)或二叉查找樹(shù)或者是一棵空樹(shù)；或者是具有下列性質(zhì)的二叉樹(shù)：如果左子樹(shù)非空,則左子樹(shù)中所有節(jié)點(diǎn)的鍵值均小于它的根結(jié)點(diǎn)的值；如果右子樹(shù)非空,則右子樹(shù)中所有節(jié)點(diǎn)的鍵值均大于它的根結(jié)點(diǎn)的值；它的左

34、右子樹(shù)也都是二叉排序樹(shù)。,BST樹(shù)定義，性質(zhì)， 實(shí)現(xiàn),二叉排序樹(shù)性質(zhì) 如果對(duì)二叉排序樹(shù)進(jìn)行中序遍歷,則得到一個(gè)從小到大排好序的列表,所以可以得到一種簡(jiǎn)單的排序方法叫做“樹(shù)排序”(treesort)。我們也可以根據(jù)這個(gè)性質(zhì)定義二叉排序樹(shù)為:如果一棵樹(shù)按中序遍歷為排好序的,則這棵樹(shù)是二叉排序樹(shù)。,BST樹(shù)查找，插入，刪除算法,BST樹(shù)查找，插入，刪除算法畫(huà)圖算法,例題,已知BST樹(shù)如左，請(qǐng)畫(huà)出插入16，再刪除36之后的BST樹(shù),例題

35、答案,例題,試求按關(guān)鍵字序列（12，1，4，3，7，8，1O，2）插入生成的二叉排序樹(shù),例題答案,練習(xí),假設(shè)結(jié)點(diǎn)序列F＝（60，30，90，50，120，70，40，80），試用BST的插入算法，用F中的結(jié)點(diǎn)依次進(jìn)行插入，畫(huà)出由F中結(jié)點(diǎn)所構(gòu)成的BST樹(shù)T1；再用刪除算法，依次刪除40，70，60，畫(huà)出刪除后的BST樹(shù)T2。,練習(xí)答案,平衡樹(shù),平衡因子（balanced factor）二叉樹(shù)上任一節(jié)點(diǎn)的左子樹(shù)高度減去右子樹(shù)高度的差A(yù)V

36、L Tree，根據(jù)其三位發(fā)明者(Adelson-Velskii and Landis)的名字命名一棵BST樹(shù)中每個(gè)節(jié)點(diǎn)平衡因子的絕對(duì)值不超過(guò)1,平衡樹(shù),基本思想 :在插入或刪除節(jié)點(diǎn)后對(duì)新樹(shù)進(jìn)行判斷,如果新樹(shù)已經(jīng)變得不平衡,則通過(guò)旋轉(zhuǎn)(rotation)的方法對(duì)樹(shù)進(jìn)行重組/改組(re-arrange),使得重組后的樹(shù)在保持查找樹(shù)特性的同時(shí)保持平衡所謂旋轉(zhuǎn):通過(guò)改變支撐點(diǎn)來(lái)維持平衡順時(shí)針旋轉(zhuǎn)為右旋;逆時(shí)針旋轉(zhuǎn)為左旋可以進(jìn)行連續(xù)的

37、多次旋轉(zhuǎn),平衡樹(shù),算法代碼及基本的時(shí)間復(fù)雜度分析,Hash查找法，常見(jiàn)的Hash函數(shù),哈希（Hash）函數(shù)：在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。這個(gè)對(duì)應(yīng)關(guān)系f為哈希函數(shù)。按這個(gè)思想建立的表為哈希表。哈希函數(shù)的設(shè)定可以很靈活，只要使得任何關(guān)鍵字的哈希函數(shù)值都落在表長(zhǎng)允許范圍之內(nèi)即可。,Hash查找法，常見(jiàn)的Hash函數(shù),練習(xí)：已知線性表關(guān)鍵字集合為：S = { an

38、d, begin, do, end, for, go, if, repeat, then, until, while}，求哈希函數(shù)。答案：H(key)=key[0] – ‘a(chǎn)’;即為關(guān)鍵字key中的第一個(gè)字母在字母表{a, b, c, ..., z}中的序號(hào),Hash查找法，常見(jiàn)的Hash函數(shù),直接定址法直接取key或者key的某個(gè)線性函數(shù)值 h(key) = a*key +b, a,b為常數(shù)如前面的例子,又如人口普查時(shí)使用年齡

39、,出生年份等,Hash查找法，常見(jiàn)的Hash函數(shù),除留余數(shù)法選擇一個(gè)適當(dāng)?shù)恼麛?shù)P，用P去除關(guān)鍵字，取所得得余數(shù)作為散列地址，即：H(key) = key%P方法的關(guān)鍵是選取適當(dāng)?shù)腜。選擇P最好不要是偶數(shù)，也不要是基數(shù)的冪。一般地選P為小于或等于散列表長(zhǎng)度m的某個(gè)最大素?cái)?shù)比較好。缺點(diǎn):整數(shù)相除速度較慢,Hash查找法，常見(jiàn)的Hash函數(shù),如:m = 8，16，32，64，128，256，512，1024P = 7，13，3

40、1，61，127，251，503，1019,解決沖突的方法,對(duì)不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱(chēng)沖突。具有相同函數(shù)值的關(guān)鍵字對(duì)該哈希函數(shù)來(lái)說(shuō)稱(chēng)作同義詞。在一般情況下，沖突只能盡可能的少，而不能完全避免。,解決沖突的方法,共同思想: 將具有相同函數(shù)值的記錄存作一個(gè)鏈閉散列方法/開(kāi)址定址法沖突記錄存儲(chǔ)在表內(nèi)開(kāi)散列方法/鏈地址法沖突記錄存儲(chǔ)在表外,解決沖突的方法,基本思想當(dāng)沖突發(fā)生時(shí)，使用某種方法在散列表中形成一個(gè)探查序

41、列(也稱(chēng)之為"鏈")，按此序列逐個(gè)單元的查找，直到找到一個(gè)指定的關(guān)鍵字或碰到一個(gè)開(kāi)放的地址（單元為空）為止。Hj = ( H(key) + dj ) MOD m 1 ?j ?m-1;m為hash表長(zhǎng)度dj為增量數(shù)列,各種方法的不同就區(qū)別在取不同的增量數(shù)列上,解決沖突的方法,常用的增量數(shù)列:線性探測(cè)法二次探測(cè)法偽隨機(jī)法再哈希法/二次哈希法桶式散列法,解決沖突的方法,線性探測(cè)法取dj = 1,2

42、,…m-1將散列表看成是一個(gè)環(huán)形表。若地址為d（即H(key)=d）的單元發(fā)生沖突，則依次探查下述地址單元：d+1，d+2，......，m-1，0，1，......，d-1,直到找到一個(gè)空單元或查找到關(guān)鍵字為key的結(jié)點(diǎn)為止。若沿著該探查序列查找一遍之后，又回到了地址d，則無(wú)論是做插入操作還是做查找操作，都意味著失敗。,解決沖突的方法,線性探測(cè)法缺點(diǎn):特別容易產(chǎn)生聚集鏈非常長(zhǎng),解決沖突的方法,拉鏈法若選定的散列函數(shù)的值域?yàn)?

43、到m-1，則可將散列表定義為一個(gè)由m個(gè)單鏈表的鏈表頭指針組成的指針數(shù)組HTP(m)，凡是散列地址為i的結(jié)點(diǎn)，均插入到以HTP(i)為頭指針的單鏈表中。,,,,,,,,,,,,,,,,,,,,,,,,,0123456789101112,若一組關(guān)鍵字為（26，36，41，38，44，15，68，12，06，51，25），散列函數(shù)定義為：H(key) = key%13。用拉練法建立的散列表為：,解決沖突的方法,拉鏈法

44、優(yōu)點(diǎn):不會(huì)堆積,所以平均查找時(shí)間較短動(dòng)態(tài)申請(qǐng)空間,適用于造表前無(wú)法確定表長(zhǎng)的情況刪除處理簡(jiǎn)單快速鏈長(zhǎng)易控制,一般較短,解決沖突的方法,負(fù)載系數(shù)的定義和作用設(shè)key的數(shù)量為N,散列表的大小為M,則N/M稱(chēng)負(fù)載系數(shù)或裝填因子(loadfactor),它表現(xiàn)了平均情況下每個(gè)鏈的長(zhǎng)度我們一般預(yù)先規(guī)定好這個(gè)值,然后當(dāng)不夠的時(shí)候再增加hash表的長(zhǎng)度(re-hash),這樣可以保證鏈的平均長(zhǎng)度不超過(guò)負(fù)載系數(shù),解決沖突的方法,增加時(shí)一般作

45、兩倍的增加，而且增加后需要將所有的表元素全部重新求值放置(因?yàn)閙變了)一般取值為0.75,解決沖突的方法,聚集(clustering)現(xiàn)象又稱(chēng)"二次聚集",指處理沖突中發(fā)生的兩個(gè)第一個(gè)hash地址不同的記錄爭(zhēng)奪同一個(gè)后繼hash地址的情況,常發(fā)生在有大量key對(duì)應(yīng)于同一Hash函數(shù)值的情況下聚集現(xiàn)象僅出現(xiàn)于使用"閉散列方法"時(shí)當(dāng)使用"線性探測(cè)法"時(shí)特別容易發(fā)生聚集現(xiàn)象,很

46、容易使散列查詢(xún)退化為對(duì)于鏈表或者數(shù)組的順序查詢(xún),解決沖突的方法,假設(shè)Hash函數(shù)為H(key)=key MOD 11,表中已經(jīng)有key 17,60,29,此時(shí)分別占據(jù)6,7,5;然后再插入38此時(shí)可以發(fā)現(xiàn),當(dāng)表中5,6,7都被占據(jù)后,凡是函數(shù)值為5,6,7,8的key都將爭(zhēng)奪8這個(gè)位置!!,例題,在初始為空的哈希表中依次插入關(guān)鍵字序列(MON，TUE，WED，THU，F(xiàn)RI，SAT，SUN), 哈希函數(shù)為H(k)=i MOD 7，其中

47、，i為關(guān)鍵字k的第一個(gè)字母在英文字母表中的序號(hào)，地址值域?yàn)閇0:6]，采用線性再散列法處理沖突。插入后的哈希表應(yīng)該如_________B_______所示。( )A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON

48、D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON,例題,若待散列的序列為(18,25,63,50,42,32,9)，哈希函數(shù)為H(key)=key MOD 9，哈希表長(zhǎng)度為9，與18發(fā)生沖突的元素有______________個(gè)答案：2,例題,已知一組關(guān)鍵字為（26，36，41，38，44，15，68，12，06，51，25），用線性探查法解決沖突構(gòu)造這組關(guān)鍵字的散列表，假設(shè)利用除余法構(gòu)造散列

49、函數(shù)。,例題答案,為了減少?zèng)_突，通常令裝填因子α<1，在此我們?nèi)ˇ?0.75。因?yàn)閚=11，所以散列表長(zhǎng)度m=high(n/α) = 15；對(duì)于除余法，選P=13（小于15的最大素?cái)?shù)），即散列函數(shù)為：H(key) = key%13。按順序插入各個(gè)結(jié)點(diǎn)：26: H(26) = 26/13 = 0 36: ...=10，41: ...=2，38: ...=12，44: ... =5插入15時(shí)，其散列地址為2，由于2已

50、被關(guān)鍵字為41的元素占用，故需進(jìn)行探查。按順序探查法，顯然3為開(kāi)放地址，故可將其放在3單元。類(lèi)似的，68和12可分別放在4和13單元中,練習(xí),在地址空間為0-16的散列區(qū)中,對(duì)以下關(guān)鍵字構(gòu)造兩個(gè)hash表 : (Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec)使用開(kāi)散列方法(此時(shí)請(qǐng)注明裝載因子為多少)使用閉散列方法(此時(shí)使用線性探測(cè)法)此處設(shè)hash函數(shù)為H

51、(x)=[i/2],其中i為關(guān)鍵字中第一個(gè)字母在字母表中的序號(hào),練習(xí)答案,0 A; 1 BC; 2 DE; 3 FG;4 HI;5 JK; 6 LM; 7 NO; 8 PQ; 9 RS; 10 TU; 11 VW; 12 XY; 13 ZJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec,練習(xí)答案,0->Apr->Aug2->Dec3->

52、Feb5->Jan->Jun->Jul6->Mar->May7->Oct->Nov9->Sep,練習(xí)答案,范圍查詢(xún),定義:在指定集合中有多少記錄的關(guān)鍵字是落在指定范圍中一維的情況:記錄可以看作直線上的點(diǎn)問(wèn)題可以看作有多少點(diǎn)落入指定線段區(qū)域中,課程安排,課程介紹棧、隊(duì)列和向量 樹(shù)查找排序圖,排序,大綱描述：排序基本概念；插入排序，希爾排序，選擇排序，快速排序，歸

53、并排序，基數(shù)排序等排序算法基本思想；算法代碼及基本的時(shí)間復(fù)雜度分析；堆的定義，堆的生成。,排序基本概念,排序(Sorting) ：重排一個(gè)記錄序列,使之成為按關(guān)鍵字有序常見(jiàn)排序可分為以下五類(lèi)：插入排序（簡(jiǎn)單插入排序、希爾排序）交換排序（冒泡排序、快速排序）選擇排序（簡(jiǎn)單選擇排序、堆排序）歸并排序計(jì)數(shù)排序（多關(guān)鍵字排序）,插入排序,[46] 26 22 68 48 42 36 84 66 22*[26 46] 22 6

54、8 48 42 36 84 66 22*[22 26 46] 68 48 42 36 84 66 22*[22 26 46 68] 48 42 36 84 66 22*[22 26 46 48 68] 42 36 84 66 22*[22 26 42 46 48 68] 36 84 66 22*[22 26 36 42 46 48 68] 84 66 22*[22 26 36 42 46 48 68 84] 66 22*[

55、22 26 36 42 46 48 66 68 84] 22*[22 22* 26 36 42 46 48 66 68 84],希爾排序,定義Shell Sort又稱(chēng)“縮小增量排序”（Diminishing Increment Sort），也是一種屬于插入排序類(lèi)的算法，但時(shí)間效率較其他排序方法有較大改進(jìn)基本思想是：先將整個(gè)待排記錄序列分割為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插

56、入排序,冒泡排序,交換排序的一種依次比較相鄰的兩個(gè)待排序元素，若為逆序（遞增或遞減）則進(jìn)行交換，將待排序元素從左至右比較一遍稱(chēng)為一趟“冒泡”每趟冒泡都將待排序列中的最大關(guān)鍵字交換到最后（或最前）位置直到全部元素有序?yàn)橹?直到某次冒泡過(guò)程中沒(méi)有發(fā)生交換為止,快速排序,就平均時(shí)間而言，快速排序是目前被認(rèn)為最好的一種內(nèi)部排序方法,由C. A. R. Hoare發(fā)明分治法(divide and conquer)思想的體現(xiàn)Unix系統(tǒng)函

57、數(shù)庫(kù)所提供的標(biāo)準(zhǔn)排序方法C標(biāo)準(zhǔn)函數(shù)庫(kù)中的排序方法直接就命名為qsort(),快速排序,基本思想:是對(duì)冒泡排序的一種改進(jìn)選取一個(gè)軸值,然后根據(jù)此軸值通過(guò)一趟排序?qū)τ涗浖M(jìn)行一次分割,然后對(duì)分割后產(chǎn)生的兩個(gè)記錄子集分別進(jìn)行快速排序,快速排序,基本概念:軸值(pivot):書(shū)上稱(chēng)樞軸用于將記錄集"分割"為兩個(gè)部分的那個(gè)鍵值分割(partition):將記錄集分為兩個(gè)部分,前面部分記錄的鍵值都比軸值小,后面部

58、分的鍵值都比軸值大,快速排序,快速排序,49,38,65,97,76,13,27,49’,,,,38,65,97,76,13,27,49’,,,27,38,65,97,76,13,,49’,,,27,38,,97,76,13,65,49’,,,27,38,13,97,76,,65,49’,,,27,38,13,,76,97,65,49’,,,27,38,13,49,76,97,65,49’,,,49,temp,,,例題,寫(xiě)出對(duì)于結(jié)點(diǎn)序列

59、（46，26，22，68，48，42，36，84，66）進(jìn)行第一次分割后序列的情況，注意列出步驟的每一步。,例題答案,【】26，22，68，48，42，36，84，6636，26，22，68，48，42，【】，84，6636，26，22，【】，48，42，68，84，6636，26，22， 42， 48，【】， 68，84，6636，26，22， 42，【】， 48， 68，84，6636，26，22， 42，46， 48，

60、68，84，66,練習(xí),已知序列（2, 8, 7, 1, 3, 5, 6, 4），如果選用4作為樞軸，那么進(jìn)行一次分割后序列表現(xiàn)是怎樣的？答案：2，3，1，4，7，5，6，8,練習(xí),對(duì)序列(49,38,65,97,76,27,13,50)采用快速排序法進(jìn)行排序，以序列的第一個(gè)元素為基準(zhǔn)元素得到的劃分結(jié)果是__________________。答案：13，38，27，49，76，97，65，50,簡(jiǎn)單選擇排序示例,49,3

61、8,65,97,76,13,27,49’,,13,38,65,97,76,49,27,49’,,13,27,65,97,76,49,38,49’,,13,27,38,97,76,49,65,49’,,13,27,38,49,76,97,65,49’,,13,27,38,49,49’,97,65,76,,13,27,38,49,49’,65,97,76,,13,27,38,49,49’,65,76,97,例題,對(duì)數(shù)據(jù)元素序列(49，72，

62、68，13，38，50，97，27)進(jìn)行排序，前三趟排序結(jié)束時(shí)的結(jié)果依次為：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；該排序采用的方法是————答案：簡(jiǎn)單選擇排序,練習(xí),若對(duì)序列(49，38，65，97，76，13，27，50)采用選擇排序法排序，則第三趟結(jié)束后序列的狀態(tài)是___________________。,

63、練習(xí)答案,13，38，65，97，76，49，27，5013，27，65，97，76，49，38，5013，27，38，97，76，49，65，50,堆的定義，堆的生成,1964年威洛姆斯(J. willioms)提出堆排序?qū)儆跇?shù)型選擇排序，僅需要一個(gè)記錄大小的輔助空間，每個(gè)待排序記錄僅占有一個(gè)存儲(chǔ)空間。,堆的定義，堆的生成,定義：n個(gè)元素的序列{k1,k2,…,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱(chēng)之為堆：ki≤k2i且ki≤k2

64、i+1或ki≥k2i且ki≥k2i+1等價(jià)的樹(shù)的定義：如果一棵完全二叉樹(shù),其中每個(gè)節(jié)點(diǎn)的鍵值不小于(或者不大于)其子樹(shù)的所有節(jié)點(diǎn)的鍵值,則稱(chēng)這棵二叉樹(shù)為(最大值/最小值)堆(max/min heap),堆的定義，堆的生成,10,15,56,25,30,70,,,,,,10,15,56,25,30,70,小根堆示例,堆的定義，堆的生成,70,56,30,25,15,10,,,,,,70,56,30,25,15,10,大根堆示例

65、,堆的定義，堆的生成,堆排序：若在輸出堆頂?shù)淖钪抵螅沟檬Ｓ鄋－1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素中的次小值，如此反腐執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過(guò)程稱(chēng)為堆排序。,堆的定義，堆的生成,堆排序基本思想:將記錄集調(diào)整為堆輸出堆頂?shù)淖钪涤涗泴⑹Ｏ掠涗浿匦抡{(diào)整為一個(gè)堆重復(fù)2,3直至所有記錄被輸出堆排序關(guān)鍵問(wèn)題:如何將一個(gè)記錄集調(diào)整為堆?,堆的定義，堆的生成,堆生成/調(diào)整算法:從樹(shù)的最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始,也就是從

66、數(shù)組的第length/2-1個(gè)元素開(kāi)始調(diào)整每次比較當(dāng)前節(jié)點(diǎn)和及其左右子節(jié)點(diǎn),取三者中最大者作為根按逆層次序考察,直至根節(jié)點(diǎn),也就是數(shù)組的第一個(gè)元素,堆的定義，堆的生成,堆排序算法：先將初始堆調(diào)整成一個(gè)最大值堆；然后將最值與最后一個(gè)元素對(duì)調(diào)，將去除最后一個(gè)元素后剩余的堆重新調(diào)整為一個(gè)最大值堆；繼續(xù)以上過(guò)程直至最后一個(gè)元素。,91,88,42,23,24,16,05,13,,,,,,,,91,88,42,23,24,16,05,1

67、3,（a）初始堆R[1]到R[8],,堆的定義，堆的生成,13,88,42,23,24,16,05,91,,,,,,,,13,88,42,23,24,16,05,91,（b）第一趟排序之后,堆的定義，堆的生成,（c）重建的堆R[1]到R[7],88,24,42,23,13,16,05,91,,,,,,,,88,24,42,23,13,16,05,91,,堆的定義，堆的生成,05,24,42,23,13,16,88,91,,,,,,,,0

68、5,24,42,23,13,16,88,91,（d）第二趟排序之后,堆的定義，堆的生成,（e）重建的堆R[1]到R[6],42,24,16,23,13,05,88,91,,,,,,,,42,24,16,23,13,05,88,91,,堆的定義，堆的生成,（f）第三趟排序之后,05,24,16,23,13,42,88,91,,,,,,,,05,24,16,23,13,42,88,91,堆的定義，堆的生成,（g）重建的堆R[1]到R[5],