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

1、整理ppt數(shù)據(jù)結(jié)構(gòu)2016MSE考研沖刺 整理ppt課程安排n課程介紹n棧、隊(duì)列和向量 n樹n查找n排序n圖整理ppt課程目的n（以最小代價(jià)）通過考試！n不是成為專家n不是初學(xué)授課整理ppt試題結(jié)構(gòu)n考試滿分60分n考試題型：問答、分析、編程整理ppt樣題問答和編程題n插入排序、選擇排序、冒泡排序、快速排序中最快的排序方法是_n試論述什么叫Hash沖突及有那些處理方法n編程實(shí)現(xiàn)對二叉樹所有節(jié)點(diǎn)的統(tǒng)計(jì)整理ppt課程安排n課程介紹n棧、隊(duì)列和向量 n樹n查找n排序n圖整理ppt鏈表、棧和隊(duì)列n大綱描述：q單鏈表,雙向鏈表,環(huán)形鏈表,帶哨兵節(jié)點(diǎn)的鏈表q棧的基本概念和性質(zhì),棧ADT及其順序,鏈接實(shí)現(xiàn);

2、棧的應(yīng)用;棧與遞歸;q隊(duì)列的基本概念和性質(zhì),隊(duì)列ADT及其順序,鏈接實(shí)現(xiàn);隊(duì)列的應(yīng)用;q向量基本概念和性質(zhì);向量ADT及其數(shù)組、鏈接實(shí)現(xiàn);整理ppt線性表基本概念和性質(zhì)n線性表q是n個(gè)數(shù)據(jù)元素的有限序列q常見線性表包括數(shù)組、鏈表、棧、隊(duì)列等n線性表的兩種實(shí)現(xiàn)方式q順序q鏈?zhǔn)絨對比：插入（有序、無序）、刪除、查找、讀取整理ppt環(huán)形鏈表n環(huán)形鏈表q又稱循環(huán)列表，是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)元素的指針域指向頭結(jié)點(diǎn)整理ppt棧的基本概念和性質(zhì)n棧：q棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表q后進(jìn)先出特性（LIFO）q棧頂、棧底、出棧、入棧整理ppt例題n設(shè)有一個(gè)棧S，元素S1

3、, S2, S3, S4, S5, S6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)镾2, S3, S4, S6, S5, S1，則棧的容量至少應(yīng)為多少？ n答案：3整理ppt棧的基本概念和性質(zhì)n設(shè)計(jì)遞歸問題的非遞歸算法一般需要用到棧機(jī)制n三個(gè)數(shù)a、b、c進(jìn)棧，不可能出現(xiàn)c、a、b順序出棧整理ppt例題n若某棧的輸入序列為a、b、c，則所有可能的出棧序列有_種，所有不可能的出棧序列有_種。n答案：5，1整理ppt例題n若棧的輸入序列為1,2,3,4，則是不可能的棧輸出序列之一。n答案：4，3，1，2整理ppt習(xí)題n若某棧的輸入序列為a、b、c、d，則所有可能的出棧序列有_種，所有不可能的出棧序列有_種。

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

5、答案： a b cd整理ppt例題n中綴表達(dá)式（a + b） c d轉(zhuǎn)為后綴表達(dá)式是？n答案： a b cdn思路：q數(shù)字位序不變，運(yùn)算符位置改變q后綴表達(dá)式無括號(hào)，運(yùn)算順序同中綴表達(dá)式整理ppt習(xí)題n中綴表達(dá)式A-(B+C)*D/E的后綴形式是_。整理ppt練習(xí)n中綴表達(dá)式a * ( b + c ) / d轉(zhuǎn)為后綴表達(dá)式是？整理ppt例題n計(jì)算后綴表達(dá)式1 2 + 4 * 2 /的值為？n答案：6n思路：q順序計(jì)算q或 轉(zhuǎn)換為中綴表達(dá)式計(jì)算整理ppt習(xí)題n計(jì)算后綴表達(dá)式3 2 4 * 2 / 3的值為？整理ppt遞歸n一個(gè)直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)，稱為遞歸函數(shù)q

6、優(yōu)點(diǎn)：結(jié)構(gòu)清晰、程序易讀、正確性容易得到證明q缺點(diǎn)：效率相對較低整理ppt隊(duì)列的基本概念和性質(zhì)n隊(duì)列：q隊(duì)列是限定僅在表的一頭進(jìn)行插入、另一頭進(jìn)行刪除操作的線性表q先進(jìn)先出特性（FIFO）q隊(duì)尾、隊(duì)頭、入隊(duì)、出隊(duì)整理ppt例題n在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)頭元素是，隊(duì)尾元素是。n答案：c，d整理ppt雙向隊(duì)列n雙向隊(duì)列：q亦稱雙端隊(duì)列（Deque）q是限定插入和刪除操作在表的兩端進(jìn)行的線性表q可以用于包裝產(chǎn)生棧和隊(duì)列整理ppt課程安排n課程介紹n棧、隊(duì)列和向量 n樹n查找n排序n圖整理ppt樹 n大綱描述：q樹的基本概念和術(shù)語；樹的前序、中序、

7、后序、層次序遍歷；q二叉樹及其性質(zhì)；普通樹與二叉樹的轉(zhuǎn)換；q樹的存儲(chǔ)結(jié)構(gòu),標(biāo)準(zhǔn)形式;完全樹(complete tree)的數(shù)組形式存儲(chǔ);q樹的應(yīng)用，Huffman樹 。 整理ppt樹的基本概念和術(shù)語n樹：q是n（n0）個(gè)結(jié)點(diǎn)的有限集q在任意一棵非空樹中：n有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)n當(dāng)n1時(shí)，其余結(jié)點(diǎn)可以分為m（m0）個(gè)互不相交的有限集，其中每個(gè)集合本身又是一棵樹，并且稱為根的子樹1.樹屬于層次結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)整理ppt樹的基本概念和術(shù)語n節(jié)點(diǎn)n標(biāo)簽n父節(jié)點(diǎn)、子節(jié)點(diǎn)、兄弟節(jié)點(diǎn)、祖先節(jié)點(diǎn)、子孫節(jié)點(diǎn)n路徑、樹枝n根、葉子n次數(shù)n內(nèi)部節(jié)點(diǎn)、外部節(jié)點(diǎn)n樹的次數(shù)、K次樹n節(jié)點(diǎn)層次、樹的高度和深度n子樹n

