哈夫曼編譯碼器_要點(diǎn)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)1. 問(wèn)題描述,第2 頁(yè)2. 系統(tǒng)設(shè)計(jì),第2 頁(yè)3. 數(shù)據(jù)結(jié)構(gòu)與算法描述, 第5 頁(yè)4. 測(cè)試結(jié)果與分析, 第6 頁(yè)5. 總 結(jié),第10頁(yè)6. 參考文獻(xiàn) ,第10頁(yè)附錄 程序源代碼, 第11 頁(yè)課程設(shè)計(jì)題目1. 問(wèn)題描述利用哈夫曼編碼進(jìn)行信息通信可大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼；在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原） 。對(duì)于雙工信道（既可以雙向傳輸信息的信道） ，每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編/譯碼系統(tǒng)。1.1 基本要求一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：1） I :初始化（In

2、itialization ）。從終端讀入字符集大小n,以及n個(gè)字符和n個(gè)權(quán) 值， 建立哈夫曼樹， 并將它存于文件hfmTree 中。 輸出哈夫曼樹， 及各字符對(duì)應(yīng)的編碼。2） W輸入（Input ）。從終端讀入需要編碼的字符用s,將字符用s存入文件 Tobetran.txt 中。3） E：編碼（Encoding）與譯碼（Decoding）。編碼（ Encoding ） 。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件 htmTree 中讀入） ，對(duì)文件 ToBeTran 中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile 中。譯碼（ Decoding ） 。利用已建好的哈夫曼樹將文件CodeFi

3、le 中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile 中。打印代碼文件（ Print ） 。將文件 CodeFile 以緊湊格式顯示在終端上，每行50 個(gè)代碼。同時(shí)將此字符形式的編碼寫入文件CodePrint 中。4） T:打印哈夫曼樹（Tree Printing ）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrint 中。5） Q:退出程序。返回WINDOWS面。1.2 設(shè)計(jì)思想哈夫曼編碼（Huffman Coding）是一種編碼方式，以哈夫曼樹一即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。是指使用一張?zhí)厥?/p>

4、的編碼表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這種方法是由 David.A.Huffman 發(fā)展起來(lái)的。例如，在英文中， e 的出現(xiàn)概率很高，而z 的出現(xiàn)概率則最低。當(dāng)利用哈夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)， e 極有可能用一個(gè)位（bit） 來(lái)表示，而z 則可能花去25 個(gè)位（不是26） 。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)（byte ） ，即 8個(gè)位。二者相比， e 使用了一般編碼的 1/8 的長(zhǎng)度， z 則使用了 3 倍多。倘若我們能實(shí)現(xiàn)對(duì)于英文中共 18頁(yè)第2頁(yè)各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無(wú)損壓縮的比例。2.3系統(tǒng)模塊劃分main()輸入待 Input編

5、io碼字 符 函初始化函數(shù)E .) 編碼函數(shù)譯 碼 函數(shù)Dec ()e 0dc打印編碼函數(shù)g打印哈夫曼rintnTfieeprinting。圖2-3哈夫曼編/解碼器的程序結(jié)構(gòu)圖2.3.1 初始化算法：程序從文件abc.txt中獲取26個(gè)英文字母的權(quán)值。2.3.2 編碼算法：(1)對(duì)輸入的一段欲編碼的字符串進(jìn)行統(tǒng)計(jì)各個(gè)字符出現(xiàn)的次數(shù)，并它們轉(zhuǎn)化 為權(quán)值w1,w2, ,wN涵成n棵二叉樹的集合F=T1,T2, ,Tn把它們保存到結(jié)構(gòu)體數(shù)組HTn中，其中Ti是按它們的ASQI碼值先后排序。其中每棵二叉樹Ti中只有一 個(gè)帶權(quán)為Wi的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。(2)在HT1.i中選取

