文档库

最新最全的文档下载
当前位置:文档库 > 贪心算法构造哈夫曼树

贪心算法构造哈夫曼树

软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码

问题简述:

两路合并最佳模式的贪心算法主要思想如下:

(1)设w={w0,w1,......wn-1}是一组权值,以每个权值作为根结点值,构造n棵只有根的二叉树

(2)选择两根结点权值最小的树,作为左右子树构造一棵新二叉树,新树根的权值是两棵子树根权值之和

(3)重复(2),直到合并成一颗二叉树为

一、实验目的

(1)了解贪心算法和哈夫曼树的定义(2)掌握贪心法的设计思想并能熟练运用(3)设计贪心算法求解哈夫曼树(4)设计测试数据,写出程序文档

二、实验内容

(1)设计二叉树结点数据结构,编程实现对用户输入的一组权值构造哈夫曼树(2)设计函数,先序遍历输出哈夫曼树各结点3)设计函数,按树形输出哈夫曼树

代码:

#include

#include

#include

#include

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个空格的串s

void 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

{

min=getMin(a,n-2-i);

Initiate(&left);

Initiate(&right);

if(mindata)//权值小的作为左节点

{

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

printf(" ");

printf("%d\n",root->data);

}

for(j=0;j

printf(" ");

printf("/ \\\n");

for(j=0;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

{

if(a[i].data

{

t=a[i].data;

a[i].data=a[0].data;

a[0].data=t;

}

}

t=a[0].data;

for(i=0;i

{

a[i]=a[i+1];

}

return t;

}

void toLength(char s[],int k)

{

int i=0;

for(;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

{

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

{

if(b[i].data==x)

{

break;

}

}

return b[i].c;

}

void prin(struct Data a[])

{

int i;

printf("字符\t出现的频率\n");

for(i=0;i

{

printf("%c\t %d\n",a[i].c,a[i].data);

}

}