數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)與習(xí)題解析.ppt

1、數(shù)據(jù)結(jié)構(gòu) 與 算法,復(fù)習(xí)與習(xí)題解析(第6-8講）,第6講 圖,圖的相關(guān)定義(無向完全圖、有向完全圖、網(wǎng)、連通圖、強(qiáng)連通圖、度、入度、出度、生成樹和生成森林) 圖的存儲方式 鄰接矩陣 無向圖鄰接矩陣 有向圖鄰接矩陣 網(wǎng)的鄰接矩陣 每個結(jié)點的出度？入度？度？ 圖的邊數(shù)？ 鄰接表 每個結(jié)點的出度？入度？度？ 圖的邊數(shù)？,12/10/2020,2,例已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。,當(dāng)鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！,例題解析,12/10/2020,3,圖的遍歷,廣度優(yōu)先搜索 從圖的某一結(jié)點出發(fā)，首先依次訪問該結(jié)點的所有鄰接頂點 V1, V2, , Vn 再按這些頂點被訪問的先后次序依次

2、訪問與它們相鄰接的所有未被訪問的頂點，重復(fù)此過程，直至所有頂點均被訪問為止。 深度優(yōu)先搜索 1、訪問指定的起始頂點； 2、若當(dāng)前訪問的頂點的鄰接頂點有未被訪問的，則任選一個訪問之；反之，退回到最近訪問過的頂點；直到與起始頂點相通的全部頂點都訪問完畢； 3、若此時圖中尚有頂點未被訪問，則再選其中一個頂點作為起始頂點并訪問之，轉(zhuǎn) 2； 反之，遍歷結(jié)束。,12/10/2020,4,例題解析,12/10/2020,5,熟悉圖的存儲結(jié)構(gòu)，畫出右邊有向圖的鄰接矩陣、鄰接表、逆鄰接表。寫出鄰接表表示的圖從頂點A出發(fā)的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。,深度優(yōu)先遍歷序列為ABCFED，廣度優(yōu)先遍歷序列為AB

3、DCEF,鄰接矩陣如下,鄰接表如下,逆鄰接表如下,【答】,最小生成樹,普里姆（Prim）算法 將頂點進(jìn)行歸并 克魯斯卡爾（Kruscal）算法 將邊進(jìn)行歸并,12/10/2020,6,例：Prim算法,最小代價生成樹的生成過程,U,V0,V1,V3,V2,V4,V5,6,1,6,5,5,5,6,3,4,2,V0,V1,V3,V2,V4,V5,1,5,3,4,2,(4),(1),(3),(2),(5),12/10/2020,7,例： Kruscal 算法,實例的執(zhí)行過程,圖G,1、初始連通分量： 0,1,2,3,4,5 2、反復(fù)執(zhí)行添加、放棄動作。 條件：邊數(shù)不等于 n-1時 邊 動作連通分量

4、(0,2) 添加0,2,1,3,4,5 (3,5) 添加0,2,3, 5,1,4 (1,4) 添加0,2,3, 5,1,4 (2,5) 添加0,2,3,5,1,4 (0,3) 放棄因構(gòu)成回路 (2,3) 放棄因構(gòu)成回路 (1,2) 添加0,2,3,5,1,4,最小代價生成樹,V0,V1,V3,V2,V4,V5,6,1,6,5,5,5,6,3,4,2,V0,V1,V3,V2,V4,V5,1,5,3,4,2,5,5,12/10/2020,8,例題解析,請分別用Prim算法和Kruskal算法構(gòu)造以下網(wǎng)絡(luò)的最小生成樹，并求出該樹的代價。,12/10/2020,9,例題解析,12/10/2020,10

5、,【解析】Prim算法的操作步驟：首先從一個只有一個頂點的集合開始，通過加入與其中頂點相關(guān)聯(lián)的最小代價的邊來擴(kuò)充頂點集，直到所有頂點都在一個集合中。,例題解析,12/10/2020,11,【解析】Kruscal算法的操作步驟： 首先將n個頂點看成n個互不連通的分量，從邊集中找最小代價的邊，如果落在不同連通分量上，則將其加入最小生成樹，直到所有頂點都在同一連通分量上。,單源最短路徑,在帶權(quán)有向圖中A點（源點）到達(dá)B點（終點）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。 迪杰斯特拉 (Dijkstra) 算法： 按路徑長度遞增次序產(chǎn)生最短路徑 1、把 V 分成兩組： (1) S：已求

6、出最短路徑的頂點的集合。 (2) V - S = T：尚未確定最短路徑的頂點集合。 2、將 T 中頂點按最短路徑遞增的次序加入到 S 中，保證： (1) 從源點 v0 到 S 中各頂點的最短路徑長度都不大于 從 v0 到 T 中任何頂點的最短路徑長度。 (2) 每個頂點對應(yīng)一個距離值： S中頂點：從 v0 到此頂點的最短路徑長度。 T中頂點：從 v0 到此頂點的只包括 S 中頂點作中間頂點的 最短路徑長度。,12/10/2020,12,Dijkstra 算法步驟：,T 中頂點對應(yīng)的距離值用輔助數(shù)組 D 存放。,Di 初值：若 存在，則為其權(quán)值；否則為。,v2,13 8 30 32,v2,8,1

7、3 13 30 32,v3,v1,v1,13,13 30 22 20,v3,8+5 v2,19 22 20,v4,v4,8+5+6 v2-v3,21 20,v6,v5,13+7 v1,21,v5,v6,初始時令 S=v0, T=其余頂點。,v0,從 T 中選取一個其距離值最小的頂點 vj，加入 S。,對 T 中頂點的距離值進(jìn)行修改：若加進(jìn) vj 作中間頂點，從 v0 到 vi 的距離值比 不加 vj 的路徑要短，則修改此距離值。,重復(fù)上述步驟，直到 S = V 為止。,8+5 +6+2 v2-v3-v4,12/10/2020,13,拓?fù)渑判?AOV網(wǎng)： 在一個有向圖中，若用頂點表示活動，有向邊

