数据结构专业课程设计哈夫曼编码译码器.doc

题目一：哈夫曼编码与译码一、任务设计一种运用哈夫曼算法编码和译码系统，重复地显示并解决如下项目，直到选取退出为止。规定：1)将权值数据存储在数据文献(文献名为data.txt，位于执行程序当前目录中) ；2)初始化：键盘输入字符集记录字符权值、自定义26个字符和26个权值、记录文献中一篇英文文章中26个字母，建立哈夫曼树；3)编码：运用建好哈夫曼树生成哈夫曼编码；4)输出编码（一方面实现屏幕输出，然后实现文献输出）；5） 译码（键盘接受编码进行译码、文献读入编码进行译码）；6)界面优化设计。二、流程图主菜单1.建立字符权值2.建立并输出哈夫曼树3.建立并查看哈弗曼编码4.编码与译码0.退出系统1.从键盘输入字符集记录权值2.从文献读入字符集记录权值3.自定义字符及权值0.返回上级菜单输出哈夫曼树并保存至文献“哈夫曼树。txt”输出哈夫曼编码并保存至文献“哈夫曼编码。txt1.编码2.译码0.返回上级菜单1.从键盘输入字符集进行编码2.从文献读入字符集进行编码1.从键盘输入编码进行译码2.从文献读入编码进行译码0.返回上级菜单0.返回上级菜单三、代码分解/头文献#include#include#include#include #define N 1000#define M 2*N-1#define MAXcode 6000/函数声明void count(CHar &ch,HTNode ht);void editHCode(HTNode ht,HCode hcd,CHar &ch,int n,char bianma)； /编码函数void printyima(HTNode ht,HCode hcd,int n,char bianma)； /译码函数void creatHT(HTNode ht,int n);void CreateHCode (HTNode ht,HCode hcd,int n);void DispHCode(HTNode ht,HCode hcd,int n);void input_key(CHar &ch);void input_file(CHar &ch);void input_cw(HTNode ht);void bianma1(HTNode ht,HCode hcd,CHar &ch,int n,char bianma);void bianma2(HTNode ht,HCode hcd,CHar &ch,int n,char bianma);void yima1(HTNode ht,HCode hcd,int n,char bianma);void yima2(HTNode ht,HCode hcd,int n,char bianma);void creat_cw();void bianmacaidan();void yimacaidan();void bianmayima();int caidan()； /构造体typedef structchar data;int parent;int weight;int lchild;int rchild;HTNode;typedef structchar cdN;int start;HCode;typedef structchar sN;int num;CHar;CHar ch;HTNode htM;HCode hcdN;/主函数int main()int xh;while(1)system(color 1f)； /操作菜单背景颜色xh=caidan()； /调用菜单函数 switch(xh) /switch语句case 1:system(cls);creat_cw();break;case 2:system(cls);creatHT(ht,n);break;case 3:system(cls);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);break;case 4:system(cls);bianmayima();break;case 0:system(cls);printf(nnnnnnnnntttt感谢使用本系统!nnnnnnn ttt);exit(0);default:system(cls);putchar(a); printf(ntt输入有误，请重新输入:n);break;return 0;/菜单函数int caidan() /菜单函数模块/ int xh; printf(nnn); printf(tt 欢迎使用哈夫曼编码译码系统 n); printf(tt n); printf(tt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n); printf(tt*= =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*= =*n); printf(tt*= 1.建立字符权值 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*= =*n); printf(tt*= 2.建立并输出哈夫曼树 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*= =*n); printf(tt*= 3.生成并查看哈夫曼编码 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*= =*n); printf(tt*= 4.编码与译码 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*= =*n); printf(tt*= 0.退出系统 =*n); printf(tt*= =*n); printf(tt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n); printf(ntt请输入序号进行选取:); scanf(%d，&xh)； return xh； /返回从键盘接受选项void bianmayima() int xh; while(1) printf(nnnnn); printf(tt 编码与译码 n); printf(tt n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 1.编码 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 2.译码 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 0.返回上级菜单 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(ntt请输入序号进行选取:); scanf(%d,&xh); switch(xh) /switch语句case 1:system(cls);bianmacaidan();break;case 2:system(cls);yimacaidan();break;case 0:system(cls);return;default:system(cls);putchar(a); printf(ntt输入有误，请重新输入:n);break; void yimacaidan() int xh; while(1) printf(nnnnn); printf(tt 译码 n); printf(tt n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 1.键盘输入编码进行译码 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 2.文献读入编码进行译码 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 0.返回上级菜单 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(ntt请输入序号进行选取:); scanf(%d,&xh); switch(xh) /switch语句case 1:system(cls);yima1(ht,hcd,n,bianma);break;case 2:system(cls);yima2(ht,hcd,n,bianma);break;case 0:system(cls);return;default:system(cls);putchar(a); printf(ntt输入有误，请重新输入:n);break; void bianmacaidan() int xh; while(1) printf(nnnnn); printf(tt 编码 n); printf(tt n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 1.键盘输入字符集编码 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 2.文献读入文章编码 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 0.返回上级菜单 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(ntt请输入序号进行选取:); scanf(%d,&xh); switch(xh) /switch语句case 1:system(cls);bianma1(ht,hcd,ch,n,bianma);break;case 2:system(cls);bianma2(ht,hcd,ch,n,bianma);break;case 0:system(cls);return;default:system(cls);putchar(a); printf(ntt输入有误，请重新输入:n);break; void creat_cw() int xh2; while(1) printf(nnnnn); printf(tt 建立字符权值 n)； printf(tt n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 1.从键盘输入字符集进行记录 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 2.从文献读入字符集记录 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 3.自定义字符权值 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(tt*= 0.返回上级菜单 =*n); printf(tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n); printf(ntt请输入序号进行选取:); scanf(%d,&xh2); switch(xh2) /switch语句case 1:system(cls);input_key(ch);break;case 2:system(cls);input_file(ch);break;case 3:system(cls);input_cw(ht);break;case 0:system(cls);return;default:system(cls);putchar(a); printf(ntt输入有误，请重新输入:n);break; /建立字符权值模块void input_key(CHar &ch)int i,j=0;char stN;printf(请输入字符集（以#结束）:n);for(i=0;iN;i+)scanf(%c,&sti); if(sti=#) sti=0;break; strcpy(ch.s,st);ch.num=strlen(st);count(ch,ht);printf(按任意键返回!);getch();system(cls);return;void input_file(CHar &ch)int i;FILE*fp;char filename20;printf(请输入要打开文献名(*.txt):);scanf(%s,&filename);if(fp=fopen(filename,r)=NULL)printf(ntt文献打开失败!);return;for(i=0;!feof(fp);i+)fread(&ch.si,sizeof(char),1,fp)；ch.num=strlen(ch.s);printf(读入成功!n);printf(文献中字符集为:%sn,ch.s);fclose(fp);count(ch,ht);printf(按任意键返回!);getch();system(cls);return;void input_cw(HTNode ht)int i,w,s,j;char a;printf(要输入字符总个数是？:);scanf(%d,&s);n=s;printf(请输入字符及其权值:n);for(i=0;is;i+)printf(请输入第%d个字母:,i+1);scanf(%s,&a);hti.data=a;printf(请输入其权值:);scanf(%d,&w);hti.weight=w;FILE *fp;if(fp=fopen(data.txt,w)=0)printf(ntt文献打开失败!);return;printf(n定义权值成功!nn);printf(各字符及其权值为:nn);fprintf(fp,各字符及其权值为:n);printf( 字符t权值);fprintf(fp, 字符t权值);for(j=0;ji;j+)printf(n); fprintf(fp,n);printf( %-8c%-8d,htj.data,htj.weight);fprintf(fp, %-8c%-8d%,htj.data,htj.weight);printf(n);printf(n字符权值已输出至文献“data.txt”！);fclose(fp);printf(输入完毕，按任意键返回！);getch();system(cls);return;/记录字符权值函数void count(CHar &ch,HTNode ht)int i,j,m=0;char cN;int sumN=0;for(i=0;ch.si!=0;i+)for(j=0;j=a&cj=z&ch.si+32=cj) break;if(j=A&ch.si=Z)cj=ch.si+32;else cj=ch.si;sumj+;m+;for(i=0;im;i+)hti.data=ci;hti.weight=sumi;n=m;FILE *fp;if(fp=fopen(data.txt,w)=0)printf(ntt文献打开失败!);return;printf(n记录权值成功!nn);printf(各字符及其权值为:nn);fprintf(fp,各字符及其权值为:n);printf( 字符t权值);fprintf(fp, 字符t权值);for(j=0;jm;j+)printf(n); fprintf(fp,n);printf( %-8c%-8d,htj.data,htj.weight);fprintf(fp, %-8c%-8d%,htj.data,htj.weight);printf(n);printf(n字符权值已输出至文献“data.txt”！);fclose(fp);/构造哈夫曼树void creatHT(HTNode ht,int n)FILE *fp;if(fp=fopen(哈夫曼树.txt,w)=0)printf(ntt文献打开失败!);return;int i,j,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; for (i=n;i2*n-1;i+)min1=min2=32767; lnode=rnode=-1; for(k=0;k=i-1;k+) if(htk.parent=-1)if (htk.weightmin1)min2=min1;rnode=lnode; min1=htk.weight;lnode=k;else if(htk.weightmin2) min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;printf(建立huffman树成功!n);printf(输出huffman树:n);fprintf(fp,输出huffman树:n);printf(t字符t权值t父节点t 左子节点t右子节点);fprintf(fp,t字符t权值t父节点t 左子节点t右子节点);for(j=1;ji;j+)printf(n); fprintf(fp,n);printf(t %-8c%-8d%-10d%-14d%-10d,htj.data,htj.weight,htj.parent,hti.lchild,htj.rchild);fprintf(fp,t %-8c%-8d%-10d%-14d%-10d,htj.data,htj.weight,htj.parent,hti.lchild,htj.rchild);printf(n);printf(哈夫曼树已输出至文献“哈夫曼树.txt”！按任意键返回!);fclose(fp);getch();system(cls);return;/生成哈夫曼编码void CreateHCode (HTNode ht,HCode hcd,int n)int i,f,c,j=0; HCode hc;for(i=0;in;i+) hc.start=n;c=i; hc.cdhc.start-=0; f=hti.parent;while(f!=-1) if (htf.lchild=c) hc.cdhc.start-=0;else hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+； for(j=0;jhc.start;j+) hc.cdj= ; hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n) FILE *fp;if(fp=fopen(哈夫曼编码.txt,w)=0)printf(ntt文献打开失败!);return;int i,k; int sum=0,m=0,j; printf(输出字符哈夫曼编码:n);fputs(输出字符哈夫曼编码:n,fp); for (i=0;in;i+)j=0; printf(%c:t,hti.data);fprintf(fp,n%c:t,hti.data); for (k=hcdi.start;k=n;k+) printf(%c,hcdi.cdk); j+; fprintf(fp,%c,hcdi.cdk);m+=hti.weight; sum+=hti.weight*j; printf(n); printf(n哈夫曼编码已保存至文献“哈夫曼编码.txt!按任意键返回！”);fclose(fp); getch(); system(cls);/编码函数void bianma1(HTNode ht,HCode hcd,CHar &ch,int n,char bianma)int i;char strN; printf(请输入要编码字符集（以#结束）:n);for(i=0;iN;i+)scanf(%c,&stri); if(stri=#) stri=0;break;strcpy(ch.s,str);ch.num=strlen(str);editHCode(ht,hcd,ch,n,bianma); getch();system(cls);return;void bianma2(HTNode ht,HCode hcd,CHar &ch,int n,char bianma)int i;FILE*fp;char filename20;printf(请输入要打开文献名(*.txt):);scanf(%s,&filename);if(fp=fopen(filename,r)=NULL)printf(ntt文献打开失败!);return;for(i=0;!feof(fp);i+)fread(&ch.si,sizeof(char),1,fp)；ch.num=strlen(ch.s);printf(n读入成功!n);printf(文献中字符集为:n%s,ch.s);fclose(fp);editHCode(ht,hcd,ch,n,bianma);getch();system(cls);return;/译码函数void yima1(HTNode ht,HCode hcd,int n,char bianma)int i;char codeMAXcode;printf(请输入编码进行译码（以#结束）:n);for(i=0;iMAXcode;i+)scanf(%c,&codei); if(codei=#) codei=0;break;strcpy(bianma,code); printyima(ht,hcd,n,bianma);printf(n译码完毕！按任意键返回!);getch();system(cls);return;void yima2(HTNode ht,HCode hcd,int n,char bianma)int i;FILE*fp;char filename20;printf(请输入要打开文献名(*.txt):);scanf(%s,&filename);if(fp=fopen(filename,r)=NULL)printf(ntt文献打开失败!);return;for(i=0;!feof(fp);i+)fread(&bianmai,sizeof(char),1,fp)；printf(读入成功!n);printf(文献中编码是:%sn,bianma);printyima(ht,hcd,n,bianma);printf(n译码完毕！按任意键返回!);getch();system(cls);四、调试成果主菜单建立字符权值选取2.从文献读入字符进行记录输入测试文献名“cs.txt”输出个字符权值建立哈夫曼树并输出至文献生成哈夫曼编码并保存至文献编码 选取2.从文献读入字符集编码 编码成果保存至文献译码选取2.从文献读入编码，读入上一步编码译码完毕，返回！退出系统