哈夫曼树及哈夫曼编码的C程序实现(数据结构题)问题描述〕输入一个有n个叶结点的权值构造一棵哈夫曼树；（例如：n＝8,权值为 5 29 7 8 14 23 3 11） 根据哈夫曼树构造哈夫曼编码,用指向字符

哈夫曼树及哈夫曼编码的C程序实现(数据结构题)问题描述〕输入一个有n个叶结点的权值构造一棵哈夫曼树；（例如：n＝8,权值为 5 29 7 8 14 23 3 11） 根据哈夫曼树构造哈夫曼编码,用指向字符
哈夫曼树及哈夫曼编码的C程序实现(数据结构题)
问题描述〕输入一个有n个叶结点的权值构造一棵哈夫曼树；（例如：n＝8,权值为 5 29 7 8 14 23 3 11） 根据哈夫曼树构造哈夫曼编码,用指向字符串的指针数组来存放,从叶子到树根逆向求每个结点的哈夫曼编码

哈夫曼树及哈夫曼编码的C程序实现(数据结构题)问题描述〕输入一个有n个叶结点的权值构造一棵哈夫曼树；（例如：n＝8,权值为 5 29 7 8 14 23 3 11） 根据哈夫曼树构造哈夫曼编码,用指向字符
//
#include
#include
#include
#include "linkqueue.h"
bitree *CreateEmptyList()
{
bitree *h;
h = (bitree *)malloc(sizeof(bitree));
h->next = h->lchild = h->rchild = NULL;
return h;
}
void InsertList(bitree *h, bitree *q)
{
while (h->next && (h->next->weight < q->weight))
{
h = h->next;
}
q->next = h->next;
h->next = q;
return;
}
void VisitList(bitree *h)
{
printf("vist: h = %p\n",h);
printf("vist: h->next = %p\n",h->next);
h = h->next;
while ( h )
{
printf("%d ", h->weight);
h = h->next;
}
printf("\n");
return;
}
void CreateHaffmanTree(bitree *h)
{
bitree *p;
while (h->next && h->next->next)
{
p = (bitree *)malloc(sizeof(bitree));
p->lchild = h->next;
p->rchild = h->next->next;
p->weight = p->lchild->weight + p->rchild->weight;
h->next = p->rchild->next;
InsertList(h, p);
}
return;
}
void NoOrder(bitree *root)
{
bitree *p;
linkqueue *queue;
queue = CreateEmptyLinkqueue();
EnQueue(queue, root);
while ( !EmptyLinkqueue(queue) )
{
p = DeQueue(queue);
if ((p->lchild == NULL) && (p->rchild == NULL))
{
printf("%c[%2d] : %s\n", p->ch, p->weight, p->code);
continue;
}
if (p->lchild)
{
strcpy(p->lchild->code, p->code);
strcat(p->lchild->code, "0");
EnQueue(queue, p->lchild);
}
if (p->rchild)
{
strcpy(p->rchild->code, p->code);
strcat(p->rchild->code, "1");
EnQueue(queue, p->rchild);
}
}
return;
}
int main(int argc, char *argv[])
{
char ch[] = {65,66,67,68,69,70};
int value[] = {10,20,30,40,50,60};
int i;
bitree *h, *p;
int j;
//for(j = 0; j ch = ch[i];
p->weight = value[i];
p->code[0] = '\0';
p->lchild = p->rchild = NULL;
InsertList(h, p);
}
VisitList(h);
CreateHaffmanTree(h);
puts("-------------------");
VisitList(h->next);
printf("h->next = %p\n",h->next);
NoOrder(h->next);
//printf("j = %d\n",j);
}
return 0;
}