数据结构课程设计之哈夫曼编码(word文档).doc

哈夫曼编码与解码的实现 一、设计思想 (一)哈夫曼树的设计思想 关于一组拥有确立权值的叶子结点能够结构出多个拥有不一样带权路径长度的二叉树，其 中拥有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树。 第一给定n个权值制造n个只含根结点的二叉树，获得一个二叉树林；再在这二叉树林 里面找根结点的权值最小和次小的两棵树作成新的二叉树，此中新的二叉树的根结点的权值 为左右子根结点权值之和；最后在二叉树林中把组合过的二叉树删除，再重复第二步，直到最后就剩一颗二叉树的时候获得的这棵二叉树就是哈夫曼树。 （二）哈夫曼编码与解码的设计思想 在数据通信中，常常要将传递的文字变换为二进制字符0和1构成的二进制串，称这个 过程为编码。与子相对的是解码或是译码，就是用与编码同样的方式将二进制串变换称编码 前的文字的过程称作解码。在这里是经过哈夫曼树实现编码与解码的，因此称作是哈夫曼编 码与解码。 第一输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二 进制串取代它，这个过程要注意树和编码问题，此中树的问题在上边已经解决，主要看编码 的问题，就是依据我们输入的字符串和权值成立相应的树模型，这一步达成那编码就已经完 成了，最后打印就行了；而后就是解码，达成编码相应的解码就相对简单了，就是先找到在 编码的时候建的那个模型树，将编码中的二进制串再依据权值变换为相应的字符串，这样一 步步解码就行了。 以上就是经过用哈夫曼树进行哈夫曼编码与解码怎样实现的主要设计思想。 -1- 哈夫曼编码与解码的实现 二、算法流程图 （一）哈夫曼树的流程图 开始 初始化哈夫曼链表 二叉树林 找最小和次小 的二叉树 组合成新的二叉树 删除用过的二叉树 不 是 能否是最后一 个二叉树 是 结束 图1哈夫曼树的流程图 （二）编码与解码的流程图 开始开始 找到树的根结点 输入字符串输入二进制串 扫描 判断权值依据树的路径 成立路径 有最小和次小 打印对应字符 否 循环成立二叉树 依据树对路径分 持续扫描 左0右1 能否结束 是 写出对应结点的编 输出字符串 码 结束结束 图2编码与解码的流程图 图片说明：（左侧）编码流程图，（右侧）解码流程图。 -2- 哈夫曼编码与解码的实现 三、源代码 下边给出的是用中缀转后缀算法实现的程序的源代码： #include"stdio.h" #include"string.h" #defineMAX100/*定义常量*/ structHaffNode { intweight;/*权值*/ intparent;/*双亲结点下标*/ charch; intlchild; intrchild; }*myHaffTree;/*结构哈夫曼树*/ structCoding { charbit[MAX];/*定义数组*/ charch; intweight;/*字符的权值*/ }*myHaffCode;/*定义结构体*/ voidHaffman(intn)/*定义哈夫曼函数*/ { inti,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(myHaffTree[j].parent==0&&myHaffTree[j].weight<s1)/*分派左右结点*/ { s2=s1;x2=x1; s1=myHaffTree[j].weight;x1=j; } elseif(myHaffTree[j].parent==0&&myHaffTree[j].weight<s2) { s2=myHaffTree[j].weight;x2=j; } } myHaffTree[x1].parent=i; myHaffTree[x2].parent=i; myHaffTree[i].weight=s1+s2;/*左右子组合为新树*/ myHaffTree[i].lchild=x1; myHaffTree[i].rchild=x2; -3- 哈夫曼编码与解码的实现 } } voidHaffmanCode(intn)/*结构n个结点哈夫曼编码*/ { intstart,c,f,i,j,k; char*cd; cd=(char*)malloc(n*sizeof(char)); myHaffCode=(structCoding*)malloc((n+1)*sizeof(structCoding)); cd[n-1]='\0'; for(i=1;i<=n;++i)/*n个叶子结点的哈夫曼编码*/ { start=n-1; for(c=i,f=myHaffTree[i].parent;f!=0;c=f,f=m