8、表示活動間先后關(guān)系，稱該有向圖叫做頂點表示活動的網(wǎng)絡(luò)(Activity On Vertex network)簡稱為AOV網(wǎng)。 拓?fù)渑判虻姆椒ǎ?在有向圖中選一個沒有前驅(qū)的頂點且輸出之。 從圖中刪除該頂點和所有以它為起點的弧。 重復(fù)上述兩步，直至全部頂點均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點為止。,12/10/2020,14,例題解析,拓?fù)渑判虻慕Y(jié)果不是唯一的，試寫出下圖任意2個不同的拓?fù)湫蛄小?12/10/2020,15,【解析】解題關(guān)鍵是弄清拓?fù)渑判虻牟襟E,（1）在AOV網(wǎng)中，選一個沒有前驅(qū)的結(jié)點且輸出；（2）刪除該頂點和以它為尾的??；（3）重復(fù)上述步驟直至全部頂點均輸出或不再有無前驅(qū)的頂點

9、。,【答案】（1）0132465 （2）0123465,關(guān)鍵路徑,AOE(Activity on Edge)網(wǎng)絡(luò)：定義結(jié)點為事件，有向邊的指向表示事件的執(zhí)行次序。單位是時間（時刻）。有向邊定義為活動，它的權(quán)值定義為活動進(jìn)行所需要的時間。 對AOE網(wǎng)，我們關(guān)心兩個問題： (1)完成整項工程至少需要多少時間？ (2)哪些活動是影響工程進(jìn)度的關(guān)鍵？ 關(guān)鍵路徑路徑長度最長的路徑。路徑長度路徑上各活動持續(xù)時間之和,ve(j) 表示事件 vj 的最早發(fā)生時間。,vl(j) 表示事件 vj 的最遲發(fā)生時間。,ee(i) 表示活動 ai 的最早開始時間。,el(i) 表示活動 ai 的最遲開始時間。,el(i

10、) - ee(i) 表示完成活動 ai 的時間余量。,關(guān)鍵活動 關(guān)鍵路徑上的活動，即 el(i) = ee(i) 的活動。,12/10/2020,16,如何找 el(i) = ee(i) 的關(guān)鍵活動？,設(shè)活動 ai 用弧 表示，其持續(xù)時間記為：dut() 則有： (1) ee(i) = ve(j) (2) el(i) = vl(k) - dut(),(1) 從 ve(1) = 0 開始向前遞推,(2) 從 vl(n) = ve(n) 開始向后遞推,如何求 ve(j) 和 vl(j) ？,12/10/2020,17, ,求關(guān)鍵路徑步驟： 求 ve(i)、vl(j) 求 ee(i)、el(i) 計

11、算 el(i) - ee(i),0 6 4 5 7 7 16 14 18,0 6 6 8 7 10 16 14 18,12/10/2020,18,圖,存儲結(jié)構(gòu),遍 歷,鄰接矩陣,鄰 接 表,十字鏈表,鄰接多重表,深度優(yōu)先搜索DFS,廣度優(yōu)先搜索BFS,無向圖的應(yīng)用,應(yīng)用,圖的連通分量,圖的生成樹,最小生成樹,Prim算法,Kruskal算法,Dijkstra算法,Floyd算法,（利用DFS）,有向圖的應(yīng)用,DAG圖,拓?fù)渑判?關(guān)鍵路徑,12/10/2020,19,第7講 查找,基本概念：表/記錄/關(guān)鍵字/靜態(tài)查找表/動態(tài)查找表/平均查找長度 順序表查找和“哨兵” 有序查找：折半查找/插值查找