8、有序樹、無序樹n森林、果園整理ppt例題整理ppt例題n列出如上圖所示樹的所有葉子結(jié)點(diǎn)q答案：K,L,F,G,M,I,Jn列出如上圖所示樹的所有分支結(jié)點(diǎn)q答案：A,B,C,D,E,Hn樹A為幾次樹？子樹B呢？q答案：3，2n前頁圖所示樹的高度為多少？q答案：4整理ppt樹的基本概念和術(shù)語n如果將樹中結(jié)點(diǎn)的各子樹看作從左到右有序的,則該樹為有序樹(ordered tree),否則為無序樹。n森林(forest)是m棵互不相交的樹的集合。n如果把一棵樹的根砍去，剩下的部分就是森林。n如果原來的樹是有序的,則砍去根后的森林也是有序的,此時(shí)稱該森林為有序森林或果園。整理ppt二叉樹及其性質(zhì)n二叉樹（B

9、inary Tree）q另一種樹形結(jié)構(gòu)，特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹，且子樹有左右之分，其次序不能任意顛倒n二叉樹可能的五種基本形態(tài)整理ppt二叉樹及其性質(zhì)n在二叉樹的第i層上至多有2i1個(gè)結(jié)點(diǎn)（i1）整理ppt例題n一棵二叉樹第五層上至多有多少個(gè)結(jié)點(diǎn)？至少多少？n答案：16，1整理ppt二叉樹及其性質(zhì)n深度為k的二叉樹至多有2k1個(gè)結(jié)點(diǎn)（k1）整理ppt例題n深度為n(n0)的二叉樹最多有_個(gè)結(jié)點(diǎn)。n答案：2n-1整理ppt例題n一棵深度為5的二叉樹至多有多少個(gè)結(jié)點(diǎn)？至少多少？n答案：31，5整理ppt例題n高度為h(h0)的二叉樹最少有_個(gè)結(jié)點(diǎn)？n答案：h整理ppt二叉樹及其性質(zhì)n對于任

10、何二叉樹,如果葉子節(jié)點(diǎn)數(shù)為n0,度為2的節(jié)點(diǎn)數(shù)為n2,則n0=n2+1整理ppt例題n在一棵二叉樹中有n0個(gè)葉結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，則n2=_。n答案： n0 1整理ppt例題n若一棵二叉樹有10個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)的點(diǎn)個(gè)數(shù)為_。n答案：9整理ppt例題n若一二叉樹有2度結(jié)點(diǎn)100個(gè)，則其葉結(jié)點(diǎn)有多少個(gè)？n答案：101整理ppt例題n若二叉樹中度為2的結(jié)點(diǎn)有15個(gè)，度為1的結(jié)點(diǎn)有10個(gè)，共有多少個(gè)結(jié)點(diǎn)？n答案：41整理ppt例題n在一棵度為3的樹中，度為3的結(jié)點(diǎn)有2個(gè)，度為2的結(jié)點(diǎn)有1個(gè)，度為1的結(jié)點(diǎn)有2個(gè)，那么，該樹有_個(gè)葉結(jié)點(diǎn)。n答案：6n構(gòu)造法整理ppt二叉樹及其性質(zhì)n

11、滿二叉樹：q一棵深度為k且有2k1個(gè)結(jié)點(diǎn)的二叉樹q可以對滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定編號(hào)從根開始，自上而下，自左而右。n完全二叉樹：q深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱為完全二叉樹。整理ppt二叉樹及其性質(zhì)n完全二叉樹特點(diǎn)：q葉子結(jié)點(diǎn)只可能出現(xiàn)在層次最大的兩層上q對任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，其左下分支的子孫的最大層次必為l或者l1。n深度為k的完全二叉樹第k層最少1個(gè)結(jié)點(diǎn)，最多2k-1-1個(gè)結(jié)點(diǎn)；整棵樹最少2k-1個(gè)結(jié)點(diǎn)，最多2k-2個(gè)結(jié)點(diǎn)整理ppt例題n若某完全二叉樹的深度為h，則該完全二叉樹中至少

12、有_個(gè)結(jié)點(diǎn)。n答案：2h-1整理ppt例題n若深度為6的完全二叉樹的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹一共有_個(gè)結(jié)點(diǎn)。n答案：25-1+334整理ppt例題n一個(gè)具有767個(gè)結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)個(gè)數(shù)為_。 n答案：384n分析：可以根據(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ù)，由二叉樹的性質(zhì)可知：n0n21，則n= n0n1n2（其中n為完全二叉樹的結(jié)點(diǎn)總數(shù)），由上述公式把n2消去得：n= 2n0+n11，由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能0或1，由此得到n0（n1）/2或n0n/2，合并成一個(gè)公式：n0（n1）/2

13、，就可根據(jù)完全二叉樹的結(jié)點(diǎn)總數(shù)計(jì)算出葉子結(jié)點(diǎn)數(shù)。本題計(jì)算得：384。整理ppt二叉樹及其性質(zhì)n具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1整理ppt例題n具有2000個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為_。n答案：11整理ppt二叉樹及其性質(zhì)n如果含有n 1個(gè)節(jié)點(diǎn)的二叉樹的高度為log2n1,將其所有結(jié)點(diǎn)按層次序編號(hào),則對于任一節(jié)點(diǎn)j(1j n),有q如果j=1,則節(jié)點(diǎn)j是樹的根,無雙親;如果j1,則其父節(jié)點(diǎn)parent(j)是節(jié)點(diǎn)j/2q如果2jn,則節(jié)點(diǎn)j無左子節(jié)點(diǎn);否則其左子節(jié)點(diǎn)為2jq如果2j+1n,則節(jié)點(diǎn)j無右子節(jié)點(diǎn);否則其右子節(jié)點(diǎn)為2j+1n證明整理ppt完全樹的數(shù)組形式存儲(chǔ)n完全樹的數(shù)