6、兩棵根結(jié)點(diǎn)的權(quán)值最小且沒(méi)有被選過(guò)的樹作為左右子樹 構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為左、右子樹上根結(jié)點(diǎn)的權(quán)值之 和。(3)哈夫曼樹已經(jīng)建立后，從葉子到根逆向求每一個(gè)字符的哈夫曼編碼。2.3.3譯碼算法：譯碼的過(guò)程是分解電文中字符串，從根出發(fā)，按字符 0',或'1'確定找左孩子 或右孩子，直至葉子結(jié)點(diǎn)，便求的該子用相應(yīng)字符并輸出接著下一個(gè)字符。3.數(shù)據(jù)結(jié)構(gòu)與算法描述3-1typedef struct int weight;int parent,lchild,rchild;HTNode,* HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹typedef c

7、har *HuffmanCode; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表3-2int min(HuffmanTree t,int i) /求赫夫曼編碼3-3void select(HuffmanTree t,int i,int &s1,int &s2) /-slect 函數(shù)-3-4void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)/ w存放n個(gè)字符的權(quán)值(均0),構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的赫夫曼編碼HC3-20 void main()/主函數(shù)3-5void Initializatio

8、n。/-初始化赫夫曼鏈表3-6void InputCode()/-獲取報(bào)文并寫入文件3-7void Encoding()/-05函數(shù)3-8void Decoding。/-譯碼函數(shù)3-9void Code_printing()/-打印編碼的函數(shù)3-19 void coprint(HuffmanTree start,HuffmanTree HT)/打印赫夫曼樹的函數(shù)共 18頁(yè)第10頁(yè)4 .測(cè)試結(jié)果與分析A186B64C13D22E32F103G21H15I47J57K15L32M20N57O63P15Q1R48S51T80U23V8W18X1Y16Z1表4-1 abc.txt文件中的字母和權(quán)值聲明

9、：程序預(yù)先將 Huffman編碼解碼所需的26個(gè)字母和權(quán)值保存在根目錄下的abc.txt 文件下。先初始化赫夫曼鏈表,輸入r，NJ HE半nK 碼 一褊i =南譯樹4夫碼、曼4釐碼夫 4化篇福打基打. > > > > 工wet c C ( C4-1.按照程序提示輸入i對(duì)Huffman進(jìn)行初始化。4-2.初始化后程序?qū)bc.txt文件中的數(shù)據(jù)進(jìn)行讀取并運(yùn)行編碼函數(shù)進(jìn)行哈夫曼編碼。然后將字母、權(quán)值和哈夫曼編碼存在根目錄下的htmTree.txt文件中。在屏幕顯示出字符、權(quán)值、編碼4-3.輸入w進(jìn)入待編碼字符輸入窗口，并鍵入字符串（注意單詞間無(wú)空格）happynewyear

10、”。-1口1>赫夫曼編碼解碼行編碼、譯碼、打印編碼tappyn e wye at'天期報(bào)支成功艮支薦又稹而景下的shCn-tMt文件中4-4.可以看出所獲得的字符串已經(jīng)存入根目錄下的C tobetran. tJit - 記事本tobetran.txt、EC數(shù)據(jù)結(jié)構(gòu)課程設(shè)詰哈弗曼樹上致?lián)Y(jié)構(gòu)謖程設(shè)計(jì)-即於碼及程.符、 表另碼 喜譯樹 夫碼、曼 蟹碼夫 化翥赫 始人行印開 初輯打離 > > > :> 1 w e t ®文件中五件IFj編輯姐格式©直看W幫助國(guó)Ihdppynewygmr4-5.輸入e進(jìn)行編碼、譯碼和打印編碼功能4-6. 輸 入

11、 t 打 印 哈 夫 曼 樹3115611530151216M1006571145721710341051994619312131118241347239447打印工作結(jié)束赫夫曼編的解碼由于哈夫曼樹過(guò)于巨大，一次截屏無(wú)法完全顯示，使用兩次截屏。以上兩幅圖顯示出來(lái)程序編出的哈夫曼樹的形狀。打印出來(lái)的圖形與教科書上的常見哈夫曼樹略有不同，左邊的數(shù)是右邊數(shù)的父節(jié)點(diǎn) 4-7.輸入q退出程序。5 .總結(jié)5-1、用戶界面設(shè)計(jì)為“菜單”模式，使人們更加容易使用。5-2、在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行 e命令之后，哈夫曼樹已經(jīng)在內(nèi)存了， 不必再讀入。5-3.在編程中使用了很不規(guī)范的編程方法，應(yīng)用了一些臨時(shí)

