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

楊野

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

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

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

0引言

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

1算法設(shè)計(jì)

1.1算法說明

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

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

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

其中：

Weight：權(quán)值；

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

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

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

Name：姓名。

1.3算法流程

1.3.1編碼

（1）初始化哈夫曼樹；

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

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

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

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

1.3.2譯碼

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

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

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

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

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

void Encode（Huff_tree T）{

char r[1000]；

int i， j；

printf（"＼n＼n請(qǐng)輸入需要編碼的字符＼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譯碼過程實(shí)現(xiàn)

void Decode（Huff_tree T） {

char r[1000]；

int p，R，t，length；

R=root（T，&p）；

t=R；

printf（"＼n請(qǐng)輸入您需要譯碼的字符串：＼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有效性檢測(cè)

在Windows環(huán)境下對(duì)程序進(jìn)行編碼譯碼檢測(cè)，結(jié)果如下：

編碼測(cè)試：

輸入值：acbdefacebadd

編碼值：11101101111000110111011001111111100000

輸入值：bacebdf

編碼值：111111101100111110010

譯碼測(cè)試：

輸入值：1110110100110000

譯碼值：acfefd

輸入值：00110000111010110100101101001001100010

譯碼值：dcdecfcfeedcdf

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

4結(jié)語

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

參考文獻(xiàn)

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

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

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