非線性數(shù)據(jù)結(jié)構(gòu)--圖(文件)
【正文】 4 3 a c b d 0 1 0 0 1 1 a b c d 0 110 10 111 abaccda 0110010101110 前綴編碼 32/32 作業(yè)、思考題 思考題： 18 第 2章作業(yè) 1 20 。 ? Huffman編碼：一種前綴編碼。 （ 1） T= { a b c d } （ 2） T= { a b T3 } （ 3） T= { a T2 } （ 4） T={ T1 } c d T3 b T1 T2 2 4 6 6 5 11 b T2 6 5 11 c d 2 4 18 a T2 7 11 T1 18 a 7 T1 b T1 T2 6 5 11 18 a 7 T1 b 5 11 c d 2 6 4 30/32 三 . Huffman編碼 ? 編碼：用二進(jìn)制數(shù)的不同組合來表示字符。 27/32 Huffman樹舉例 ? 以下三棵樹帶權(quán)路徑之和： （ a） （ b） （ c） a b c d a b c d a c b d 7 7 7 5 5 5 2 2 2 4 4 4 WPLa =7x2+5x2+2x2+4x2 = 36 WPLb =7x3+5x3+2x1+4x2 = 46 WPLc = 7x1+5x2+2x3+4x3 = 35 √ ? 按哈夫曼樹構(gòu)造二叉樹，應(yīng)用于實(shí)際問題，可提高處理效率。 ? 算法 – 1) 訪問某個(gè)指定頂點(diǎn) V0； – 2) 從 V0出發(fā)，訪問 V0的各個(gè)未曾訪問的鄰接點(diǎn) W1， W2， … ,Wk。 重復(fù)上述過程 ， 直到不存在未訪問過的鄰接點(diǎn)為止 。 G1 A= = 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 3 2 4 G2 15/32 ? 定義： Wij （ Vi,Vj） 或 〈 Vi,Vj〉 ? E A[i][j] = ? （ Vi,Vj） 或 〈 Vi,Vj〉 ? E = V1 V2 V3 V4 A== ? 5 ? 3 ? ? 2 ? ? ? ? ? ? ? 7 ? 4x4 G5的鄰接矩陣。 12/32 ? 定義 設(shè)圖 G=(V,E)是有 n(n?1)個(gè)頂點(diǎn)的圖，則 G的鄰接矩陣是具有下述性質(zhì)的對(duì)稱陣： 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
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1