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

哈夫曼编/译码系统的设计与实现一、需求分析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.程序模块本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。系统子程序及功能设计本系统共有七个子程序，分别是：a.intmin1(HuffmanTreet,inti)//进行比较b.voidselect(HuffmanTreet,inti,int*s1,int*s2)//求权值最小的两个数c.voidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,char*u,intn)///*w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/d.voidInitialzation(HuffmanTree*HT,HuffmanCode*HC)//初始化e.intEnCoding(HuffmanTree*HT,HuffmanCode*HC)//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中f.intpipei(char*c,intn,HuffmanCode*HC)//在huffmancode寻找匹配的编码g.voidDecoding(HuffmanTree*HT,HuffmanCode*HC)//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中3.各模块之间的调用关系以及算法设计主函数调用Initialzation，EnCoding，Decoding。函数HuffmanCoding调用函数select。函数select调用函数min1函数Initialzation调用函数HuffmanCoding函数Decoding调用函数pipei三、详细设计1.数据类型定义typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;charch;}HTNode,*HuffmanTree;/*动态分配数组存储赫夫曼树*/typedefchar**HuffmanCode;/*动态分配数组存储赫夫曼编码表*/2.系统主要子程序详细设计a.构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCvoidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,char*u,intn)/*算法6.12*/{/*w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/intm,i,s1,s2,start;unsignedc,f;HuffmanTreep;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)/*建赫夫曼树*/{/*在HT[1~i-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));/*分配求编码的工作空间*/cd[n-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';elsecd[--start]='1';(*HC)[i]=(char*)malloc((n-start)*sizeof(char));/*为第i个字符编码分配空间*/strcpy((*HC)[i],&cd[start]);/*从cd复制编码(串)到HC*/}free(cd);/*释放工作空间*/}b.初始化voidInitialzation(HuffmanTree*HT,HuffmanCode*HC)//初始化{FILE*f1;inti,n=0;if((f1=fopen(DataFile.txt,r))==NULL){printf(error\n);}intg[100];charh[100];printf(从数据文件DataFile.txt中读入字符及每个字符的权值\n);for(i=1;;i++){fscanf(f1,%c,&h[i]);if(h[i]=='#')break;fscanf(f1,%d,&g[i]);n++;printf(%c:,h[i]);printf(%d\n,g[i]);}fclose(f1);HuffmanCoding(HT,HC,g,h,n);}c.编码intEnCoding(HuffmanTree*HT,HuffmanCode*HC)//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中{inti,j,m=0,n=0;FILE*f1,*f2,*f3;if((f1=fopen(DataFile.txt,r))==NULL){printf(error\n);}intg[100];charh[100];for(i=1;;i++){fscanf(f1,%c,&h[i]);if(h[i]=='#')break;fscanf(f1,%d,&g[i]);n++;}fclose(f1);if((f2=fopen(ToBeTran.txt,r))==NULL){printf(error\n);}printf(从数据文件ToBeTran.txt中读入字符\n);charu[100],a[100];for(i=1;;i++){fscanf(f2,%c,&u[i]);if(u[i]=='#')break;a[i]=u[i];m++;couta[i];}coutendl;fclose(f2);if((f3=fopen(Code.txt,w))==NULL){printf(error\n);}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;returnm;}intpipei(char*c,intn,HuffmanCode*HC)/*在huffmancode寻找匹配的编码*/{inti;for(i=1;i5;i++){if(strcmp(c,(*HC)[i])==0){returni;break;}}return0;}d.译码voidDecoding(HuffmanTree*HT,HuffmanCode*HC)//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中{inti=1,j=1,y=0,num=0,len,n=0,d,q,v,ii;inta[2]={1,2};charc[20];for(i=0;i20;i++)c[i]='\0';FILE*f1,*f4,*f5;if((f1=fopen(DataFile.txt,r))==NULL)//求权值个数n{printf(error\n);}intg[100];charh[100];for(i=1;;i++){fscanf(f1,%c,&h[i]);if(h[i]=='#')break;fscanf(f1,%d,&g[i]);n++;}fclose(f1);if((f4=fopen(CodeFile.txt,r))==NULL)//读字符{printf(error\n);}printf(从数据文件CodeFile.txt中读入代码\n);charb[100];for(i=1;;i++){fscanf(f4,%c,&b[i]);if(b[i]=='#')break;coutb[i];}coutendl;fclose(f4);if((f5=fopen(TextFile.txt,w))==NULL){printf(error\n);}cout输出原文endl;i=1;j=1;y=1;while(true){if(b[y]=='#')break;for(j=0;ji;j++){c[j]=b[y+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;}elsei++;for(ii=0;ii20;ii++)c[ii]='\0';}coutendl;}四、测试与分析1.显示主菜单，运行程序可以显示出如下界面。2.初始化在主菜单下选1，初始胡，即可从数据文件DataFile.txt中读入字符及每个字符的权值。3.编码在主菜单下选2，编码，将给定文件ToBeTran.txt中的字符输出报文。4.译码在主菜单下选3，完成译码功能，读取文件CodeFile.txt中的代码并输出原文。5.退出在主菜单下选4，退出系统五、附录1.哈夫曼编译码系统.h#includeiostream#includemalloc.h#includestring.husingnamespacestd;typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;charch;}HTNode,*HuffmanTree;/*动态分配数组存储赫夫曼树*/typedefchar**HuffmanCode;/*动态分配数组存储赫夫