復(fù)習(xí)課(3)

1、主要內(nèi)容：1. 圖2.查找、排序,數(shù)據(jù)結(jié)構(gòu)學(xué)位考復(fù)習(xí)課(3),第七章 圖,考核內(nèi)容及要求：熟練掌握?qǐng)D的相關(guān)概念、性質(zhì)、存儲(chǔ)結(jié)構(gòu)熟練掌握遍歷：深度優(yōu)先遍歷、廣度優(yōu)先遍歷過程；熟練掌握連通分量的求法；熟練掌握最小生成樹、最短路徑概念與方法；掌握拓?fù)渑判?、關(guān)鍵路徑的求法及實(shí)現(xiàn)方法。,1 圖的定義、術(shù)語(yǔ)和存儲(chǔ)結(jié)構(gòu),圖：圖結(jié)構(gòu)中，任意兩個(gè)結(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)圖的抽象數(shù)據(jù)類型頂點(diǎn)、弧、邊有

2、向圖（digraph)有向圖G1=(V1,{A1})，其中V1={v1,v2,v3,v4},A1={,,,}無(wú)向圖(undigraph)無(wú)向圖G2=(V2,{E2})V2={v1,v2,v3,v4,v5}, E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)},有向圖,無(wú)向圖,頂點(diǎn)數(shù)n和邊(弧)的數(shù)目e：無(wú)向圖：有向圖：完全圖：有n(n-1)/2條邊的無(wú)向圖;

3、有向完全圖：有n(n-1)條弧的有向圖;稀疏圖、稠密圖子圖：G=(V,{E}),G’=(V’,{E’})，若V’ V,且E’ E,則稱G’為G的子圖鄰接點(diǎn)：無(wú)向圖中，(v,v’)∈E，則v,v’互為鄰接點(diǎn)；頂點(diǎn)v的度：與v相關(guān)聯(lián)的邊的數(shù)目，TD(v)有向圖中,若∈A，則頂點(diǎn)v鄰接到頂點(diǎn)v’，而頂點(diǎn)v’鄰接自v出度：以v為尾的弧的數(shù)目，OD(v)入度：以v為頭的弧的數(shù)目，ID(v) TD(v)=OD(

4、v)+ID(v),路徑：回路（環(huán)）簡(jiǎn)單路徑：頂點(diǎn)序列中頂點(diǎn)不重復(fù)的路徑。連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量：,一個(gè)連通圖的生成樹：一個(gè)極小連通子圖，含有圖中全部結(jié)點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。一棵有n個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊但有n-1條邊的圖不一定是生成樹有向圖：如果有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度都為1，則是一棵有向樹。,圖的存儲(chǔ)結(jié)構(gòu),數(shù)組表示法（鄰接矩陣）： 用兩個(gè)數(shù)組分別存放頂點(diǎn)信息和邊（?。?/p>

5、信息,G1.VEXS[4]=[V1 V2 V3 V4],G1,G2,圖的鄰接矩陣 A[i][j]=1 //若存在 A[i][j]=0 //若不存在 無(wú)向圖：第i行分量的和為結(jié)點(diǎn)vi的度 有向圖：第i行分量的和為結(jié)點(diǎn)vi的出度； 第i列分量的和為結(jié)點(diǎn)vi的入度 網(wǎng)的鄰接矩陣 A[

6、i][j]=無(wú)窮大 間無(wú)邊 =權(quán) 間有邊 問題：為什么放無(wú)窮大而不放0,鄰接表：一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為圖中的每一個(gè)頂點(diǎn)創(chuàng)建一個(gè)單鏈表，其中的結(jié)點(diǎn)表示依附于頂點(diǎn)的邊(以該頂點(diǎn)為尾的弧),無(wú)向圖的鄰接表中，頂點(diǎn)v的度就是該頂點(diǎn)的單鏈表中的結(jié)點(diǎn)數(shù)；有向圖中，第i個(gè)鏈表的結(jié)點(diǎn)數(shù)是該頂點(diǎn)的出度；如何求有向圖中頂點(diǎn)的入度？——有向圖的逆鄰接表。

