《数据结构》实验三

1、精选优质文档-倾情为你奉上华北水利水电大学 数据结构 实验报告20152016学年 第 一 学期 2013级 计算机科学与技术专业班级： 学号： 姓名： 冯浩亮 实验三 树的应用一、 实验题目：树的应用哈夫曼编码二、 实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：1 输出存放哈夫曼树的数组HT的初态和终态；2 输出每个字符的哈夫曼编码；3 输入由上述若干字符组

2、成的字符串，对电文进行编码并输出；4 （选作）输入电文的哈夫曼编码，进行译码并输出。三、 实验要求：1 使用C语言完成算法设计和程序设计并上机调试通过。2 撰写实验报告，提供实验结果和数据。3 写出算法设计小结和心得。四、 程序源代码：#include <stdio.h>#include <string.h>#include <stdlib.h>#include <memory.h>#include <conio.h>#define INIT_CAPCITY 100struct HTNode /结点信息char c;/数据项int p

3、arent;/双亲结点的位置int lchild;int rchild;int weight;/权值;struct ChNode /定义一个结构体，用来存放字符串的各个字符和权值信息char c;int weight;struct HCodechar codeINIT_CAPCITY;/存放当前结点的哈夫曼编码int m_start;/开始存放的位置;/创建哈夫曼树void CreateHT(HTNode ht,int n,ChNode s)int i,k,lnode,rnode;/lnode为最小权值结点的位置，rnode为次小权值结点的位置int min1,min2;/min1为最小值，m

4、in2为次小值for (i=0;i<2*n-1;i+)/初始化hti.parent=-1;hti.lchild=-1;hti.rchild=-1;hti.weight=0;for (i=0;i<n;i+)hti.c=si.c;hti.weight=si.weight;printf("哈夫曼树初态为:n");printf("data weight parent lchild rchildn");for (i=0;i<2*n-1;i+)printf("%-6c %-6d %-6d %-6d %-6dn",hti.c,ht

5、i.weight,hti.parent,hti.lchild,hti.rchild);for (i=n;i<2*n-1;i+)min1=min2=32767;lnode=rnode=0;for (k=0;k<=i-1;k+)if (htk.parent=-1)if (htk.weight<min1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weight<min2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;hti.weigh

6、t=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;printf("n哈夫曼树终态为:n");printf("data weight parent lchild rchildn");for (i=0;i<2*n-1;i+)printf("%-6c %-6d %-6d %-6d %-6dn",hti.c,hti.weight,hti.parent,hti.lchild,hti.rchild);printf("n");/哈夫曼编码vo

7、id CreateCode(HTNode ht,HCode hcd,int n)int i,f,c;HCode hc;for (i=0;i<n;i+)hc.m_start=n-1;c=i;f=hti.parent;while(f!=-1)if(htf.lchild=c)hc.codehc.m_start-='0'elsehc.codehc.m_start-='1'c=f;f=htf.parent;hc.m_start+;hcdi=hc;printf("哈夫曼编码:n");printf("结点信息 权值 哈夫曼编码n"

8、);for (i=0;i<n;i+)printf(" %c%s%d%s",hti.c," ",hti.weight," ");for (int j=hcdi.m_start;j<n;j+)printf("%c",hcdi.codej);printf("n");/译码void Coding(HTNode ht,HCode hcd,int n,char buf)for (int i=0;bufi!='0'i+)for (int j=0;j<n;j+)if (bufi

9、=htj.c)for (int k=hcdj.m_start;k<n;k+)printf("%c",hcdj.codek);break;printf("n");/解码void DeCode(HTNode ht,HCode hcd,int n,char buf,int len)char temp10;/用来存放某哈夫曼编码的字符数组int nLen=0;while (nLen<len)for (int i=0;i<n;i+)memset(temp,0,10);int j=0;for (int k=hcdi.m_start;k<n;k

10、+)tempj+=hcdi.codek;int m=n-hcdi.m_start;int nResult=strncmp(buf,temp,m);if (nResult=0)/匹配成功printf("%c",hti.c);break;buf=buf+n-hcdi.m_start;nLen+=n-hcdi.m_start;printf("n");void Menu()char *str="1.创建哈夫曼树并查看初态和终态n","2.创建并查看哈夫曼编码n","3.译码n","4.解码n&

11、quot;,"0.退出n"for (int i=0;i<5;i+)printf("%s",stri);printf("请选择<0-4>");void main()char bufINIT_CAPCITY;printf("请输入一段英文字母:n");scanf("%s",buf);ChNode s20;memset(s,0,sizeof(ChNode)*20);int j=0;for (int i=0;bufi!='0'i+)int flag=0;for(int

12、k=0;k<j;k+)if(bufi=sk.c)/若bufi在s中已经存在，将其权值加1sk.weight+;flag=1;break;if(!flag)/若s中不存在bufi,将其添加到s中，并将权值置为1sj.c=bufi;sj.weight=1;j+;HTNode htINIT_CAPCITY;memset(ht,0,sizeof(HTNode)*INIT_CAPCITY);HCode hcdINIT_CAPCITY;int nChoice=-1;while(1)Menu();scanf("%d",&nChoice);if(nChoice=0)break

13、;switch (nChoice)case 1:CreateHT(ht,j,s);break;case 2:CreateCode(ht,hcd,j);break;case 3:char strINIT_CAPCITY;printf("请输入译文:n");scanf("%s",str);printf("译码后为:");Coding(ht,hcd,j,str);break;case 4:char ssINIT_CAPCITY;printf("请输入要解码的0,1序列:n");scanf("%s",ss);printf("解码后为:");DeCode(ht,hcd,j,ss,strlen(ss);break;default:break;printf("按任意键继续.");getch();system("cls");五、 程序运行情况（采用截图方式给出运行结果）六、 小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）通过这次试验我能熟练掌握及应用了树的结构及非线性特点，递归特点和动态性，进一步巩固了对指针的使用和二叉树的建立方法，能比较熟练的运用建立哈夫曼树及求哈