14、組形式存儲(chǔ)算法q將其編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組下標(biāo)為i1的分量中整理ppt例題n已知數(shù)組20,30,19,87,30,40表示一棵完全二叉樹，請畫出該樹。整理ppt練習(xí)答案整理ppt樹的遍歷n樹的遍歷 q按某種搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)均被訪問一次僅且一次q二叉樹的遍歷可分為前序、中序、后序、層次序等q普通樹的遍歷可以分為先根、后根、層次序等整理ppt樹的遍歷n二叉樹的遍歷q前序、中序、后序定義q層次序：從上而下，從左至右n常見問題q已知樹寫遍歷結(jié)果q已知遍歷結(jié)果畫樹n依據(jù)：二叉樹的前序和中序遍歷可以唯一確定一棵二叉樹n思路：前序定根，中序定左右q遞歸和非遞歸算法實(shí)現(xiàn)整理ppt

15、例題n寫出左圖所示二叉樹的前序、中序、后序、層次序遍歷結(jié)果整理ppt例題答案n前序：ABDCEFGn中序：DBAECFGn后序：DBEGFCAn層次序：ABCDEFG整理ppt例題n假設(shè)一棵二叉樹的前序遍歷為EBADCHGFIKJ，中序遍歷為ABCDEFGHIJK，請畫出該樹。整理ppt例題答案整理ppt樹的遍歷n普通樹的遍歷q前根：先遍歷根結(jié)點(diǎn)，再依次前根遍歷各棵子樹q后根：先后根遍歷各課子樹，再遍歷根結(jié)點(diǎn)q已知樹寫遍歷結(jié)果q已知遍歷結(jié)果畫樹n思路：先根定根，后根定子樹整理ppt例題n寫出如右圖所示樹的先根、后根、層次序遍歷結(jié)果整理ppt例題答案n前序： ABECFGHDn后序：EBFHGC

16、DAn層次序：ABCDEFGH整理ppt練習(xí)給出如圖所示樹的先根、后根和層次序遍歷結(jié)果整理ppt練習(xí)答案n前根：ABEFHIGCJKLDMNOQPn后根：EHIFGBKLJCNQOPMDAn層次序：ABCDEFGJMHIKLNOPQ整理ppt例題n畫出和下列已知序列對應(yīng)的樹T：樹的先根次序訪問序列為GFKDAIEBCHJ樹的后根次序訪問序列為DIAEKFCJHBG整理ppt例題答案整理ppt普通樹與二叉樹的轉(zhuǎn)換n對于任意k次樹到相應(yīng)二叉樹的轉(zhuǎn)換算法q對于具有子節(jié)點(diǎn)n1,n2nk的節(jié)點(diǎn)n,將n1作為其左子節(jié)點(diǎn),且kj+1作為kj(1 j k-1)的右子節(jié)點(diǎn)n思路：“不同層在左，同層在右”整理pp

17、t普通樹與二叉樹的轉(zhuǎn)換n對于任意森林到相應(yīng)二叉樹的轉(zhuǎn)換算法為 q設(shè)T=(T1,T2.Tm)為m(m0)棵樹的序列,而BT (T1,T2.Tm)為相應(yīng)的二叉樹,則n如果m=0,則BT為空樹n如果m0,則T1的根節(jié)點(diǎn)就是BT的根節(jié)點(diǎn),而BT的左子樹是T1的子樹T11,T12T1K轉(zhuǎn)換成的BTl(T11,T12T1K),其右子樹為BTr(T2.Tm)整理ppt例題n將下頁圖所示森林轉(zhuǎn)換為等價(jià)的二叉樹整理ppt例題整理ppt例題答案整理ppt練習(xí)將如圖所示樹轉(zhuǎn)換為二叉樹整理ppt練習(xí)答案整理pptHuffman樹nHuffman樹：q又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹n基本概念：q樹的路徑長度：從

18、根到每一結(jié)點(diǎn)的路徑長度之和。q結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積。q樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記做WPL。整理pptHuffman樹n基本概念：q假設(shè)有n個(gè)權(quán)值wi，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子的結(jié)點(diǎn)帶權(quán)為wi，則其中WPL最小的二叉樹稱為最優(yōu)二叉樹或赫夫曼樹n算法q見下頁整理pptHuffman算法(1) 由給定的n個(gè)權(quán)值w0, w1, w2, , wn-1，構(gòu)造具有n棵二叉樹的集合F = T0, T1, T2, , Tn-1，其中每一棵二叉樹Ti只有一個(gè)帶有權(quán)值wi的根結(jié)點(diǎn)，其左、右子樹均為空。(2) 在F中選取兩

19、棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。(3) 在F中刪去這兩棵二叉樹，加入新得的樹。(4) 重復(fù)(2) (3)，直到F只含一棵樹為止。這棵樹就是赫夫曼樹整理pptZKFCUDL E2724323742421202Z7K24F32C37U42D42L120EStep 12Z7K24F32C37U42D42L120E92Z7K24F32C37U42D42L120E933Round 1Round 2例題整理ppt2Z7K24F32C37U42D42L120E93365Round 3整理ppt2Z7K24F32C37

20、U42D42L120E9336579Round 4整理ppt2Z7K24F32C37U42D42L120E9336579107Round 5整理ppt2Z7K24F32C37U42D42L120E9336579107186Round 6整理ppt2Z7K24F32C37U42D42L120E9336579107186306Round 7 (final)整理pptHuffman編碼n編碼：等長編碼/不等長編碼n前綴編碼：若要設(shè)計(jì)長短不等的編碼，則必須是任一個(gè)字符的編碼抖不是另一個(gè)字符編碼的前綴，這種編碼叫做前綴編碼nHuffman編碼：以n種字符出現(xiàn)的頻率做權(quán)，設(shè)計(jì)一棵赫夫曼樹，由此得到的前綴編

