數(shù)據(jù)結(jié)構(gòu)設(shè)計-哈夫曼編譯碼系統(tǒng)的設(shè)計與實現(xiàn)

1、哈夫曼編/譯碼系統(tǒng)的設(shè)計與實現(xiàn)一、需求分析1、問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（解碼）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站設(shè)計一個哈夫曼編譯碼系統(tǒng)。2、基本要求（1）初始化（Initialzation）。從數(shù)據(jù)文件DataFile.txt中讀入字符及每個字符的權(quán)值，建立哈夫曼樹HuffTree；（2）編碼（EnCoding）。用已建好的哈夫曼樹，對文件ToBeTran.txt中的文本進(jìn)行編碼形成報

2、文，將報文寫在文件Code.txt中；（3）譯碼（Decoding）。利用已建好的哈夫曼樹，對文件CodeFile.txt中的代碼進(jìn)行解碼形成原文，結(jié)果存入文件Textfile.txt中；（4）輸出（Output）。輸出DataFile.txt中出現(xiàn)的字符以及各字符出現(xiàn)的頻度（或概率）；輸出ToBeTran.txt及其報文Code.txt；輸出CodeFile.txt及其原文Textfile.txt；二、概要設(shè)計1.數(shù)據(jù)結(jié)構(gòu)本程序需要用到以一個結(jié)構(gòu)體HTNode，以及一個二維數(shù)組HuffmanCode。2.程序模塊本程序包含兩個模塊，一個是實現(xiàn)功能的函數(shù)的模塊，另一個是主函數(shù)模塊。系統(tǒng)子程序及

3、功能設(shè)計本系統(tǒng)共有七個子程序，分別是： min1(HuffmanTree t,int i)/進(jìn)行比較 b.void select(HuffmanTree t,int i,int *s1,int *s2)/ 求權(quán)值最小的兩個數(shù)c.void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n)/ /* w存放n個字符的權(quán)值(均>0),構(gòu)造赫夫曼樹HT,并求出n個字符的赫夫曼編碼HC */d.void Initialzation(HuffmanTree *HT,HuffmanCode *HC)/初始化e

4、.int EnCoding(HuffmanTree *HT,HuffmanCode *HC)/對文件ToBeTran.txt中的文本進(jìn)行編碼形成報文，將報文寫在文件Code.txt中 pipei(char *c,int n,HuffmanCode *HC)/在huffmancode尋找匹配的編碼g.void Decoding(HuffmanTree *HT,HuffmanCode *HC)/對文件CodeFile.txt中的代碼進(jìn)行解碼形成原文，結(jié)果存入文件Textfile.txt中3. 各模塊之間的調(diào)用關(guān)系以及算法設(shè)計主函數(shù)調(diào)用Initialzation，EnCoding，Deco

5、ding。函數(shù)HuffmanCoding調(diào)用函數(shù)select。函數(shù)select調(diào)用函數(shù)min1函數(shù)Initialzation調(diào)用函數(shù)HuffmanCoding函數(shù)Decoding調(diào)用函數(shù)pipei三、詳細(xì)設(shè)計1.數(shù)據(jù)類型定義typedef struct unsigned int weight; unsigned int parent,lchild,rchild; char ch; HTNode,*HuffmanTree; /* 動態(tài)分配數(shù)組存儲赫夫曼樹 */ typedef char *HuffmanCode; /* 動態(tài)分配數(shù)組存儲赫夫曼編碼表 */ 2.系統(tǒng)主要子程序詳細(xì)設(shè)計a. 構(gòu)造赫夫

6、曼樹HT,并求出n個字符的赫夫曼編碼HCvoid HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n) /* 算法6.12 */ /* w存放n個字符的權(quán)值(均>0),構(gòu)造赫夫曼樹HT,并求出n個字符的赫夫曼編碼HC */ int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0號單元未用

7、*/ for(p=*HT+1,i=1;i<=n;+i,+p,+w,+u) (*p).ch=*u; (*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) /* 建赫夫曼樹 */ /* 在HT1i-1中選擇parent為0且weight最小的兩個結(jié)點,其序號分別為s1和s2 */ select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (

8、*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; /* 從葉子到根逆向求每個字符的赫夫曼編碼 */ *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /* 分配n個字符編碼的頭指針向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求編碼的工作空間 */ cdn-1='0' /* 編碼結(jié)束符 */ for(i=1;i<=n;i+) /* 逐個字符求赫夫曼編碼 */ start=n-

9、1; /* 編碼結(jié)束符位置 */ for(c=i,f=(*HT)i.parent;f!=0;c=f,f=(*HT)f.parent) /* 從葉子到根逆向求編碼 */ if(*HT)f.lchild=c) cd-start='0' else cd-start='1' (*HC)i=(char*)malloc(n-start)*sizeof(char); /* 為第i個字符編碼分配空間 */ strcpy(*HC)i,&cdstart); /* 從cd復(fù)制編碼(串)到HC */ free(cd); /* 釋放工作空間 */ b.初始化void Initia

