《数据结构实验报告实验五》由会员分享，可在线阅读，更多相关《数据结构实验报告实验五（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验五 数据结构实验报告 实验五 实现哈夫曼编码的生成算法。 1、使学生熟练掌握哈夫曼树的生成算法。 2、熟练掌握哈夫曼编码的方法。 已知n个字符在原文中出现的频率，求它们的哈夫曼编码。 1、读入n个字符，以及字符的权值，试建立一棵Huffman树。 2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。 (1)郝夫曼树的存储表示 typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; /动态分配数组
2、存储郝夫曼树 郝夫曼编码的存储表示 typedef char* *HuffmanCode;/动态分配数组存储郝夫曼编码 (2)主要的实现思路： a.首先定义郝夫曼树的存储形式，这里使用了数组 b.用select()遍历n个字符，找出权值最小的两个 c.构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC 1.基本上没有什么太大的问题，在调用select()这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding()，所以把那2个序号设置成了引用。 2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长 3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低
3、级的输入错误。把HTi.weight=HTs1.weight+HTs2.weight;中的s2写成了i /动态分配数组存储郝夫曼树 typedef struct int weight; /字符的权值 int parent,lchild,rchild; HTNode,*HuffmanTree; /动态分配数组存储郝夫曼编码 typedef char* *HuffmanCode; /选择n个(这里是k=n)节点中权值最小的两个结点 void Select(HuffmanTree &HT,int k,int &s1,int &s2) int i; i=1; while(i=k & HTi.paren
4、t!=0)i+; /下面选出权值最小的结点，用s1指向其序号 s1=i; for(i=1;i=k;i+) if(HTi.parent=0&HTi.weight /下面选出权值次小的结点，用s2指向其序号 for(i=1;i=k;i+) if(HTi.parent=0&i!=s1)break; s2=i; for(i=1;i=k;i+) if(HTi.parent=0&i!=s1&HTi.weight /构造Huffman树，求出n个字符的编码 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,c,f,s
5、1,s2,i,start; char *cd; if(n=1)return; m=2*n-1; /n个叶子n-1个结点 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0号单元未用，预分配m+1个单元 HuffmanTree p=HT+1; w+; /w的号单元也没有值，所以从号单元开始 for(i=1;iweight=*w; p-parent=p-rchild=p-lchild=0; for(;iweight=p-parent=p-rchild=p-lchild=0; for(i=n+1;i=m;i+) Select(HT,i-1,s1,s2); /
6、选出当前权值最小的 HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; /从叶子到根逆向求每个字符的郝夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /分配n个字符编码的头指针变量 cd=(char*)malloc(n*sizeof(char); /分配求编码的工作空间 cdn-1=;/编码结束符 for(i=1;i=n;i+) /逐个字符求郝夫曼编码 start=n-1; /编码结束符位置 for(c=i,
7、f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码 if(HTf.lchild=c)cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间 strcpy(HCi,&cdstart);/从cd复制编码到HC free(cd); /释放工作空间 void main() int n,i; int* w; /记录权值 char* ch; /记录字符 HuffmanTree HT; HuffmanCode HC; coutn; w=(int*)malloc(n+1)*sizeof(int); /记录权值，号单元未用 ch=(char*)malloc(n+1)*sizeof(char);/记录字符，号单元未用 cout依次输入待编码的字符data及其权值weight for(i=1;i=n;i+) coutdata 【数据结构实验报告 实验五】相关文章： 1. 2. 3. 4. 5. 6. 7. 8. 模板,内容仅供参考
