打開(kāi)文本圖片集
摘 要 利用哈夫曼編碼可縮短信息傳輸時(shí)間，提高信道利用率。本文分析了用C語(yǔ)言實(shí)現哈夫曼編碼譯碼。
關(guān)鍵詞 C語(yǔ)言 哈夫曼 編碼 譯碼
中圖分類(lèi)號：TP313 文獻標識碼：A
0引言
當今時(shí)代信息高速發(fā)展，利用哈夫曼編碼進(jìn)行通信可提高信道利用率從而獲得更大的利潤。
1算法設計
1.1算法說(shuō)明
哈夫曼樹(shù)也稱(chēng)最優(yōu)二叉樹(shù)。給定一組具有確定權值的葉子結點(diǎn)，可以構造出不同的二叉樹(shù)，二叉樹(shù)的帶權路徑長(cháng)度記為：WPL=∑Wklk，Wk為第k個(gè)葉子結點(diǎn)的權值，lk為從根結點(diǎn)到第k個(gè)葉子結點(diǎn)的路徑長(cháng)度。
1.2算法所需數據結構
表1：結點(diǎn)結構
其中：
Weight：權值；
L_child：左孩子結點(diǎn)信息；
R_child：右孩子結點(diǎn)信息；
Parent：雙親結點(diǎn)信息；
Name：姓名。
1.3算法流程
1.3.1編碼
（1）初始化哈夫曼樹(shù)；
（2）初始化結構體；
（3）輸入葉子權值及名稱(chēng)；
（4）選取兩個(gè)最小權值的葉子；
（5）創(chuàng )建哈夫曼樹(shù)。
1.3.2譯碼
（1）找尋哈夫曼樹(shù)根節點(diǎn)；
（2）遍歷哈夫曼樹(shù)： 1->右子樹(shù)，0->左子樹(shù)；
（3）判斷是否走到葉子節點(diǎn)，若是，打印字符并回歸根節點(diǎn)。
2算法程序實(shí)現
2.1編碼過(guò)程實(shí)現
void Encode（Huff_tree T）{
char r[1000]；
int i， j；
printf（"＼n＼n請輸入需要編碼的字符＼n"）；
gets（r）；
printf（"編碼結果為："）；
for（j=0；r[j]！="＼0"；j++）{
for（i=0；i if（r[j]==T[i].Name） Path（T，i，j）； } } printf（"＼n"）； } 2.2譯碼過(guò)程實(shí)現 void Decode（Huff_tree T） { char r[1000]； int p，R，t，length； R=root（T，&p）； t=R； printf（"＼n請輸入您需要譯碼的字符串：＼n"）； gets（r）； length=strlen（r）； printf（"＼n譯碼結果是：＼n"）； for（int i=0；i if（r[i]=="0"）{ t=T[t].L_child； if（T[t].L_child==-1）{ printf（"%c"，T[t].Name）； t=R； } } else if（r[i]=="1"）{ t=T[t].R_child； if（T[t].R_child==-1）{ printf（"%c"，T[t].Name）； t=R； printf（"＼n＼n"）； 3有效性檢測 在Windows環(huán)境下對程序進(jìn)行編碼譯碼檢測，結果如下： 編碼測試： 輸入值：acbdefacebadd 編碼值：11101101111000110111011001111111100000 輸入值：bacebdf 編碼值：111111101100111110010 譯碼測試： 輸入值：1110110100110000 譯碼值：acfefd 輸入值：00110000111010110100101101001001100010 譯碼值：dcdecfcfeedcdf 經(jīng)驗證，程序運行正常。 4結語(yǔ) 本文給出了哈夫曼樹(shù)的C語(yǔ)言實(shí)現方法并在windows環(huán)境下進(jìn)行了實(shí)現。 參考文獻 [1] 譚浩強.C語(yǔ)言程序設計（第三版）[M].北京：清華大學(xué)出版社，2014. [2] 屈婉玲，耿素云，張立昂.離散數學(xué)[M].北京：高等教育出版社，2008. [3] 嚴蔚敏，吳偉民.數據結構（C版）[M].北京：清華大學(xué)出版社，2012.