7、,有向圖G1的鄰接表,有向圖G1的逆鄰接表,十字鏈表：有向圖的鏈?zhǔn)酱鎯?chǔ),鄰接多重表：無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,2. 圖的遍歷,圖的遍歷目標(biāo)是解決圖的連通性問題、拓?fù)渑判騿栴}、關(guān)鍵路徑問題。圖的遍歷方法：深度優(yōu)先算法、廣度優(yōu)先算法,深度優(yōu)先遍歷,深度優(yōu)先搜索遍歷：類似于樹的先根遍歷，是樹的先根遍歷的推廣算法：1.假設(shè)圖中所有頂點(diǎn)的初始狀態(tài)為：未訪問；2.從圖中某個(gè)未訪問的頂點(diǎn)v出發(fā)，訪問此結(jié)點(diǎn)；3.依次從v的鄰接點(diǎn)出發(fā)

8、深度優(yōu)先遍歷圖，直到圖中所有與v有路徑的頂點(diǎn)都被訪問到；4.若圖中還有未訪問結(jié)點(diǎn)，則另選一個(gè)結(jié)點(diǎn)作起始點(diǎn)，重復(fù)2、3過程。,v1,V2,v6,v4,v5,v8,v3,v7,,,,,,,,,,,,,,,圖解深度優(yōu)先遍歷過程,一個(gè)非連同圖的深度優(yōu)先遍歷過程圖解,H,A,B,L,M,C,D,E,F,G,H,I,J,K,,,,,,,,,,,,,,,,,,,,可能的遍歷序列：A L M J B F C D E G I H K

9、,注：圖的存儲(chǔ)結(jié)構(gòu)沒有給定的情況下，圖的遍歷序列不是唯一的。,,廣度優(yōu)先遍歷,廣度優(yōu)先搜索遍歷類似于樹的層次遍歷算法,v1,V2,v6,v4,v5,v8,v3,v7,,,,,,,,一個(gè)非連同圖的廣度優(yōu)先遍歷過程圖解,H,A,B,L,M,C,D,E,F,G,H,I,J,K,,,,,,,,,,,可能的遍歷序列：A L F C B M D E G I H K,3.圖的連通性問題——掌握連通分量的求法,無(wú)向圖的連通分量和

10、生成樹由圖的遍歷得出：對(duì)于連通圖，從圖中任一頂點(diǎn)出發(fā)，可以訪問到圖中的所有頂點(diǎn)；對(duì)于非連通圖，需要從多個(gè)頂點(diǎn)出發(fā)，搜索到樹的各個(gè)連通分量中的頂點(diǎn)集。,4 掌握最小生成樹的概念和求法,最小生成樹構(gòu)造連通網(wǎng)的最小代價(jià)生成樹。MST性質(zhì)：假設(shè)N=(V,{E})是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V上的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。構(gòu)造最小生成樹的算法：Pr

11、in算法和Kruskal算法。,Prim算法構(gòu)造最小生成樹的過程：,Kruskal算法構(gòu)造最小生成樹的過程,兩種算法的區(qū)別：普魯姆算法：基于連通地選擇，避免回路克魯斯卡兒算法：離散地選擇，避免回路,拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，就是拓?fù)渑判?。偏序：集合中僅有部分成員之間可以比較；全序：集合中全體成員之間均可比較。AOV網(wǎng)：頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)之間的優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)。,偏序,全序

12、,5 拓?fù)渑判?進(jìn)行拓?fù)渑判虻姆椒ǎ涸谟邢驁D中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出；從圖中刪除該結(jié)點(diǎn)和所有以該結(jié)點(diǎn)為尾的弧。重復(fù)上述操作。若可以輸出全部頂點(diǎn)，則該圖中不存在環(huán)，否則存在環(huán)。例如：算法實(shí)現(xiàn)：以鄰接表的方法存儲(chǔ)有向圖；頭結(jié)點(diǎn)增加信息：頂點(diǎn)入度；增加一個(gè)棧：存放入度為0的頂點(diǎn)。,6 最短路徑,7.6.1 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑Dijkstra算法：按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑D[i]表示當(dāng)前所找到的從點(diǎn)

13、v到每個(gè)終點(diǎn)vi的最短路徑的長(zhǎng)度。D[i]初值：v到vi的弧的權(quán)值；則：初值最小的路徑就是從v出發(fā)的最短的一條路徑下面按照長(zhǎng)度遞增多次序產(chǎn)生各個(gè)終點(diǎn)的最短路徑,Dijkstra算法 求最短路徑,查找,考核內(nèi)容及要求：熟練掌握順序查找、有序表的查找、索引順序查找、二分查找法及HASHING查找技術(shù)；了解平衡二叉樹、B樹及B+樹的概念；理解查找速度的分析及比較、算法復(fù)雜性的級(jí)別。,1 順序表的查找,物理存儲(chǔ)： 順序表方