10、lzation(HuffmanTree *HT,HuffmanCode *HC)/初始化FILE *f1;int i,n=0;if(f1=fopen("DataFile.txt","r")=NULL) printf("errorn"); int g100;char h100; printf("從數(shù)據(jù)文件DataFile.txt中讀入字符及每個字符的權(quán)值n"); for(i=1;i+) fscanf(f1,"%c",&hi); if(hi='#') break; fscan

11、f(f1,"%d",&gi);n+; printf("%c: ",hi); printf("%dn",gi); fclose(f1);HuffmanCoding(HT,HC,g,h,n);c.編碼int EnCoding(HuffmanTree *HT,HuffmanCode *HC)/對文件ToBeTran.txt中的文本進(jìn)行編碼形成報文，將報文寫在文件Code.txt中int i,j,m=0,n=0;FILE *f1,*f2,*f3;if(f1=fopen("DataFile.txt","r&

12、quot;)=NULL) printf("errorn"); int g100;char h100; for(i=1;i+) fscanf(f1,"%c",&hi); if(hi='#') break; fscanf(f1,"%d",&gi);n+; fclose(f1);if(f2=fopen("ToBeTran.txt","r")=NULL) printf("errorn"); printf("從數(shù)據(jù)文件ToBeTran.txt中

13、讀入字符n");char u100,a100; for(i=1;i+) fscanf(f2,"%c",&ui); if(ui='#') break;ai=ui;m+; cout<<ai<<" " cout<<endl; fclose(f2);if(f3=fopen("Code.txt","w")=NULL) printf("errorn"); cout<<"輸出報文"<<endl;f

14、or(i=0;i<m;i+)for(j=1;j<=n;+j)if(*(a+i)=(*HT)j.ch)printf("%s ",(*HC)j);fprintf(f3,"%s",(*HC)j);fclose(f3);cout<<endl;return m;int pipei(char *c,int n,HuffmanCode *HC)/*在huffmancode尋找匹配的編碼*/ int i; for(i=1;i<5;i+) if(strcmp(c,(*HC)i)=0) return i; break; return 0;d.譯

15、碼void Decoding(HuffmanTree *HT,HuffmanCode *HC)/對文件CodeFile.txt中的代碼進(jìn)行解碼形成原文，結(jié)果存入文件Textfile.txt中int i=1,j=1,y=0,num=0,len,n=0,d,q,v,ii;int a2=1,2;char c20;for(i=0;i<20;i+) ci='0'FILE *f1,*f4,*f5;if(f1=fopen("DataFile.txt","r")=NULL)/求權(quán)值個數(shù)n printf("errorn"); in

16、t g100;char h100; for(i=1;i+) fscanf(f1,"%c",&hi); if(hi='#') break; fscanf(f1,"%d",&gi);n+; fclose(f1);if(f4=fopen("CodeFile.txt","r")=NULL)/讀字符 printf("errorn"); printf("從數(shù)據(jù)文件CodeFile.txt中讀入代碼n");char b100; for(i=1;i+) fsc

17、anf(f4,"%c",&bi); if(bi='#') break; cout<<bi; cout<<endl;fclose(f4);if(f5=fopen("TextFile.txt","w")=NULL) printf("errorn"); cout<<"輸出原文"<<endl;i=1; j=1;y=1;while(true) if(by='#') break; for(j=0;j<i;j+) c

18、j=by+j; q=pipei(c,n,HC); if(q!=0) printf("%c",(*HT)q+1.ch);fprintf(f5,"%c",(*HT)q+1.ch); y=y+i; i=1; else i+;for(ii=0;ii<20;ii+) cii='0'cout<<endl;四、測試與分析1.顯示主菜單，運行程序可以顯示出如下界面。2.初始化 在主菜單下選1，初始胡，即可從數(shù)據(jù)文件DataFile.txt中讀入字符及每個字符的權(quán)值。 3.編碼在主菜單下選2，編碼，將給定文件ToBeTran.txt中的字

19、符輸出報文。 4.譯碼在主菜單下選3，完成譯碼功能，讀取文件CodeFile.txt中的代碼并輸出原文。5.退出在主菜單下選4，退出系統(tǒng)五、附錄1.哈夫曼編譯碼系統(tǒng).h#include<iostream>#include<malloc.h>#include<string.h>using namespace std;typedef struct unsigned int weight; unsigned int parent,lchild,rchild; char ch; HTNode,*HuffmanTree; /* 動態(tài)分配數(shù)組存儲赫夫曼樹 */ type

20、def char *HuffmanCode; /* 動態(tài)分配數(shù)組存儲赫夫曼編碼表 */ int min1(HuffmanTree t,int i) /* 函數(shù)void select()調(diào)用 */ int j,flag; unsigned int k=UINT_MAX; /* 取k為不小于可能的值 */ for(j=1;j<=i;j+) if(tj.weight<k&&tj.parent=0) k=tj.weight,flag=j; tflag.parent=1; return flag; void select(HuffmanTree t,int i,int *s1

21、,int *s2) /* s1為最小的兩個值中序號小的那個 */ int j; *s1=min1(t,i); *s2=min1(t,i); if(*s1>*s2) j=*s1; *s1=*s2; *s2=j; void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n) /* 算法6.12 */ /* w存放n個字符的權(quán)值(均>0),構(gòu)造赫夫曼樹HT,并求出n個字符的赫夫曼編碼HC */ int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *

