哈夫曼編譯碼器

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

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

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

4、個符號）進(jìn)行編碼。這種方法是由 David.A.Huffman 發(fā)展起來的。 例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率則最低。當(dāng)利用哈夫曼編碼對一 篇英文進(jìn)行壓縮時，e極有可能用一個位（bit）來表示，而z則可能花去25個位（不是 26）。用普通的表示方法時，每個英文字母均占用一個字節(jié)（byte ），即8個位。二者相 比，e使用了一般編碼的1/8的長度，z則使用了 3倍多。倘若我們能實(shí)現(xiàn)對于英文中各個字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例。2.3系統(tǒng)模塊劃分mai n()prin ti ng()圖2-3哈夫曼編/解碼器的程序結(jié)構(gòu)圖2.3.1 初始化算法：程序從文件a

5、bc.txt中獲取26個英文字母的權(quán)值。2.3.2 編碼算法：(1) 對輸入的一段欲編碼的字符串進(jìn)行統(tǒng)計各個字符出現(xiàn)的次數(shù)，并它們轉(zhuǎn)化 為權(quán)值w1,w2,wN構(gòu)成n棵二叉樹的集合F=T1,T2,Tn把它們保存到結(jié)構(gòu) 體數(shù)組HTn中,其中Ti是按它們的ASCH碼值先后排序。其中每棵二叉樹Ti中只有一 個帶權(quán)為Wi的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。(2) 在HT1.i中選取兩棵根結(jié)點(diǎn)的權(quán)值最小且沒有被選過的樹作為左右子樹 構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為左、右子樹上根結(jié)點(diǎn)的權(quán)值之 和。(3) 哈夫曼樹已經(jīng)建立后，從葉子到根逆向求每一個字符的哈夫曼編碼。2.3.3 譯

6、碼算法：譯碼的過程是分解電文中字符串，從根出發(fā)，按字符 0',或'1'確定找左孩子 或右孩子，直至葉子結(jié)點(diǎn)，便求的該子串相應(yīng)字符并輸出接著下一個字符。3. 數(shù)據(jù)結(jié)構(gòu)與算法描述3-1typedef struct int weight;int pare nt,lchild,rchild;HTNode,* Huffma nTree;/動態(tài)分配數(shù)組存儲赫夫曼樹 typedef char *Huffma nCode; /動態(tài)分配數(shù)組存儲赫夫曼編碼表3-2int min(HuffmanTree t,int i)/求赫夫曼編碼3-3 void select(HuffmanTree t

7、,int i,int &s1,int &s2) /-sleet 函數(shù)-3-4void Huffma nCodi ng(Huffma nTree &H T,Huffma nCode & HC,i nt *w,i nt n)/ w存放n個字符的權(quán)值(均0)，構(gòu)造赫夫曼樹HT,并求出n個字符的赫夫曼編碼HC3-5 void In itializati on()3-6 void In putCode()3-7 void En cod in g()3-8 void Decodi ng()3-9 void Code_pri nting()/初始化赫夫曼鏈表-/獲取報文并寫入

8、文件/編碼函數(shù)/譯碼函數(shù)-/打印編碼的函數(shù)3-19 void coprint(HuffmanTree start,HuffmanTree HT)/打印赫夫曼樹的函數(shù)3-20 void main()/主函數(shù)4. 測試結(jié)果與分析A186B64C13D22E32F103G21H15I47J57K15L32M20N57O63P15Q1R48S51T80U23V8W18X1Y16Z1表4-1 abc.txt文件中的字母和權(quán)值聲明：程序預(yù)先將Huffman編碼解碼所需的26個字母和權(quán)值保存在根目錄下的abc.txt 文件下。4-1.按照程序提示輸入i對Huffman進(jìn)行初始化。4-2.初始化后程序?qū)bc

9、.txt文件中的數(shù)據(jù)進(jìn)行讀取并運(yùn)行編碼函數(shù)進(jìn)行哈夫曼編碼。 然后將字母、權(quán)值和哈夫曼編碼存在根目錄下的htmTree.txt文件中。在屏幕顯示出字符、權(quán)值、編碼。4-3.輸入w進(jìn)入待編碼字符輸入窗口，并鍵入字符串（注意單詞間無空格）“ I”happynewyear。57劎入何漪朗斷子訶逬布囁碼，譯碼、打印編碼 <3打印赫天曼樹3熏升<"初妬化赫<w><c>赫夫曼編碼解碼養(yǎng) 宇符, 一行編碼、譯碼、打印編列 打印旃夫曼樹3違開文件中。4-4.可以看出所獲得的字符串已經(jīng)存入根目錄下的tobetra n.txt4-5.輸入e進(jìn)行編碼、譯碼和打印編碼功能。

