问题遇到的现象和发生背景
是一个关于哈夫曼编码的问题，我用的堆维护但是第一个测试点一直显示超时或者段错误，找不到原因啊，求帮改
用代码块功能插入代码，请勿粘贴截图
#include<malloc.h>
#include<cstdio>
#include<string.h>
using namespace std;
typedef struct Node *node;
typedef struct MINHeap *minheap;
struct Node
{
int data;
int time;//次数
int number;//节点个数
int order;//生成次序
struct Node *left;
struct Node *right;
};
struct MINHeap
{
int size;
struct Node p[27];
};
int time[26];//出现次数数组
int rank[30];//生成次序数组
int flag[26];//访问标记数组
int bit;//保存一共多少位
char answer[40][500];//答案数组
char tmp[29];//临时工作数组
char translate[10000];//翻译数组
int trans;//翻译数组下标
void Build(minheap h);//建立堆
struct Node pop(const minheap h);//抛出
void insert(minheap h,struct Node t3);//插入堆
void percdown(minheap h,int i);//调整堆
void forward(node,int num,char id);//获得答案
int main(void)
{
for(int i=0;i<26;i++) time[i]=0; //初始化次数数组为0
for(int i=1;i<=29;i++) rank[i]=1;//初始化次序数组为1
for(int i=0;i<26;i++) flag[i]=0;//初始化标记数组
char work[10000];
char t1[10000];
char t2[10000];
minheap h=(minheap)malloc(sizeof(struct MINHeap));
h->size=0;
h->p[0].time=-1;
for(int i=0;i<27;i++)
{
h->p[i].left=NULL;
h->p[i].right=NULL;
}
bit=0;
scanf("%s %s %s",work,t1,t2);
//计算次数
int i;
for(i=0;work[i]!='\0';i++)
{
int letter=work[i]-97;
time[letter]++;
}
//插入堆
for(i=0;work[i]!='\0';i++)
{
int letter=work[i]-97;
if(flag[letter]==0)
{
flag[letter]=1;
h->size++;
int now=h->size;
h->p[now].data=work[i];
h->p[now].order=rank[time[letter]];
h->p[now].number=1;
h->p[now].time=time[letter];
h->p[now].left=h->p[now].right=NULL;
rank[time[letter]]++;
}
}
//调整堆
Build(h);
//保存调整后的初始堆后序输出用
//开始操作
while(h->size!=1)
{
struct Node *t1=(node)malloc(sizeof(struct Node));
struct Node *t2=(node)malloc(sizeof(struct Node));
*t1=pop(h);
*t2=pop(h);
struct Node t3;
t3.left=t1;
t3.right=t2;
t3.time=t1->time+t2->time;
t3.number=t1->number+t2->number;
t3.data=-1;
t3.order=rank[t3.time];
rank[t3.number]++;
insert(h,t3);
}
struct Node *huff=(node)malloc(sizeof(struct Node));
*huff=h->p[1];
//编码
forward(huff,0,'0');
//输出
int length=strlen(work);
printf("%d ", length);
if(bit%8==0) printf("%d\n",bit/8);
else printf("%d\n",bit/8+1);
while(out->size!=0)
{
struct Node p=pop(out);
printf("%c:",p.data);
int letter=p.data-97;
for(int i=1;answer[letter][i]!='\0';i++) printf("%c",answer[letter][i]);
printf("\n");
}
//翻译
trans=0;
node root=huff;
int len1=strlen(t1);
for(int i=0;i<len1;i++)
{
if(t1[i]=='0') root=root->left;
else if(t1[i]=='1') root=root->right;
if(root->left==NULL&&root->right==NULL)
{
translate[trans++]=root->data;
root=huff;
}
}
translate[trans]='\0';
if(root!=huff) printf("INVALID\n");
else
{
for(int i=0;translate[i]!='\0';i++) printf("%c",translate[i]);
printf("\n");
}
trans=0;
root=huff;
int len2=strlen(t2);
for(int i=0;i<len2;i++)
{
if(t2[i]=='0') root=root->left;
else if(t2[i]=='1') root=root->right;
if(root->left==NULL&&root->right==NULL)
{
translate[trans++]=root->data;
root=huff;
}
}
translate[trans]='\0';
if(root!=huff) printf("INVALID\n");
else
{
for(int i=0;translate[i]!='\0';i++) printf("%c",translate[i]);
printf("\n");
}
}
void Build(minheap h)
{
int i;
for(i=h->size/2;i>0;i--) percdown(h,i);
}
//调整堆
void percdown(const minheap h,int i)
{
struct Node x=h->p[i];
int parent,child;
for(parent=i;parent*2<=h->size;parent=child)
{
child=parent*2;
if(child!=h->size&&h->p[child+1].time<h->p[child].time) child++;
else if(child!=h->size&&h->p[child+1].time==h->p[child].time&&h->p[child+1].number<h->p[child].number) child++;
else if(child!=h->size&&h->p[child+1].time==h->p[child].time&&h->p[child+1].number==h->p[child].number&&h->p[child+1].order<h->p[child].order)child++;
if(x.time<h->p[child].time) break;
else if(x.time==h->p[child].time&&x.number<h->p[child].number) break;
else if(x.time==h->p[child].time&&x.number==h->p[child].number&&x.order<h->p[child].order) break;
else h->p[parent]=h->p[child];
}
h->p[parent]=x;
}
//抛出元素
struct Node pop(const minheap h)
{
struct Node min;
int tmp=h->p[1].data;
min=h->p[1];
int last=h->size;
struct Node x=h->p[last];
h->size--;
int parent,child;
//调整堆
for(parent=1;parent*2<=h->size;parent=child)
{
child=parent*2;
if(child!=h->size&&h->p[child+1].time<h->p[child].time) child++;
else if(child!=h->size&&h->p[child+1].time==h->p[child].time&&h->p[child+1].number<h->p[child].number) child++;
else if(child!=h->size&&h->p[child+1].time==h->p[child].time&&h->p[child+1].number==h->p[child].number&&h->p[child+1].order<h->p[child].order)child++;
if(x.time<h->p[child].time) break;
else if(x.time==h->p[child].time&&x.number<h->p[child].number) break;
else if(x.time==h->p[child].time&&x.number==h->p[child].number&&x.order<h->p[child].order) break;
h->p[parent]=h->p[child];
parent=child;
}
h->p[parent]=x;
return min;
}
//插入
void insert(minheap h,struct Node t3)
{
h->size++;
int i=h->size;
for(;h->p[i/2].time>t3.time;i/=2)
{
h->p[i]=h->p[i/2];
}
if(h->p[i/2].time==t3.time)
{
while(h->p[i/2].time==t3.time&&h->p[i/2].number>t3.number)
{
h->p[i]=h->p[i/2];
i/=2;
}
}
if(h->p[i/2].time==t3.time&&h->p[i/2].number==h->p[i].number)
{
while(h->p[i/2].time==t3.time&&h->p[i/2].number==h->p[i].number&&h->p[i/2].order>h->p[i].order)
{
h->p[i]=h->p[i/2];
i/=2;
}
}
h->p[i]=t3;
}
void forward(node t,int num,char id)
{
if(num>0) tmp[num]=id;
if(t->left!=NULL) forward(t->left,num+1,'0');
if(t->right!=NULL) forward(t->right,num+1,'1');
//若为叶子节点
if(t->left==NULL&&t->right==NULL)
{
int letter=t->data-97;
int i;
for(i=1;i<=num;i++)
{
answer[letter][i]=tmp[i];
}
answer[letter][num+1]='\0';
bit+=num*time[letter];
}
}
