huffman算法c语言实验报告,huffman二叉树实验报告--数据结构(c语言).doc
江海強(qiáng) PAGE 7
數(shù) 據(jù) 結(jié) 構(gòu) 作 業(yè) 報(bào) 告
——Huffman二叉樹(shù)實(shí)驗(yàn)報(bào)告
姓名：江海強(qiáng)
班級(jí)：070921班
學(xué)號(hào)上機(jī)時(shí)間：2010-
報(bào)告時(shí)間：2010-10-26
摘要
1.實(shí)驗(yàn)?zāi)康?/p>
本實(shí)驗(yàn)是為了讓我們深入了解Huffman二叉樹(shù)，學(xué)會(huì)使用Huffman編碼對(duì)數(shù)據(jù)進(jìn)行無(wú)損壓縮，最終能夠靈活運(yùn)用Huffman二叉樹(shù)。
2.實(shí)驗(yàn)方法
利用遞歸的方法創(chuàng)建Huffman二叉樹(shù)，且利用了二叉樹(shù)的性質(zhì)對(duì)字符串進(jìn)行編碼和譯碼。
3.實(shí)驗(yàn)結(jié)果
此程序是在C++環(huán)境中運(yùn)行的。由后面的運(yùn)行出來(lái)的結(jié)果且由驗(yàn)證解碼的結(jié)果可以得知，此程序是正確無(wú)誤的。由此我們還可以看出利用Huffman編碼可以大大節(jié)省空間復(fù)雜度。
內(nèi)容
一．問(wèn)題重述
設(shè)計(jì)一個(gè)程序，首先讀入一個(gè)ASCII文件，統(tǒng)計(jì)文檔中字符出現(xiàn)的頻度，并根據(jù)頻度對(duì)每個(gè)字符生成Huffman編碼。需要打印出原始數(shù)據(jù)、每個(gè)字符對(duì)應(yīng)的Huffman編碼以及原文檔的Huffman編碼。還要按照Huffman樹(shù)對(duì)編碼后的數(shù)據(jù)進(jìn)行解碼且驗(yàn)證解碼的結(jié)果。最后輸出一些統(tǒng)計(jì)數(shù)據(jù)，如總編碼長(zhǎng)度、編碼效率等。
二．算法描述
本程序除了運(yùn)用一些條件語(yǔ)句，判斷語(yǔ)句之外，主要是運(yùn)用了二叉樹(shù)的性質(zhì)來(lái)設(shè)計(jì)程序的。
本程序利用二叉樹(shù)來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼。約定了左分支表示字符'0'，右分支表示字符'1'，則可以從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串作為該葉子結(jié)點(diǎn)字符的編碼。
假設(shè)每種字符在輸入的字符串中出現(xiàn)的次數(shù)為，其編碼長(zhǎng)度為，字符串中只有n種字符，則字符串總長(zhǎng)為(即二叉樹(shù)上帶權(quán)路徑的長(zhǎng)度)：
WPL =
當(dāng)輸入字符串jiang_hai_qiang時(shí)，
即可建立Huffman樹(shù)，如下面兩表所示，
根據(jù)此３表可以建立如右圖①的Huffman
３
二叉樹(shù)的結(jié)構(gòu)圖
３２２２１例如n的頻率為2，q的頻率為1，
３
２
２
２
１
這兩個(gè)結(jié)點(diǎn)的共同parent結(jié)點(diǎn)的頻率為圖①１
圖①
１
１
2+1=3。
編碼表：
編碼表：
編碼頻率：
編碼長(zhǎng)度：
編碼表：
編碼頻率：
編碼長(zhǎng)度：
j:1110
1
4
g:100
2
3
i:110
3
3
_:101
2
3
a:00
3
2
h:1111
1
4
n:010
2
3
q:011
1
3
表1
num
num
weight
parent
lchild
rchild
1
1
9
0
0
2
3
12
0
0
3
3
13
0
0
4
2
10
0
0
5
2
11
0
0
6
2
11
0
0
7
1
9
0
0
8
1
10
0
0
9
2
12
1
7
10
3
13
4
8
11
4
14
5
6
12
5
14
2
9
13
6
15
3
10
14
9
15
11
12
15
15
0
13
14
表2
由此可以算出WPL=2×3+3×(3+2+2+2+1)+4×(1+1)=42。
開(kāi)始
開(kāi)始
輸入一串字符數(shù)組，用m來(lái)記錄字符串個(gè)數(shù)，n來(lái)記錄
輸入一串字符數(shù)組，用m來(lái)記錄字符串個(gè)數(shù)，n來(lái)記錄字符串中不同字符的個(gè)數(shù)。
用for語(yǔ)句把不同字符賦值給數(shù)組b[]
用for語(yǔ)句把不同字符賦值給數(shù)組b[]。
結(jié)束
結(jié)束
調(diào)用函數(shù)Calculate()，
調(diào)用函數(shù)Calculate()，
計(jì)算不同字符的個(gè)數(shù)，
并把結(jié)果賦值給A[]。
最后調(diào)用
最后調(diào)用HuffmanDecoding()，對(duì)輸入的二進(jìn)制編碼進(jìn)行解碼。
調(diào)用HuffmanCoding()，
調(diào)用HuffmanCoding()，構(gòu)造Huffman二叉樹(shù)HT，并求出Huffman編碼HC。首先對(duì)前n個(gè)結(jié)點(diǎn)初始化，也對(duì)n+1到2n-1個(gè)結(jié)點(diǎn)初始化。調(diào)用Select()構(gòu)建Huffman二叉樹(shù)；還讀出ASCII1文件，并且求出了每個(gè)字符的Huffman編碼。
調(diào)用SC_HuffmanCoding()，輸出Huffman編碼
調(diào)用
調(diào)用函數(shù)ASCII2()，讀出ASCII2文件
三．變量說(shuō)明
全局變量A[]是用來(lái)存儲(chǔ)字符的權(quán)值的。
weight代表的是該結(jié)點(diǎn)的權(quán)值。
程序中有m=2*n-1，是為Huffman二叉樹(shù)開(kāi)辟2n-1個(gè)結(jié)點(diǎn)。
在主函數(shù)中，m是用來(lái)記錄輸入字符串的個(gè)數(shù)的；n是用來(lái)記錄有多少種字符的；a[]則是完整地記錄輸入的字符串；而b[]是記錄輸入字符串中的不同字符。
HT表示Huffman樹(shù)；而HC表示Huffman編碼。
其中還要說(shuō)明的一些C++語(yǔ)句：如cout<>a代表的輸入語(yǔ)句；outfile<
四．函數(shù)與思路說(shuō)明
此程序有1個(gè)主函數(shù)和7個(gè)子函數(shù)。其中子函數(shù)分別為Calculate()，Select()，ASCII1()，ASC
總結(jié)
以上是生活随笔為你收集整理的huffman算法c语言实验报告,huffman二叉树实验报告--数据结构(c语言).doc的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： python3迭代器是什么,python
- 下一篇： pmw调光c语言程序,51单片机led灯