实验二：用Huffman树进行编码与解码算法

（规格为A4纸或A3纸折叠）（用五号宋体和TimesNewRoman,A4纸双面打印）一、实验目的；1、通过本实验，熟悉二叉树、Huffman树的基本概念，掌握二叉树的存储结构与各种算法。2、熟悉用Huffman树进行电文的加密与解密算法。二、实验内容；1、Huffman树的存储方式。2、加密与解密算法在电文编码中的应用。三、实验原理；给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，又称为哈夫曼树（Huffmantree）。Huffman树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符的频度，能够达到编码电文的最小化。假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：（1）将w1、w2、…，wn看成是有n棵树的森林（每棵树仅有一个结点）；（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；（3）从森林中删除选取的两棵树，并将新树加入森林；（4）重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。四、实验步骤；1.调试下列程序“二叉树程序一”，掌握链式二叉树构造的算法和实现方式。2.根据二叉树程序的学习，完成Huffman树的构造、编码和解码的实现。（1）统计电文中字符的出现频率。（2）用统计频率建立Huffman树，并生成前缀码；（3）建立Huffman树的解码算法。（4）用随机输入的电文完成编码与解码过程。五、程序源代码及注释#includestdio.h#includemalloc.h#includestring.htypedefstruct{charch;intweight;intparent,lchild,rchild;}HTnode,*Huffmantree;//动态分配数组存储赫夫曼树typedefchar**Huffmancode;//动态分配数组存储赫夫曼编码表intmain(){//------------构造赫夫曼树及赫夫曼编码-------------------HuffmantreeHT;HuffmancodeHC;char*cd,s[100],g[100];intn,mm,m,i,j=0,f,start,c,s1=0,s2=0,temp1,temp2;intw[26];inta[26]={0};printf(请输入字符：);gets(s);n=strlen(s);HT=(Huffmantree)malloc((m+1)*sizeof(HTnode));//0号单元未用for(i=0;in;i++)a[s[i]-'a']++;for(i=0;i26;i++)if(a[i]!=0){w[j]=a[i];j++;}n=j;m=2*j-1;HT=(Huffmantree)malloc((m+1)*sizeof(HTnode));for(i=0,j=0;i26;i++)if(a[i]!=0){HT[j+1].ch=i+'a';j++;}for(i=1,j=0;i=n;++i,++j){HT[i].weight=w[j];HT[i].parent=HT[i].lchild=HT[i].rchild=0;}for(;i=m;++i)HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;//除叶子外的节点赋初值for(i=n+1;i=m;i++){//建赫夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个节点，其序号为别为s1,s2.temp1=temp2=100;for(j=1;j=i-1;j++)if(HT[j].parent==0)if(HT[j].weighttemp1){temp1=HT[j].weight;s1=j;}for(j=1;j=i-1;j++)if(HT[j].parent==0&&j!=s1)if(HT[j].weighttemp2){temp2=HT[j].weight;s2=j;}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;//父节点权值为左右两孩子权值之和}printf(numweightlchildparentrchildch\n);for(i=1;i=m;i++)printf(%-4d%4d%8d%8d%8d%6c\n,i,HT[i].weight,HT[i].lchild,HT[i].parent,HT[i].rchild,HT[i].ch);//---------------从叶子到根逆向求每个字符的赫夫曼编码--------------------HC=(Huffmancode)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=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],cd+start);//从cd复制编码到HC}free(cd);printf(\nnumbianma\n);for(i=1;i=n;i++)printf(%-5d%s\n,i,HC[i]);//--------------Huffmancoding-----------------------------------------------------printf(\n请输入一段0-1编码\n);gets(g);printf(\n解码后为:);mm=m;for(i=0;i=(signed)strlen(g);){if(HT[mm].lchild==0&&HT[mm].rchild==0){printf(%c,HT[mm].ch);mm=m;}else{if(g[i]=='0'){mm=HT[mm].lchild;i++;}else{mm=HT[mm].rchild;i++;}}}printf(\n);return0;}六、实验结果分析及实验体会实验体会：我对于二叉树的概念还停留在离散数学时的那么简单，但是对于关于赫夫曼树的概念是没有的，因为课上也还没有讲到。刚开始时我们都非常迷茫，看着书本哪些陌生的结构，可以说是一头雾水啊。但是随着百度的帮助，了解了一些单词的用意。在全班人的协助与借鉴其他程序，书本的情况下，我们终于成功编译出。那是我们共同努力的成果。