数据结构实验报告 实验五.pdf

《数据结构实验报告 实验五.pdf》由会员分享，可在线阅读，更多相关《数据结构实验报告 实验五.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本文为本文为 WordWord版本，下载可任意编辑版本，下载可任意编辑 unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态安排数组存储郝夫曼树实现哈夫曼编码的生成算法。郝夫曼编码的存储表示二.试验目的：typedef char*HuffmanCode;/动态安排数组存储郝夫曼编码 1、使同学娴熟掌控哈夫曼树的生成算法。(2)主要的实现思路：2、娴熟掌控哈夫曼编码的方法。a.首先定义郝夫曼树的存储形式，这里运用了数组三.问题描述：b.用 select()遍历 n 个字符，找出权值最小的两个已知

2、 n 个字符在原文中涌现的频率，求它们的哈夫曼编码。c.构造郝夫曼树 HT，并求出 n 个字符的郝夫曼编码 HC 1、读入 n 个字符，以及字符的.权值，试建立一棵 Huffman 树。总结 2、依据生成的 Huffman 树，求每个字符的 Huffman 编码。并对给 1.基本上没有什么太大的问题，在调用 select()这个函数时，想定的待编码字符序列进行编码，并输出。把权值最小的两个结点的序号带回 HuffmanCoding()，所以把那 2 个四.问题的实现序号设置成了引用。(1)郝夫曼树的存储表示 2.在编程过程中，在什么时候安排内存，什么时候初始化花的时 typedef struc

3、t第 1 页 共 5 页数据结构实验报告数据结构实验报告 实验五实验五本文为本文为 WordWord版本，下载可任意编辑版本，下载可任意编辑间比较长 3.最末基本上实现后，发觉结果仍旧存在问题，经过分步调试，发觉了特别低级的输入错误。把HTi.weight=HTs1.weight+HTs2.weight;中的 s2 写成了 i附：/动态安排数组存储郝夫曼树 typedef struct int weight;/字符的权值 int parent,lchild,rchild;HTNode,*HuffmanTree;/动态安排数组存储郝夫曼编码 typedef char*HuffmanCode;/选

4、择 n 个(这里是 k=n)节点中权值最小的两个结点 void Select(HuffmanTree HT,int k,int s1,int s2)int i;i=1;while(i=k HTi.parent!=0)i+;/下面选出权值最小的结点，用 s1 指向其序号 s1=i;for(i=1;i=k;i+)if(HTi.parent=0HTi.weight /下面选出权值次小的结点，用 s2 指向其序号 for(i=1;i=k;i+)if(HTi.parent=0i!=s1)break;第 2 页 共 5 页本文为本文为 WordWord版本，下载可任意编辑版本，下载可任意编辑 s2=i;f

5、or(i=1;i=k;i+)if(HTi.parent=0i!=s1HTi.weight /构造 Huffman 树，求出 n 个字符的编码 void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int*w,intn)int m,c,f,s1,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 的号单元也没有值，所以

6、从号单元开始 for(i=1;i=n;i+,p+,w+)p-weight=*w;p-parent=p-rchild=p-lchild=0;for(;i=m;+i,+p)p-weight=p-parent=p-rchild=p-lchild=0;for(i=n+1;i=m;i+)第 3 页 共 5 页本文为本文为 WordWord版本，下载可任意编辑版本，下载可任意编辑 Select(HT,i-1,s1,s2);/选出当前权值最小的 HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs

7、2.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,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码 if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char

8、*)malloc(n-start)*sizeof(char);/为第 i 个字符编码安排空间 strcpy(HCi,cdstart);/从 cd 复制编码到 HC free(cd);/释放工作空间第 4 页 共 5 页本文为本文为 WordWord版本，下载可任意编辑版本，下载可任意编辑 void main()int n,i;int*w;/记录权值 char*ch;/记录字符 HuffmanTree HT;HuffmanCode HC;cout 请输入待编码的字符个数 n=;cinn;w=(int*)malloc(n+1)*sizeof(int);/记录权值，号单元未用 ch=(char*)malloc(n+1)*sizeof(char);/记录字符，号单元未用 cout 依次输入待编码的字符 data 及其权值 weight for(i=1;i=n;i+)coutdata 第 5 页 共 5 页