數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三題目二：哈夫曼樹(shù)(編輯修改稿)
2025-04-21 03:01 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 不斷將兩棵子樹(shù)合并為一棵子樹(shù)，并將新子樹(shù)的根節(jié)點(diǎn)順序存放到數(shù)組huffTree的前n個(gè)分量的后面。偽代碼描述：，除葉子節(jié)點(diǎn)外，所有元素結(jié)點(diǎn)左右子樹(shù)、雙親域?yàn)?；權(quán)值為0；字符編號(hào)域?yàn)閈0。，其下標(biāo)分別即為j1和j2時(shí)間復(fù)雜度O(n)，空間復(fù)雜度S(2)為每個(gè)葉子結(jié)點(diǎn)編碼自然語(yǔ)言描述：1) 初始化一個(gè)字符數(shù)組Code暫存每個(gè)葉子結(jié)點(diǎn)的編碼。2) 從葉子結(jié)點(diǎn)開(kāi)始，如果是哈夫曼樹(shù)的左孩子，則將編碼表中的code值賦為0，否則為13) 將指針層層上移，重復(fù)2）直到根結(jié)點(diǎn)4) 將所得編碼逆置，并將編碼最后一位賦為’\0’5) 進(jìn)行下一葉子結(jié)點(diǎn)的編碼算法時(shí)間復(fù)雜度O(n2)，空間復(fù)雜度S(60)為信息編碼自然語(yǔ)言描述：1) 定義字符串str1儲(chǔ)存編碼2) 遍歷信息字符串中的每一個(gè)字符3) 對(duì)每一個(gè)字符，將其與huffTree前n個(gè)葉子結(jié)點(diǎn)的word域逐個(gè)比較，發(fā)現(xiàn)相同的則將該結(jié)點(diǎn)的編碼串code連接到str1串的末尾。4) 遍歷信息字符串結(jié)束，輸出str1算法時(shí)間復(fù)雜度O(n 2) ，空間復(fù)雜度S(2)譯碼自然語(yǔ)言描述：1) 從編碼串str1第一個(gè)字符開(kāi)始和數(shù)組huffTree第一個(gè)結(jié)點(diǎn)的編碼域第一個(gè)字符進(jìn)行比較。2) 若相等，則繼續(xù)比較兩者的后續(xù)字符3) 否則，從str1第一個(gè)字符與huffTree第二個(gè)節(jié)點(diǎn)的編碼域第一個(gè)字符進(jìn)行比較。4) 重復(fù)上述過(guò)程，當(dāng)huffTree結(jié)點(diǎn)中的字符全部比較完畢則說(shuō)明本趟匹配成功，輸出huffTree結(jié)點(diǎn)的word域值。5) 重復(fù)上述過(guò)程，當(dāng)str1中的字符全部比較完畢，譯碼結(jié)束。 本趟匹配開(kāi)始位置 i 主串CodeStr 回溯。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1