數(shù)據(jù)結構課程設計哈夫曼編譯碼器

1、數(shù)據(jù)結構課程設計設計題目：哈弗曼編/譯碼器 專 業(yè)：網(wǎng)絡工程 班 級：24070901 學 號：2407090133 姓 名：王 璇目 錄1. 問題描述第 2頁2. 系統(tǒng)設計第 2頁3. 數(shù)據(jù)結構與算法描述第 5頁4. 測試結果與分析第 6頁5. 總 結第10頁6. 參考文獻第10頁附錄 程序源代碼第11頁課程設計題目1. 問題描述利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。試為這樣的信息傳輸寫一個哈夫曼編/譯碼系統(tǒng)。2. 系統(tǒng)設計2.1 設計目標一個完整的系統(tǒng)應

2、具有以下功能：1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。輸出哈夫曼樹，及各字符對應的編碼。2）W：輸入（Input）。從終端讀入需要編碼的字符串s，將字符串s存入文件Tobetran.txt中。3）E：編碼（Encoding）與譯碼（Decoding）。編碼（Encoding）。利用已建好的哈夫曼樹（如不在內存，則從文件htmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼

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

4、進行編碼。這種方法是由David.A.Huffman發(fā)展起來的。例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均占用一個字節(jié)（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現(xiàn)對于英文中各個字母出現(xiàn)概率的較準確的估算，就可以大幅度提高無損壓縮的比例。2.3 系統(tǒng)模塊劃分main()Initialization（）初始化函數(shù)Input()輸入待編碼字符函數(shù)Encoding（）編碼函數(shù)Code_prin

5、ting()打印編碼函數(shù)Tree_printing()打印哈夫曼樹圖2-3 哈夫曼編/解碼器的程序結構圖 初始化算法： 構造huffman tree的構造函數(shù)和析構函數(shù) 編碼算法：    （1）對輸入的一段欲編碼的字符串進行統(tǒng)計各個字符出現(xiàn)的次數(shù)，并它們轉化為權值w1,w2,，wN構成n棵二叉樹的集合F=T1,T2,，Tn把它們保存到結構體數(shù)組HTn中,其中Ti是按它們的ASC碼值先后排序。其中每棵二叉樹Ti中只有一個帶權為Wi的根結點的權值為其左、右子樹上根結點的權值之和。   （2）在HT1.i中選取兩棵根結點的權值最小且沒有被選過的樹作為左右子樹構造一棵新的

6、二叉樹，且置新的二叉樹的根結點的權值為左、右子樹上根結點的權值之和。   （3）哈夫曼樹已經建立后，從葉子到根逆向求每一個字符的哈夫曼編碼。 2.3.3 譯碼算法：     譯碼的過程是分解電文中字符串，從根出發(fā)，按字符'0',或'1'確定找左孩子或右孩子，直至葉子結點，便求的該子串相應字符并輸出接著下一個字符。3. 數(shù)據(jù)結構與算法描述3-1typedef struct int weight; int parent,lchild,rchild;HTNode,* HuffmanTree; /動態(tài)分配數(shù)組存儲赫夫曼樹 

7、0;typedef char *HuffmanCode; /動態(tài)分配數(shù)組存儲赫夫曼編碼表3-2 int min(HuffmanTree t,int i) / -求赫夫曼編碼-3-3 void select(HuffmanTree t,int i,int &s1,int &s2) /-slect函數(shù)-3-4 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)/ w存放n個字符的權值(均>0),構造赫夫曼樹HT,并求出n個字符的赫夫曼編碼HC3-5 void Initializati

8、on() /-初始化赫夫曼鏈表-3-6 void InputCode() /-獲取報文-3-7 void Encoding() /-編碼函數(shù)-3-8 void Decoding() /-譯碼函數(shù)-3-9 void Code_printing() /-打印編碼的函數(shù)-3-19 void coprint(HuffmanTree start,HuffmanTree HT) /-打印赫夫曼樹的函數(shù)-3-20 void main() /-主函數(shù)-4. 測試結果與分析A186B64C13D22E32F103G21H15I47J57K15L32M20N57O63P15Q1R48S51T80U23V8W18X

