huffman的创建及编码的实验报告

数据结构算法设计(哈夫曼树的建立和编码)班级：0912201学号：1091220107姓名：李佳莉实验四哈夫曼树的建立和编码一．问题的提出如何进行如下操作：1.借助哈夫曼树模型来对不同的字符进行编码,以及以哈夫曼树形式输出哈夫曼树。2.根据每个字符不同的权值建立哈夫曼树，并对输入的字符进行编码处理，并存入文件中。二．Huffman树及编码算法的主要思想哈夫曼树（Huffman树）是带权路径长度最小的二叉树。根据哈夫曼树的定义，一棵二叉树要使其带权路径长度最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。哈夫曼依据这一特点提出了哈夫曼算法，其基本思想是：⑴初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}；⑵选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点权值之和；⑶删除与加入：在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；⑷重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。通过上述Huffman树的构造过程，我们可以得到如下要点：⑴当有n个权值（相应的Huffman树中有n个叶子），共需合并n-1次；⑵每合并一次产生一个分支结点，经过n-1次合并后得到的Huffman树中共有2n-1个结点，其中有n-1个分支结点；⑶在Huffman树中只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点；⑷算法要求选取根结点权值最小的两棵二叉树作为左右子树构造一棵新的二叉树，但并没有要求哪一棵作左子树，哪一棵作右子树，所以左右子树的顺序是任意的，一般情况下权值小的作为左子树。⑸对同一组权值可以构造出不同的huffman树，但是他们的带权路径长度相同。Huffman编码的主要思想：在建好的huffman树中左孩子的边赋值均为0，右孩子的边赋值均为1，然后从根节点遍历到所求节点，依次将遇到的0或1写出就是所求的点的编码。三、算法的设计和实现#includeiostream#includestring.husingnamespacestd;#defineMAX100#defineN26typedefstruct{//哈夫曼树的结点unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*Huffmantree;typedefstruct{//字符存储结点信息chardata;//待编码的字符intweight;//字符的权值charcode[N];//字符的编码}HTCode;//初始化结点信息voidInitCode(HTCode*Hr,int&n){cout请输入字符编码的个数n：;cinn;cout请输入字符编码以及相应的权值：endl;for(inti=1;i=n;i++){cin(Hr+i)-data(Hr+i)-weight;}}voidSelect(Huffmantree&HT,intend,int*s1,int*s2){//在0~end之间,找出最小和次小的两个结点序号,返回S1,S2inti;intmin1=MAX;intmin2;for(i=1;i=end;i++){//找最小的结点序号if((HT+i)-parent==0&&(HT+i)-weight=min1){*s1=i;min1=(HT+i)-weight;}}min2=MAX;for(i=1;i=end;i++){//找次小结点的序号if((HT+i)-parent==0&&*s1!=i&&min2=(HT+i)-weight){*s2=i;min2=(HT+i)-weight;}}}//初始化哈夫曼树,并把信息存入HrvoidInitHfmtree(Huffmantree&Ht,HTCodeHr[],int&n){if(n=1)return;intm,start,i,j,f;ints1,s2;m=2*n-1;Ht=newHTNode[m+1];HuffmantreeP;P=Ht+1;for(i=1;i=m;i++,P++){if(i=n)P-weight=Hr[i].weight;elseP-weight=0;P-lchild=0;P-rchild=0;P-parent=0;}for(i=n+1;i=m;i++)//建赫夫曼树{Select(Ht,i-1,&s1,&s2);//寻找匹配双亲节点(Ht+s1)-parent=i;(Ht+s2)-parent=i;(Ht+i)-lchild=s1;(Ht+i)-rchild=s2;(Ht+i)-weight=(Ht+s1)-weight+(Ht+s2)-weight;}char*code;code=newchar[n];code[n-1]='\0';for(i=1;i=n;i++){//编码存入Hr-codestart=n-1;for(j=i,f=Ht[j].parent;f!=0;j=f,f=Ht[f].parent)if(Ht[f].lchild==j)code[--start]='0';elsecode[--start]='1';strcpy(Hr[i].code,&code[start]);}cout字符编码初始化完成！endl;}voidEncoding(HTCode*Hr,intn){//编码inti,j;char*encode;encode=newchar[n];cout请选择编码的字符：endl;cinencode;for(i=0;encode[i]!='\0';i++){j=1;while(encode[i]!=Hr[j].data)j++;if(jn)cout输入编码encode[i]错误！endl;elsecoutHr[j].data的编码是Hr[j].codeendl;}cout字符串;for(i=0;encode[i]!='\0';i++){coutencode[i];}cout的编码是：endl;for(i=0;encode[i]!='\0';i++){j=1;while(encode[i]!=Hr[j].data)j++;if(jn)cout输入编码encode[i]错误！endl;elsecoutHr[j].code;}coutendl;cout编码已经结束！endl;}intmain(){HuffmantreeHt;HTCodeHr[N];intn=0;charcmd;do{cout初始化赫夫曼树（I）编码（E）离开（Q）endl;cincmd;switch(cmd){case'I':InitCode(Hr,n);InitHfmtree(Ht,Hr,n);break;case'E':Encoding(Hr,n);break;case'Q':exit(0);break;default:cout输入的命令不正确！endl;}}while(1);return0;}四、实验结论下面是该程序一组实验数据的结果：