数据结构——实验四哈夫曼树与哈夫曼编码

软软件件学学院院哈夫曼树与哈夫曼编码实验报告课程名称：数据结构姓名：郑斌学号：201370034217班级：卓越131卓越131班郑斌哈弗曼树1实验四哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容本次实验提供3个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！题目一、哈夫曼树和哈夫曼编码[问题描述]一电文，有若干个不同字符，要求从终端输入这些不同字符及其出现的频率，然后对这些字符进行哈夫曼编码，并输出。［测试数据］利用教材P.148例6－2中的数据调试程序(可自己设定测试数据)。[选作内容]1、打印出该哈夫曼树2、若从终端输入任意一段电文（假设仅为26个大小写英文字母）,试编程高效地求出该段电文的哈夫曼编码。提示：如何快速统计不同字符的出现频率3、译码：将上述1的编码结果还原成电文。三、算法设计1)本程序包含三个模块1．voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)//选择函数2．voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)w存放n个权值,构造哈夫曼树p,3．VoidHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn)求出哈夫曼编码hc并输出哈弗曼编码卓越131班郑斌哈弗曼树2四、实验结果图1-1输入哈弗曼树的权值图1-2显示哈弗曼树表与其编码五、总结通过做哈弗曼树实验让对最优二叉树这种结构有了更深的了解和应用，对我以后的编程产生了比较深远的影响。六、源程序（带注释）#includeiostream#includeiomanip#includestdlib.h#includestring.h#includestdio.husingnamespacestd;typedefstruct{intweight;intparent,lchild,rchild;卓越131班郑斌哈弗曼树3charcharr;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,inti,int&s1,int&s2){intj,k=1;while(HT[k].parent!=0)k++;s1=k;for(j=1;j=i;++j)if(HT[j].parent==0&&HT[j].weightHT[s1].weight)s1=j;k=1;while((HT[k].parent!=0||k==s1))k++;s2=k;for(j=1;j=i;++j)if(HT[j].parent==0&&HT[j].weightHT[s2].weight&&j!=s1)s2=j;}voidHuffmanCoding(HuffmanTree&HT,int*w,intn){intm,i,s1,s2;if(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i=n;++i){HT[i].weight=w[i];HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}for(i=n+1;i=m;++i){HT[i].weight=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}//构建哈弗曼树for(i=n+1;i=m;++i){Select(HT,i-1,s1,s2);//选择parent为0且weight最小的两个结点，期序号分别为s1，s2HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}cout\n哈弗曼树表如下：endl;//打印哈弗曼树表coutiweightparentlchildrchildendl;HuffmanTreep;卓越131班郑斌哈弗曼树4for(p=HT+1,i=1;i=m;i++,p++)coutsetw(2)isetw(7)p-weightsetw(6)p-parentsetw(7)p-lchildsetw(8)p-rchildendl;}voidHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn){char*cd;intc,f,start;inti;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=newchar[n];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));strcpy(HC[i],&cd[start]);}coutendl;cout哈夫曼编码如下:;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复制编码到HCprintf(\nHT[%d]节点的哈夫曼编码是:%s对应权值为：%d,i,HC[i],HT[i].weight);}coutendl;free(cd);}intmain(){HuffmanTreeHT;HuffmanCodeHC;int*w;卓越131班郑斌哈弗曼树5char*e;charc;inti,n,m,wei;cout--请输入哈弗曼树的带权数目--endl;cinn;w=newint[n+1];e=newchar[n+1];for(i=1;i=n;i++){cout--请输入第i个元素的权值--;cinwei;w[i]=wei;}HuffmanCoding(HT,w,n);m=2*n-1;Huffmancode(HT,HC,n);return0;}