分類導(dǎo)航

C++哈夫曼樹編碼和譯碼的實現(xiàn)

發(fā)布時間：2017年02月16日作者：文章轉(zhuǎn)自網(wǎng)絡(luò)，版權(quán)歸原作者所有，反饋可立刻刪除 (該文來自筆記，點擊查看原文)

一．背景介紹：

　　給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。

二．實現(xiàn)步驟：

　　1.構(gòu)造一棵哈夫曼樹

　　2.根據(jù)創(chuàng)建好的哈夫曼樹創(chuàng)建一張哈夫曼編碼表

　　3.輸入一串哈夫曼序列，輸出原始字符

三．設(shè)計思想：

　　1.首先要構(gòu)造一棵哈夫曼樹，哈夫曼樹的結(jié)點結(jié)構(gòu)包括權(quán)值，雙親，左右孩子；假如由n個字符來構(gòu)造一棵哈夫曼樹，則共有結(jié)點2n-1個；在構(gòu)造前，先初始化，初始化操作是把雙親，左右孩子的下標值都賦為0；然后依次輸入每個結(jié)點的權(quán)值

2.第二步是通過n-1次循環(huán)，每次先找輸入的權(quán)值中最小的兩個結(jié)點，把這兩個結(jié)點的權(quán)值相加賦給一個新結(jié)點，，并且這個新結(jié)點的左孩子是權(quán)值最小的結(jié)點，右孩子是權(quán)值第二小的結(jié)點；鑒于上述找到的結(jié)點都是雙親為0的結(jié)點，為了下次能正確尋找到剩下結(jié)點中權(quán)值最小的兩個結(jié)點，每次循環(huán)要把找的權(quán)值最小的兩個結(jié)點的雙親賦值不為0（i）.就這樣通過n-1循環(huán)下、操作，創(chuàng)建了一棵哈夫曼樹，其中，前n個結(jié)點是葉子（輸入的字符結(jié)點）后n-1個是度為2的結(jié)點

3.編碼的思想是逆序編碼，從葉子結(jié)點出發(fā)，向上回溯，如果該結(jié)點是回溯到上一個結(jié)點的左孩子，則在記錄編碼的數(shù)組里存“0”，否則存“1”，注意是倒著存；直到遇到根結(jié)點（結(jié)點雙親為0），每一次循環(huán)編碼到根結(jié)點，把編碼存在編碼表中，然后開始編碼下一個字符（葉子）

4．譯碼的思想是循環(huán)讀入一串哈夫曼序列，讀到“0”從根結(jié)點的左孩子繼續(xù)讀，讀到“1”從右孩子繼續(xù)，如果讀到一個結(jié)點的左孩子和右孩子是否都為0，如果是說明已經(jīng)讀到了一個葉子（字符），翻譯一個字符成功，把該葉子結(jié)點代表的字符存在一個存儲翻譯字符的數(shù)組中，然后繼續(xù)從根結(jié)點開始讀，直到讀完這串哈夫曼序列，遇到結(jié)束符便退出翻譯循環(huán)

四．源代碼：

移動開發(fā)培訓(xùn),Android培訓(xùn),安卓培訓(xùn),手機開發(fā)培訓(xùn),手機維修培訓(xùn),手機軟件培訓(xùn) 哈夫曼編碼譯碼

五．運行截圖：

移動開發(fā)培訓(xùn),Android培訓(xùn),安卓培訓(xùn),手機開發(fā)培訓(xùn),手機維修培訓(xùn),手機軟件培訓(xùn)

分類導(dǎo)航

C++哈夫曼樹編碼和譯碼的實現(xiàn)

延伸閱讀

我想了解如何學(xué)習(xí)