资源描述：
《数据结构实验报告 实验五》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构实验报告实验五 一.实验内容： 实现哈夫曼编码的生成算法。 二.实验目的： 1、使学生熟练掌握哈夫曼树的生成算法。 2、熟练掌握哈夫曼编码的方法。 三.问题描述： 已知n个字符在原文中出现的频率，求它们的哈夫曼编码。 1、读入n个字符，以及字符的权值，试建立一棵Huffman树。 2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。 四.问题的实现 (1)郝夫曼树的存储表示 typedefstruct{ unsignedintweight; unsignedin
2、tparent,lchild,rchild; }HTNode,*HuffmanTree;//动态分配数组存储郝夫曼树 郝夫曼编码的存储表示 typedefchar**HuffmanCode;//动态分配数组存储郝夫曼编码 (2)主要的实现思路： a.首先定义郝夫曼树的存储形式，这里使用了数组 b.用select()遍历n个字符，找出权值最小的两个 c.构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC 总结 1.基本上没有什么太大的问题，在调用select()这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding()，
3、所以把那2个序号设置成了引用。 2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长 3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HT.weight=HT.weight+HT.weight;中的s2写成了i 附： //动态分配数组存储郝夫曼树 typedefstruct{ intweight;//字符的权值 intparent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储郝夫曼编码 typedefchar**HuffmanCo
4、de; //选择n个(这里是k=n)节点中权值最小的两个结点 voidSelect(HuffmanTree&HT,intk,int&s1,int&s2) {inti; i=1; while(i //下面选出权值最小的结点，用s1指向其序号 s1=i; for(i=1;i { if(HT.parent==0&&HT.weight } //下面选出权值次小的结点，用s2指向其序号 for(i=1;i { if(HT.parent==0&&i!=s1)break; } s2=i; for(i=1;i { if(HT.
5、parent==0&&i!=s1&&HT.weight } } //构造Huffman树，求出n个字符的编码 voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn) { intm,c,f,s1,s2,i,start; char*cd; if(n m=2*n-1;//n个叶子n-1个结点 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用，预分配m+1个单元 HuffmanTreep=HT+1; w++;//w
6、的号单元也没有值，所以从号单元开始 for(i=1;i { p->weight=*w; p->parent=p->rchild=p->lchild=0; } for(;i { p->weight=p->parent=p->rchild=p->lchild=0; } for(i=n+1;i { Select(HT,i-1,s1,s2);//选出当前权值最小的 HT.parent=i; HT.parent=i; HT.lchild=s1; HT.rchild=s2; HT.weight=HT.weight+HT.weig
7、ht; } //从叶子到根逆向求每个字符的郝夫曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针变量 cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间 cd='';//编码结束符 for(i=1;i { start=n-1;//编码结束符位置 for(c=i,f=HT.parent;f!=0;c=f,f=HT.parent)//从叶子到根逆向求编码 { if(HT.lchild==c)cd='0'; else
8、cd='1'; } HC=(char*)malloc((n-start)*sizeof(char));/
