數(shù)據(jù)結(jié)構(gòu)實驗三題目二：哈夫曼樹(完整版)
【正文】 回溯算法時間復(fù)雜度O(n2)1. 程序運(yùn)行結(jié)果測試主函數(shù)流程：開始測試的字符串為：I love data structure,I love will try my best to study data structure建立哈夫曼樹建立編碼表編碼解碼輸出長度，比較壓縮效果結(jié)束測試條件：問題規(guī)模n的數(shù)量級為1。在n個帶權(quán)葉子結(jié)點所構(gòu)成的二叉樹中，滿二叉樹或完全二叉樹不一定是最優(yōu)二叉樹。通過本實驗我也總結(jié)了一些經(jīng)驗，那就是再修改程序的時候，不要死轉(zhuǎn)牛角尖，要從大處著手，逐步深入，逐個修改，還要用聯(lián)系的觀點來看程序，有時候一個地方錯了，會引起很多個錯誤，而顯示錯誤的句子本身可能會沒有錯誤，只是與之相關(guān)聯(lián)的一些語句發(fā)生了錯誤而引起的錯誤。哈夫曼樹的應(yīng)用非常廣泛，在通信中，采用0,1的不同排列來表示不同的字符，而哈夫曼樹在數(shù)據(jù)編碼中的應(yīng)用，若每個字符出現(xiàn)的頻率相同，則可以采用等長的二進(jìn)制編碼，若頻率不同，則可以采用不等長的二進(jìn)編碼，頻率較大的采用位數(shù)較少的編碼，頻率較小的字符采用位數(shù)較多的編碼，這樣可以使字符的整體編碼長度最小，哈夫曼編碼就是一種不等長的二進(jìn)制編碼，且哈夫曼樹是一種最優(yōu)二叉樹，它的編碼也是一種最優(yōu)編碼，在哈夫曼樹中，規(guī)定往左編碼為0，往右編碼為1，則得到葉子結(jié)點編碼為從根結(jié)點到葉子結(jié)點中所有路徑中0和1的順序排列。哈夫曼樹是根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。各項功能均能正常運(yùn)行。4) 遍歷信息字符串結(jié)束，輸出str1算法時間復(fù)雜度O(n 2) ，空間復(fù)雜度S(2)譯碼自然語言描述：1) 從編碼串str1第一個字符開始和數(shù)組huffTree第一個結(jié)點的編碼域第一個字符進(jìn)行比較。 HuffTree[j].weight=1。 存儲結(jié)構(gòu)哈夫曼樹結(jié)點儲存結(jié)構(gòu)wordweightparen
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1