实验报告（ 2013 / 2014 学年第二学期）学院贝尔学院学生姓名任晓强班级学号 Q12010218 指导教师季一木指导单位计算机软件教学中心日期 2014年3月12日实验一：贪心算法构造哈夫曼树问题简述：两路合并最佳模式的贪心算法主要思想如下：（1）设w={w0,w1,......w}是一组权值，以每个权值作为根结点值，构造n棵只有根的n-1二叉树（2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和（3）重复（2），直到合并成一颗二叉树为止一、实验目的（1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档二、实验内容（1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点(3)设计函数，按树形输出哈夫曼树三、程序源代码#include <stdio.h>#include <string.h>#include <time.h>#include <stdlib.h>typedef struct Node{ //定义树结构int data;struct Node *leftchild;struct Node *rightchild;}Tree;typedef struct Data{ //定义字符及其对应的频率的结构int data;//字符对应的频率是随机产生的char c;};void Initiate(Tree **root);//初始化节点函数int getMin(struct Data a[],int n);//得到a中数值（频率）最小的数void toLength(char s[],int k);//设置有k个空格的串svoid set(struct Data a[],struct Data b[]);//初始化a,且将a备份至b char getC(int x,struct Data a[]);//得到a中频率为x对应的字符void prin(struct Data a[]);//输出初始化后的字符及对应的频率int n;void main(){//srand((unsigned)time(NULL));Tree *root=NULL,*left=NULL,*right=NULL,*p=NULL;int min,num;int k=30,j,m;struct Data a[100];struct Data b[100];int i;char s[100]={'\0'},s1[100]={'\0'}; char c;set(a,b);prin(a);Initiate(&root);Initiate(&left);Initiate(&right);Initiate(&p);//设置最底层的左节点min=getMin(a,n);left->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;for(i=0;i<n-2;i++){min=getMin(a,n-2-i);Initiate(&left);Initiate(&right);if(min<root->data)//权值小的作为左节点{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=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("哈夫曼树如下图:\n");while(num){if(num==n-1){for(j=0;j<k-3;j++)printf(" ");printf("%d\n",root->data);}for(j=0;j<k-4;j++)printf(" ");printf("/ \\\n");for(j=0;j<k-5;j++)printf(" ");printf("%d",root->leftchild->data);printf(" %d\n",root->rightchild->data);if(root->leftchild->leftchild!=NULL){root=root->leftchild;k=k-2;}else{root=root->rightchild;k=k+3;}num--;}num=n-1;Initiate(&root);root=p;printf("各字符对应的编码如下:\n");while(num){if(root->leftchild->leftchild==NULL){strcpy(s1,s);m=root->leftchild->data;c=getC(m,b);printf("%c 【%d】:%s\n",c,m,strcat(s1,"0"));}if(root->rightchild->leftchild==NULL){strcpy(s1,s);m=root->rightchild->data;c=getC(m,b);printf("%c 【%d】:%s\n",c,m,strcat(s1,"1"));}if(root->leftchild->leftchild!=NULL){strcat(s,"0");root=root->leftchild;}if(root->rightchild->leftchild!=NULL){strcat(s,"1");root=root->rightchild;}num--;}}int getMin(struct Data a[],int n){int i,t;for(i=1;i<n;i++){if(a[i].data<a[0].data){t=a[i].data;a[i].data=a[0].data;a[0].data=t;}}t=a[0].data;for(i=0;i<n-1;i++){a[i]=a[i+1];}return t;}void toLength(char s[],int k){int i=0;for(;i<k;i++)strcat(s," ");}void Initiate(Tree **root){*root=(Tree *)malloc(sizeof(Tree));(*root)->leftchild=NULL;(*root)->rightchild=NULL;}void set(struct Data a[],struct Data b[]) {int i;srand((unsigned)time(NULL));n=rand()%10+2;for(i=0;i<n;i++){a[i].data=rand()%100+1;a[i].c=i+97;b[i].data=a[i].data;b[i].c=a[i].c;if(i>=0&&a[i].data==a[i-1].data)i--;}}char getC(int x,struct Data b[]){int i;for(i=0;i<n;i++){if(b[i].data==x){break;}}return b[i].c;}void prin(struct Data a[]){int i;printf("字符\t出现的频率\n");for(i=0;i<n;i++){printf("%c\t %d\n",a[i].c,a[i].data);}}四、程序运行结果演示五、实验体会哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树，n-1次合并后，成为最终的一棵哈夫曼树。

这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数最快（或最慢）为原则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。

每次选择两个权值最小的二叉树时，规定了较小的为左子树。