哈弗曼树实现及用途

哈弗曼树

哈夫曼树

2009年04月30日 星期四 19:20

哈夫曼树2009年04月30日 星期四 19:20//vc++6.0下通过测试

#include

#include

int MAX=65000;

struct HtNode

{

int ww; //权值

int llink; //左子节点下标

int rlink; //右子节点下标

int parent; //父节点下标

};

//typedef struct HtNode PHtNode;

struct HtTree

{

int m;

int root;

HtNode *ht;

};

typedef struct HtTree *PHtTree;

PHtTree huffman(int m,int *w)

{

PHtTree pht;

int i,j;

int x1,x2;

int m1,m2;

pht=(PHtTree)malloc(sizeof (struct HtTree));

if(pht==NULL)

{

printf("Out of space !!\n");

return NULL;

}

pht->ht=(struct HtNode *)malloc(sizeof (struct HtNode) * (2*m-1));

if(pht->ht==NULL)

{

printf("Out of space !!\n");

return 0;

}

for(i=0;i<2*m-1;++i)

{

pht->ht[i].llink=-1;

pht->ht[i].rlink=-1;

pht->ht[i].parent=-1;

if(i

pht->ht[i].ww=w[i];

else

pht->ht[i].ww=-1;

}

for(i=0;i

{

m1=MAX;

m2=MAX;

x1=-1;

x2=-1;

for(j=0;j

if(pht->ht[j].wwht[j].parent==-1)

{

m2=m1;

x2=x1;

m1=pht->ht[j].ww;

x1=j;

}

else if (pht->ht[j].wwht[j].parent==-1)

{

m2=pht->ht[j].ww;

x2=j;

}

pht->ht[x1].parent=m+i;

pht->ht[x2].parent=m+i;

pht->ht[m+i].ww=m1+m2;

pht->ht[j].llink=x1;

pht->ht[j].rlink=x2;

}

pht->root=2*m-2;

return pht;

}

int main()

{

int w[]={2,3,5,7,11,13,17,19,23,29,31,37,41};

PHtTree pht;

pht=huffman(13,w);

for(int i=0;i<25;++i)

{

printf("%d: ",i);

printf("%d\t",pht->ht[i].ww);

printf("%d\t",pht->ht[i].parent);

printf("%d\t",pht->ht[i].llink);

printf("%d\t",pht->ht[i].rlink);

printf("\n");

}

return 0;

}

类别：java开发--爱恨情仇 | 添加到搜藏 | 浏览(353) | 评论 (0)

上一篇：diy相册地址2    下一篇：jar打包详解

相关文章：

最近读者：

本文来源：https://www.2haoxitong.net/k/doc/20555e4bcf84b9d528ea7a4b.html