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