14、式： typedef struct { ElemType *elem; int length; } SSTable查找過程：從表中最后一個(gè)元素開始，逐個(gè)比較，相等則比較成功，否則直到第一個(gè)元素。,Int Search_Seq(SSTable ST, KeyType key) { //從尾部依次比較key和數(shù)據(jù)元素的關(guān)鍵字， //當(dāng)比到0下標(biāo)才成功則查找不成功，返

15、回0 //否則返回下標(biāo)i ST.elem[0].key = key; for (i=ST.length; !EQ(ST.elem[i].key, key); --i); return i; }//Search-Seq0下標(biāo)為監(jiān)視哨,時(shí)間復(fù)雜度O(n)平均查找長(zhǎng)度： ASL =sum(pici) i=1…n,查找成功： pi = 1/n ci= 1,2,

16、3…n ASL=1/n[1+2+…+n] = (n+1)/2查找不成功：ASL = n+1 , (n, n-1…1, 0)成功和不成功同概率：1/2 ASL = ½*1/n[1+2+…+n]+1/2(n+1) = ¾(n+1),折半查找：先確定待查記錄的范圍，逐步縮小范圍直到找到或找不到。例：在下列數(shù)據(jù)元

17、素中查找關(guān)鍵字為21和85的數(shù)據(jù)元素分析：設(shè)置兩個(gè)指針low ,high指示待查元素所在范圍的上界和下界。mid＝（low+high）/2ST.elem[mid].key=key:查找成功ST.elem[mid].keykey: high=mid-1 low=high:查找不成功,2 有序表的查找,,,low,high,,mid,int Search_Bin (SSTable ST, KeyTable key) {

18、 //對(duì)有序表的查找采用折半查找，逐步縮小 //查找范圍，直到找到或找不到，返回值為 //找到返回下標(biāo)，找不到返回0 low = 1; high = ST.length; while (low<=high) { mid = (low+high)/2; if EQ(key, ST.elem[mid].key) return

19、mid; else if LT(key, ST.elem[mid].key) high = mid –1; else low = mid +1; } return OK; } //Search_Bin 時(shí)間復(fù)雜度：O(log2n), ASL = log2(n+1)+1 (按照滿二叉樹),分塊

20、查找，索引順序查找分塊有序兩步查找：確定待查記錄所在地子表（塊）；在子表中順序查找,3 索引順序表的查找,,,,4.動(dòng)態(tài)查找表——二叉排序樹,例 已知如下長(zhǎng)度為8的表，試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成后的二叉排序樹，并求其在等概率下查找成功的平均查找長(zhǎng)度。（Mon, Tiger, Win, Butter, Fish, Fly, Pig,Cat),平衡二叉樹平衡因子：左子深度減去右子深度為 –1，

21、0， 1的二叉排序樹。二叉平衡樹的構(gòu)造（單項(xiàng)左旋/單項(xiàng)右旋）， （左右旋，右左旋）,右旋,左旋,左右旋,右左旋,9.3 哈希表,確定的對(duì)應(yīng)關(guān)系f：記錄的存儲(chǔ)位置 關(guān)鍵字對(duì)應(yīng)關(guān)系f就是哈希函數(shù)：f(K)哈希函數(shù)是一個(gè)映象，構(gòu)造哈希函數(shù)的方法：直接定址法；哈希地址：直接取關(guān)鍵字或者關(guān)鍵字的線性函數(shù)H(key)=key; or H(key)=a*key+b數(shù)字分析法；分析關(guān)鍵字，取關(guān)鍵字的若干