9、1Y16Z1表4-1 abc.txt文件中的字母和權值聲明：程序預先將Huffman編碼解碼所需的26個字母和權值保存在根目錄下的abc.txt文件下。4-1.按照程序提示輸入i對Huffman進行初始化。4-2.初始化后程序對abc.txt文件中的數(shù)據(jù)進行讀取并運行編碼函數(shù)進行哈夫曼編碼。然后將字母、權值和哈夫曼編碼存在根目錄下的htmTree.txt文件中。在屏幕顯示出字符、權值、編碼。4-3.輸入w進入待編碼字符輸入窗口，并鍵入字符串（注意單詞間無空格）“happynewyear”。4-4.可以看出所獲得的字符串已經存入根目錄下的tobetran.txt文件中。4-5.輸入e進行編碼、譯

10、碼和打印編碼功能。4-6.輸入t打印哈夫曼樹。由于哈夫曼樹過于巨大，一次截屏無法完全顯示，使用兩次截屏。以上兩幅圖顯示出來程序編出的哈夫曼樹的形狀。打印出來的圖形與教科書上的常見哈夫曼樹略有不同，左邊的數(shù)是右邊數(shù)的父節(jié)點。4-7.輸入q退出程序。5. 總 結5-1、用戶界面設計為“菜單”模式，使人們更加容易使用。5-2、在程序的一次執(zhí)行過程中，第一次執(zhí)行e命令之后，哈夫曼樹已經在內存了，不必再讀入。5-3.在編程中使用了很不規(guī)范的編程方法，應用了一些臨時變量來實現(xiàn)功能，而大量臨時變量在代碼中沒有很好地進行命名。這給程序的閱讀和維護帶來了極大的困難。5-4.本程序僅能對26個小寫字母構成的字符串

11、進行處理，并不具有對漢字等的編碼處理能力。5-5.設計中得到了老師和廣大同學的幫助，并參考了網(wǎng)絡上的優(yōu)秀論文和紙質文件，使我的程序設計能夠較為順利的進行下去。在此我衷心感謝我的老師同學和對以上資源的作者。6. 參考文獻 A：書籍資料1 李春葆 數(shù)據(jù)結構教程 上機實驗指導北京：清華大學出版社2 嚴蔚敏 吳偉民數(shù)據(jù)結構（C語言版）北京：清華大學出版社3 蘇仕華 數(shù)據(jù)結構 課程設計 北京：機械工業(yè)出版社B：網(wǎng)絡資料1 哈夫曼編/譯碼器(課程設計).html2 哈夫曼編碼432169091693efce3bc763ab.html附錄 程序源代碼 /哈夫曼編/譯碼器(課程設計) 2008/5/21#in

12、clude <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 struct int weight; int parent,lchild,rchild;HTNode,* HuffmanTree; /動態(tài)分配數(shù)組存儲赫夫曼樹  

13、;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()調用 int j,flag; int k=UINT_MAX; / 取k為不小于可能的值 for(j=1;j<=i;j+) if(tj.weight<k&&tj.parent=0)

14、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.12-void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) / w存放n個字符的權值(均

15、>0),構造赫夫曼樹HT,并求出n個字符的赫夫曼編碼HC int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd; if(n<=1) return;/檢測結點數(shù)是否可以構成樹 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->lchild=0; p->rchild=0; for(;i<=m;+i,+p)

16、p->parent=0; for(i=n+1;i<=m;+i) / 建赫夫曼樹 /在HT1i-1中選擇parent=0且weight最小的兩個結點,其序號分別為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)malloc(n+1)*sizeof(char*); / 分配n個字符編碼的頭指針向量(0不用) cd=(cha

17、r*)malloc(n*sizeof(char); / 分配求編碼的工作空間 cdn-1='0' / 編碼結束符 for(i=1;i<=n;i+) / 逐個字符求赫夫曼編碼 start=n-1; / 編碼結束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 從葉子到根逆向求編碼 if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char*)malloc(n-start)*sizeof(char); / 為第i個字符編碼分配空間 strc

