哈夫曼编码和译码系统

通达学院算法与数据结构程序设计题目：哈夫曼编码和译码系统专业学生姓名班级学号指导教师指导单位日期教师评语同学出勤率(满勤、较高、一般，较低)，学习态度(端正、较端正、一般、较差)，程序设计基础（好、较好、一般、较差），演示程序(已经、没有)达到了基本要求，算法设计（好、较好、一般），界面友好程度（好、较好、一般），答辩过程中回答问题（准确、较准确、错误率较高），撰写报告格式(规范、一般)、内容（丰满、简单）、表述(清晰、一般、不清楚)，（圆满、较好、基本)完成了课题任务。教师签名：年月日成绩评定备注一、题目要求：题目：哈夫曼编码和译码系统基本要求：(1)能输入字符集和各字符频度建立哈夫曼树；(2)产生各字符的哈夫曼编码，并进行解码。提高要求：(1)能设计出简捷易操作的窗口界面；(2)编码和译码存储在文件中。二、需求分析：2.1基本思想根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是:(1)初始化:由给定的n个权值{w1,w2,…,wn}构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合F={T1,T2,…,Tn};(2)选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和;(3)删除与加入:在F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到F中;(4)重复(2)、(3)两步,当集合F中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树.2.2存储结构在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为2，根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,其中有n-1个非叶子结点,它们是在n-1次的合并过程中生成的.为了便于选取根结点权值最小的二叉树以及合并操作,设置一个数组HuffmanNode[2n-1]保存哈夫曼树中各结点的信息,数组元素的结点结构如图所示.图哈夫曼树的结点结构其中:weightparentlchildrchildinfweight:权值域,保存该结点的权值;Lchild:指针域,保存该结点的左孩子结点在数组中的下标;Rchild:指针域,保存该结点的右孩子结点在数组中的下标;parent:指针域,保存该结点的双亲结点在数组中的下标.三、概要设计：1.我首先创建了两个结构体HTNode和Node，分别来记录哈弗曼树各节点的信息以及叶子节点的信息。建立六个成员函数，如下图所示：各功能函数实现如下功能：1、voidCreateWeight(){......}作用：产生叶子结点的字符和权值。2、voidCreateHuffmanTree(){......}作用：创建HuffmanTree。3、voidCrtHuffmanNodeCode(){......}作用：生成叶子结点的编码4、voidCrtHuffmanCode(){......}作用：生成所有字符的编码5、voidTrsHuffmanTree(){......}作用：解码6、主函数main()程序开始运行，提示用户输入需要编码的字符串。运行CreateWeight（）函数，产生叶子结点信息（包括叶子节点的信息和权值），并输出运行CreateHuffmanTree（）函数，产生Huffman树，并通过printf函数打印Huffman树的信息。运行CrtHuffmanNodeCode（）函数，产生叶子节点的编码，并在屏幕输出运行CrtHuffmanCode（）函数，产生所有叶子节点的编码，并在屏幕输出。最后运行TrsHuffmanTree（）函数，还原出原先的编码四、详细设计○1voidCreateWeight(charch[],int*s,WeightNodeCW,int*p)其中形参分别表示：charch[]//存放用户输入的字符串int*s//字符串ch[]的长度WeightNodeCW//存放叶子节点的信息int*p//叶子节点的个数核心功能：函数通过定义三个变量i，j，k，来控制三个循环，主要是为了遍历字符串，找出叶子节点的字符与权值信息。○2voidCreateHuffmanTree(Huffmanht,WeightNodeCW,intn)形参表示：Huffmanht//Huffman的一个对象htWeightNodeCW//权值大小intn//叶子节点的个数功能描述：函数先通过两个for循环对哈夫曼树进行初始化，然后在通过一个循环每次找出权值最小的两个节点，进行权值相加。○3voidCrtHuffmanNodeCode(Huffmanht,charch[],HuffmanCodeh,WeightNodeweight,intm,intn)形参表示：Huffmanht//Huffman的一个对象charch[]//存放用户输入的字符串HuffmanCodeh//存放叶子节点的编码WeightNodeweight//叶子节点的信息（字符与权值）intm//字符串ch[]的长度intn//叶子节点的个数函数功能：这个函数从每个叶子节点出发，通过比较父类的左孩子的数组下标是否与对应的左孩子下标相同，相同则置0，不同则置1.(从后往前置数)核心代码：for(i=1;i=n;i++){start=n-1;//cd串每次从末尾开始c=i;p=ht[i].parent;//p在n+1至2n-1while(p)//沿父亲方向遍历,直到为0{start--;//依次向前置值if(ht[p].LChild==c)//与左孩子结点在数组中的下标相同,置0cd[start]='0';else//与右孩子结点在数组中的下标相同，置1cd[start]='1';c=p;p=ht[p].parent;}○4voidCrtHuffmanCode(charch[],HuffmanCodeh,HuffmanCodehc,WeightNodeweight,intn,intm)功能描述：通过循环遍历整个字符串，再通过判断每一个字符串与相应的叶子节点的字符相同，相同的话，则将该叶子节点的编码拷贝到hc[]数组中。完成所有字符的编码。核心代码：for(i=0;im;i++){for(k=1;k=n;k++)/*从weight[k].c中查找与ch[i]相等的下标K*/if(ch[i]==weight[k].c)break;hc[i]=(char*)malloc((weight[k].num)*sizeof(char));strcpy(hc[i],h[k]);//拷贝二进制编码}}○5voidTrsHuffmanTree(Huffmanht,WeightNodew,HuffmanCodehc,intn,intm)功能描述：TrsHuffmanTree(ht,weight,hc,n,m);为该函数的调用其中：ht,weight,hc,n,m,分别表示哈夫曼对象，叶子节点对象，存放所有字符编码的数组hc,叶子节点的个数n,一起字符串的长度m。核心代码：while(im){p=2*n-1;//从父亲节点向下遍历直到叶子节点for(j=0;hc[i][j]!='\0';j++){if(hc[i][j]=='0')p=ht[p].LChild;elsep=ht[p].RChild;}printf(%c,w[p].c);/*打印原信息*/i++;}五、测试数据及其结果分析当程序运行后，提示用户输入需要编码的字符串，假如我输入：woshiyuanhao则程序运行后会打印出叶子节点的字符和所对应的权值，如下图所示：继续按任意键则会打印出所对应的哈夫曼树，如下图所示：根据所画的哈弗曼数的直观图，可以对照的依次写出每个字符的编码，如下图所示：输出所有字符的编码：最后将编码还原成字符串，如下图：下面是程序运行的全过程：从中可以看出程序大抵完成了哈夫曼树的编码与解码功能六、总结程序分析：本次哈夫曼编码译码器的课程实验做得还算成功，不仅仅在于程序能够正常运行，实现应有的功能，关键在于过程，在于小组成员的分工合作和一起纠错排错的过程，在完成程序的过程中才能真正理解面向对象和模块化设计的思想，我们不仅仅是说要每人分几个函数，关键在于这些函数代表的是一个个功能模块，任何一个模块出现问题或者模块之间的衔接出现问题都将导致程序运行的失败。在初始设计的时候，我体会到书写流程图的重要性，只有又一个清晰的设计思路才能事半功倍，分工明确，避免无效劳动或者在错误的编程方向上走弯路，也让大家明白自己在程序设计中的位置和职责。初始的创建是哈夫曼编码译码系统成功的关键，我在创建的过程当中多次使用树的先根，配合中根遍历操作，输出接点字符或者权重信息，作为检验，对验证和纠错起到了非常大的作用。在适当的地方调用它们，运行时可以看到验证编写程序的正确性；通过本次实验，提高了自已调试程序的能力。充分体会到了在程序执行时的提示性输出的重要性。编写大一点的程序，应先写出算法，再写程序，一段一段调试；对于没有实现的操作用空操作代替，这样容易找出错误所在。最忌讳将所有代码写完后再调试，这样若程序有错误，太难找。附录：完整程序代码：#includestdio.h#includestdlib.h#includestring.h#defineN100//定义叶子节点最多100个#defineM2*N-1//所有节点的个数typedefchar*HuffmanCode[2*M];//haffman编码typedefstruct{intweight;//权值intparent;//父节节点intLChild;//左子节点intRChild;//右子节点}HTNode,Huffman[M+1];//huffman树typedefstructNode{intweight;//叶子结点的权值charc;//叶子结点intnum;//叶子结点的二进制码的长度}WNode,WeightNode[N];/***产生叶子结点的字符和权值***/voidCreateWeight(charch[],int*s,WeightNodeCW,int*p){inti,j,k;inttag;*p=0;//叶子节点个数//统计字符出现个数,放入CWfor(i=0;ch[i]!='\0';i++){tag=1;for(j=0;ji;j++)if(ch[j]==ch[i])//通过判断让相同元素存在同一个数组单元中{tag=0;break;}if(tag){CW[++*p].c=ch[i];CW[*p].weight=1;for(k=i+1;ch[k]!='\0';k++)if(ch[i]==ch[k])CW[*p].weight++;//权值累加}}*s=i;//字符串长度}/********创建HuffmanTree********/voidCreateHuffmanTree(Huffmanht,WeightNodew,intn){inti,j;ints1,s2;//初始化哈夫曼树for(i=1;i=n;i++){ht[i].weight=w[i].weight;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}for(i=n+1;i=2*n-1;i++){ht[i].weight=0;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}for(i=n+1;i=2*n-1;i++){for(j=1;j=i-1;j++)if(!ht[j].parent)break;s1=j;//找到第一个双亲不为零的结点for(;j=i-1;j++)if(!ht[j].parent)s1=ht[s1].weightht[j].weight?j:s1;ht[s1].parent=i;ht[i].LChild=s1;for(j=1;j=i-1;j++)i