22、數(shù)位組成哈希地址。平方取中法；取關(guān)鍵字平方后的中間幾位為哈希地址——較為常用的方法折疊法：分割關(guān)鍵字、疊加除留余數(shù)法：H(key)=key MOD p p<=哈希表長(zhǎng)m,,沖突現(xiàn)象：當(dāng)K1≠K2時(shí)f(K1)=f(K2)解決沖突的方法開放定址法；Hi=(H(key)+di) MOD m i=1,2,···k (k<=m-1)m為哈希表長(zhǎng)度；di為增量,di的取法：(1

23、)線性探測(cè)再散列；di=1,2,3,···(2)二次探測(cè)再散列；di=±k2(3)偽隨機(jī)探測(cè)再散列 ：di=偽隨機(jī)數(shù)序列再哈希：Hi=RHi(key)鏈地址：所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中公共溢出區(qū)：發(fā)生沖突時(shí)填入溢出表。,排序,考核要求：熟練掌握插入排序、快速排序、堆及選擇排序、歸并排序、基數(shù)排序法；了解最好、最壞、平均排序的時(shí)間復(fù)雜性分析方法。,插入排序的思想：將一

24、個(gè)元素插入到一個(gè)有序表中。根據(jù)尋找插入位置的方法不同分為：直接插入、折半插入、2路插入、表插入等。直接插入排序：最簡(jiǎn)單的排序方法思想：將一個(gè)元素向一個(gè)有序序列插入 做法：0位監(jiān)測(cè)哨，從一個(gè)元素逐步擴(kuò)大有序序列。舉例,1 插入排序,直接插入排序算法：void InsertSort(SqList &L){//對(duì)順序表L作直接插入排序 for (i=2;i<L.length;++i)if (L.

25、r[i].key<L.r[i-1].key){ L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for (j=i-2;L[0].key<L[j].key;--j)L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0];} },折半插入排序查找過程用折半查找方法。,void BInsertSort(SqList &L){ for (i=2

26、;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; while (low<=high){ m=(low+high)/2; if (L.r[0].key<L.[m].key) high=m-1;else low=m+1; }//while for(j=i-1;j<=high+1;--j) L

27、.r[j+1]=L.r[j]; L.r[high+1]=L.r[0];}//for}//BInsertSort,算法思想：先將整個(gè)待排序記錄分割成若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，再進(jìn)行一次全體記錄的插入排序。具體操作：,49 38 65 97 76 13 27 49 55 04,49 13,38 27,65 49,76 04,,13 27 49 55 04 49

28、 38 65 97 76,13 55 38 76,27 04 65,49 49 97,,第一次分組,,,這就是第一趟排序結(jié)果,第二趟的“增量”就要縮小了！,2 希爾排序：縮小增量排序，屬于插入排序,希爾排序算法:void ShellInsert (SqList &L,int dk){ //對(duì)順序表L作一趟希爾排序。 for (i=dk+1;i0&L.r[0].key<L.r[j].key;

29、j-=dk) L.r[j+dk]=L.r[j];L.r[j+dk]=L.r[0]; }}//shelinsertvoid ShellSort(SqList &L,int dlta[],int t){//按增量序列dlta[0..t-1]對(duì)順序表L作希爾排序for (k=0;k<t;++k) ShellInsert(L,dlta[k]);},3 快速排序,冒泡排序：具體做法：依

30、次比較第i個(gè)關(guān)鍵字和第i+1個(gè)關(guān)鍵字，大者排后，一趟得到最大值。（i=1,2,3,4,---n-1),49 38 65 97 76 13 27 49,38 49 65 97 76 13 27 49,38 49 65 76 97 13 27 49,38 49 65 76 13 97 27 49,38 49 65 76 13 27 97 49,38 49 65 76

31、 13 27 49 97,冒泡排序算法void Bubble Sort (SqList &L ){for (k=L.length-1;k>=1;k--) for (i=0;iL.r[i+1].key) {交換兩個(gè)記錄}}時(shí)間復(fù)雜度：O(n2),49 38 65 97 76 13 27 49,,,low,high,27 38 65 97 76 13 49,,low

32、,high,,,,,,,27 38 13 97 76 65 49,low,high,,,27 38 97 76 13 65 49,low,high,,,,,,,27 38 13 76 97 65 49,low,high,,,,,快速排序的算法,快速排序算法：Int Partition (SqList &L,int low,int high){L.r[0]=

33、L.r[low];pivotkey=L.r[low].key;while (low=pivotkey) --high; L.r[low]=L.r[high]; while(low<high &&L.r[low].key<=pivotkey) ++low; L.r[high]= L.r[low];}L.r[low]=L.r[0];return low;}//平均時(shí)

