贪心法构造哈夫曼树

《贪心法构造哈夫曼树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告（2013/2014学年第二学期）学院贝尔学院学生姓名任晓强班级学号Q12010218指导教师季一木指导单位计算机软件教学中心日期2014年3月12日-实验一：贪心算法构造哈夫曼树问题简述：两路合并最佳模式的贪心算法主要思想如下：（1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树（2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和（3）重复（2），直到合并成一颗二叉树为止一、实验目的（1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈

2、夫曼树（4）设计测试数据，写出程序文档二、实验内容（1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点(3)设计函数，按树形输出哈夫曼树三、程序源代码#include#include#include#includetypedefstructNode{//定义树结构intdata;structNode*leftchild;structNode*rightchild;}Tree;typedefstructData{//定义字符及其对应的频率的结构intd

3、ata;//字符对应的频率是随机产生的charc;};voidInitiate(Tree**root);//初始化节点函数intgetMin(structDataa[],intn);//得到a中数值（频率）最小的数-voidtoLength(chars[],intk);//设置有k个空格的串svoidset(structDataa[],structDatab[]);//初始化a,且将a备份至bchargetC(intx,structDataa[]);//得到a中频率为x对应的字符voidprin(structDataa[]);//输出初始化后的字符及对应的频率intn;voidma

4、in(){//srand((unsigned)time(NULL));Tree*root=NULL,*left=NULL,*right=NULL,*p=NULL;intmin,num;intk=30,j,m;structDataa[100];structDatab[100];inti;chars[100]={''},s1[100]={''};charc;set(a,b);prin(a);Initiate(&root);Initiate(&left);Initiate(&right);Initiate(&p);//设置最底层的左节点min=getMin(a,n);left->

5、data=min;left->leftchild=NULL;left->rightchild=NULL;//设置最底层的右节点min=getMin(a,n-1);right->data=min;right->leftchild=NULL;right->rightchild=NULL;root->data=left->data+right->data;Initiate(&root->leftchild);Initiate(&root->rightchild);//将设置好的左右节点插入到root中root->leftchild=left;root->rightchild=right;

6、for(i=0;idata)//权值小的作为左节点-{left->data=min;left->leftchild=NULL;left->rightchild=NULL;p->data=min+root->data;Initiate(&p->leftchild);Initiate(&p->rightchild);p->leftchild=left;p->rightchild=root;root=p;}else{right->data

7、=min;right->leftchild=NULL;right->rightchild=NULL;p->data=min+root->data;Initiate(&p->leftchild);Initiate(&p->rightchild);p->leftchild=root;p->rightchild=right;root=p;}Initiate(&p);}num=n-1;p=root;printf("哈夫曼树如下图:");while(num){if(num=