數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三題目二：哈夫曼樹-文庫(kù)吧
2025-03-10 03:01 本頁(yè)面
【正文】 判別，直到確定一個(gè)字符。這可以用生成哈夫曼樹的逆過(guò)程實(shí)現(xiàn)。由于每個(gè)字符的編碼各不相同，且編碼也是個(gè)字符串，所以只要遍歷編碼串，從哈夫曼樹中找到相應(yīng)的葉子結(jié)點(diǎn)，取得相應(yīng)的字符再將找到的字符連接起來(lái)即可。 存儲(chǔ)結(jié)構(gòu)哈夫曼樹結(jié)點(diǎn)儲(chǔ)存結(jié)構(gòu)wordweightparentLChildRChild哈夫曼樹順序存儲(chǔ)結(jié)構(gòu)wordweightlchildparentsrchild0A351311B251312C151413\0400414\075312 關(guān)鍵算法分析統(tǒng)計(jì)字符的頻度自然語(yǔ)言描述：1) 取出字符串中的一個(gè)字符2) 遍歷所有初始化的哈夫曼樹結(jié)點(diǎn)3) 如果結(jié)點(diǎn)中有記錄代表的字符且字符等于取出的字符，說(shuō)明該字符的葉子存在，則將該結(jié)點(diǎn)的權(quán)加一。4) 如果所有結(jié)點(diǎn)均沒有記錄字符與取出字符一致，說(shuō)明該字符的葉子不存在，則將結(jié)點(diǎn)的字符記為取出字符，并將權(quán)重設(shè)為1.5) 重復(fù)（1）（2）（3）（4）步驟，如此遍歷字符串中的所有字符。偽代碼：(int i=0。i字符長(zhǎng)度。i++) (int j=0。j字符長(zhǎng)度。j++) if (WordStr[i]==HuffTree[j].word) ++ break。 HuffTree[j].word=WordStr[i]。 HuffTree[j].weight=1。 葉子數(shù)++。 break。結(jié)束 時(shí)間復(fù)雜度O(n2),空間復(fù)雜度S(0)構(gòu)造哈夫曼樹自然語(yǔ)言描述：1) 將n個(gè)權(quán)值的葉子結(jié)點(diǎn)存放到數(shù)組huffTree的前n個(gè)分量中2) 通過(guò)統(tǒng)計(jì)字符頻度的算法給n個(gè)結(jié)點(diǎn)賦權(quán)值3) 將數(shù)組huffTree中出葉子結(jié)點(diǎn)外的結(jié)點(diǎn)初始化：左右子樹、雙親域?yàn)?；權(quán)值為0；字符編號(hào)域?yàn)閈0。4)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1