34、間：K為常數(shù)因子。就平均時(shí)間而言快速排序是目前被認(rèn)為最好的一種內(nèi)部排序方法。,4 選擇排序,選擇排序基本思想：每一趟在n-i+1(i=1,2,···,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。簡(jiǎn)單選擇排序：Void SelectSort(SqList &L){ for (i=1;i<L.length;++i){ j=SelectMinKey(L,i);//從

35、L.r[i..L.length]中選擇key最小的記錄 if (i!=j) L.r[i] L.r[j];}},堆排序堆的定義：n個(gè)元素的序列{k1,k2,,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱為堆：思想：每趟選取最小關(guān)鍵字、次小關(guān)鍵字、次次小關(guān)鍵字---。 做法：建立一個(gè)完全二叉樹，任何非終端結(jié)點(diǎn)的值均不大于其左、右孩子結(jié)點(diǎn)的值。輸出堆頂，將其余的元素建立新的堆。,ki≤k2iki≤k2i+1,,ki≥k2

36、iki≥k2i+1,,49 38 65 97 76 13 27 49,49 38 65 49 76 13 27 97,,,,49 38 13 49 76 65 27 97,,,,49 38 13 49 76 65 27 97,,,,,5 歸并排序,思想：將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。具體做法：以兩路歸并示例,[49] [38] [65] [97] [76] [13]

37、 [27],n個(gè)記錄看成n個(gè)有序的序列,[ 38 49 ] [ 65 97 ] [ 13 76 ] [27],第一趟合并,,,,,[ 38 49 65 97 ] [13 27 76],,,[ 13 27 38 49 65 76 97],第二趟合并,第三趟合并,外部排序,考核要求：了解外存及分類技術(shù)簡(jiǎn)介 了解緩沖區(qū)管理、初始合并串、置換選擇分類技術(shù)、勝者樹及敗者樹,3

38、. 置換-選擇排序目標(biāo)：減少m(初始?xì)w并段的個(gè)數(shù))來(lái)減少歸并趟數(shù)。 m=upper(n/l), n為外部文件中記錄數(shù)， l為每段記錄數(shù)目。 故增大l, l受內(nèi)存空間限制 置換-選擇排序：在得到所有初始?xì)w并段的過程中，選擇最?。ù螅╆P(guān)鍵字和輸入、輸出交叉或同時(shí)進(jìn)行。外部排序方法：思想：分段讀入內(nèi)存、排序；分段寫入外存、有序段歸并。,已知圖G的鄰接表如下圖所示

39、，從其頂點(diǎn)V1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列分別寫出來(lái)，并按圖中給出的存儲(chǔ)結(jié)構(gòu)給出深度優(yōu)先生成樹和廣度優(yōu)先生成樹。,典型例題——圖、查找、排序,7.5 已知以二維數(shù)組表示的圖的鄰接矩陣如下，分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷得到的深度優(yōu)先和廣度優(yōu)先生成樹,1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 1

40、 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0

41、 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0

42、0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0,,,給出如圖所示的無(wú)向圖的鄰接矩陣和鄰接表，并從其頂點(diǎn)V1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列分別寫出來(lái)。,已知圖2所示的圖，若從頂點(diǎn)A出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的遍歷序列為：A) A,B,E,C,D,

43、FB)A,C,F,E,B,DC) A,E,B,C,F,DD) A,E,D,F,C,B,7.9 試列出下圖中全部可能的拓?fù)溆行蛐蛄?，并指?.5.1節(jié)中算法Topological Sort求得到是哪一個(gè)序列。,9.8 已知含12個(gè)關(guān)鍵字的有序表及其相應(yīng)權(quán)值如下，畫出對(duì)以下有序表進(jìn)行折半查找的判斷樹。,10.1 以關(guān)鍵字序列(53, 87, 12, 61,98,17, 97, 75, 53, 26)為例，手工執(zhí)行以下排序算法，

44、寫出每一趟排序結(jié)束時(shí)的關(guān)鍵字狀態(tài)： (1) 希爾排序(增量d[1]=5) (2) 快速排序 (3)堆排序,10.2 判別以下序列是否為堆，如果不是，則把它調(diào)整為堆。 (1) (100,86,48,73,35,39,42,57,66,21); (2) (12,70,33,65,24,56,48,92,86,33),考試題型,選擇題（20題，每題一分，共20分）填空題（10空，