21、碼稱為Huffman編碼整理ppt例題LetterFreqCodeBitsC3211104D421013E12001F24111115K71111016L421103U371003Z211110062Z7K24F32C37U42D42L120E933657910718630600000111111001整理ppt習(xí)題n某通訊系統(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樹，并給出相應(yīng)的Huffman編碼。整理ppt習(xí)題答案整理ppt習(xí)題答案nA：0110nB：

22、10nC：1110nD：1111nE：110nF：00nG：0111nH：010整理ppt課程安排n課程介紹n棧、隊(duì)列和向量 n樹n查找n排序n圖整理ppt查找 n大綱描述：q查找的基本概念；對線性關(guān)系結(jié)構(gòu)的查找，順序查找，二分查找；qHash查找法,常見的Hash函數(shù)(直接定址法,隨機(jī)數(shù)法),hash沖突的概念, 解決沖突的方法(開散列方法/拉鏈法,閉散列方法/開址定址法),二次聚集現(xiàn)象;qBST樹定義,性質(zhì),ADT及其實(shí)現(xiàn),BST樹查找,插入,刪除算法;q平衡樹 (AVL) 的定義,性質(zhì),ADT及其實(shí)現(xiàn),平衡樹查找,插入算法,平衡因子的概念;q優(yōu)先隊(duì)列與堆,堆的定義,堆的生成,調(diào)整算法;范

23、圍查詢;整理ppt查找的基本概念n查找表(search table)：q具有同一類型數(shù)據(jù)元素(經(jīng)常稱為記錄)的集合n查找表的基本操作有：q查找某個(gè)“特定”記錄是否在表中q查找到后取出某個(gè)“特定”記錄的各個(gè)數(shù)據(jù)項(xiàng)q向表中插入記錄q從表中刪除記錄整理ppt查找的基本概念n靜態(tài)查找表(static search table)：q僅用于查詢的查找表。n動(dòng)態(tài)查找表(dynamic search table):q若在查找過程中需同時(shí)插入表中不存在的記錄;或者需要?jiǎng)h除記錄,則稱之為動(dòng)態(tài)查找表。n關(guān)鍵字/鍵值(key) ：q記錄某個(gè)數(shù)據(jù)項(xiàng)的值,用其可以標(biāo)示該記錄q當(dāng)記錄只有一個(gè)數(shù)據(jù)項(xiàng)時(shí),其關(guān)鍵字即為該記錄的值

24、q如果一個(gè)key可以唯一標(biāo)示一個(gè)就,則稱之為主關(guān)鍵字(primary key),否則稱之為次關(guān)鍵字(secondary key)整理ppt查找的基本概念n查找(search)：q在一個(gè)查找表中找出具有“特定”鍵值的那些記錄q所謂查找成功是指在查找表中找到了滿足條件的記錄,此時(shí)一般會(huì)返回找到的記錄,或者返回記錄的位置信息,或者僅僅返回找到(true)q否則稱為查找失敗,此時(shí)一般返回空指針,或特殊值,或者僅僅返回沒有找到(false),有時(shí)也會(huì)就此插入這個(gè)元素整理pptBST樹定義，性質(zhì)， 實(shí)現(xiàn)n二叉排序樹(Binary Sorted Tree)q又稱二叉搜索樹或二叉查找樹q或者是一棵空樹；q或者

25、是具有下列性質(zhì)的二叉樹：n如果左子樹非空,則左子樹中所有節(jié)點(diǎn)的鍵值均小于它的根結(jié)點(diǎn)的值；n如果右子樹非空,則右子樹中所有節(jié)點(diǎn)的鍵值均大于它的根結(jié)點(diǎn)的值；n它的左右子樹也都是二叉排序樹。整理pptBST樹定義，性質(zhì)， 實(shí)現(xiàn)n二叉排序樹性質(zhì) q如果對二叉排序樹進(jìn)行中序遍歷,則得到一個(gè)從小到大排好序的列表,所以可以得到一種簡單的排序方法叫做“樹排序”(treesort)。q我們也可以根據(jù)這個(gè)性質(zhì)定義二叉排序樹為:如果一棵樹按中序遍歷為排好序的,則這棵樹是二叉排序樹。整理pptBST樹查找，插入，刪除算法nBST樹查找，插入，刪除算法q畫圖q算法整理ppt例題n已知BST樹如左，請畫出插入16，再刪除

26、36之后的BST樹整理ppt例題答案整理ppt例題n試求按關(guān)鍵字序列（12，1，4，3，7，8，1O，2）插入生成的二叉排序樹整理ppt例題答案整理ppt練習(xí)n假設(shè)結(jié)點(diǎn)序列F（60，30，90，50，120，70，40，80），試用BST的插入算法，用F中的結(jié)點(diǎn)依次進(jìn)行插入，畫出由F中結(jié)點(diǎn)所構(gòu)成的BST樹T1；再用刪除算法，依次刪除40，70，60，畫出刪除后的BST樹T2。整理ppt練習(xí)答案整理ppt平衡樹n平衡因子（balanced factor）q二叉樹上任一節(jié)點(diǎn)的左子樹高度減去右子樹高度的差nAVL Tree，根據(jù)其三位發(fā)明者(Adelson-Velskii and Landis)的名

27、字命名n一棵BST樹中每個(gè)節(jié)點(diǎn)平衡因子的絕對值不超過1整理ppt平衡樹n基本思想 :q在插入或刪除節(jié)點(diǎn)后對新樹進(jìn)行判斷,如果新樹已經(jīng)變得不平衡,則通過旋轉(zhuǎn)(rotation)的方法對樹進(jìn)行重組/改組(re-arrange),使得重組后的樹在保持查找樹特性的同時(shí)保持平衡n所謂旋轉(zhuǎn):q通過改變支撐點(diǎn)來維持平衡q順時(shí)針旋轉(zhuǎn)為右旋;逆時(shí)針旋轉(zhuǎn)為左旋q可以進(jìn)行連續(xù)的多次旋轉(zhuǎn)整理ppt平衡樹整理ppt算法代碼及基本的時(shí)間復(fù)雜度分析查找方法查找方法平均時(shí)間平均時(shí)間順序查找O(n)二分查找O(logn)BST查找O(logn)AVL查找O(logn)整理pptHash查找法，常見的Hash函數(shù)n哈希（Hash

28、）函數(shù)：q在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對應(yīng)。這個(gè)對應(yīng)關(guān)系f為哈希函數(shù)。按這個(gè)思想建立的表為哈希表。q哈希函數(shù)的設(shè)定可以很靈活，只要使得任何關(guān)鍵字的哈希函數(shù)值都落在表長允許范圍之內(nèi)即可。整理pptHash查找法，常見的Hash函數(shù)n練習(xí)：q已知線性表關(guān)鍵字集合為：S = and, begin, do, end, for, go, if, repeat, then, until, while，求哈希函數(shù)。n答案：qH(key)=key0 a;即為關(guān)鍵字key中的第一個(gè)字母在字母表a, b, c, ., z中的序號(hào)整理pptHas