12、變量來(lái)實(shí)現(xiàn)功能，而大量臨時(shí)變量在代碼中沒(méi)有很好地進(jìn)行命名。這給程序的閱讀和維護(hù)帶來(lái)了極大的困難。5-4.本程序僅能對(duì)26個(gè)小寫字母構(gòu)成的字符串進(jìn)行處理， 并不具有對(duì)漢字等的編碼 處理能力。5-5.設(shè)計(jì)中得到了老師和廣大同學(xué)的幫助，并參考了網(wǎng)絡(luò)上的優(yōu)秀論文和紙質(zhì)文件， 使我的程序設(shè)計(jì)能夠較為順利的進(jìn)行下去。在此我衷心感謝我的老師同學(xué)和對(duì)以上資源 的作者。五、心得體會(huì)通過(guò)這次課程設(shè)計(jì)使我對(duì)哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識(shí)和理解，也使我 更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。開始的時(shí)候，代碼中有許多的 錯(cuò)誤，特別是有一個(gè)“無(wú)法找到文件”的錯(cuò)誤讓我束手無(wú)策，最后還是屏蔽了定義的四 個(gè)頭

13、文件然后慢慢地改正錯(cuò)誤才讓我又看到了希望。然后在實(shí)現(xiàn)文章的讀入時(shí)，由于對(duì) 文件不是太熟悉，只好翻開C語(yǔ)言書本仿照其模式編寫，但后來(lái)進(jìn)入了死循環(huán)，最后的 解決方式是把main函數(shù)里的一個(gè)do -while循環(huán)去掉。在程序中，我還另外加了一個(gè) 功能-輸出哈夫曼樹的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)。這使得我更加的明白了哈夫曼到底是 怎么存儲(chǔ)信息的。6 .參考文獻(xiàn)A：書籍資料1嚴(yán)蔚敏 吳偉民數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）北京：清華大學(xué)出版社2蘇仕華數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)北京：機(jī)械工業(yè)出版社B:網(wǎng)絡(luò)資料1哈夫曼編/譯碼器（課程設(shè)計(jì)）2哈夫曼編碼 附錄程序源代碼哈夫曼編/譯碼器（課程設(shè)計(jì)）2008/5/21#include <

14、;iostream.h>#include <fstream.h>#include <iomanip.h>#include <string.h>#include <malloc.h>#include <stdio.h>#include <iomanip.h> const int UINT_MAX=10000;typedef structint weight;int parent,lchild,rchild;HTNode,* HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹typedef char *HuffmanCo

15、de; / 動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表/ 全局變量 HuffmanTree HT;HuffmanCode HC;int *w,i,j;const int n=26;char *z;int flag=0;int numb=0;/ 求赫夫曼編碼int min(HuffmanTree t,int i)/ 此函數(shù)將要被void select() 調(diào)用int j,flag;int k=UINT_MAX; / 取 k 為不小于可能的值for(j=1;j<=i;j+)if(tj.weight<k&&tj.parent=0) k=tj.weight,flag=j;tflag.pa

16、rent=1;return flag;/slect 函數(shù) void select(HuffmanTree t,int i,int &s1,int &s2)/ s1 為最小的兩個(gè)值中序號(hào)小的那個(gè)int j;s1=min(t,i);s2=min(t,i);if(s1>s2)j=s1;s1=s2;s2=j;/ 參考課本算法6.12HCvoid HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)/ w存放n個(gè)字符的權(quán)值(均>0),構(gòu)造赫夫曼樹 HT,并求出n個(gè)字符的赫夫曼編碼 int m,i

