用C語言實現(xiàn)哈夫曼編碼譯碼

楊野

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

關(guān)鍵詞 C語言 哈夫曼 編碼 譯碼

中圖分類號：TP313 文獻(xiàn)標(biāo)識碼：A

0引言

當(dāng)今時代信息高速發(fā)展，利用哈夫曼編碼進(jìn)行通信可提高信道利用率從而獲得更大的利潤。

1算法設(shè)計

1.1算法說明

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

1.2算法所需數(shù)據(jù)結(jié)構(gòu)

表1：結(jié)點結(jié)構(gòu)

其中：

Weight：權(quán)值；

L_child：左孩子結(jié)點信息；

R_child：右孩子結(jié)點信息；

Parent：雙親結(jié)點信息；

Name：姓名。

1.3算法流程

1.3.1編碼

（1）初始化哈夫曼樹；

（2）初始化結(jié)構(gòu)體；

（3）輸入葉子權(quán)值及名稱；

（4）選取兩個最小權(quán)值的葉子；

（5）創(chuàng)建哈夫曼樹。

1.3.2譯碼

（1）找尋哈夫曼樹根節(jié)點；

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

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

2算法程序?qū)崿F(xiàn)

2.1編碼過程實現(xiàn)

void Encode（Huff_tree T）{

char r[1000]；

int i， j；

printf（"＼n＼n請輸入需要編碼的字符＼n"）；

gets（r）；

printf（"編碼結(jié)果為："）；

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譯碼過程實現(xiàn)

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譯碼結(jié)果是：＼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)行編碼譯碼檢測，結(jié)果如下：

編碼測試：

輸入值：acbdefacebadd

編碼值：11101101111000110111011001111111100000

輸入值：bacebdf

編碼值：111111101100111110010

譯碼測試：

輸入值：1110110100110000

譯碼值：acfefd

輸入值：00110000111010110100101101001001100010

譯碼值：dcdecfcfeedcdf

經(jīng)驗證，程序運行正常。

4結(jié)語

本文給出了哈夫曼樹的C語言實現(xiàn)方法并在windows環(huán)境下進(jìn)行了實現(xiàn)。

參考文獻(xiàn)

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

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

[3] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C版）[M].北京：清華大學(xué)出版社，2012.