數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三題目二：哈夫曼樹-在線瀏覽
2025-05-12 03:01本頁面
【正文】 譯碼，并輸出譯碼結(jié)果。2. 程序分析哈夫曼樹結(jié)點(diǎn)的儲存結(jié)構(gòu)除了二叉樹所有的雙親域parents，左子樹域lchild，右子樹域rchild。其中由于編碼是一串由0和1組成的字符串，所以code是一個(gè)字符數(shù)組。統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)（頻度）作為葉子的權(quán)重，統(tǒng)計(jì)次數(shù)可以根據(jù)每個(gè)字符不同的ASCII碼。建立每個(gè)葉子的編碼從根結(jié)點(diǎn)開始，規(guī)定通往左子樹路徑記為0，所以需要前序遍歷哈夫曼樹，故編碼過程是以前序遍歷二叉樹為基礎(chǔ)的。編碼信息只要遍歷字符串中每個(gè)字符，從哈夫曼樹中找到相應(yīng)的葉子結(jié)點(diǎn)，取得相應(yīng)的編碼。譯碼則是將編碼串從左到右諸位判別，直到確定一個(gè)字符。由于每個(gè)字符的編碼各不相同，且編碼也是個(gè)字符串，所以只要遍歷編碼串，從哈夫曼樹中找到相應(yīng)的葉子結(jié)點(diǎn)，取得相應(yīng)的字符再將找到的字符連接起來即可。4) 如果所有結(jié)點(diǎn)均沒有記錄字符與取出字符一致，說明該字符的葉子不存在，則將結(jié)點(diǎn)的字符記為取出字符，并將權(quán)重設(shè)為1.5) 重復(fù)（1）（2）（3）（4）步驟，如此遍歷字符串中的所有字符。i字符長度。j字符長度。 HuffTree[j].word=WordStr[i]。 葉子數(shù)++。結(jié)束 時(shí)間復(fù)雜度O(n2),空間復(fù)雜度S(0)構(gòu)造哈夫曼樹自然語言描述：1) 將n個(gè)權(quán)值的葉子結(jié)點(diǎn)存放到數(shù)組huffTree的前n個(gè)分量中2) 通過統(tǒng)計(jì)字符頻度的算法給n個(gè)結(jié)點(diǎn)賦權(quán)值3) 將數(shù)組huffTree中出葉子結(jié)點(diǎn)外的結(jié)點(diǎn)初始化：左右子樹、雙親域?yàn)?；權(quán)值為0；字符編號域?yàn)閈0。偽代碼描述：，除葉子節(jié)點(diǎn)外，所有元素結(jié)點(diǎn)左右子樹、雙親域?yàn)?；權(quán)值為0；字符編號域?yàn)閈0。2) 從葉子結(jié)點(diǎn)開始，如果是哈夫曼樹的左孩子，則將編碼表中的code值賦為0，否則為13) 將指針層層上移，重復(fù)2）直到根結(jié)點(diǎn)4) 將所得編碼逆置，并將編碼最后一位賦為’\0’5) 進(jìn)行下一葉子結(jié)點(diǎn)的編碼算法時(shí)間復(fù)雜度O(n2)，空間復(fù)雜度S(60)為信息編碼自然語言描述：1) 定義字
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1