c语言哈夫曼树的问题
#include <stdio.h>
#include <stdlib.h>
#include "malloc.h"
typedef struct Node{
Node *left;
Node *right;//孩子节点
int grade;//权值,也就是成绩
int bol;//用来查看是否遍历过
}*HFtree;
//用来查找最小的两个节点
void find12(HFtree H,int k,int *s1,int *s2)
{int i,min1,min2;
min1=-1;
for(i=1;i<=k;i++)
{if(H[i].grade!=100 && H[i].bol==0 && min1==-1)
{min1=i;
continue;}
if(H[i].grade!=100 && H[i].bol==0)
{min2=i ;
break;}
}
for(i=min2;i<k;i++)
{
if(H[i].grade!=100 && H[i].bol==0)
{
if(H[i].grade<H[min1].grade )
{
min2=min1;
min1=i;
}
else if(H[i].grade<H[min2].grade)
{
min2=i;
}
}
}
*s1=min1;
*s2=min2;
}
//生成树
HFtree creatHF(HFtree *H,int *w,int n)
{int m;
m=2*n-1;
*H=(HFtree)malloc(m+1*sizeof(HFtree));
HFtree ARR=*H;
int i,j,s1,s2;
for(i=1;i<=n;i++)//叶子节点用于存储成绩
{ARR[i].grade=w[i-1];
ARR[i].left=NULL;
ARR[i].right=NULL;
ARR[i].bol=0;
}
for(i=n+1;i<=m;i++)//非叶子节点用于设置条件
{ARR[i].grade=100;
ARR[i].left=NULL;
ARR[i].right=NULL;
ARR[i].bol=0;
}
for(j=n+1;j<=m;j++)//按最小的两节点插法
{find12(*H,i-1,&s1,&s2);
if(j==n+1)
{(*H)[j].left=&ARR[s1];
(*H)[j].right=&ARR[s2];
ARR[s1].bol=1;
ARR[s2].bol=1;
}
if(j!=n+1)
{(*H)[j].left=&ARR[s1];
(*H)[j].right=&((*H)[j-1]);
ARR[s1].bol=1;
ARR[s2].bol=0;
}
}
for(i=1;i<=m;i++)
{
(*H)[i].bol=0;
}
i=1;
while((*H)[i].bol==0)
{printf("第%d位同学的成绩为:%d。 ",i,(*H)[i].grade);
(*H)[i].bol=1;
i++;
}
free(ARR);
return *H;
}
int main(int argc, char *argv[])
{int n=20;
int w[20]={7,48,51,60,71,15,5,78,8,75,47,97,45,53,23,67,58,5,95,81};
HFtree HF;
creatHF(&HF,w,n);
return 0;
}
全部代码如上
当我运行到这段代码
while((*H)[i].bol==0)
{printf("第%d位同学的成绩为:%d。 ",i,(*H)[i].grade);
(*H)[i].bol=1;
i++;
会报错
你的HFtree只是一个链表的指针,在creatHF中,你的*H=(HFtree)malloc(m+1*sizeof(HFtree));只申请了一个结构体,而却把它当成数组了HFtree ARR=*H;。明显的下标溢出了
你若是以链表作为数结构的,那么它的叶子每个都要重新申请内存的,或就用数组