1、哈夫曼编码译码器数据结构C语言哈夫曼编码译码器数据结构C语言一、需求分析目前,进行快速远距离通信的主要手段是电报,即将需传送的文字转化成由二级制的字符组成的字符串。例如,假设需传送的电文为“ABACCDA”,它只有4种字符,只需两个字符的串,便可以分辨。假设A、B、C、D、的编码分别为00,01,10和11,则上述7个字符的电文便为“00010010101100”,总长14位,对方接受时,可按二位一分进行译码。当然,在传送电文时,希望总长尽可能地短。如果对每个字符设计长度不等的编码,且让电文中出现次数较多的字符采用尽可能短的编码,则传送电文的总长便可减少。如果设计A、B、C、D的编码分别为0,
2、00,1,01,则上述7个字符的电文可转换成总长为9的字符串“000011010”。但是,这样的电文无法翻译,例如传送过去的字符串中前4个字符的字串“0000”就可以有很多种译法,或是“AAAA”或者“BB”,或者“ABA”等。因此,若要设计长短不等的编码,则必须是任一字符的编码都不是另一个字符的编码的前缀,这种编码称作前缀编码。然而,如何进行前缀编码就是利用哈夫曼树来做,也就有了现在的哈夫曼编码和译码。二、概要设计利用哈夫曼树编/译码(一)、建立哈夫曼树(二)、对哈夫曼树进行编码(三)、输出对应字符的编码(四)、译码过程主要代码实现:struct code /结构体的定义 char a; i
3、nt w; int parent; int lchild; int rchild;void creation(code *p,int n,int m); /建立哈夫曼树void coding(code *p,int n); /编码void display(code *p,int n,int m); /输出函数void translate(char *hc,code *p,int n); /译码三、 详细设计(1)、建立哈夫曼树(2)从叶子到根逆向求编码、对哈夫曼树进行编码主要代码实现:for(c=i,f=pi.parent;f!=0;c=f,f=pf.parent) if(pf.lchild=
4、c) /左孩子编码为0 cd-start=0; else /右孩子编码为1 图3-4 cd-start=1; (3)、输出对应字符的码字符编码a110b111c10d表3-10(4)、译码过程主要代码实现:if(strcmp(a,hci)=0) /比较两个字符串是否相等,相等则输出0 for(c=2*n-1,j=0;aj!=0;j+) /从根出发,按字符0或1确定找左孩子或右孩子从跟到叶子顺向求字符 if(aj=0) /左孩子 c=pc.lchild; else c=pc.rchild; /右孩子 图3-5四、 调试分析(一)、数字的输入判断(二)、字母的输入判断(三)、程序是否继续进行的判断
5、图4-3五、 用户手册(1)、首先根据提示输入初始化数据,提示输入一个数字,请输入一个数a,0a9999;提示输入一个字母,则请输入一个字母(az)或者(AZ)中的一个字符;请勿在输入一个数字后再输入一个字符,或者在输入一个字符后再输入一个数字。(2)在某一界面结束后,会有“请按回车继续下面操作”提示,请按提示进行操作,如输入其他数字则无效,知道输入回车符界面才会跳转。(3)对界面的操作可以自行选择,在询问是否译码的时候,请按要求进行选择,在一次译码结束后会询问是否继续译码,如需要则输入y或者Y,输入其他字符则退出程序。六、测试结果(一)、初始化(二)、建立哈夫曼树(三)、哈夫曼编码(四)、哈
6、夫曼译码(五)、错误判定附录:源代码:#include#include#include#includestruct code /结构体的定义 char a; int w; int parent; int lchild; int rchild;void creation(code *p,int n,int m); /建立哈夫曼树void coding(code *p,int n); /编码void translate(char *hc,code *p,int n);/译码void display(code *p,int n,int m); /输出函数/主函数void main() int i,n
7、,m; code *ht; printf(字符的数量:n(请输入一个大于0的数字,输入多个数字则按第一个数字运行)n); while(scanf(%d,&n)!=1|n9999) printf(重新输入:n); fflush(stdin); m=2*n-1; /哈夫曼树中没有度为1的结点,故含有m=2n-1个结点 ht=(code*)malloc(m+1)*sizeof(code);/动态申请内存 for(i=1;ia|hti.aA|hti.aZ) printf(重新输入:n); fflush(stdin); scanf(%c,&hti.a);/清空输入缓冲区,往往是确保不影响后面数据的读取
8、printf(输入字符的权值(请输入一个数字):n); while(scanf(%d,&hti.w)!=1|hti.w9999) printf(重新输入:n); fflush(stdin); /清空输入缓冲区,往往是确保不影响后面数据的读取 hti.lchild=0; hti.rchild=0; hti.parent=0; for(i=n+1;i=m;i+) /对n+12n-1的数进行初始化 hti.a=*; hti.w=0; hti.lchild=0; hti.rchild=0; hti.parent=0; creation(ht,n,m); printf(请按回车进入哈夫曼树对应界面n);
9、 getchar(); getchar(); system(cls); display(ht,n,m); printf(请按回车进入编码对应界面n); getchar(); system(cls); coding(ht,n); getchar();void creation(code *ht,int n,int m) int i,j,m1,m2,t1,t2; for(i=n+1;i=m;i+) j=1; /找到第一个最小值(双亲不为0) while(htj.parent!=0) /找到表中第一个没有双亲的结点 j+; t1=htj.w; m1=j; for(j=m1+1;j=m;j+) if(
10、htj.parent=0&htj.w!=0)/条件(htj.w!=0)是因为n2n-1的权值初始值为0 if(htj.wt1) t1=htj.w; m1=j; htm1.parent=i; /第一个值的双亲为hti hti.lchild=m1; /hi的的左孩子是最小值的序号 j=1; /剩余中找到第二个最小值(双亲不为0) while(htj.parent!=0) j+; t2=htj.w; m2=j; for(j=m2+1;j=m;j+) if(htj.parent=0&htj.w!=0) if(htj.wt2) t2=htj.w; m2=j; htm2.parent=i; /第二个值的双
11、亲为hti hti.rchild=m2; /hi的的左孩子是最小值的序号 hti.w=t1+t2; /hi的权值是找到的两个值的权值之和 void coding(code *p,int n) int i,c,f; char *hc; /指针的指针 char *cd; char ch; int start; hc=(char*)malloc(n+1)*sizeof(char *); /分配n个字符编码的头指针向量 cd=(char*)malloc(n*sizeof(char); /分配求编码的工作空间 cdn-1=0; /编码结束符 for(i=1;i=n;i+) start=n-1; for(
12、c=i,f=pi.parent;f!=0;c=f,f=pf.parent)/从叶子到根逆向求编码 if(pf.lchild=c) /左孩子编码为0 cd-start=0; else /右孩子编码为1 cd-start=1; hci=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间 strcpy(hci,&cdstart); /从cd复制编码(串)到hc,&是取地址符,即取首地址,从start位置到0的编码为止。 free(cd); /释放工作空间 printf(n输出编码后的结果:n); printf(符号 数码n); for(i=1;i=n;
13、i+) printf(n%c %sn,pi.a,hci); printf(是否进行译码操作,是则译码,否则退出程序!n是(输入y/Y)否(输入其他字符)n); scanf(%d,&ch); if(ch=y|ch=Y) translate(hc,p,n); else exit(0);void translate(char *hc,code *p,int n) char a10,ch; int i,j,c; do printf(nnn请输入编码:n); scanf(%s,a); /回车之后会自动生成0 for(i=1;in) printf(编码不存在对应的字符!n); printf(是否继续输入?
14、是(输入y或者Y)否(其他)n); fflush(stdin); scanf(%c,&ch); while(ch=y|ch=Y); void display(code *p,int n,int m) int i; printf(n序号 码值 权值 双亲 左孩子 右孩子n); for(i=1;i=m;i+) printf(%d %c %d %d %d %dn,i,pi.a,pi.w,pi.parent,pi.lchild,pi.rchild); 设计体会通过这个课程设计,让我对数据结构这门课程有了更深一步的了解,对以后的深造奠定了基础。本次课程设计的课题是:哈夫曼编码以及译码的实现。本程序的特色是:结构清晰,内容全面,输入的错误提醒。在输入的错误的提醒方面,做了很大的改进。不过在这方面仍存在些许的不足,就是在输入一个字母的时候,如果输入的数据是ab,不会提示错误,只会按第一个a有效。在初始化的时候,输入a3这种数据,则不会提示错误,而是执行了下一条scanf语句输入的数字。学习是一个无止境的过境,我们要善于使用资源,书籍,网络等等,努力地提升自己,为今后的发展做更大的努力。
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2