29、h查找法，常見的Hash函數(shù)n直接定址法q直接取key或者key的某個(gè)線性函數(shù)值 h(key) = a*key +b, a,b為常數(shù)q如前面的例子,又如人口普查時(shí)使用年齡,出生年份等整理pptHash查找法，常見的Hash函數(shù)n除留余數(shù)法q選擇一個(gè)適當(dāng)?shù)恼麛?shù)P，用P去除關(guān)鍵字，取所得得余數(shù)作為散列地址，即：H(key) = key%Pq方法的關(guān)鍵是選取適當(dāng)?shù)腜。選擇P最好不要是偶數(shù)，也不要是基數(shù)的冪。一般地選P為小于或等于散列表長度m的某個(gè)最大素?cái)?shù)比較好。q缺點(diǎn):n整數(shù)相除速度較慢整理pptHash查找法，常見的Hash函數(shù)n如:m = 8，16，32，64，128，256，512，1024

30、P = 7，13，31，61，127，251，503，1019整理ppt解決沖突的方法n對不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對該哈希函數(shù)來說稱作同義詞。n在一般情況下，沖突只能盡可能的少，而不能完全避免。整理ppt解決沖突的方法n共同思想: 將具有相同函數(shù)值的記錄存作一個(gè)鏈n閉散列方法/開址定址法q沖突記錄存儲(chǔ)在表內(nèi)n開散列方法/鏈地址法q沖突記錄存儲(chǔ)在表外整理ppt解決沖突的方法n基本思想q當(dāng)沖突發(fā)生時(shí)，使用某種方法在散列表中形成一個(gè)探查序列(也稱之為鏈)，按此序列逐個(gè)單元的查找，直到找到一個(gè)指定的關(guān)鍵字或碰到一個(gè)開放的地址（單元為空）為止。qHj =

31、( H(key) + dj ) MOD m n1 j m-1;m為hash表長度ndj為增量數(shù)列,各種方法的不同就區(qū)別在取不同的增量數(shù)列上整理ppt解決沖突的方法n常用的增量數(shù)列:q線性探測法q二次探測法q偽隨機(jī)法q再哈希法/二次哈希法q桶式散列法整理ppt解決沖突的方法n線性探測法q取dj = 1,2,m-1q將散列表看成是一個(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，則無論是做插入操作還是做查找操作，都意味著

32、失敗。整理ppt解決沖突的方法n線性探測法q缺點(diǎn):n特別容易產(chǎn)生聚集n鏈非常長整理ppt解決沖突的方法n拉鏈法q若選定的散列函數(shù)的值域?yàn)?到m-1，則可將散列表定義為一個(gè)由m個(gè)單鏈表的鏈表頭指針組成的指針數(shù)組HTP(m)，凡是散列地址為i的結(jié)點(diǎn)，均插入到以HTP(i)為頭指針的單鏈表中。整理ppt26416815064436381251250123456789101112若一組關(guān)鍵字為（若一組關(guān)鍵字為（26，36，41，38，44，15，68，12，06，51，25），散列函數(shù)定），散列函數(shù)定義為：義為：H(key) = key%13。用拉練法建立的散列表為：用拉練法建立的散列表為：整理ppt

33、解決沖突的方法n拉鏈法q優(yōu)點(diǎn):n不會(huì)堆積,所以平均查找時(shí)間較短n動(dòng)態(tài)申請空間,適用于造表前無法確定表長的情況n刪除處理簡單快速n鏈長易控制,一般較短整理ppt解決沖突的方法n負(fù)載系數(shù)的定義和作用q設(shè)key的數(shù)量為N,散列表的大小為M,則N/M稱負(fù)載系數(shù)或裝填因子(loadfactor),它表現(xiàn)了平均情況下每個(gè)鏈的長度q我們一般預(yù)先規(guī)定好這個(gè)值,然后當(dāng)不夠的時(shí)候再增加hash表的長度(re-hash),這樣可以保證鏈的平均長度不超過負(fù)載系數(shù)整理ppt解決沖突的方法n增加時(shí)一般作兩倍的增加，而且增加后需要將所有的表元素全部重新求值放置(因?yàn)閙變了)n一般取值為0.75整理ppt解決沖突的方法n聚集

34、(clustering)現(xiàn)象又稱二次聚集,指處理沖突中發(fā)生的兩個(gè)第一個(gè)hash地址不同的記錄爭奪同一個(gè)后繼hash地址的情況,常發(fā)生在有大量key對應(yīng)于同一Hash函數(shù)值的情況下n聚集現(xiàn)象僅出現(xiàn)于使用閉散列方法時(shí)n當(dāng)使用線性探測法時(shí)特別容易發(fā)生聚集現(xiàn)象,很容易使散列查詢退化為對于鏈表或者數(shù)組的順序查詢整理ppt解決沖突的方法n假設(shè)Hash函數(shù)為H(key)=key MOD 11,表中已經(jīng)有key 17,60,29,此時(shí)分別占據(jù)6,7,5;然后再插入38n此時(shí)可以發(fā)現(xiàn),當(dāng)表中5,6,7都被占據(jù)后,凡是函數(shù)值為5,6,7,8的key都將爭奪8這個(gè)位置!整理ppt例題n在初始為空的哈希表中依次插入關(guān)

35、鍵字序列(MON，TUE，WED，THU，F(xiàn)RI，SAT，SUN), 哈希函數(shù)為H(k)=i MOD 7，其中，i為關(guān)鍵字k的第一個(gè)字母在英文字母表中的序號(hào)，地址值域?yàn)?: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 D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON整

