1、計(jì)算機(jī)信息工程學(xué)院數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計(jì) 報(bào) 告題 目： 哈夫曼編碼 專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)（軟件方向） 班 級(jí)： 15計(jì)算機(jī)軟件二班 學(xué) 號(hào)： 姓 名： 郭琪 指導(dǎo)教師： 范智華 完成日期： 2016年6月24日 目 錄摘 要3【關(guān)鍵詞】3哈夫曼編碼4一、需求分析4二、哈夫曼樹(shù)4三、哈夫曼樹(shù)的理論創(chuàng)建過(guò)程如下：41、構(gòu)成初始集合42、選取左右子樹(shù)43、刪除左右子樹(shù)5五、解碼5六、測(cè)試分析61、62、63、6七、運(yùn)行結(jié)果7參考文獻(xiàn)8附錄9致謝14摘 要在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來(lái)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來(lái)越引起人們的重視。電報(bào)通信是傳遞文字的

2、二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長(zhǎng)度盡可能最短，即采用最短碼。利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸?shù)臅r(shí)間，減低傳輸成本。但是，前提要求必須在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)準(zhǔn)備傳輸?shù)臄?shù)據(jù)進(jìn)行預(yù)先編碼，而在接收端將傳輸來(lái)的數(shù)據(jù)進(jìn)行譯碼。本次實(shí)例要實(shí)現(xiàn)一個(gè)簡(jiǎn)單的哈夫曼編譯器。構(gòu)造哈夫曼樹(shù)時(shí)，首先將由n個(gè)字符形成的n個(gè)葉子結(jié)點(diǎn)存放到數(shù)組HTNode的前n個(gè)分量中，然后根據(jù)前文介紹的哈夫曼方法的基本思想，不斷將兩個(gè)小子樹(shù)合并為一個(gè)較大的子樹(shù)，每次構(gòu)成的新子樹(shù)的根結(jié)點(diǎn)順序放到HTNode數(shù)組中的前n個(gè)分量的后面。【關(guān)鍵詞】哈夫曼樹(shù)； 編碼； 解碼； 數(shù)據(jù)壓縮技術(shù)；哈夫曼編

3、碼一、需求分析利用哈夫曼編碼進(jìn)行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r(shí)間，降低傳輸成本。根據(jù)哈夫曼編碼的原理，編寫一個(gè)程序，在用戶輸入結(jié)點(diǎn)權(quán)值的基礎(chǔ)上求哈夫曼編碼。要求：從鍵盤輸入若干字符及每個(gè)字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結(jié)點(diǎn)的權(quán)值，建立哈夫曼樹(shù)，然后對(duì)各個(gè)字符進(jìn)行哈夫曼編碼，最后打印輸出字符及對(duì)應(yīng)的哈夫曼編碼。二、哈夫曼樹(shù) 哈夫曼樹(shù)也稱最優(yōu)二叉樹(shù).給定一組具有確定權(quán)值的葉子結(jié)點(diǎn),可以構(gòu)造出不同的二叉樹(shù),將其中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱為哈夫曼樹(shù).其中,葉子結(jié)點(diǎn)的權(quán)值(weight)是對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量.設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn),從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的

4、路徑長(zhǎng)度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度(weighted path length),記為: WPL=Wklk1å=n k,wk為第k個(gè)葉子結(jié)點(diǎn)的權(quán)值,lk為從根結(jié)點(diǎn)到第k個(gè)葉子結(jié)點(diǎn)的路徑 長(zhǎng)度.三、哈夫曼樹(shù)的理論創(chuàng)建過(guò)程如下：1、構(gòu)成初始集合對(duì)給定的n個(gè)權(quán)值W1,W2,W3,.,Wi,.,Wn構(gòu)成n棵二叉樹(shù)的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉樹(shù)Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左右子樹(shù)均為空。 2、選取左右子樹(shù)在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為新構(gòu)造的二叉樹(shù)的左右子樹(shù)，新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)的根結(jié)點(diǎn)的權(quán)值之和。 3、

