数据结构与算法实验报告_3霍夫曼树

《数据结构与算法实验报告_3霍夫曼树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

实验四数据结构与程序设计专题实验报告赫夫曼树学院:物理与电子学院班级:电信1105班姓名:刘岩学号:14041107298 实验报告一、实验任务实验题目：数据结构与程序设计专题实验二、实验内容实验三：树的基本操作及基于霍夫曼树的编码/译码（一）实验目的：掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。（二）基本要求：熟练掌握树的操作。（三）内容提要：给定一段字符，构建霍夫曼树；根据该树求每个字符的编码，并对该段字符串进行编码；将得到的编码进行译码；基于该霍夫曼树，通过遍历算法来输出该树中的叶子节点。注：在实现时要求霍夫曼树的左右孩子的大小关系（左孩子节点值小于右孩子节点），在遍历的时候也可以为递归与非递归办法寻找叶子节点。三、要点分析题目中涉及的主要知识点：1、本程序参考霍夫曼算法（由给定的权值构造赫夫曼树）：（1）由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵二叉树的集合F={T0,T1,T2,…,Tn-1}，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。（2）重复以下步骤,直到F中仅剩下一棵树为止：①在F中选取两棵根结点的权值最小的二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。2、用构造赫夫曼树以完成赫夫曼编码：把d1,d2,…,dn作为叶子结点，把w1,w2,…,wn作为叶子结点的权，构造赫夫曼树。在赫夫曼树中结点的左分支赋0，右分支赋1，从根结点到叶子结点的路径上的数字拼接起来就是这个叶子结点字符的编码。3、译码的过程是分解电文中的字符串，从根出发，按字符‘0’或‘1’确定找左孩子或右孩子，直至叶子节点，便求得该子串相应的字符。四、程序的算法描述1、所用存储结构：typedefstructHfNode8 {intweight;intparent,lchild,rchild;}HfNode,*HuffmanTree;//动态分配数组存储霍夫曼树typedefchar**HuffmanCode;//动态分配数组存储霍夫曼编码表2、程序中各函数的简要说明：(1)voidSelect(HuffmanTree&HT,inti,int&a,int&b)从前i个节点中选择权值最小的两个节点分别存入a,b中。设置a，b两个变量用“打擂台”的方法求出两个最小值。(2)voidCreatHuffmanTree(HuffmanTree&HT,intn,intWeight[])根据Weight[53]及Letter[52]中的信息建立具有2n-1个节点的Huffman树。首先创建有2*n-1个节点的存储空间，将前n个节点的权值付为对应的Weight[i]，双亲结点和左右孩子结点均置为零。剩余结点的权值、双亲结点和左右孩子结点置为零。之后，i从n+1到2*n-1每次加1，在HT[1..i-1]中选取parent为零且weight最小的两个节点，将他们的双亲结点置为HT[i]。(3)voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn)获得n个字符的Huffman码。从叶子节点到根逆向求编码。先求叶子结点的双亲结点，如果该结点为左孩子，则在Huffman码中从后往前字符置为‘0’；若为右孩子则置为‘1’，直至根节点结束。(4)char*HuffmanEncoding(HuffmanCodehc,intn,charText[],charLetter[])对输入文本进行Huffman编码。将要编码的字符串传入函数，截取一个字符，与编码表中的字符比较，找到对应的huffman码，连接到编码串后，直至所有的字符都读入。(5)voidHuffmanDecoding(HuffmanTree&HT,chara[],intn,charLetter[])对输入文本进行Huffman解码。从根结点出发，按字符‘0’，‘1’确定找左孩子或右孩子，直至叶子结点，便求得该子串相应的字符。将所有子串找遍，得译码结果。(6)intStatistic(intWeight[],charLetter[],charText[])对输入文本中的字母出现频数进行统计，存入Text[100],Letter[53],Weight[53]中。逐个读入字符，与Letter[]中的字符比较，如果该字符已经出现过，则将相应的权值加1；否则，新建一个字符统计项，相应的权值加1.直至所有的字符都读入。(7)voidmain()在主函数中输出交互信息，提示用户输入要编码的字符串，调用Statistic函数并输出统计结果。调用CreatHuffmanTree、HuffmanCoding，并输出每一个字符的huffman码。最后调用HuffmanEncoding、HuffmanDecoding对其编码和解码。3、源代码完整程序及相应说明如下;#include#include#includetypedefstructHfNode{intweight;intparent,lchild,rchild;}HfNode,*HuffmanTree;//动态分配数组存储霍夫曼树8 typedefchar**HuffmanCode;//动态分配数组存储霍夫曼编码表//从前i个节点中选择权值最小的两个节点分别存入a,b中voidSelect(HuffmanTree&HT,inti,int&a,int&b){intj=1;if(i<2)return;while(!(HT[j].weight)){j++;}b=a=j;for(j=1;j<=i;j++){if(!(HT[j].weight))continue;if((HT[a].weight)>(HT[j].weight)){a=j;}}if(b!=a){for(j=1;j<=i;j++){if(!(HT[j].weight)||j==(a))continue;if((HT[b].weight)>(HT[j].weight)&&j!=a){b=j;}}}else{j=a+1;while(!(HT[j].weight)){j++;}b=j;for(j=1;j<=i;j++){if(!(HT[j].weight)||j==(a))continue;if((HT[b].weight)>(HT[j].weight)){b=j;}}}}/*根据Weight[53]及Letter[52]中的信息建立具有2n-1个节点的Huffman树*/voidCreatHuffmanTree(HuffmanTree&HT,intn,intWeight[]){inti,m;8 if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HfNode));/*不用0号单元*/for(i=1;i<=n;++i){HT[i].weight=Weight[i];HT[i].parent=HT[i].lchild=HT[i].rchild=0;}for(i=n+1;i<=m;++i){HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;}for(i=n+1;i<=m;++i)/*构造赫夫曼树*/{ints1,s2;Select(HT,i-1,s1,s2);/*在HT[1...i-1]选择parent为0且weight最小的两个节点，其序号分别为s1和s2*/HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s2;HT[i].rchild=s1;(HT[i].weight)=(HT[s1].weight)+(HT[s2].weight);(HT[s1].weight)=(HT[s2].weight)=0;}}/*获得n个字符的Huffman码*/voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn){inti,start,c;intf;char*cd;if(!HT)return;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='';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));strcpy(HC[i],&cd[start]);}8 free(cd);}/*对输入文本进行Huffman编码*/char*HuffmanEncoding(HuffmanCodehc,intn,charText[],charLetter[]){inti,j=0;chara[400];for(i=0;i<400;i++)a[i]='';while(Text[j]){for(i=1;i<=n;i++){if(Text[j]==Letter[i]){strcat(a,hc[i]);break;}}j++;}returna;}/*对输入文本进行Huffman解码*/voidHuffmanDecoding(HuffmanTree&HT,chara[],intn,charLetter[]){inti=0,m,count=0,location;charb[100];m=2*n-1;for(i=0;i<100;i++)b[i]='';i=0;while(a[count]!=''){location=m;while(1){if(!(HT[location].lchild)&&!(HT[location].rchild))break;if(a[count]=='0')location=HT[location].lchild;elselocation=HT[location].rchild;count++;}b[i++]=Letter[location];8 }printf(" Huffman解码的结果: %s ",b);}/*对输入文本中的字母出现频数进行统计，存入Text[100],Letter[53],Weight[53]中*/intStatistic(intWeight[],charLetter[],charText[]){chara;intcount=0,i,j=0,flag=0;for(i=1;i<=52;i++)//字母及权值置零{Letter[i]=Weight[i]=0;}while((a=getchar())!=' ')//逐个读入字符并统计{Text[j++]=a;for(i=1;i<=count;i++){if(a==Letter[i]){Weight[i]++;flag=1;break;}}if(flag){flag=0;continue;}else{Letter[count+1]=a;Weight[count+1]++;count++;}}Text[j]='';returncount;}voidmain(){intWeight[53];//权值HuffmanCodehc;//霍夫曼编括码HuffmanTreeht;//霍夫曼树骸charLetter[53],Text[100];//letter统计每个字母的信息，text存储要编括码的字符串inti=1,n;char*a;printf("请输入将要进行Huffman编码的字母序列: ");n=Statistic(Weight,Letter,Text);printf(" 字母序列统计: %s ",Text);8 while(i<=n){printf("%3c%3d ",Letter[i],Weight[i]);i++;}CreatHuffmanTree(ht,n,Weight);HuffmanCoding(ht,hc,n);printf(" 每一个字的Huffman编码: ");i=1;while(i<=n){printf("%c%s ",Letter[i],hc[i]);i++;}a=HuffmanEncoding(hc,n,Text,Letter);printf(" Huffman编码的结果: %s ",a);HuffmanDecoding(ht,a,n,Letter);}五、程序运行结果8 六、实验总结通过本次实验，我对赫夫曼树有了更加深刻的了解。我尝试了书上没有的结构体，使自己的感觉丰富了许多，耳目一新，加深了我对学习这个赫夫曼树知识的兴趣。练习了结构体、指针及二叉树的生成、遍历等操作，熟练掌握树的操作。对知识的巩固与加深起到了很大的作用，我受益匪浅。8