36、理ppt例題n若待散列的序列為(18,25,63,50,42,32,9)，哈希函數(shù)為H(key)=key MOD 9，哈希表長度為9，與18發(fā)生沖突的元素有_個(gè)n答案：2整理ppt例題n已知一組關(guān)鍵字為（26，36，41，38，44，15，68，12，06，51，25），用線性探查法解決沖突構(gòu)造這組關(guān)鍵字的散列表，假設(shè)利用除余法構(gòu)造散列函數(shù)。整理ppt例題答案q為了減少?zèng)_突，通常令裝填因子Apr-Aug2-Dec3-Feb5-Jan-Jun-Jul6-Mar-May7-Oct-Nov9-Sep整理ppt練習(xí)答案012345678910111213141516AprAugDecFebJanMar

37、MayJunJulSepOctNov整理ppt范圍查詢n定義:q在指定集合中有多少記錄的關(guān)鍵字是落在指定范圍中n一維的情況:q記錄可以看作直線上的點(diǎn)q問題可以看作有多少點(diǎn)落入指定線段區(qū)域中整理ppt課程安排n課程介紹n棧、隊(duì)列和向量 n樹n查找n排序n圖整理ppt排序 n大綱描述：q排序基本概念；q插入排序，希爾排序，選擇排序，快速排序，歸并排序，基數(shù)排序等排序算法基本思想；q算法代碼及基本的時(shí)間復(fù)雜度分析；q堆的定義，堆的生成。整理ppt排序基本概念n排序(Sorting) ：q重排一個(gè)記錄序列,使之成為按關(guān)鍵字有序q常見排序可分為以下五類：n插入排序（簡單插入排序、希爾排序）n交換排序（冒

38、泡排序、快速排序）n選擇排序（簡單選擇排序、堆排序）n歸并排序n計(jì)數(shù)排序（多關(guān)鍵字排序）整理ppt插入排序46 26 22 68 48 42 36 84 66 22*26 46 22 68 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*22 26 3

39、6 42 46 48 66 68 84 22*22 22* 26 36 42 46 48 66 68 84整理ppt希爾排序n定義qShell Sortq又稱“縮小增量排序”（Diminishing Increment Sort），也是一種屬于插入排序類的算法，但時(shí)間效率較其他排序方法有較大改進(jìn)q基本思想是：先將整個(gè)待排記錄序列分割為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插入排序整理ppt冒泡排序n交換排序的一種n依次比較相鄰的兩個(gè)待排序元素，若為逆序（遞增或遞減）則進(jìn)行交換，將待排序元素從左至右比較一遍稱為一趟“冒泡”n每趟冒泡都將待排序列中

40、的最大關(guān)鍵字交換到最后（或最前）位置n直到全部元素有序?yàn)橹?直到某次冒泡過程中沒有發(fā)生交換為止整理ppt快速排序n就平均時(shí)間而言，快速排序是目前被認(rèn)為最好的一種內(nèi)部排序方法,由C. A. R. Hoare發(fā)明n分治法(divide and conquer)思想的體現(xiàn)nUnix系統(tǒng)函數(shù)庫所提供的標(biāo)準(zhǔn)排序方法nC標(biāo)準(zhǔn)函數(shù)庫中的排序方法直接就命名為qsort()整理ppt快速排序n基本思想:q是對冒泡排序的一種改進(jìn)q選取一個(gè)軸值,然后根據(jù)此軸值通過一趟排序?qū)τ涗浖M(jìn)行一次分割,然后對分割后產(chǎn)生的兩個(gè)記錄子集分別進(jìn)行快速排序整理ppt快速排序n基本概念:q軸值(pivot):n書上稱樞軸n用于將記錄集

41、分割為兩個(gè)部分的那個(gè)鍵值q分割(partition):n將記錄集分為兩個(gè)部分,前面部分記錄的鍵值都比軸值小,后面部分的鍵值都比軸值大整理ppt快速排序整理ppt快速排序4938659776132749 38659776132749273865977613 492738 97761365492738139776 6549273813 76976549273813 49 76 97 654949temp整理ppt例題n寫出對于結(jié)點(diǎn)序列（46，26，22，68，48，42，36，84，66）進(jìn)行第一次分割后序列的情況，注意列出步驟的每一步。整理ppt例題答案【】26，22，68，48，42，36，8

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

43、答案：13，38，27，49，76，97，65，50整理ppt49386597761327491338659776492749132765977649384913273897764965491327384976976549132738494997657613273849496597761327384949657697整理ppt例題n對數(shù)據(jù)元素序列(49，72，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；

44、該排序采用的方法是n答案：簡單選擇排序整理ppt練習(xí)n若對序列(49，38，65，97，76，13，27，50)采用選擇排序法排序，則第三趟結(jié)束后序列的狀態(tài)是_。 整理ppt練習(xí)答案n13，38，65，97，76，49，27，50n13，27，65，97，76，49，38，50n13，27，38，97，76，49，65，50整理ppt堆的定義，堆的生成n1964年威洛姆斯(J. willioms)提出堆排序n屬于樹型選擇排序，僅需要一個(gè)記錄大小的輔助空間，每個(gè)待排序記錄僅占有一個(gè)存儲(chǔ)空間。整理ppt堆的定義，堆的生成n定義：qn個(gè)元素的序列k1,k2,kn當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆：nk

45、ik2i且kik2i+1或nkik2i且kik2i+1q等價(jià)的樹的定義：n如果一棵完全二叉樹,其中每個(gè)節(jié)點(diǎn)的鍵值不小于(或者不大于)其子樹的所有節(jié)點(diǎn)的鍵值,則稱這棵二叉樹為(最大值/最小值)堆(max/min heap)整理ppt堆的定義，堆的生成10155625307010 15 56 25 30 70小根堆示例小根堆示例整理ppt堆的定義，堆的生成70563025151070 56 30 25 15 10大根堆示例大根堆示例整理ppt堆的定義，堆的生成n堆排序：q若在輸出堆頂?shù)淖钪抵?，使得剩余n1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素中的次小值，如此反腐執(zhí)行，便能得到一個(gè)有序序列，這