5、刪除左右子樹(shù)從F中刪除這兩棵樹(shù)，并把這棵新的二叉樹(shù)同樣以升序排列加入到集合F中。 4、重復(fù)二和三兩步，重復(fù)二和三兩步，直到集合F中只有一棵二叉樹(shù)為止。四、編碼具體操作：（1） 從葉子結(jié)點(diǎn)開(kāi)始按照所儲(chǔ)存的夫結(jié)點(diǎn)的信息向上尋找，若該結(jié)點(diǎn)是夫結(jié)點(diǎn)的左孩子結(jié)點(diǎn)將路徑記為0，是右孩子將路徑記為1。（2） 用臨時(shí)字符數(shù)組cd來(lái)存儲(chǔ)路徑并從后先前存儲(chǔ)。（3） 從1找到的夫結(jié)點(diǎn)開(kāi)始繼續(xù)向上尋找，直到找到根結(jié)點(diǎn)，即parent=0結(jié)束。五、解碼具體操作：（1） 以字符串的形式輸入編碼存于code中。（2） 從根結(jié)點(diǎn)開(kāi)始編碼所給的路徑依次向下尋找。（3） 直到找到葉子結(jié)點(diǎn)為止。（4） 此時(shí)，若code=0，則譯碼

6、結(jié)束，否則繼續(xù)從根結(jié)點(diǎn)開(kāi)始尋找。六、測(cè)試分析1、感覺(jué)文件操作自己并不是很熟練，盡管在向顯示器輸出的時(shí)候并沒(méi)有什么錯(cuò)誤但是讀寫文件的時(shí)候就沒(méi)那么順利了，比如說(shuō)當(dāng)編寫savewithhufcode函數(shù)時(shí)讀文件，卻總不執(zhí)行，后來(lái)通過(guò)斷點(diǎn)測(cè)試發(fā)現(xiàn)每次fgetc()返回值總為-1，于是我考慮是否是文件沒(méi)有打開(kāi)或者文件結(jié)束的緣故，后來(lái)想通了是之前打開(kāi)的文件光標(biāo)讀操作結(jié)束后仍在結(jié)尾故每次總返回-1，故調(diào)用rewind函數(shù)將光標(biāo)位置移動(dòng)到文章開(kāi)始。2、用哈夫曼編碼存儲(chǔ)文件的時(shí)候還應(yīng)注意數(shù)字0,1與字符0,1的不同，不應(yīng)直接在fputc()函數(shù)中直接寫入0,1那么將會(huì)是寫入的文章中什么都沒(méi)有，因?yàn)?在ASCII

7、碼中代表NULL。3、該程序函數(shù)清晰功能明確，程序具有通用性，對(duì)于不同的輸入文章都可進(jìn)行處理，由于采用哈夫曼編碼對(duì)照表，使得查看哈夫曼編碼是效率較高無(wú)需每次遍歷哈夫曼樹(shù)。七、運(yùn)行結(jié)果參考文獻(xiàn)1孫家廣，楊長(zhǎng)青計(jì)算機(jī)圖形學(xué)M北京：清華大學(xué)出版社，199526282Skolink M IRadar HandbookM New York： McGraw-Hill, 19903李旭東，宗光華，畢樹(shù)生等生物工程微操作機(jī)器人視覺(jué)系統(tǒng)的研究4王明亮關(guān)于中國(guó)學(xué)術(shù)期刊標(biāo)準(zhǔn)化數(shù)據(jù)系統(tǒng)工程的進(jìn)展EB/OL http：/wwwcajcdeducn/pub/wm1txt/980810-2html,1998-08-16/1

8、998-10-045 嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)，清華大學(xué)出版社，20076 鄭莉，C+語(yǔ)言程序設(shè)計(jì)（第4版），清華大學(xué)出版社，20107 譚浩強(qiáng)，C程序設(shè)計(jì)（第三版），清華大學(xué)出版社，2005附錄#include <iostream.h>#include <fstream.h>#include <string.h>#include <stdlib.h> typedef struct char data; int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char

9、* * HuffmanCode;void Select(HuffmanTree &HT,int n,int m) HuffmanTree p=HT; int tmp; for(int j=n+1;j<=m;j+) int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x<=j-1;x+) if(px.parent=0&&px.weight<tag1) tag1=px.weight;s1=x; for(int y=1;y<=j-1;y+) if(py.parent=0&&y!=s1&am

10、p;&py.weight<tag2) tag2=py.weight;s2=y; if(s1>s2) /將選出的兩個(gè)節(jié)點(diǎn)中的序號(hào)較小的始終賦給s1 tmp=s1; s1=s2; s2=tmp;ps1.parent=j;ps2.parent=j;pj.lchild=s1;pj.rchild=s2;pj.weight=ps1.weight+ps2.weight; void HuffmanCoding(HuffmanTree &HT,int n,char *w1,int*w2) int m=2*n-1; if(n<=1) return; HT=(HuffmanTree

11、)malloc(m+1)*sizeof(HTNode); HuffmanTree p=HT; for(int i=1;i<=n;i+) pi.data=w1i-1; pi.weight=w2i; pi.parent=pi.lchild=pi.rchild=0; for(;i<=m;i+) pi.weight=pi.parent=pi.lchild=pi.rchild=0; Select(HT,n,m); ofstream outfile; /生成hfmTree文件 outfile.open("hfmTree.txt",ios:out); for (i=1;i&l

12、t;=m;i+)outfile<<HTi.weight<<"t"<<HTi.parent<<"t"<<HTi.lchild <<"t"<<HTi.rchild<<"t"<<endl; outfile.close(); cout<<"初始化結(jié)果已保存在hfmTree文件中n"void ToBeTree() /將正文寫入文件ToBeTree中ofstream outfile;out

