C语言有关堆中的路径问题

Question

将一系列给定数字依次插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。
输入格式:
每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
输出格式:
对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。
输入样例:
5 3
46 23 26 24 10
5 4 3
输出样例:
24 23 10
46 23 10
26 10

#include <stdio.h>
#include <stdlib.h>
#define Mindata -10001
typedef struct HNode *Head;
struct HNode{
    int *Data;
    int Size;
    int Maxsize;
};
typedef Head MinHead;
MinHead Creat(int Max);
void Insert(MinHead H,int X);
int main(void){
    int n,m,x,j,k,p;
    scanf("%d %d",&n,&m);
    MinHead H=Creat(n);
    for(k=0;k<n;k++){
        scanf("%d",&x);
        Insert(H,x);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&p);
        printf("%d",H->Data[p]);
        for(j=p;p>1;j/=2){
            printf(" %d",H->Data[p]);
        }
    }
    return 0;
}
MinHead Creat(int Max){
    MinHead H=(MinHead)malloc(sizeof(struct HNode));
    H->Data=(int *)malloc((Max+1)*sizeof(int));
    H->Size=0;
    H->Maxsize=Max;
    H->Data[0]=Mindata;
    return H;
}
void Insert(MinHead H,int x){
    int i;
    for(i=++H->Data;H->Data[i/2]>x;i/=2){
        H->Data[i]=H->Data[i/2];
    }
    H->Data[i]=x;
}

能帮忙看看这段代码有什么错误吗？要怎么改呢？一直一直段错误来着。

Answer 1

基于Monster 组和GPT的调写：

这段代码有几个错误：

• int i; 这里应该将 i 初始化为 H->Size+1，因为堆从下标 1 开始存储，而 H->Size 表示已经存储了多少个元素，下一个元素应该存储在下标 H->Size+1。
• 在 Insert 函数中，循环条件应该是 H->Data[i/2] > x 而不是 H->Data[i/2] > x, i >= 1。因为当插入元素到根结点的时候，i/2=0，不满足 i >= 1 的条件，会退出循环，导致元素无法插入堆中。
• 在 Insert 函数中，循环退出后应该将新插入元素赋值给 H->Data[i]，而不是 H->Data[H->Size]。因为前者是新插入元素的正确位置，后者是存储最后一个元素的位置。
• 在循环输出路径时，for(j=p;p>1;j/=2) 应该是 for(j=p; j>1; j/=2)，这样才能正确地遍历从 H[p] 到根结点的路径。

下面是修改后的代码：

#include <stdio.h>
#include <stdlib.h>
#define Mindata -10001

typedef struct HNode *Head;

struct HNode {
    int *Data;
    int Size;
    int Maxsize;
};

typedef Head MinHead;

MinHead Creat(int Max);
void Insert(MinHead H,int X);

int main(void) {
    int n,m,x,j,k,p;
    scanf("%d %d",&n,&m);
    MinHead H=Creat(n);
    for(k=0;k<n;k++){
        scanf("%d",&x);
        Insert(H,x);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&p);
        printf("%d",H->Data[p]);
        for(j=p;j>1;j/=2){
            printf(" %d",H->Data[j/2]);
        }
        printf("\n");
    }
    return 0;
}

MinHead Creat(int Max){
    MinHead H=(MinHead)malloc(sizeof(struct HNode));
    H->Data=(int *)malloc((Max+1)*sizeof(int));
    H->Size=0;
    H->Maxsize=Max;
    H->Data[0]=Mindata;
    return H;
}

void Insert(MinHead H,int x){
    int i;
    for(i=++H->Size; H->Data[i/2] > x; i/=2){
        H->Data[i] = H->Data[i/2];
    }
    H->Data[i] = x;
}