46、個(gè)過程稱為堆排序。整理ppt堆的定義，堆的生成n堆排序基本思想:q 將記錄集調(diào)整為堆q 輸出堆頂?shù)淖钪涤涗泀 將剩下記錄重新調(diào)整為一個(gè)堆q 重復(fù)2,3直至所有記錄被輸出n堆排序關(guān)鍵問題:1.如何將一個(gè)記錄集調(diào)整為堆?整理ppt堆的定義，堆的生成n堆生成/調(diào)整算法:q從樹的最后一個(gè)非葉子節(jié)點(diǎn)開始,也就是從數(shù)組的第length/2-1個(gè)元素開始調(diào)整q每次比較當(dāng)前節(jié)點(diǎn)和及其左右子節(jié)點(diǎn),取三者中最大者作為根q按逆層次序考察,直至根節(jié)點(diǎn),也就是數(shù)組的第一個(gè)元素整理ppt堆的定義，堆的生成n堆排序算法：q先將初始堆調(diào)整成一個(gè)最大值堆；q然后將最值與最后一個(gè)元素對調(diào)，將去除最后一個(gè)元素后剩余的堆重新調(diào)整為一

47、個(gè)最大值堆；q繼續(xù)以上過程直至最后一個(gè)元素。整理ppt919188884242232324241616050513139188422324160513（a a）初始堆）初始堆R1R1到到R8R8堆的定義，堆的生成整理ppt131388884242232324241616050591911388422324160591（b b）第一趟排序之后）第一趟排序之后堆的定義，堆的生成整理ppt（c c）重建的堆）重建的堆R1R1到到R7R7888824244242232313131616050591918824422313160591堆的定義，堆的生成整理ppt050524244242232313131

48、616888891910524422313168891（d d）第二趟排序之后）第二趟排序之后堆的定義，堆的生成整理ppt（e e）重建的堆）重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891堆的定義，堆的生成整理ppt（f f）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891堆的定義，堆的生成整理ppt（g g）重建的堆）重建的堆R1R1到到R5R524242323161605051313424288889191242316051342889

49、1堆的定義，堆的生成整理ppt（h h）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891堆的定義，堆的生成整理ppt（i i）重建的堆）重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891堆的定義，堆的生成整理ppt（j j）第五趟排序之后）第五趟排序之后050513131616232324244242888891910513162324428891堆的定義，堆的生成整理ppt（k k）重建的堆）重建的堆R1R1到到R3R316161313050

50、5232324244242888891911613052324428891堆的定義，堆的生成整理ppt（l l）第六趟排序之后）第六趟排序之后050513131616232324244242888891910513162324428891堆的定義，堆的生成整理ppt（m m）重建的堆）重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891堆的定義，堆的生成整理ppt（n n）第七趟排序之后）第七趟排序之后050513131616232324244242888891910513162324428891堆的定義，堆的生成整理pp

51、t練習(xí)n已知序列88，91，42，23，24，16，5，13，用堆排序方法進(jìn)行排序，求排序過程中堆的狀況。整理ppt練習(xí)答案n91，88，42，23，24，16，5，13n13，88，42，23，24，16，5，91n88，24，42，23，13，16，5，91n5，24，42，23，13，16，88，91n42，24，16，23，13，5，88，91n5，24，16，23，13，42，88，91n24，23，16，5，13，42，88，91n13，23，16，5，24，42，88，91整理ppt練習(xí)答案n23，13，16，5，24，42，88，91n5，13，16，23，24，42，88，9

52、1n16，13，5，23，24，42，88，91n5，13，16，23，24，42，88，91n13，5，16，23，24，42，88，91n5，13，16，23，24，42，88，91整理ppt練習(xí)n序列（4, 1, 10, 14, 16, 9, 3, 2, 8, 7 ）是否是一個(gè)最大值堆？如果不是請將其調(diào)整為一個(gè)最大值堆，并且使用堆排序算法進(jìn)行排序，寫出過程中每步序列的變化狀況。整理ppt歸并排序nJon von Neumann于1945年提出n徹底的分治法,完全的等分(相對于快速排序而言)n適用于巨量數(shù)據(jù)的排序nJava類庫所提供的標(biāo)準(zhǔn)排序方法n所謂歸并是指將兩個(gè)或兩個(gè)以上有序表合并為一

53、個(gè)有序表的過程整理ppt歸并排序(25) (57) (48) (37) (12) (92) (86)(25 57) (37 48) (12 92) (86)(25 37 48 57) (12 86 92)(12 25 37 48 57 86 92)整理ppt基數(shù)排序n多關(guān)鍵字排序:q根據(jù)排序時(shí)首先選取高位低位的不同,可以分為 :n最高位優(yōu)先(Most Significant Digit First,MSD)q主要通過遞歸實(shí)現(xiàn)q對人而言更自然n最低位優(yōu)先(Least Significant Digit First,LSD)q主要通過分配,收集過程實(shí)現(xiàn),重點(diǎn)研究q部分單關(guān)鍵字排序也可以當(dāng)作多關(guān)鍵字

54、排序來做n數(shù)字,字符串n以r為基的排序整理ppt基數(shù)排序n基數(shù)排序是一種典型的LSD排序方法,它利用“分配”和“收集”兩種運(yùn)算對單關(guān)鍵字進(jìn)行排序n此時(shí)往往是把單關(guān)鍵字看成是由多個(gè)關(guān)鍵字復(fù)合而成的,且每個(gè)關(guān)鍵字的基都相等整理ppt基數(shù)排序n基本思想:q設(shè)每個(gè)關(guān)鍵字有d位,基為r,共有n個(gè)記錄;則開r個(gè)隊(duì)列,每個(gè)隊(duì)列長度為n,將記錄分配到每個(gè)隊(duì)列中去,然后再收集起來,做d次結(jié)束q共需nr的空間整理ppt各種內(nèi)部排序方法的比較排序方法排序方法平均時(shí)間平均時(shí)間最壞時(shí)間最壞時(shí)間輔助存儲(chǔ)輔助存儲(chǔ)穩(wěn)定性穩(wěn)定性簡單排序O(n2)O(n2)O(1)穩(wěn)定快速排序O(nlogn)O(n2)O(logn)不穩(wěn)定堆排序

