哈夫曼樹與樹的應(yīng)用-文庫(kù)吧在線文庫(kù)
【正文】 int root。 int n。 /* 樹類型的指針類型 */ Hu Junfeng 28 28 父指針表示特點(diǎn) ? 結(jié)點(diǎn)順序存放，結(jié)點(diǎn)的位置由結(jié)點(diǎn)在數(shù)組中的下標(biāo)給出。 /* 樹類型的指針類型 */ struct ParTree { struct ParTreeNode nodelist[MAXNUM]。這樣就使得譯碼可以一個(gè)字符一個(gè)字符地進(jìn)行 ， 不需要在字符與字符之間添加分隔符 Hu Junfeng 23 信息編碼 1 ? 定長(zhǎng)編碼 – 所有的字符都具有相同的編碼長(zhǎng)度 ? 如 26個(gè)字符： A, B, C, D, …, Z A: 00000 B: 00001 C: 00010 D: 00011 …… Z: 11001 信息發(fā)送 信息接收 編碼： 00000 00001 00001 譯碼： 00000 00001 00001 A B B ABB… 線路傳輸 Hu Junfeng 24 哈夫編碼： 在概率意義上平均碼長(zhǎng)最短 ? 互不為子串？ 145 220 80 100 50 65 50 0 1 1 0 1 { (hot,50), (warm,65),(mild,120), (cold,80), (very cold,50)} 120 1 0 365 0 hot 111 warm 01 mild 10 cold 00 very cold 110 Hu Junfeng 25 25 樹和樹林的存儲(chǔ)表示 ? 選擇存儲(chǔ)表示方法原則 ：結(jié)點(diǎn)本身 +結(jié)點(diǎn)之間的關(guān)系 ? 樹的存儲(chǔ)表示（三種鏈表結(jié)構(gòu)） – 父指針表示法 [雙親表示法 ] – 子表表示法 [孩子表示法 ] – 長(zhǎng)子 兄弟表示法 [孩子兄弟表示法 ] ? 樹林的存儲(chǔ)表示 Hu Junfeng 26 26 樹的父指針表示法 ? 方法： 用一組連續(xù)空間 ， 即一維數(shù)組存儲(chǔ)樹的結(jié)點(diǎn) ， 結(jié)點(diǎn)存放的次序是任意的 ， 數(shù)組元素為結(jié)構(gòu)體類型 ， 結(jié)點(diǎn)類型定義為： struct ParTreeNode /* 樹中結(jié)點(diǎn)結(jié)構(gòu) */ { DataType info。 /* 哈夫曼樹根在數(shù)組中的位置 */ struct HtNode *ht。 ww parent llink
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1