22、cd; if(n<=1) return; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0號單元未用 */ for(p=*HT+1,i=1;i<=n;+i,+p,+w,+u) (*p).ch=*u; (*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) /* 建赫夫曼樹 */ /* 在HT1i-1中選擇parent為0且weight最小

23、的兩個結(jié)點,其序號分別為s1和s2 */ select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; /* 從葉子到根逆向求每個字符的赫夫曼編碼 */ *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /* 分配n個字符編碼的頭指針向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分

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

25、 strcpy(*HC)i,&cdstart); /* 從cd復(fù)制編碼(串)到HC */ free(cd); /* 釋放工作空間 */ void Initialzation(HuffmanTree *HT,HuffmanCode *HC)/初始化FILE *f1;int i,n=0;if(f1=fopen("DataFile.txt","r")=NULL) printf("errorn"); int g100;char h100; printf("從數(shù)據(jù)文件DataFile.txt中讀入字符及每個字符的權(quán)值n&quo

26、t;); for(i=1;i+) fscanf(f1,"%c",&hi); if(hi='#') break; fscanf(f1,"%d",&gi);n+; printf("%c: ",hi); printf("%dn",gi); fclose(f1);HuffmanCoding(HT,HC,g,h,n); int EnCoding(HuffmanTree *HT,HuffmanCode *HC)/對文件ToBeTran.txt中的文本進(jìn)行編碼形成報文，將報文寫在文件Code.tx

27、t中int i,j,m=0,n=0;FILE *f1,*f2,*f3;if(f1=fopen("DataFile.txt","r")=NULL) printf("errorn"); int g100;char h100; for(i=1;i+) fscanf(f1,"%c",&hi); if(hi='#') break; fscanf(f1,"%d",&gi);n+; fclose(f1);if(f2=fopen("ToBeTran.txt",

28、"r")=NULL) printf("errorn"); printf("從數(shù)據(jù)文件ToBeTran.txt中讀入字符n");char u100,a100; for(i=1;i+) fscanf(f2,"%c",&ui); if(ui='#') break;ai=ui;m+; cout<<ai<<" " cout<<endl; fclose(f2);if(f3=fopen("Code.txt","w&quo

29、t;)=NULL) printf("errorn"); cout<<"輸出報文"<<endl;for(i=0;i<m;i+)for(j=1;j<=n;+j)if(*(a+i)=(*HT)j.ch)printf("%s ",(*HC)j);fprintf(f3,"%s",(*HC)j);fclose(f3);cout<<endl;return m;int pipei(char *c,int n,HuffmanCode *HC)/*在huffmancode尋找匹配的編碼*

30、/ int i; for(i=1;i<5;i+) if(strcmp(c,(*HC)i)=0) return i; break; return 0; void Decoding(HuffmanTree *HT,HuffmanCode *HC)/對文件CodeFile.txt中的代碼進(jìn)行解碼形成原文，結(jié)果存入文件Textfile.txt中int i=1,j=1,y=0,num=0,len,n=0,d,q,v,ii;int a2=1,2;char c20;for(i=0;i<20;i+) ci='0'FILE *f1,*f4,*f5;if(f1=fopen("

31、DataFile.txt","r")=NULL)/求權(quán)值個數(shù)n printf("errorn"); int g100;char h100; for(i=1;i+) fscanf(f1,"%c",&hi); if(hi='#') break; fscanf(f1,"%d",&gi);n+; fclose(f1);if(f4=fopen("CodeFile.txt","r")=NULL)/讀字符 printf("errorn&q

32、uot;); printf("從數(shù)據(jù)文件CodeFile.txt中讀入代碼n");char b100; for(i=1;i+) fscanf(f4,"%c",&bi); if(bi='#') break; cout<<bi; cout<<endl;fclose(f4);if(f5=fopen("TextFile.txt","w")=NULL) printf("errorn"); cout<<"輸出原文"<<endl;i=1; j=1;y=1;while(true) if(by='#'