10、輸夫打印哈曼樹入4-6.t0316115301£121571145721?1034185199481?31213111824134723?447札印工作結(jié)束X M：JC6e iC J * ：M JC KJBKKXXXE赫夫曼編碼解碼由于哈夫曼樹過于巨大，一次截屏無法完全顯示，使用兩次截屏。以上兩幅圖顯示出來程序編出的哈夫曼樹的形狀。打印出來的圖形與教科書上的常 見哈夫曼樹略有不同，左邊的數(shù)是右邊數(shù)的父節(jié)點(diǎn)。4- 7.輸入q退出程序。5總結(jié)5- 1、用戶界面設(shè)計為“菜單”模式，使人們更加容易使用。5-2、在程序的一次執(zhí)行過程中，第一次執(zhí)行 e命令之后，哈夫曼樹已經(jīng)在內(nèi)存了， 不必再讀入

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

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

13、7a65804eed2e73b32bhtml2 哈夫曼編碼 附錄程序源代碼哈夫曼編/譯碼器（課程設(shè)計）2008/5/21#i nclude <iostream.h>#in clude <fstream.h>#i nclude <ioma nip.h>#in clude <stri ng.h>#i nclude <malloc.h>#in clude <stdio.h>#i nclude <ioma nip.h>con st i nt UINT_MAX=10000;typedef structint weight

14、;int parent,lchild,rchild;HTNode,* HuffmanTree;/ 動態(tài)分配數(shù)組存儲赫夫曼樹typedef char *HuffmanCode; / 動態(tài)分配數(shù)組存儲赫夫曼編碼表/ 全局變量 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 為不小于可能的

15、值 for(j=1;j<=i;j+)if(tj.weight<k&&tj.parent=0) k=tj.weight,flag=j;tflag.parent=1; return flag;/slect 函數(shù) void select(HuffmanTree t,int i,int &s1,int &s2) / s1 為最小的兩個值中序號小的那個int j;s1=min(t,i);s2=min(t,i);if(s1>s2)j=s1;s1=s2;s2=j;/ 參考課本算法 6.12void HuffmanCoding(HuffmanTree &

16、;HT,HuffmanCode &HC,int *w,int n)HC / w存放n個字符的權(quán)值(均>0),構(gòu)造赫夫曼樹 HT,并求出n個字符的赫夫曼編碼 int m,i,s1,s2,start;int c,f;HuffmanTree p;char *cd;if(n<=1)return;/ 檢測結(jié)點(diǎn)數(shù)是否可以構(gòu)成樹m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0 號單元未用 for(p=HT+1,i=1;i<=n;+i,+p,+w) p->weight=*w; p->parent=0; p-&g

17、t;lchild=0; p->rchild=0; for(;i<=m;+i,+p) p->parent=0;for(i=n+1;i<=m;+i) / 建赫夫曼樹 / 在 HT1i-1 中選擇 parent=0 且 weight 最小的兩個結(jié)點(diǎn) ,其序號分別為 s1 和 s2 select(HT,i-1,s1,s2);HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/ 從葉子到根逆向求每個字符的赫夫曼編碼 HC=(HuffmanCode)mal

18、loc(n+1)*sizeof(char*);/ 分配 n 個字符編碼的頭指針向量 (0不用 ) cd=(char*)malloc(n*sizeof(char); / 分配求編碼的工作空間 cdn-1='0' / 編碼結(jié)束符 for(i=1;i<=n;i+) / 逐個字符求赫夫曼編碼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*

19、)malloc(n-start)*sizeof(char);/ 為第 i 個字符編碼分配空間 strcpy(HCi,&cdstart); / 從 cd 復(fù)制編碼 (串 )到 HCfree(cd); / 釋放工作空間/ 初始化赫夫曼鏈表 void Initialization()flag=1;int num2;cout<<" 下面初始化赫夫曼鏈表 "<<endl; w=(int*)malloc(n*sizeof(int); / 為第 26 個字符權(quán)值分配空間 z=(char*)malloc(n*sizeof(char); / 為第 26 個字符

20、分配空間 cout<<"n 依次顯示 "<<n<<" 個字符與其權(quán)值和編碼 n"<<endl; char base2;/?ifstream 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

21、)<<" 權(quán)值 "<<setw(11)<<" 編碼 "<<endl; for(i=1;i<=n;i+)cout<<setw(3)<<*(z+i-1); cout<<setw(6)<<*(w+i-1)<<setw(12)<<HCi<<endl;/ 將赫夫曼編碼寫入文件 cout<<" 下面將赫夫曼編碼寫入文件 "<<endl<<""<<

22、;endl;FILE *htmTree;char r=' ','0'if(htmTree=fopen("htmTree.txt","w")=NULL)cout<<" 不能打開文件 "<<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=

23、1;i<=n;i+) fputs(HCi,htmTree); fputs(r,htmTree);fclose(htmTree);cout<<" 已將字符與對應(yīng)編碼寫入根目錄下文件htmTree.txt 中 "<<endl<<endl;/ 獲取報文并寫入文件 void InputCode()FILE *tobetran;char str100;if(tobetran=fopen("tobetran.txt","w")=NULL)cout<<" 不能打開文件 "&l

