哈夫曼树建树的过程访问不了PQueue中的size
第一张图片是创建了优先级队列之后单步调试建树运行到第二次到进入Padd的时候，也就是把第二个结点插入到队列的时候出现问题
然后调试出错
以下是建树和优先级队列的代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _HTreeNode
{
char symbol;
struct _HTreeNode *left,*right;
}HTreeNode;
typedef struct _PQueueNode
{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _HTreeNode
{
char symbol;
struct _HTreeNode *left,*right;
}HTreeNode;
typedef struct _PQueueNode
{
unsigned int pir;
HTreeNode *val;
struct _PQueueNode *next;
}PQueueNode; //创造优先级队列的每一个节点含有的内容
typedef struct PQueue
{
PQueueNode *first;
unsigned int size;
}PQueue ;//优先级队列
//按照优先级大小从小到大插入结点
int Padd(PQueue **pq,HTreeNode *hn,int pir) //插入节点
{
PQueueNode *pqn=(PQueueNode *)malloc(sizeof(PQueueNode));
pqn->pir=pir;
pqn->next=NULL;
pqn->val=hn;
if((*pq)->first==NULL && (*pq)->size==0) //第一个数
{
(*pq)->first=pqn;
(*pq)->size++;
printf("%c,%d\n",hn->symbol,pir);
return 1;
}
else
{
if((*pq)->first->pir >= pir) //传入的优先级是否比第一个数小
{
pqn->next=(*pq)->first;
(*pq)->first=pqn;
(*pq)->size++;
printf("%c,%d\n",hn->symbol,pir);
return 1;
}
else //传入的优先级大于第一个数，需要逐个遍历，插入到大于it，小于it->next
{
PQueueNode *it=(*pq)->first;
while(it->next != NULL) //需要it->next不为空，因为要取it和it->next进行比较，所以it->next不能为空
{
if(it->next->pir >= pir)
{
it->next=pqn->next;
it->next=pqn;
(*pq)->size++;
printf("%c,%d\n",hn->symbol,pir);
return 1;
}
it=it->next;
}
if(it->next== NULL)
{
it->next=pqn;
(*pq)->size++;
printf("%c,%d\n",hn->symbol,pir);
return 1;
}
}
return 0;
}
}
HTreeNode *GetNode(PQueue **pq)
{
HTreeNode *p=(HTreeNode *)malloc(sizeof(HTreeNode));
if((*pq)->size>0)
{
p=(*pq)->first->val;
(*pq)->size--;
(*pq)->first=(*pq)->first->next; //不用释放，直接指向下一个结点。
}
else
printf("empty\n");
return p;
}
HTreeNode* CreateTree(char *inputstring)
{
//以下为获得优先级，weight为优先级权值
int *weight=(int *)malloc(sizeof(int)*256);
for(int i=0;i<256;i++)
{
weight=0;
}
for (int i=0; i < strlen(inputstring); i++)
{
weight[(unsigned int)inputstring]++;
}
//以下为创建优先级队列
PQueue *pq=(PQueue *)malloc(sizeof(PQueue));
pq->first=NULL;
pq->size=0;
int com;
for(int i=0;i<256;i++)
{
if(weight!=0)
{
HTreeNode *hn=(HTreeNode *)malloc(sizeof(HTreeNode));
hn->symbol=(char)i;
hn->left=NULL;
hn->right=NULL;
com=Padd(&pq,hn,weight);
//printf("%d",com);
}//beep boop beer!e4,b3,o2,p2, 2,r1,!1
}
free(weight);
//以下为创建树
int newpir;
while(pq->size != 1)
{
newpir=pq->first->pir + pq->first->next->pir;
HTreeNode *p1=GetNode(&pq);
HTreeNode *p2=GetNode(&pq);
HTreeNode *newh=(HTreeNode *)malloc(sizeof(HTreeNode));
newh->left=p1;
newh->right=p2;
Padd(&pq,newh,newpir);
}
HTreeNode *root=(HTreeNode *)malloc(sizeof(HTreeNode));
root=GetNode(&pq);
return root;
}
void TestTraverse(HTreeNode *root)//尝试遍历树
{
printf("%c",root->symbol);
TestTraverse(root->left);
TestTraverse(root->right);
}
int main()
{
HTreeNode *tree;
tree=CreateTree("beep boop beer!");
TestTraverse(tree);
}
顶
页:
[1]