《(完整word版)数据结构--课程设计之哈夫曼编码(word文档良心出品).doc》由会员分享，可在线阅读，更多相关《(完整word版)数据结构--课程设计之哈夫曼编码(word文档良心出品).doc（8页珍藏版）》请在金锄头文库上搜索。
1、哈夫曼编码与解码的实现一、设计思想 (一) 哈夫曼树的设计思想对于一组具有确定权值的叶子结点可以构造出多个具有不同带权路径长度的二叉树，其中具有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树。首先给定n个权值制造n个只含根结点的二叉树，得到一个二叉树林；再在这二叉树林里面找根结点的权值最小和次小的两棵树作成新的二叉树，其中新的二叉树的根结点的权值为左右子根结点权值之和；最后在二叉树林中把组合过的二叉树删除，再重复第二步，直到最后就剩一颗二叉树的时候得到的这棵二叉树就是哈夫曼树。（二）哈夫曼编码与解码的设计思想在数据通讯中，经常要将传送的文字转换为二进制字符0和1组成的二进制串，称这个过程为编
2、码。与子相对的是解码或是译码，就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。在这里是通过哈夫曼树实现编码与解码的，所以称作是哈夫曼编码与解码。首先输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二进制串代替它，这个过程要注意树和编码问题，其中树的问题在上面已经解决，主要看编码的问题，就是根据我们输入的字符串和权值建立相应的树模型，这一步完成那编码就已经完成了，最后打印就行了；然后就是解码，完成编码相应的解码就相对简单了，就是先找到在编码的时候建的那个模型树，将编码中的二进制串再根据权值转换为相应的字符串，这样一步步解码就行了。以上就是通过用哈夫曼树进行
3、哈夫曼编码与解码如何实现的主要设计思想。二、算法流程图（一）哈夫曼树的流程图图1哈夫曼树的流程图（二）编码与解码的流程图图2编码与解码的流程图图片说明：（左边）编码流程图，（右边）解码流程图。三、源代码下面给出的是用中缀转后缀算法实现的程序的源代码：#include stdio.h#include string.h#define MAX 100/*定义常量*/struct HaffNode int weight;/*权值*/ int parent;/*双亲结点下标*/ char ch; int lchild; int rchild;*myHaffTree; /*构造哈夫曼树*/struct C
4、oding char bitMAX;/*定义数组*/ char ch; int weight;/*字符的权值*/*myHaffCode;/*定义结构体*/void Haffman(int n)/*定义哈夫曼函数*/ int i,j,x1,x2,s1,s2; for (i=n+1;i=2*n-1;i+)/*树的初始化*/ s1=s2=10000; x1=x2=0; for (j=1;j=i-1;j+)/*构造哈夫曼树的非叶子结点*/ if(myHaffTreej.parent=0&myHaffTreej.weights1)/*分配左右结点*/ s2=s1;x2=x1; s1=myHaffTree
5、j.weight;x1=j; else if(myHaffTreej.parent=0&myHaffTreej.weights2) s2=myHaffTreej.weight;x2=j; myHaffTreex1.parent=i; myHaffTreex2.parent=i; myHaffTreei.weight=s1+s2;/*左右子组合为新树*/ myHaffTreei.lchild=x1; myHaffTreei.rchild=x2; void HaffmanCode(int n)/*构造n个结点哈夫曼编码*/ int start,c,f,i,j,k; char *cd; cd=(ch
6、ar *)malloc(n*sizeof(char); myHaffCode=(struct Coding *)malloc(n+1)*sizeof(struct Coding); cdn-1=0; for(i=1;i=n;+i)/*n个叶子结点的哈夫曼编码*/ start=n-1; for(c=i,f=myHaffTreei.parent;f!=0;c=f,f=myHaffTreef.parent) if(myHaffTreef.lchild=c) cd-start=0; else cd-start=1; for(j=start,k=0;jn;j+) myHaffCodei.bitk=cdj
7、; k+; myHaffCodei.ch=myHaffTreei.ch; /*取编码对应的权值*/ myHaffCodei.weight=myHaffTreei.weight; free(cd);Init()/*定义有返回值的函数*/ int i,n,m; printf(please input the number of words:); scanf(%d,&n); m=2*n-1; myHaffTree=(struct HaffNode *)malloc(sizeof(struct HaffNode)*(m+1); for(i=1;i=n;i+) printf(please input t
8、he word and the equal:); scanf(%s%d,&myHaffTreei.ch,&myHaffTreei.weight); myHaffTreei.parent=0; myHaffTreei.lchild=0; myHaffTreei.rchild=0; for(i=n+1;i=m;i+) myHaffTreei.ch =#; myHaffTreei.lchild=0; myHaffTreei.parent=0; myHaffTreei.rchild=0; myHaffTreei.weight=0; Haffman(n); HaffmanCode(n); for(i=1
9、;i=n;i+) printf(%c %d,myHaffCodei.ch,myHaffCodei.weight); printf(n); printf(init success!n); return n;void Caozuo_C(int m)/* 编码函数 */ int n,i,j; char string50,*p; printf(please input the words：); scanf(%s,string); n=strlen(string);/*计算字符串长度*/ for(i=1,p=string;i=n;i+,p+)/*进行编码*/ for(j=1;j=m;j+) if(myH
10、affCodej.ch=*p) printf(%sn,myHaffCodej.bit); void Caozuo_D(int n)/*解码函数*/ int i,c; char code1000,*p; printf(please input the coding：);/*输入二进制编码*/ scanf(%s,code); for(p=code,c=2*n-1;*p!=0;p+) /*进行解码*/ if(*p=0) /*结束条件*/ c=myHaffTreec.lchild;/*赋值*/ if(myHaffTreec.lchild=0) /* 扫描*/ printf(%c,myHaffTreec
11、.ch); c=2*n-1; continue;/*结束*/ else if(*p=1) c=myHaffTreec.rchild; if(myHaffTreec.lchild=0) printf(%c,myHaffTreec.ch); c=2*n-1;/*赋值*/ continue; printf(n);void main()/*主函数*/ int n; char char1;/*定义字符*/ n=Init();/*函数的调用*/ printf(A.coding B.codeprinting C.exitnplease input the process:n); while(1) scanf
12、(%c,&char1); if(char1=c) /*判断字符*/ break; switch(char1) caseA:Caozuo_C(n);break; /*执行编码操作*/ caseB:Caozuo_D(n);break; /*执行解码操作*/ caseC:;break; 四、运行结果（一）中缀转后缀算法的运行结果：五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：l 问题1: 刚开始不知道如何建一个好树，因为我开始试着建了几个二叉树，不知道什么原因运行的时候那编码总是不对，跟在草稿纸上自己画的那个二叉树总是不相符，就找原因。解决方法: 开始时总是编码出错，就试着找错，树的初始化不可能出错，所以首先看那叶子结点的for函数，没什么错误，接着看非叶子结点的for函数，非叶子结点不好弄，找起来麻烦一些，就是费时间，盘查到最后也没什么错，最后就是左右子结点重生结点的一块了，这也比较好查，可是结果却是错处在这儿了，没想到最放心的一块出了错，得好好反省反省了，以后绝不能在这些问题上出错了，还好不是很严重，还可以补回来。l 问题2: 由于前一个问题的解决，后面小心意义的写，尽量放慢写的速度，省的再花时间找错，可是最后能运行，运行的结果却是错的不容乐观啊，还出现一些不认识的乱码，这样的问题最难了