18、py(HCi,&cdstart); / 從cd復制編碼(串)到HC free(cd); / 釋放工作空間/-初始化赫夫曼鏈表-void Initialization() flag=1; int num2; cout<<"下面初始化赫夫曼鏈表"<<endl; w=(int*)malloc(n*sizeof(int); / 為第26個字符權值分配空間 z=(char*)malloc(n*sizeof(char); / 為第26個字符分配空間 cout<<"n依次顯示"<<n<<"個

19、字符與其權值和編碼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)<<"權值"<<setw(11)<<"編碼&quo

20、t;<<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<<"."<<endl; FILE *htmTree; char r=' ','0' if(htmTr

21、ee=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=1;i<=n;i+) fputs(HCi,htmTree); fputs(r,htmTree)

22、; fclose(htmTree); cout<<"已將字符與對應編碼寫入根目錄下文件htmTree.txt中"<<endl<<endl;/-獲取報文并寫入文件-void InputCode() FILE *tobetran; char str100; if(tobetran=fopen("tobetran.txt","w")=NULL) cout<<"不能打開文件"<<endl; return; cout<<"請輸入你想要編碼的字符

23、"<<endl; /字符個數(shù)應當小于100 gets(str); fputs(str,tobetran); cout<<"獲取報文成功"<<endl; fclose(tobetran);cout<<"."<<endl<"報文存入根目錄下的tobetran.txt文件中"<<endl;/-編碼函數(shù)-void Encoding() cout<<"下面對目錄下文件tobetran.txt中的字符進行編碼"<<e

24、ndl; FILE *tobetran,*codefile; if(tobetran=fopen("tobetran.txt","rb")=NULL) cout<<"不能打開文件"<<endl; if(codefile=fopen("codefile.txt","wb")=NULL) cout<<"不能打開文件"<<endl; char *tran; i=99; tran=(char*)malloc(100*sizeof(cha

25、r); 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) cout<<"字符錯誤，無法編碼!"<<endl; break; cout<<"編碼完成"<<

26、endl；cout<<"編碼寫入目錄下的codefile.txt中"<<endl<<endl; fclose(tobetran); fclose(codefile); free(tran);/-譯碼函數(shù)-void Decoding() cout<<"下面對根目錄下文件codefile.txt中的字符進行譯碼"<<endl; FILE *codef,*txtfile; if(txtfile=fopen("Textfile.txt","w")=NULL) co

27、ut<<"不能打開文件"<<endl; txtfile=fopen("Textfile.txt","w"); if (codef=fopen("codefile.txt","r")=NULL) cout<<"不能打開文件"<<endl; codef=fopen("codefile.txt","r"); char *work,*work2,i2; int i4=0,i,i3; unsigne

28、d 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(i2='0') i3=HTi3.lchild; else if(i2=&

29、#39;1') i3=HTi3.rchild; *(work2+i4)='0' fputs(work2,txtfile); cout<<"譯碼完成"<<endl；cout<<"內容寫入根目錄下的文件textfile.txt中"<<endl<<endl; free(work); /釋放工作區(qū) free(work2); /釋放工作區(qū) fclose(txtfile); /關閉文件txtfile.txt fclose(codef); /關閉文件codef.txt/-打印編碼的函數(shù)

30、-void Code_printing() cout<<"下面打印根目錄下文件CodePrin.txt中編碼字符"<<endl; FILE * CodePrin,* codefile; if(CodePrin=fopen("CodePrin.txt","w")=NULL) cout<<"不能打開文件"<<endl; return; if(codefile=fopen("codefile.txt","r")=NULL) cout&

31、lt;<"不能打開文件"<<endl; return; char *work3; work3=(char*)malloc(51*sizeof(char);if(fgets(work3,51,codefile)=NULL) cout<<"不能讀取文件"<<endl; else do fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50&&fgets(work3,51,codefile)!=NULL); free(work3); cout

32、<<"打印結束"<<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<<"創(chuàng)建文件失敗"<<

33、;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+26 cout<<"下面打印赫夫曼樹"<<endl; coprint(p,HT); /p=HT+26 cout<<"打印工作結束"<<endl;/-主函數(shù)-void main() cout&