算法设计与分析实验报告贪心算法

算法设计与分析实验报告

贪心算法

班级： 2013156 学号： 201315614 姓名：张 春 阳

哈夫曼编码

代码

#include

float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree {

float weight;

intlchild,rchild,parent;

}huffman;

huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) {

inti;

void select();

printf(\请输入%d个节点的权值:\for(i=0;i

scanf(\

}

printf(\for(i=0;i

for(count=n;count

select();

huffmantree[flag1].parent=count; huffmantree[flag2].parent=count;

huffmantree[count].weight=small1+small2; huffmantree[count].lchild=flag1; huffmantree[count].rchild=flag2; huffmantree[i].lchild=-1; huffmantree[i].rchild=-1; huffmantree[i].parent=-1;

void select() {

inti,a,b; float stemp; intftemp;

a=0;b=0;

for(i=0;i

if(huffmantree[i].parent==-1) { }

if((a==1)&&(b==1))

break; if(a==0) { } else

if(b==0) { }

small2=huffmantree[i].weight; flag2=i; b=b+1;

small1=huffmantree[i].weight; flag1=i; a=a+1;

if(small1>small2) { }

for(i=0;i

if(huffmantree[i].parent==-1)

if((flag1!=i)&&(flag2!=i))

if(huffmantree[i].weight

small2=huffmantree[i].weight; flag2=i;

if(small1>small2) {

stemp=small1; small1=small2; small2=stemp; ftemp=flag1;

stemp=small1; small1=small2; small2=stemp; ftemp=flag1; flag1=flag2; flag2=ftemp;

}

}

}

flag1=flag2; flag2=ftemp;

void huffmancode(int n) {

inta[100]; intj,k,i,c; for(i=0;i

j=i; c=0;

while(huffmantree[j].parent!=-1) {

k=huffmantree[j].parent; if(huffmantree[k].lchild==j)

a[c]=0;

if(huffmantree[k].rchild==j)

a[c]=1;

c=c+1; j=k;