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