数据结构设计哈夫曼编译码系统的设计与实现.docx

哈夫曼编/译码系统的设计与实现一、需求分析1、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。2、基本要求（1）初始化（Initialzation）。从数据文件DataFile.txt中读入字符及每个字符的权值，建立哈夫曼树HuffTree；（2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中；（3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中；（4）输出（Output）。输出DataFile.txt中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.txt及其报文Code.txt；输出CodeFile.txt及其原文Textfile.txt；二、概要设计1.数据结构本程序需要用到以一个结构体HTNode，以及一个二维数组HuffmanCode。2.程序模块本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。系统子程序及功能设计本系统共有七个子程序，分别是： min1(HuffmanTree t,int i)/进行比较 b.void select(HuffmanTree t,int i,int *s1,int *s2)/ 求权值最小的两个数c.void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n)/ /* w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */d.void Initialzation(HuffmanTree *HT,HuffmanCode *HC)/初始化 EnCoding(HuffmanTree *HT,HuffmanCode *HC)/对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中 pipei(char *c,int n,HuffmanCode *HC)/在huffmancode寻找匹配的编码g.void Decoding(HuffmanTree *HT,HuffmanCode *HC)/对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中3. 各模块之间的调用关系以及算法设计主函数调用Initialzation，EnCoding，Decoding。函数HuffmanCoding调用函数select。函数select调用函数min1函数Initialzation调用函数HuffmanCoding函数Decoding调用函数pipei三、详细设计1.数据类型定义typedef struct unsigned int weight; unsigned int parent,lchild,rchild; char ch; HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */ typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */ 2.系统主要子程序详细设计a. 构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCvoid HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n) /* 算法6.12 */ /* w存放n个字符的权值(均0),构造赫夫曼树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号单元未用 */ 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最小的两个结点,其序号分别为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); /* 分配求编码的工作空间 */ cdn-1=0; /* 编码结束符 */ for(i=1;i=n;i+) /* 逐个字符求赫夫曼编码 */ start=n-1; /* 编码结束符位置 */ 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复制编码(串)到HC */ free(cd); /* 释放工作空间 */ b.初始化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(从数据文件DataFile.txt中读入字符及每个字符的权值n); 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);c.编码int EnCoding(HuffmanTree *HT,HuffmanCode *HC)/对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中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,r)=NULL) printf(errorn); printf(从数据文件ToBeTran.txt中读入字符n);char u100,a100; for(i=1;i+) fscanf(f2,%c,&ui); if(ui=#) break;ai=ui;m+; coutai ; coutendl; fclose(f2);if(f3=fopen(Code.txt,w)=NULL) printf(errorn); cout输出报文endl;for(i=0;im;i+)for(j=1;j=n;+j)if(*(a+i)=(*HT)j.ch)printf(%s ,(*HC)j);fprintf(f3,%s,(*HC)j);fclose(f3);coutendl;return m;int pipei(char *c,int n,HuffmanCode *HC)/*在huffmancode寻找匹配的编码*/ int i; for(i=1;i5;i+) if(strcmp(c,(*HC)i)=0) return i; break; return 0;d.译码void Decoding(HuffmanTree *HT,HuffmanCode *HC)/对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件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;i20;i+) ci=0;FILE *f1,*f4,*f5;if(f1=fopen(DataFile.txt,r)=NULL)/求权值个数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); printf(从数据文件CodeFile.txt中读入代码n);char b100; for(i=1;i+) fscanf(f4,%c,&bi); if(bi=#) break; coutbi; coutendl;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;ji;j+) cj=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;ii20;ii+) cii=0;coutendl;四、测试与分析1.显示主菜单，运行程序可以显示出如下界面。2.初始化 在主菜单下选1，初始胡，即可从数据文件DataFile.txt中读入字符及每个字符的权值。 3.编码在主菜单下选2，编码，将给定文件ToBeTran.txt中的字符输出报文。 4.译码在主菜单下选3，完成译码功能，读取文件CodeFile.txt中的代码并输出原文。5.退出在主菜单下选4，退出系统五、附录1.哈夫曼编译码系统.h#include#include#includeusing namespace std;typedef struct unsigned int weight; unsigned int parent,lchild,rchild; char ch; HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */ typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */ int min1(HuffmanTree t,int i) /* 函数void select()调用 */ int j,flag; unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */ for(j=1;j=i;j+) if(tj.weight*s2) j=*s1; *s1=*s2; *s2=j; void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n) /* 算法6.12 */ /* w存放n个字符的权值(均0),构造赫夫曼树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号单元未用 */ 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最小的两个结点,其序号分别为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); /* 分配求编码的工作空间 */ cdn-1=0; /* 编码结束符 */ for(i=1;i=n;i+) /* 逐个字符求赫夫曼编码 */ start=n-1; /* 编码结束符位置 */ 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复制编码(串)到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(从数据文件DataFile.txt中读入字符及每个字符的权值n); 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中的文本进行编码形成报文，将报文写在文件Code.txt中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,r)=NULL) printf(errorn); printf(从数据文件ToBeTran.txt中读入字符n);char u100,a100; for(i=1;i+) fscanf(f2,%c,&ui); if(ui=#) break;ai=ui;m+; coutai ; coutendl; fclose(f2);if(f3=fopen(Code.txt,w)=NULL) printf(errorn); cout输出报文endl;for(i=0;im;i+)for(j=1;j=n;+j)if(*(a+i)=(*HT)j.ch)printf(%s ,(*HC)j);fprintf(f3,%s,(*HC)j);fclose(f3);coutendl;return m;int pipei(char *c,int n,HuffmanCode *HC)/*在huffmancode寻找匹配的编码*/ int i; for(i=1;i5;i+) if(strcmp(c,(*HC)i)=0) return i; break; return 0; void Decoding(HuffmanTree *HT,HuffmanCode *HC)/对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件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;i20;i+) ci=0;FILE *f1,*f4,*f5;if(f1=fopen(DataFile.txt,r)=NULL)/求权值个数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); prin