55、O(nlogn)O(nlogn)O(1)不穩(wěn)定歸并排序O(nlogn)O(nlogn)O(n)不穩(wěn)定基數(shù)排序 O(d(n+rd) O(d(n+rd)O(rd)穩(wěn)定整理ppt課程安排n課程介紹n棧、隊(duì)列和向量 n樹n查找n排序n圖整理ppt圖 n大綱描述：q圖的基本概念;q圖的存儲(chǔ)結(jié)構(gòu),鄰接矩陣,鄰接表;q圖的遍歷,廣度度優(yōu)先遍歷和深度優(yōu)先遍歷;q最小生成樹基本概念,Prim算法,Kruskal算法;q最短路徑問題,廣度優(yōu)先遍歷算法,Dijkstra算法,Floyd算法;拓?fù)渑判蛘韕pt圖的基本概念和術(shù)語n頂點(diǎn)、弧和邊n出弧、入弧n鄰接點(diǎn)n度、出度、入度n有向圖、無向圖n稀疏圖、稠密圖n權(quán)、網(wǎng)

56、n帶權(quán)圖、無權(quán)圖n子圖n連通圖整理ppt圖的存儲(chǔ)結(jié)構(gòu)n常用方法 :q數(shù)組表示法/鄰接矩陣 (Adjacency Matrix)法q鄰接表(Adjacency List)法q鄰接多重表*q十字鏈表法*整理ppt鄰接矩陣n設(shè)|V|=nn用一個(gè)n維矩陣V存儲(chǔ)頂點(diǎn)標(biāo)簽n用一個(gè)n*n矩陣E存儲(chǔ)頂點(diǎn)鄰接關(guān)系q對于E中每個(gè)元素evw,取值如下:n無權(quán)圖 :1E0否則n帶權(quán)圖 :權(quán)值 E且vw0v=w否則整理ppt鄰接矩陣n對于無向圖,鄰接矩陣呈上/下三角形,可以只存儲(chǔ)這部分內(nèi)容n一般用0表示無向圖的不鄰接,而用表示有向圖的不鄰接n合適存儲(chǔ)稠密圖n合適如果圖的主要功能是查詢整理ppt鄰接矩陣n在有向圖中, 統(tǒng)

57、計(jì)第 i 行 1 的個(gè)數(shù)可得頂點(diǎn) i 的出度，統(tǒng)計(jì)第 j 列 1 的個(gè)數(shù)可得頂點(diǎn) j 的入度n在無向圖中, 統(tǒng)計(jì)第 i 行 (列) 1 的個(gè)數(shù)可得頂點(diǎn)i 的度整理ppt例題n給出指定圖的鄰接矩陣整理ppt例題n給出指定圖的鄰接矩陣整理ppt鄰接表n設(shè)|V|=nn對于每個(gè)頂點(diǎn)v,使用一個(gè)單鏈表存儲(chǔ)所有與其鄰接的頂點(diǎn)wn使用一個(gè)n維的數(shù)組存儲(chǔ)所有單鏈表的表頭整理ppt鄰接表n對于鏈表中每個(gè)節(jié)點(diǎn),存儲(chǔ)以下信息 :q頂點(diǎn)w的名字;弧的信息(比如說權(quán));指向下個(gè)節(jié)點(diǎn)的引用n對于數(shù)組中每個(gè)元素,至少存儲(chǔ)以下內(nèi)容 :q節(jié)點(diǎn)v的名字;指向第一個(gè)鄰接頂點(diǎn)節(jié)點(diǎn)的引用n合適如果經(jīng)常要查詢頂點(diǎn)的前驅(qū),后驅(qū)以及插入,刪

58、除頂點(diǎn)或者弧/邊n此外還有逆鄰接表整理ppt鄰接表n在有向圖的鄰接表中,第 i 個(gè)邊鏈表鏈接的邊都是頂點(diǎn) i 發(fā)出的邊,也叫做出邊表.n在有向圖的逆鄰接表中,第 i 個(gè)邊鏈表鏈接的邊都是進(jìn)入頂點(diǎn) i 的邊,也叫做入邊表.n帶權(quán)圖的邊結(jié)點(diǎn)中須保存該邊上的權(quán)值 cost整理ppt例題n給出指定圖的鄰接表整理ppt例題n給出指定圖的鄰接表整理ppt例題n給出指定圖的鄰接表整理ppt圖的遍歷n圖的兩種最基本遍歷 :q深度優(yōu)先遍歷(depth-first traversal)q廣度優(yōu)先遍歷(breadth-first traversal)整理ppt圖的遍歷n對于深度優(yōu)先遍歷,頂點(diǎn)集合是一個(gè)棧類型集合n其

59、最優(yōu)先元素為棧頂元素n也可以使用遞歸方法n對于廣度優(yōu)先遍歷,頂點(diǎn)集合為一個(gè)隊(duì)列類型集合n其最優(yōu)先元素為隊(duì)列最前元素整理ppt例題n給出下圖的深度優(yōu)先遍歷子圖整理ppt例題n給出下圖的廣度優(yōu)先遍歷子圖整理ppt最小生成樹n生成樹q對于連通圖G(V,E), 支撐樹 T(V,E)為包含G中所有頂點(diǎn)的一個(gè)無回路連通子圖,即具有如下性質(zhì):nV = VnE有|V| -1條邊nT是連通的,為一棵樹q對于指定圖G,其支撐樹T不唯一整理ppt最小生成樹n最小生成樹:q設(shè)有邊帶權(quán)無向圖G,則其最小代價(jià)支撐樹T必須滿足:nT為G支撐樹nT所有邊的權(quán)之和是G所有支撐樹中最小的q圖G的最小代價(jià)支撐樹T不唯一,但所有T的

60、邊權(quán)和都相等整理ppt最小生成樹n兩種算法:qPrim算法: n逐步增長的方式建成一棵樹n每次挑選一條代價(jià)最小且不會(huì)構(gòu)成回路的邊加入正在建造的MST樹qKruskal算法: n先建造一個(gè)最小代價(jià)邊構(gòu)成的森林,最后合并為一棵樹n每次挑選頂點(diǎn)落在圖中不同連通分量上且不會(huì)構(gòu)成回路的代價(jià)最小的邊,直至樹建成整理pptPrim算法12346510158311624從一棵空樹 T開始, 隨機(jī)選一個(gè)頂點(diǎn),然后初始化為U = 1), T =整理pptPrim算法12346510158311624選取一個(gè)頂點(diǎn)w 不在U中,且其到U中某個(gè)頂點(diǎn)v的邊(v,w)的權(quán)最小,此時(shí)U=1,3 T= (1,3)整理pptPr