復習課(3)

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

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

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

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

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

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

7、,有向圖G1的鄰接表,有向圖G1的逆鄰接表,十字鏈表：有向圖的鏈式存儲,鄰接多重表：無向圖的另一種鏈式存儲結(jié)構(gòu)。,2. 圖的遍歷,圖的遍歷目標是解決圖的連通性問題、拓撲排序問題、關鍵路徑問題。圖的遍歷方法：深度優(yōu)先算法、廣度優(yōu)先算法,深度優(yōu)先遍歷,深度優(yōu)先搜索遍歷：類似于樹的先根遍歷，是樹的先根遍歷的推廣算法：1.假設圖中所有頂點的初始狀態(tài)為：未訪問；2.從圖中某個未訪問的頂點v出發(fā)，訪問此結(jié)點；3.依次從v的鄰接點出發(fā)

8、深度優(yōu)先遍歷圖，直到圖中所有與v有路徑的頂點都被訪問到；4.若圖中還有未訪問結(jié)點，則另選一個結(jié)點作起始點，重復2、3過程。,v1,V2,v6,v4,v5,v8,v3,v7,,,,,,,,,,,,,,,圖解深度優(yōu)先遍歷過程,一個非連同圖的深度優(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、,注：圖的存儲結(jié)構(gòu)沒有給定的情況下，圖的遍歷序列不是唯一的。,,廣度優(yōu)先遍歷,廣度優(yōu)先搜索遍歷類似于樹的層次遍歷算法,v1,V2,v6,v4,v5,v8,v3,v7,,,,,,,,一個非連同圖的廣度優(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.圖的連通性問題——掌握連通分量的求法,無向圖的連通分量和

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

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

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

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

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

15、回0 //否則返回下標i ST.elem[0].key = key; for (i=ST.length; !EQ(ST.elem[i].key, key); --i); return i; }//Search-Seq0下標為監(jiān)視哨,時間復雜度O(n)平均查找長度： 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、素中查找關鍵字為21和85的數(shù)據(jù)元素分析：設置兩個指針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、 //對有序表的查找采用折半查找，逐步縮小 //查找范圍，直到找到或找不到，返回值為 //找到返回下標，找不到返回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 時間復雜度：O(log2n), ASL = log2(n+1)+1 (按照滿二叉樹),分塊

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

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

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

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

24、個元素插入到一個有序表中。根據(jù)尋找插入位置的方法不同分為：直接插入、折半插入、2路插入、表插入等。直接插入排序：最簡單的排序方法思想：將一個元素向一個有序序列插入 做法：0位監(jiān)測哨，從一個元素逐步擴大有序序列。舉例,1 插入排序,直接插入排序算法：void InsertSort(SqList &L){//對順序表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,算法思想：先將整個待排序記錄分割成若干個子序列分別進行直接插入排序，待整個序列中的記錄基本有序時，再進行一次全體記錄的插入排序。具體操作：,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){ //對順序表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]對順序表L作希爾排序for (k=0;k<t;++k) ShellInsert(L,dlta[k]);},3 快速排序,冒泡排序：具體做法：依

30、次比較第i個關鍵字和第i+1個關鍵字，大者排后，一趟得到最大值。（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) {交換兩個記錄}}時間復雜度：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;}//平均時

34、間：K為常數(shù)因子。就平均時間而言快速排序是目前被認為最好的一種內(nèi)部排序方法。,4 選擇排序,選擇排序基本思想：每一趟在n-i+1(i=1,2,···,n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。簡單選擇排序：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個元素的序列{k1,k2,,kn}當且僅當滿足下列關系時，稱為堆：思想：每趟選取最小關鍵字、次小關鍵字、次次小關鍵字---。 做法：建立一個完全二叉樹，任何非終端結(jié)點的值均不大于其左、右孩子結(jié)點的值。輸出堆頂，將其余的元素建立新的堆。,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 歸并排序,思想：將兩個或兩個以上的有序表組合成一個新的有序表。具體做法：以兩路歸并示例,[49] [38] [65] [97] [76] [13]

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

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

39、，從其頂點V1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列分別寫出來，并按圖中給出的存儲結(jié)構(gòu)給出深度優(yōu)先生成樹和廣度優(yōu)先生成樹。,典型例題——圖、查找、排序,7.5 已知以二維數(shù)組表示的圖的鄰接矩陣如下，分別畫出自頂點1出發(fā)進行遍歷得到的深度優(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,,,給出如圖所示的無向圖的鄰接矩陣和鄰接表，并從其頂點V1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列分別寫出來。,已知圖2所示的圖，若從頂點A出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的遍歷序列為：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 試列出下圖中全部可能的拓撲有序序列，并指出7.5.1節(jié)中算法Topological Sort求得到是哪一個序列。,9.8 已知含12個關鍵字的有序表及其相應權值如下，畫出對以下有序表進行折半查找的判斷樹。,10.1 以關鍵字序列(53, 87, 12, 61,98,17, 97, 75, 53, 26)為例，手工執(zhí)行以下排序算法，

44、寫出每一趟排序結(jié)束時的關鍵字狀態(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空，