24、t;<endl;return;cout<<" 請輸入你想要編碼的字符 "<<endl;/ 字符個數(shù)應(yīng)當(dāng)小于 100gets(str);fputs(str,tobetran);cout<<" 獲取報文成功 "<<endl; fclose(tobetran);cout<<""<<endl<" 報文存入根目錄下的 tobetran.txt 文件中 "<<endl;/ 編碼函數(shù) void Encoding()cout<&l

25、t;" 下面對目錄下文件 tobetran.txt 中的字符進(jìn)行編碼 "<<endl;FILE *tobetran,*codefile; if(tobetran=fopen("tobetran.txt","rb")=NULL)cout<<" 不能打開文件 "<<endl; if(codefile=fopen("codefile.txt","wb")=NULL)cout<<" 不能打開文件 "<<e

26、ndl;char *tran;i=99;tran=(char*)malloc(100*sizeof(char);while(i=99) if(fgets(tran,100,tobetran)=NULL) cout<<" 不能打開文件 "<<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<<" 字符錯

27、誤，無法編碼break;"<<endl ;COdefile.txt 中 "<<endl<<endl;COUt<<"編碼完成cout<<" 編碼寫入目錄下的 fClOse(tObetran); fClOse(COdefile); free(tran);/ 譯碼函數(shù) vOid DeCOding()COut<<" 下面對根目錄下文件 COdefile.txt 中的字符進(jìn)行譯碼 "<<endl;FILE *COdef,*txtfile; if(txtfile=

28、fOpen("Textfile.txt","w")=NULL) COut<<" 不能打開文件 "<<endl;txtfile=fOpen("Textfile.txt","w");if (COdef=fOpen("COdefile.txt","r")=NULL)COut<<" 不能打開文件 "<<endl;codef=fopen("codefile.txt","

29、r");char *work,*work2,i2;int i4=0,i,i3;unsigned long length=10000; work=(char*)malloc(length*sizeof(char);fgets(work,length,codef); work2=(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

30、(i2='0') i3=HTi3.lchild;else if(i2='1') i3=HTi3.rchild; *(work2+i4)='0' fputs(work2,txtfile);cout<<"譯碼完成"<<endl ;cout<<"內(nèi)容寫入根目錄下的文件textfile.txt中"<<endl<<endl;free(work);/釋放工作區(qū)free(work2);/釋放工作區(qū)fclose(txtfile);/關(guān)閉文件 txtfile.txt

31、fclose(codef); /關(guān)閉文件 codef.txt/ 打印編碼的函數(shù) void Code_printing()cout<<" 下面打印根目錄下文件 CodePrin.txt 中編碼字符 "<<endl; FILE * CodePrin,* codefile;if(CodePrin=fopen("CodePrin.txt","w")=NULL)cout<<" 不能打開文件 "<<endl;return;if(codefile=fopen("codef

32、ile.txt","r")=NULL)cout<<" 不能打開文件 "<<endl;return;char *work3;work3=(char*)malloc(51*sizeof(char); if(fgets(work3,51,codefile)=NULL)cout<<" 不能讀取文件 "<<endl;elsedofputs(work3,CodePrin);puts(work3);while(strlen(work3)=50&&fgets(work3,51,

33、codefile)!=NULL); free(work3);cout<<" 打印結(jié)束 "<<endl<<endl;fclose(CodePrin);fclose(codefile);/ 打印赫夫曼樹的函數(shù) void coprint(HuffmanTree start,HuffmanTree HT)/start=ht+26 這是一個遞歸算法if(start!=HT)FILE * TreePrint;if(TreePrint=fopen("TreePrint.txt","a")=NULL)cout<

34、;<" 創(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;coprint(p,HT); /p=HT+26 cout<<&qu