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