优先队列实现huffman，有指针错误，求纠正
程序代码：/*
*优先队列实现哈夫曼树:哈夫曼树外部结点的个数为m,内部结点为m-1，所以总结点树为2m-1
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX_PQ_SIZE 100
#define MAX_NUM 6
/*Haffuman tree data type define*/
struct HtNode /*哈夫曼树结点的结构*/
{
int ww; /*以该结点为根的子树中所有外部结点的加权和*/
int parent,llink,rlink;
};
struct HtTree /*哈夫曼树结构*/
{
int m; /*外部结点的个数*/
int root; /*哈夫曼树根在数组中的下标*/
struct HtNode *ht; /*存放2*m-1个结点的数组*/
};
typedef struct HtTree *PHtTree;
typedef struct HtNode* element_type;
/*Priority tree datatype define*/
struct heap_struct
{
/*Maximum # that can fit in the heap*/
unsigned int max_heap_size;
/*Crurrent # of elements in the head*/
unsigned int size;
element_type *elements;
};
typedef struct heap_struct*PRIORITY_QUEUE;
PRIORITY_QUEUE create_pq(unsigned int max_elements)
{
PRIORITY_QUEUE H;
if(max_elements>MAX_PQ_SIZE)
{
printf("Priority queue size is too large\n");
return NULL;
}
H=(PRIORITY_QUEUE)malloc(sizeof(struct heap_struct));
if(NULL==H)
{
printf("Out of space!\n");
return NULL;
}
/*Allocate the array + one extra for sentinel*/
H->elements=(element_type*)malloc((max_elements+1)*sizeof(element_type));
if(NULL==H->elements)
{
printf("Out of space!\n");
free(H);
return NULL;
}
H->max_heap_size=max_elements;
H->size=0;
H->elements[0]=NULL;
return H;
}
bool isEmptyPriorityQueue(PRIORITY_QUEUE H)
{
return H->size==0;
}
/*H->elements[0] is a sentinel*/
void enQueue(element_type x,PRIORITY_QUEUE H)
{
unsigned int i;
if(H->size==H->max_heap_size)
printf("Priority queue is full\n");
else
{
i=++H->size; /*the position of new element*/
while((i/2)!=0)/*compare with the value of the parent node*/
{
if((*(H->elements[i/2])).ww>(*x).ww)/*通过间接访问运算与父结点的值进行比较*/
{
H->elements[i]=H->elements[i/2];/*swap down*/
i=i/2;
}
else
break;
H->elements[0]=x; /*the final position*/
}
}
}
element_type deQueue(PRIORITY_QUEUE H)
{
unsigned int i,child;
element_type min_element,last_element;
if(0==H->size)
{
printf("Priority queue if empty\n");
return H->elements[0];
}
min_element=H->elements[1];
last_element=H->elements[H->size--];
for(i=1;i*2<=H->size;i=child)
{
/*find smaller child*/
child=i*2;
if((child!=H->size)&&((*H->elements[child+1]).ww<(*H->elements[child]).ww))
child++;
/*percolate one level*/
if((*last_element).ww>(*H->elements[child]).ww)
H->elements[i]=H->elements[child];/*child move up*/
else
break;/*is the smallest*/
}
H->elements[i]=last_element;/*set here*/
return min_element;
}
element_type topPriorityQueue(PRIORITY_QUEUE H)
{
if(isEmptyPriorityQueue(H))
{
printf("Priority queue is empty!\n");
return H->elements[0];
}
else
return H->elements[1];
}
PHtTree huffman(int m,int *w)/*构造具有m个外部结点的哈夫曼树*/
{
PHtTree pht;/*declare a pointer to Huffman tree*/
PRIORITY_QUEUE pq;/*declare a pointer to priority queue*/
int i,m1,m2;
struct HtNode x1,x2;/*two pointer of HtNode*/
pht=(PHtTree)malloc(sizeof(struct HtTree));
if(NULL==pht)
{
printf("Out of space!\n");
return pht;
}
pht->ht=(struct HtNode*)malloc(sizeof(struct HtNode)*(2*m-1));
if(NULL==pht)
{
printf("Out of space!\n");
return pht;
}
for(i=0;i<2*m-1;i++)/*the array(ht) initializtion*/
{
pht->ht[i].llink=-1;
pht->ht[i].rlink=-1;
pht->ht[i].parent=-1;
if(i<m)
pht->ht[i].ww=w[i];
else
pht->ht[i].ww=-1;
}
pq=create_pq(MAX_NUM);/*分配优先队列空间 */
for(i=0;i<m;i++)
{
enQueue(pht->ht+i,pq);/*注意：是将结点的地址加入优先队列*/
}
for(i=0;i<m-1;i++)/*需要构造m-1个内部结点*/
{
x1=NULL;
x2=NULL;
x1=topPriorityQueue(pq);/* 从优先队列里找两个最小权的无父结点的结点,存放在x1,x2中 */
x2=topPriorityQueue(pq);
pht->x1->parent=m+i;/*填入指向父节点的下标信息*/
pht->x2->parent=m+i;
pht->ht[m+i].ww=m1+m2; /*填入父节点的权重*/
pht->ht[m+i].llink=x1;/*填入父节点的左右儿子字段信息*/
pht->ht[m+i].rlink=x2;
enQueue(pht->ht+m+i.pq);/*将新构造的节点的地址插入优先队列*/
}
pht->root=2*m-2;/*指向根节点*/
for(i=2*m-2;i>=0;i--)/*print Huffman tree*/
printf("No.%2d,value =%3d,lLink =%2d,rLink =%2d,parent =%2d\n",i,pht->ht[i].ww,pht->ht[i].llink,pht->ht[i].rlink,pht->ht[i].parent);
return pht;
}
int main()
{
int weight[MAX_NUM]={12,3,56,7,8,32};
huffman(MAX_NUM,weight);
return 0;
}
