【正文】 該過程稱為“譯碼”。 ? Huffman編碼：一種非等長度的編碼。 應用舉例 ? 由統(tǒng)計規(guī)律可知，考試成績的分布符合正態(tài)分布： 1 1 0 分數(shù) 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100 比例數(shù) ? 根據(jù)正態(tài)分布規(guī)律，在 60 ～ 90之間的分數(shù)占 85%，而不及格和優(yōu)秀是少數(shù)。 示意為： RL平衡化處理 由于在 A的右子樹的左子樹上插入結(jié)點 ， 使 A點失去平衡 ，需進行一次 RL旋轉(zhuǎn) （ 兩次旋轉(zhuǎn) 。 10 （ 1） 10 18 （ 2） 10 3 18 （ 3） 10 3 18 4 （ 4） 10 3 4 18 9 （ 5） （ 7） 10 3 9 4 18 13 25 10 3 4 9 18 13 （ 6） 示例 平衡二叉排序樹 在二叉排序樹的動態(tài)生成過程中 ， 由于數(shù)據(jù)本身的特性 ， 將影響二叉排序樹的性質(zhì) ， 例如 {3，5， 7， 9， 20}這樣的數(shù)列 ， 生成的二叉排序樹就是一棵單枝樹 。 if (r = = 0) return 。 else root=rootright。 } return r。 exit(0)。 scanf(“%s”,amp。 do { printf(“Enter a letter:”)。 ? 打印輸出該二叉排序樹； ? 輸入一個值，在該樹中查找，若找到輸出該結(jié)點值；否則，顯示查找失敗。 即研究的是工程進度及影響進度的關鍵因素問題 。 克魯斯卡爾（ Kruskal）算法舉例 1 2 3 4 5 6 1 5 2 4 6 6 3 5 5 6 2 5 1 3 4 6 1 2 3 (4) 1 3 1 4 6 2 (3) 1 2 3 4 5 6 (1) 1 3 (2) 1 克魯斯卡爾（ Kruskal）算法舉例 (續(xù)） 1 2 3 4 5 6 (5) 1 2 3 4 1 2 3 4 5 6 1 5 2 4 6 6 3 5 5 6 1 3 2 5 6 4 1 2 4 3 5 （ 6） 拓撲排序 ? 研究一個有機整體中不同個體間的次序問題 。 五、圖的應用 ? 最小生成樹 ? 拓撲排序 ? 關鍵路徑 ? 最短路徑 最小生成樹 ? 該問題是構造連通圖的最小代價生成樹問題 。 圖的常用基本操作 ? LOC_VERTEX（ G， Vi） 確定頂點 Vi在 G中的位置 。 } } } } 廣度優(yōu)先遍歷算法 ? 廣度優(yōu)先遍歷法類似于樹的按層次遍歷的過程。 visited[padjvex]=1。i++) visited[I]=0。 ? 算法思想： – step1 從圖中某個頂點 V0出發(fā) ， 并訪問此頂點； – step2 從 V0出發(fā) ， 訪問與 V0鄰接的頂點 V1后 ， 再從 V1出發(fā) ， 訪問與 V1鄰接且未被訪問過的頂點 V2。i,amp。(j=0 amp。 } scanf(“%d,%d,%f”, amp。 建立鄰接表算法的程序 createadjlist(struct headnode G[],int n) { int i,j,k。 對圖的每個頂點建立一個單鏈表 （ n個頂點建立 n個單鏈表 ） ， 第 i個單鏈表中的結(jié)點包含頂點 Vi的所有鄰接頂點 。 – 鄰接矩陣又分為 有向圖鄰接矩陣 和 無向圖鄰接矩陣 。 權通常用來表示從一個頂點到另一個頂點的距離或費用 。 ? 強連通圖 （ Strongly Connected Graph） 在有向圖中 ， 若每對頂點 Vx到 Vy 間都存在 Vx到 Vy， 及從 Vy到 Vx的路徑 ， 則稱此圖是強連通圖 。 o o o o v1 v2 v3 v4 G1 1 3 2 4 G2 路徑、長度 ? 路徑 （ Path） 在圖中 ， 從頂點 Vx到頂點 Vy的頂點序列 （ Vx， V1，V2， … ,Vn,Vy)稱為從 Vx到 Vy的路徑 。 Vx Vy Ｖ x、Ｖ y互為鄰接點 Vx Vy Ｖ y是Ｖ x的鄰接點 1 3 2 4 G2 o o o o v1 v2 v3 v4 G1 頂點的度（ Degree） ? 無向圖中 ， 頂點的 度 是以該頂點為一個端點的邊的條數(shù) 。記為： 〈 Vx， Vy〉 。 ? 例 ， 圖 G1 = （ V， E） V={v1， v2， v3， v4} E={（ v1， v2） ， （ v1， v3） ， （ v2， v1） ， （ v2， v3） ， （ v2， v4） ， （ v3， v1） ， （ v3， v2） ， （ v4， v2） } o o o o v1 v2 v3 v4 G1 有向圖、無向圖 ? 有向圖（ Digraph） 圖 G中頂點的偶對若是有向的，形成的圖稱有向圖。教學目標 ? 了解有關圖的 – 基本概念 – 存儲結(jié)構及實現(xiàn) – 遍歷算法 教學要求 ? 通過本單元學習，了解、掌握有關圖 : – 基本概念 ?有向圖、無向圖、連通圖、網(wǎng) – 存儲結(jié)構及實現(xiàn) ?鄰接矩陣、鄰接表 – 遍歷及其它操作 ?深度優(yōu)先、廣度優(yōu)先遍歷 – 應用 本單元涉及的內(nèi)容 ? 第 2章 – – – – ? P73~P90 一、 圖及其基本概念 ? 圖是一種較之線性表和樹形結(jié)構更為復雜的非線性數(shù)據(jù)結(jié)構 。如圖 G2所示。 弧是有序的 ， 〈 Vx， Vy〉 表示從Vx到 Vy。 例如 ， G1中 V2的度為 3， V4的度為 1。 路徑可能是不唯一的 。 如圖 G4所示 。 ? 網(wǎng) （ Network） 帶權的圖稱為網(wǎng) 。 有向圖鄰接矩陣 ? 定義 設圖 G=（ V， E） 是有 n（ n ? 1） 個頂點的圖 ， 則 G的鄰接矩陣是具有下述性質(zhì)的 nxn的方陣 ， 元素為： 1 當 〈 Vi， Vj? E 時 A[ i， j] = 0 當 〈 Vi， Vj? E 時 例如 ， G2的鄰接矩陣為： = 1 2 3 4 A= = 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 4x4 1 3 2 4 G2 無向圖鄰接矩陣 ? 定義 設圖 G=（ V， E）是有 n（ n ? 1）個頂點的圖，則 G的鄰接矩陣是具有下述性質(zhì)的對稱陣，元素為： 1 當 (Vi， Vj） ? E 時 A[ i， j] =A[j,i] = 0 當 (Vi， Vj） ? E 時 例如， G1的鄰接矩陣為： = 1 2 3 4 A= = 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 4x4 o o o o v1 v2 v3 v4 G1 求圖中頂點的度 ? 借助鄰接矩陣 ,可以很容易地求出圖中頂點的度 。 ? 在鄰接表中 ， 每個頂點由三個域組成： ? 每個單鏈表附設一個頭結(jié)點 ， 結(jié)構為： adjvex data nextarc 頂點 Vi的鄰接點 與邊或弧有關的權值 指向 Vi的下一個 鄰接點的指針 Vexdata firstarc 指向 Vi單鏈表的第一個結(jié)點 存放 Vi信息 鄰接表存儲結(jié)構描述 C語言描述 define VTXNUM n struct arode { int adjvex； float data； struct arode *nextarc； }； typedef struct arode ARCNODE ； struct headnode { int data ； ARCNODE * firstarc ； } adjlist[VTXNUM]； 無向圖 G1的鄰接表 V1 V2 V3 V4 ^ V3 V2 V1 V4 ^ V3 ^ V1 V2 ^ V2 頂點 Vi的度恰好就是 第 i個單鏈表中的結(jié)點數(shù)。