12、/斐波那契查找 線性索引：稠密索引/分塊索引/倒排索引 二叉排序樹/平衡二叉樹：構(gòu)建/插入/刪除/保持平衡 B-樹/B+樹：構(gòu)建/插入/刪除操作 散列表：散列函數(shù)的選擇和處理沖突的方法,12/10/2020,20,例題解析,設(shè)有序表為(a, b, c, d, e, f, g, h, i, j, k, p, q)，請分別畫出對給定值a, g和n進(jìn)行折半查找的過程。,12/10/2020,21,【答】,例題解析,構(gòu)造有12個元素的二分查找的判定樹，并求解下列問題： （1）各元素的查找長度最大是多少？ （2）查找長度為1、2、3、4的元素各有多少？具體是哪些元素？ （3）查找第5個元素依次要比較哪些

13、元素？ 【答】 12個元素的判斷樹如下圖所示：,12/10/2020,22,（1）最大查找長度是樹的深度4。,（2）查找長度為1的元素有1個，為第6個，查找長度為2的元素有2個，為第3個和第9個，查找長度為3的元素有4個，為第1、4、7、11個，查找長度為4的元素有5個，為第2、5、8、10、12個。,（3）查找第五個元素依次比較6，3，4，5。,例：設(shè)有一組關(guān)鍵字32,75,63,48,94,25,36,18,70，采用哈希函數(shù)：H(key)=key MOD 11并采用步長為1的線性探測法解決沖突，試在0-10的散列地址空間中對該關(guān)鍵字序列構(gòu)造哈希表。,【答】依題意，m=11，線性探測再散列

14、的下一地址計算公式為： d1=H(key)， dj+1=(dj+1) MOD 11；j=1,2,. 其計算過程如下： H(32)=32 MOD 11=10 H(75)=75 MOD 11=9 H(63)=63 MOD 11=8 H(48)=48 MOD 11=4 H(94)=94 MOD 11=6 H(25)=25 MOD 11=3 H(36)=36 MOD 11=3(沖突) H(36)=(3+1) MOD 11=4(仍沖突) H(36)=(4+1) MOD 11=5 H(18)=18 MOD 11=7 H(70)=70 MOD 11=4 (沖突) H(70)=(4+1) MOD 11=5 (

15、仍沖突) H(70)=(10+1) MOD 11=0,例題解析,12/10/2020,23,第八講 排序,簡單排序方法（0（n2） 插入排序（穩(wěn)定排序） 選擇排序（不穩(wěn)定排序） 冒泡排序（不穩(wěn)定排序） 先進(jìn)排序方法（ O(nlogn)） 快速排序（不穩(wěn)定排序） 歸并排序（穩(wěn)定排序） 堆排序（不穩(wěn)定排序）,12/10/2020,24,一、時間性能,時間復(fù)雜度為 O(nlogn)：快速排序、堆排序和歸并排序，其中以 快速排序為最好。,時間復(fù)雜度為 O(n2)：直接插入排序、起泡排序和簡單選擇排序， 其中以直接插入為最好，特別是對那些對關(guān) 鍵字基本有序的記錄序列尤為如此。,時間復(fù)雜度為 O(n*d)

16、：基數(shù)排序。,1. 按平均時間性能來分，有三類排序方法：,2. 當(dāng)待排序列按關(guān)鍵字順序有序時，直接插入排序和起泡排序能 達(dá)到 O(n) 的時間復(fù)雜度，快速排序的時間性能蛻化為 O(n2) 。,3. 簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中 關(guān)鍵字的分布而改變。,3.5 各種排序方法的綜合比較,12/10/2020,25,二、空間性能,指的是排序過程中所需的輔助空間大小。,所有的簡單排序方法(包括：直接插入、冒泡和簡單選擇) 和 堆排序的空間復(fù)雜度為 O(1)；,快速排序為 O(logn)，為遞歸程序執(zhí)行過程中，棧所需的輔助 空間；,3. 歸并排序所需輔助空間最多，其空間復(fù)雜度為 O(n)；,4. 鏈?zhǔn)交鶖?shù)排序需附設(shè)隊列首尾指針，則空間復(fù)雜度為 O(2*rd+n),三、排序方法的穩(wěn)定性能,1. 當(dāng)對多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時，必須采用穩(wěn) 定的排序方法。,2. 對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。,3. 快速排序、堆排序是不穩(wěn)定的排序方法。,12/10/2020,26,各種內(nèi)部排序方法的比較,12/10/2020,27,例題解析,設(shè)待排序的排序碼序列