非線性數(shù)據(jù)結(jié)構(gòu)--圖(參考版)
2024-08-12 14:45本頁(yè)面
【正文】 W={3 1 2 1} 3 1 2 1 W={3 2 2} 1 1 2 W= {3 2 2} 1 1 2 2 4 W={3 4} 1 1 2 2 4 1 1 2 2 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編碼：一種前綴編碼。任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。 （ 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ù)的不同組合來(lái)表示字符。 – 2）在 T中選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左右子樹(shù)，構(gòu)成一個(gè)新的二叉樹(shù)，其根結(jié)點(diǎn)的權(quán)值取左右子樹(shù)權(quán)值之和； – 3）在 T中刪除這兩棵樹(shù)，將新構(gòu)成的樹(shù)加入到 T中； – 4）重復(fù) 2）、 3）步，直到 T中只含一棵樹(shù)為止，該樹(shù)就是 Huffman樹(shù)。 27/32 Huffman樹(shù)舉例 ? 以下三棵樹(shù)帶權(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 √ ? 按哈夫曼樹(shù)構(gòu)造二叉樹(shù)，應(yīng)用于實(shí)際問(wèn)題，可提高處理效率。 – 3) 重復(fù) 2)，直到全部頂點(diǎn)都被訪問(wèn)。 ? 算法 – 1) 訪問(wèn)某個(gè)指定頂點(diǎn) V0； – 2) 從 V0出發(fā)，訪問(wèn) V0的各個(gè)未曾訪問(wèn)的鄰接點(diǎn) W1， W2， … ,Wk。 22/32 V1 V3 V2 V5 V4 V6 G6 深度優(yōu)先遍歷法舉例 遍歷過(guò)程 訪問(wèn)頂點(diǎn) 所過(guò)邊 ?起點(diǎn) V1 V1 ?V1的第 1個(gè)鄰接點(diǎn) V3 V3 （ V1， V3） ?V3的第 1個(gè)鄰接點(diǎn) V1已訪問(wèn)，取下 一個(gè)鄰接點(diǎn) V5
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1