数据结构-实验三

1、PAGE 第7页 共7页数据结构 实验报告20112012学年 第 * 学期 *级 * 专业班级： * 学号： * 姓名： * 实验三 树的应用实验题目：树的应用哈夫曼编/译码实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入字符及权值的基础上求哈夫曼编码。要求：从键盘输入字符集（字母az，空格）共27个字符，以及出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，并输出数组ht的初态和终态。对各个字符进行哈夫曼编码，打印输出字符及对应的哈夫曼编码。编码：从键盘输入字符串，利用已建好的哈夫曼编码，实现

2、该字符串的编码。（选作）译码：从键盘输入二进制串，利用已建好的哈夫曼编码，将二进制串还原为字符串。三、程序源代码：#include #include #include typedef structchar data;/结点值float weight;/权重int parent;/双亲结点int lchild;/左孩子结点int rchild;/右孩子节点HTNode;typedef structchar cd27;/各个字符的哈夫曼编码int start;/各个字符的哈夫曼编码的起始下标HCode;void CreateHT(HTNode ht,int n)/构建哈夫曼树int i,k,lno

3、de,rnode;char str27;float s27;cout请输入空格和26个字母:endl;gets(str);cout请分别输入这27个字符的权重:endl;for(i=0;isi;float min1,min2;for(i=0;in;i+)hti.data=stri;hti.weight=si;for(i=0;i2*n-1;i+)/所有结点的相关域置初值-1hti.parent=hti.lchild=hti.rchild=-1;cout哈夫曼树的初态:n序号 结点值 权重 双亲结点 左孩子结点 右孩子节点endl;for(i=0;in;i+)coutithti.datathti.

4、weightt;couthti.parentthti.lchildthti.rchildendl;for(i=n;i2*n-1;i+)/构造哈夫曼树min1=min2=32767;lnode=rnode=-1;for(k=0;k=i-1;k+)if(htk.parent=-1)if(htk.weightmin1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if(htk.weightmin2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;hti.weight=htlno

5、de.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;cout哈夫曼树的终态:n序号 结点值 权重 双亲结点 左孩子结点 右孩子节点endl;for(i=0;i2*n-1;i+)coutit;if(in)couthti.datat;elsecout t;couthti.weightthti.parentt;couthti.lchildthti.rchildendl;void CreateHCode(HTNode ht,HCode hcd,int n)/对哈夫曼树进行编码int i,f,c;HCode hc;for(i=0;in;i

6、+)hc.start=n-1;c=i;f=hti.parent;while(f!=-1)if(htf.lchild=c)hc.cdhc.start-=0;elsehc.cdhc.start-=1;c=f;f=htf.parent;hc.start+;hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n)/输出各个字符的哈夫曼编码int i,k;cout输出哈夫曼编码:n字符t对应编码endl;for(i=0;in;i+)couthti.datat;for(k=hcdi.start;kn;k+)couthcdi.cdk;coutendl;void CreateStrHCode(HTNode ht,HCode hcd,int n)/对字符串进行编码char str50;int i,j,k;cout请输入要编码的字符串:endl;gets(str);int nLen=strlen(str);cout该字符串的编码为:endl;for(i=0;inLen;i+)for(j=0;jn;j+)if(stri=htj.data)for(k=hcdj.start;kn;k+)couthcdj.cdk;cout ;coutendl;void main()int n=27;HTN