用C語言實現哈夫曼編碼譯碼

楊野

摘 要 利用哈夫曼編碼可縮短信息傳輸時間，提高信道利用率。本文分析了用C語言實現哈夫曼編碼譯碼。

關鍵詞 C語言 哈夫曼 編碼 譯碼

中圖分類號：TP313 文獻標識碼：A

0引言

當今時代信息高速發展，利用哈夫曼編碼進行通信可提高信道利用率從而獲得更大的利潤。

1算法設計

1.1算法說明

哈夫曼樹也稱最優二叉樹。給定一組具有確定權值的葉子結點，可以構造出不同的二叉樹，二叉樹的帶權路徑長度記為：WPL=∑Wklk，Wk為第k個葉子結點的權值，lk為從根結點到第k個葉子結點的路徑長度。

1.2算法所需數據結構

表1：結點結構

其中：

Weight：權值；

L_child：左孩子結點信息；

R_child：右孩子結點信息；

Parent：雙親結點信息；

Name：姓名。

1.3算法流程

1.3.1編碼

（1）初始化哈夫曼樹；

（2）初始化結構體；

（3）輸入葉子權值及名稱；

（4）選取兩個最小權值的葉子；

（5）創建哈夫曼樹。

1.3.2譯碼

（1）找尋哈夫曼樹根節點；

（2）遍歷哈夫曼樹： 1->右子樹，0->左子樹；

（3）判斷是否走到葉子節點，若是，打印字符并回歸根節點。

2算法程序實現

2.1編碼過程實現

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譯碼過程實現

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環境下對程序進行編碼譯碼檢測，結果如下：

編碼測試：

輸入值：acbdefacebadd

編碼值：11101101111000110111011001111111100000

輸入值：bacebdf

編碼值：111111101100111110010

譯碼測試：

輸入值：1110110100110000

譯碼值：acfefd

輸入值：00110000111010110100101101001001100010

譯碼值：dcdecfcfeedcdf

經驗證，程序運行正常。

4結語

本文給出了哈夫曼樹的C語言實現方法并在windows環境下進行了實現。

參考文獻

[1] 譚浩強.C語言程序設計（第三版）[M].北京：清華大學出版社，2014.

[2] 屈婉玲，耿素云，張立昂.離散數學[M].北京：高等教育出版社，2008.

[3] 嚴蔚敏，吳偉民.數據結構（C版）[M].北京：清華大學出版社，2012.