17、,s1,s2,start;int c,f;HuffmanTree p;char *cd;if(n<=1) return;/ 檢測(cè)結(jié)點(diǎn)數(shù)是否可以構(gòu)成樹 m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0 號(hào)單元未用 for(p=HT+1,i=1;i<=n;+i,+p,+w) p->weight=*w;p->parent=0;p->lchild=0; p->rchild=0; for(;i<=m;+i,+p) p->parent=0;for(i=n+1;i<=m;+i) / 建赫夫曼樹

18、 在HT1i-1中選擇parent=0且weight最小的兩個(gè)結(jié)點(diǎn) 淇序號(hào)分別為si和s2 select(HT,i-1,s1,s2);HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/ 從葉子到根逆向求每個(gè)字符的赫夫曼編碼HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/ 分配 n 個(gè)字符編碼的頭指針向量(0 不用 )cd=(char*)malloc(n*sizeof(char); / 分配求編碼的工作空間 cdn-1='

19、0' / 編碼結(jié)束符for(i=1;i<=n;i+) / 逐個(gè)字符求赫夫曼編碼start=n-1; / 編碼結(jié)束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 從葉子到根逆向求編碼if(HTf.lchild=c)cd-start='0' elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char); / 為第 i 個(gè)字符編碼分配空間 strcpy(HCi,&cdstart); / 從 cd 復(fù)制編碼 (串 )到 HC free(cd); /

20、釋放工作空間 / 初始化赫夫曼鏈表void Initialization()flag=1;int num2;cout<<" 下面初始化赫夫曼鏈表"<<endl;w=(int*)malloc(n*sizeof(int);/ 為第 26 個(gè)字符權(quán)值分配空間z=(char*)malloc(n*sizeof(char); / 為第 26 個(gè)字符分配空間cout<<"n 依次顯示 "<<n<<" 個(gè)字符與其權(quán)值和編碼n"<<endl;char base2;/?ifstrea

21、m fin("abc.txt");for(i=0;i<n;i+)fin>>base;*(z+i)=*base;/?fin>>num2;/ 上面 123 行*(w+i)=num2;HuffmanCoding(HT,HC,w,n);/ 打印編碼 cout<<" 字符 "<<setw(6)<<" 權(quán)值 "<<setw(11)<<" 編碼 "<<endl; for(i=1;i<=n;i+)cout<<se

22、tw(3)<<*(z+i-1);cout<<setw(6)<<*(w+i-1)<<setw(12)<<HCi<<endl;/ 將赫夫曼編碼寫入文件 cout<<" 下面將赫夫曼編碼寫入文件"<<endl<<""<<endl;FILE *htmTree;char r=' ','0'if(htmTree=fopen("htmTree.txt","w")=NULL)cou

23、t<<" 不能打開文件"<<endl;return;for(i=0;i<n;i+)fputc(*(z+i),htmTree);fputs(r,htmTree);for(i=0;i<n;i+)fprintf(htmTree,"%6d",*(w+i);fputs(r,htmTree);for(i=1;i<=n;i+)fputs(HCi,htmTree);fputs(r,htmTree);fclose(htmTree);cout<<"已將字符與對(duì)應(yīng)編碼寫入根目錄下文件htmTree.txt中&qu

24、ot;<<endl<<endl;/ 獲取報(bào)文并寫入文件 void InputCode()FILE *tobetran;char str100;if(tobetran=fopen("tobetran.txt","w")=NULL)cout<<" 不能打開文件"<<endl;return;cout<<" 請(qǐng)輸入你想要編碼的字符"<<endl;/字符個(gè)數(shù)應(yīng)當(dāng)小于100gets(str);fputs(str,tobetran);cout<<

25、" 獲取報(bào)文成功 "<<endl;fclose(tobetran);cout<<""<<endl<"報(bào)文存入根目錄下的 tobetran.txt 文件中 "<<endl;/ 編碼函數(shù) void Encoding()cout<<" 下面對(duì)目錄下文件tobetran.txt 中的字符進(jìn)行編碼"<<endl;FILE *tobetran,*codefile;if(tobetran=fopen("tobetran.txt",&

26、quot;rb")=NULL)cout<<" 不能打開文件"<<endl;if(codefile=fopen("codefile.txt","wb")=NULL)cout<<" 不能打開文件"<<endl;char *tran;i=99;tran=(char*)malloc(100*sizeof(char);while(i=99)if(fgets(tran,100,tobetran)=NULL)cout<<" 不能打開文件"&

27、lt;<endl;break;for(i=0;*(tran+i)!='0'i+)for(j=0;j<=n;j+)if(*(z+j-1)=*(tran+i)fputs(HCj,codefile);if(j>n)!"<<endl;cout<<" 字符錯(cuò)誤，無(wú)法編碼 break;cout<<" , 編碼完成 ,"<<endl ；cout<<" 編碼寫入目錄下的 codefile.txt 中 "<<endl<<endl;fcl

28、ose(tobetran);fclose(codefile);free(tran);/ 譯碼函數(shù) void Decoding()cout<<" 下面對(duì)根目錄下文件codefile.txt 中的字符進(jìn)行譯碼"<<endl;FILE *codef,*txtfile;if(txtfile=fopen("Textfile.txt","w")=NULL)cout<<" 不能打開文件"<<endl;txtfile=fopen("Textfile.txt",&q

29、uot;w");if (codef=fopen("codefile.txt","r")=NULL)cout<<" 不能打開文件"<<endl;codef=fopen("codefile.txt","r");char *work,*work2,i2;int i4=0,i,i3;unsigned long length=10000;work=(char*)malloc(length*sizeof(char);fgets(work,length,codef);work

30、2=(char*)malloc(length*sizeof(char);i3=2*n-1;for(i=0;*(work+i-1)!='0'i+)i2=*(work+i);if(HTi3.lchild=0)*(work2+i4)=*(z+i3-1);i4+;i3=2*n-1;i-;else if(i2='0') i3=HTi3.lchild;else if(i2='1') i3=HTi3.rchild;*(work2+i4)='0'fputs(work2,txtfile);cout<<" , 譯碼完成 ,&qu

31、ot;<<endl ；cout<<"內(nèi)容寫入根目錄下的文件texfile.txt中"<<endl<<endl;free(work);/釋放工作區(qū)free(work2);/釋放工作區(qū)fclose(txtfile);/關(guān)閉文件txtfile.txtfclose(codef);/關(guān)閉文件codef.txt/ 打印編碼的函數(shù) void Code_printing()cout<<" 下面打印根目錄下文件CodePrin.txt 中編碼字符"<<endl;FILE * CodePrin,* co

32、defile;if(CodePrin=fopen("CodePrin.txt","w")=NULL) cout<<" 不能打開文件"<<endl;return;if(codefile=fopen("codefile.txt","r")=NULL)cout<<" 不能打開文件"<<endl;return;char *work3;work3=(char*)malloc(51*sizeof(char);if(fgets(work3,5

33、1,codefile)=NULL)cout<<" 不能讀取文件"<<endl;elsedofputs(work3,CodePrin);puts(work3);while(strlen(work3)=50&&fgets(work3,51,codefile)!=NULL);free(work3);cout<<" 打印結(jié)束 "<<endl<<endl;fclose(CodePrin);fclose(codefile);/ 打印赫夫曼樹的函數(shù)void coprint(HuffmanTre

34、e start,HuffmanTree HT) /start=ht+26 這是一個(gè)遞歸算法 if(start!=HT)FILE * TreePrint;if(TreePrint=fopen("TreePrint.txt","a")=NULL)cout<<" 創(chuàng)建文件失敗"<<endl;return;numb+; /number=0 該變量為已被聲明為全局變量coprint(HT+start->rchild,HT);/遞歸先序遍歷cout<<setw(5*numb)<<start->weight<<endl;fprintf(TreePrint,"%dn",start->weight);coprint(HT+start->lchild,HT);numb-;fclose(TreePrint);void Tree_printing(HuffmanTree HT,int w)HuffmanTree p;p=HT+w;/p=HT+26cout<<" 下面打印赫夫曼樹"<<endl;共 18頁(yè)第1 9頁(yè)coprint(p,HT);/