13、file.open("ToBeTree.txt",ios:out);outfile<<"THIS PROGRAM IS MYFAVORITE"outfile.close();void Encoding(HuffmanTree &HT,int n) /編碼 HuffmanCode HC; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); char *cd; cd=(char *)malloc(n*sizeof(char); cdn-1='0' for(int k=1;k<=n;

14、k+) int start=n-1; for(int c=k,f=HTk.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCk=(char *)malloc(n-start)*sizeof(char); strcpy(HCk,&cdstart); cout<<"輸出哈夫曼編碼:"<<endl; for(int h=1;h<=n;h+) /輸出編碼 cout<<HTh.data<&

15、lt;":" cout<<HCh; cout<<" " if (h%8=0) cout<<endl; cout<<endl<<"輸出正文編碼:"<<endl; ToBeTree(); /讀取TOBETREE文件里的正文，并進(jìn)行編碼 fstream infile; infile.open("ToBeTree.txt",ios:in); char s80; while(!infile.eof() infile.getline(s,sizeof(s)

16、; infile.close(); fstream outfile; outfile.open("CodeFile.txt",ios:out); int count=0; for (h=0;sh!='0'h+) for(k=1;k<=n;k+) if (sh=HTk.data) cout<<HCk; cout<<" " count+; outfile<<HCk; break; if (count%9=0) cout<<endl; /每輸出7個(gè)換行 outfile.close(); co

17、ut<<"n編碼結(jié)果已保存在文件CodeFile中." cout<<endl;void Decoding(HuffmanTree &HT,int n) /譯碼 int f=2*n-1; fstream infile; infile.open("CodeFile.txt",ios:in); char s1000; while(!infile.eof() infile.getline(s,sizeof(s); infile.close(); int i=0; int j=0; fstream outfile; outfile.

18、open("TextFile.txt",ios:out); while(si!='0') f=2*n-1;while(HTf.lchild!=0)/以f對(duì)應(yīng)的節(jié)點(diǎn)的左孩子的值=0作為結(jié)束 if (sj='0') f=HTf.lchild;else f=HTf.rchild;j+; i=j; cout<<HTf.data; outfile<<HTf.data; outfile.close();cout<<"n譯碼結(jié)果已保存在文件TextFile中."cout<<endl;voi

19、d Print() /印代碼文件 int count=0; fstream infile; infile.open("CodeFile.txt",ios:in); char s1000; while(!infile.eof() infile.getline(s,sizeof(s); for(int i=0;si!='0'i+) cout<<si;count+;if (count%50=0) cout<<endl; /在終端上每行顯示50個(gè)代碼 infile.close();cout<<endl;char menu() /菜

20、單函數(shù) cout<<"功能菜單如下:"<<endl; cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl; cout<<" I:初始化(Initialization) "<<endl; cout<<" E:編碼(Encoding) "<<endl; cout<<" D:譯碼(Decoding) "<<endl; cou

21、t<<" P:打印編碼(Print) "<<endl; cout<<" Q:退出(Exit) "<<endl; cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl; cout<<"請(qǐng)輸入功能字符:"char ch;cin>>ch;return ch;void main() int n; int Array100; char cArray100; HuffmanT

22、ree HT; cout<<"輸入n個(gè)字符:" cin.getline(cArray,100); n=strlen(cArray); cout<<"一共"<<n<<"個(gè)字符.n" cout<<"依次輸入各個(gè)字符的權(quán)值:"<<endl; for (int i=1;i<=n;i+) cin>>Arrayi; int tag; char x=menu(); while(1) switch (x) case 'I':H

23、uffmanCoding(HT,n,cArray,Array);break; case 'E':Encoding(HT,n);break; case 'D':Decoding(HT,n);break; case 'P':Print();break; case 'Q':tag=0;cout<<"結(jié)束"<<endl;break; default:cout<<"你輸入錯(cuò)誤!"<<endl; if(tag=0) break; cout<<"y(繼續(xù)) or n(退出)"<<endl; char ch; cin>>ch; if (