哈夫曼编码译码器数据结构C语言

勇者，必以决斗之勇气与五张试卷一决雌雄；懦夫，概以鼠目之寸光量人生此战必输无疑！一、需求分析目前进行快速远距离通信的主要手段是电报即将需传送的文字转化成由二级制的字符组成的字符串例如假设需传送的电文为"ABACCDA"它只有4种字符只需两个字符的串便可以分辨假设A、B、C、D、的编码分别为000110和11则上述7个字符的电文便为"00010010101100"总长14位对方接受时可按二位一分进行译码当然在传送电文时希望总长尽可能地短如果对每个字符设计长度不等的编码且让电文中出现次数较多的字符采用尽可能短的编码则传送电文的总长便可减少如果设计A、B、C、D的编码分别为000101则上述7个字符的电文可转换成总长为9的字符串"000011010"但是这样的电文无法翻译例如传送过去的字符串中前4个字符的字串"0000"就可以有很多种译法或是"AAAA"或者"BB"或者"ABA"等因此若要设计长短不等的编码则必须是任一字符的编码都不是另一个字符的编码的前缀这种编码称作前缀编码然而如何进行前缀编码就是利用哈夫曼树来做也就有了现在的哈夫曼编码和译码二、概要设计利用哈夫曼树编/译码（一）、建立哈夫曼树（二）、对哈夫曼树进行编码（三）、输出对应字符的编码（四）、译码过程主要代码实现：struct code //结构体的定义{char a;int w;int parent;int lchild;int rchild;};void creation(code *pint nint m); //建立哈夫曼树void coding(code *pint n); //编码void display(code *pint nint m); //输出函数void translate(char **hccode *pint n); //译码三、详细设计（一）、建立哈夫曼树（二）、对哈夫曼树进行编码主要代码实现：for(c=if=p[i].parent;f!=0;c=ff=p[f].parent){if(p[f].lchild==c) //左孩子编码为'0' {cd[--start]='0';}else //右孩子编码为'1' {cd[--start]='1';}}（三）、输出对应字符的码字符编码a110b111c10d0（四）、译码过程主要代码实现：if(strcmp(ahc[i])==0) //比较两个字符串是否相等相等则输出0{for(c=2*n-1j=0;a[j]!='\0';j++) //从根出发按字符'0'或'1'确定找左孩子或右孩子{if(a[j]=='0') //左孩子{c=p[c].lchild;}else{c=p[c].rchild; //右孩子}}四、调试分析（一）、数字的输入判断（二）、字母的输入判断（三）、程序是否继续进行的判断五、用户手册（一）、首先根据提示输入初始化数据提示输入一个数字请输入一个数a0<a<9999；提示输入一个字母则请输入一个字母（a~z)或者(A~Z)中的一个字符；请勿在输入一个数字后再输入一个字符或者在输入一个字符后再输入一个数字（二）在某一界面结束后会有"请按回车继续下面操作"提示请按提示进行操作如输入其他数字则无效知道输入回车符界面才会跳转（三）对界面的操作可以自行选择在询问是否译码的时候请按要求进行选择在一次译码结束后会询问是否继续译码如需要则输入y或者Y输入其他字符则退出程序六、测试结果（一）、初始化（二）、建立哈夫曼树（三）、哈夫曼编码（四）、哈夫曼译码（五）、错误判定附录：源代码：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>struct code //结构体的定义{char a;int w;int parent;int lchild;int rchild;};void creation(code *pint nint m); //建立哈夫曼树void coding(code *pint n); //编码void translate(char **hccode *pint n);//译码void display(code *pint nint m); //输出函数//主函数void main(){int inm;code *ht;printf("字符的数量:\n(请输入一个大于0的数字输入多个数字则按第一个数字运行)\n");while(scanf("%d"&n)!=1||n<0||n>9999){printf("重新输入：\n");fflush(stdin);}m=2*n-1; //哈夫曼树中没有度为1的结点故含有m=2n-1个结点ht=(code*)malloc((m+1)*sizeof(code));//动态申请内存for(i=1;i<=n;i++) //对1~n的数进行初始化{printf("输入编码中的字符(请输入一个字母):\n");fflush(stdin);scanf("%c"&ht[i].a);while(!(ht[i].a>'a'||ht[i].a<'z'||ht[i].a>'A'||ht[i].a<'Z')){printf("重新输入：\n");fflush(stdin);scanf("%c"&ht[i].a);//清空输入缓冲区往往是确保不影响后面数据的读取}printf("输入字符的权值(请输入一个数字):\n");while(scanf("%d"&ht[i].w)!=1||ht[i].w<0||ht[i].w>9999){printf("重新输入：\n");fflush(stdin); //清空输入缓冲区往往是确保不影响后面数据的读取}ht[i].lchild=0;ht[i].rchild=0;ht[i].parent=0;}for(i=n+1;i<=m;i++) //对n+1~2n-1的数进行初始化{ht[i].a='*';ht[i].w=0;ht[i].lchild=0;ht[i].rchild=0;ht[i].parent=0;}creation(htnm);printf("请按回车进入哈夫曼树对应界面\n");getchar();getchar();system("cls");display(htnm);printf("请按回车进入编码对应界面\n");getchar();system("cls");coding(htn);getchar();}void creation(code *htint nint m){int ijm1m2t1t2;for(i=n+1;i<=m;i++){j=1; //找到第一个最小值（双亲不为0）while(ht[j].parent!=0) //找到表中第一个没有双亲的结点{j++;}t1=ht[j].w;m1=j;for(j=m1+1;j<=m;j++){if(ht[j].parent==0&&ht[j].w!=0)//条件(ht[j].w!=0)是因为n~2n-1的权值初始值为0{if(ht[j].w<t1){t1=ht[j].w;m1=j;}}}ht[m1].parent=i; //第一个值的双亲为ht[i]ht[i].lchild=m1; //h[i]的的左孩子是最小值的序号j=1; //剩余中找到第二个最小值（双亲不为0）while(ht[j].parent!=0){j++;}t2=ht[j].w;m2=j;for(j=m2+1;j<=m;j++){if(ht[j].parent==0&&ht[j].w!=0){if(ht[j].w<t2){t2=ht[j].w;m2=j;}}}ht[m2].parent=i; //第二个值的双亲为ht[i]ht[i].rchild=m2; //h[i]的的左孩子是最小值的序号ht[i].w=t1+t2; //h[i]的权值是找到的两个值的权值之和}}void coding(code *pint n){int icf;char **hc; //指针的指针char *cd;char ch;int start;hc=(char**)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间cd[n-1]='\0'; //编码结束符for(i=1;i<=n;i++){start=n-1;for(c=if=p[i].parent;f!=0;c=ff=p[f].parent)//从叶子到根逆向求编码{if(p[f].lchild==c) //左孩子编码为'0'{cd[--start]='0';}else //右孩子编码为'1'{cd[--start]='1';}}hc[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(hc[i]&cd[start]); //从cd复制编码（串）到hc&是取地址符即取首地址从start位置到'\0'的编码为止}free(cd); //释放工作空间printf("\n输出编码后的结果：\n");printf("符号数码\n");for(i=1;i<=n;i++){printf("\n%c %s\n"p[i].ahc[i]);}printf("是否进行译码操作是则译码否则退出程序！\n是（输入y/Y）否（输入其他字符）\n");scanf("%d"&ch);if(ch=='y'||ch=='Y'){translate(hcpn);}elseexit(0);}void translate(char **hccode *pint n){char a[10]ch;int ijc;do{printf("\n\n\n请输入编码：\n");scanf("%s"a); //回车之后会自动生成'\0'for(i=1;i<=n;i++){if(strcmp(ahc[i])==0) //比较两个字符串是否相等相等则输出0{for(c=2*n-1j=0;a[j]!='\0';j++) //从根出发按字符'0'或'1'确定找左孩子或右孩子{if(a[j]=='0') //左孩子{c=p[c].lchild;}else{c=p[c].rchild; //右孩子}}printf("字符是：\n");printf("%c\n"p[c].a);break;}}if(i>n){printf("编码不存在对应的字符！\n");}printf("是否继续输入?是（输入y或者Y）否(其他）\n");fflush(stdin);scanf("%c"&ch);}while(ch=='y'||ch=='Y');}void display(code *pint nint m){int i;printf("\n序号码值权值双亲左孩子右孩子\n");for(i=1;i<=m;i++){printf("%d %c %d %d %d %d\n"ip[i].ap[i].wp[i].parentp[i].lchildp[i].rchild);}}设计体会通过这个课程设计让我对数据结构这门课程有了更深一步的了解对以后的深造奠定了基础本次课程设计的课题是：哈夫曼编码以及译码的实现本程序的特色是：结构清晰内容全面输入的错误提醒在输入的错误的提醒方面做了很大的改进不过在这方面仍存在些许的不足就是在输入一个字母的时候如果输入的数据是"ab"不会提示错误只会按第一个'a'有效在初始化的时候输入'a3'这种数据则不会提示错误而是执行了下一条scanf语句输入的数字学习是一个无止境的过境我们要善于使用资源书籍网络等等努力地提升自己为今后的发展做更大的努力????????1。