0

我遇到的问题是 buildHeap 和 buildMinHeap 中的那个。以前，那些根本没有触发，这就是为什么我知道打印部分应该或多或少地工作，因为它正确打印了节点，如果使用未排序的数组。

目前我假设我在那里有一个无限循环，因为程序在显示我输入的一些调试消息后崩溃。我对可能出现的问题没有任何想法。有任何想法吗？

#include <stdio.h>

#define ARRAY_SIZE 10

int parent(int i) {
    return i/2;
}

int left(int i) {
    return 2*i;
}

int right(int i) {
    return 2*i+1;
}

void heapify(int A[], int i, int s) {
    int m = i;
    int temp;
    int l = left(i);
    int r = right(i);

    if (l <= s && A[l] > A[m]) m = l;
    if (r <= s && A[r] > A[m]) m = r;
    if (i != m) {
        temp = A[i];
        A[i] = A[m];
        A[m] = temp;
        heapify(A, m, s);
    }
    printf("heapify done\n");

}

void buildHeap(int A[]) {
    int i;

    for (i = ARRAY_SIZE / 2; i > 0; i--) {
        heapify(A, i, ARRAY_SIZE);
    }
    printf("buildHeap done\n");
}

// this still creates a normal heap, not a min heap afaik
void buildMinHeap(int A[]) {
    int s = ARRAY_SIZE - 1;
    int i;
    int temp;

    buildHeap(A);

    for (i = ARRAY_SIZE; i > 1; i--) {
        temp = A[i];
        A[i] = A[1];
        A[1] = temp;
        s = s-1;
        heapify(A, 1, s);
    }
}

void printHeap(int A[]) {
    int i;

    printf("graph g {\n");

    for (i = 0; i < ARRAY_SIZE; i++) {
        printf("%d -- %d\n", parent(i), A[i]);
    }

    printf(" }\n");

    //temp debug code
    printf("[ ");
    i = 0;
    for (i = 0; i < ARRAY_SIZE; i++) {
    printf("%d", A[i]);
    if (i < ARRAY_SIZE - 1) printf(", ");
    }
    printf(" ]\n");
}

int main() {
    int array[ARRAY_SIZE] = {4, 3, 2, 5, 6, 7, 8, 9, 12, 1};

    buildMinHeap(array);
    printHeap(array);
}

编辑：哦，还有，我还是个学生，所以还不太精通C。只是为了提供一些背景。

4

1 回答 1

0

在 C 中，数组使用从零开始的索引。即具有十个元素的数组将具有元素索引 0 到 9。

看起来您假设数组元素将从1to索引ARRAY_SIZE，而实际上它们被索引0到ARRAY_SIZE - 1。

尝试一个非常简单的main函数，它只输出数组的内容，然后再尝试对其进行任何操作：

#include <stdio.h>

#define ARRAY_SIZE    10

int main(void)
{
    int index;
    int array[ARRAY_SIZE] = {4, 3, 2, 5, 6, 7, 8, 9, 12, 1};

    for(index = ARRAY_SIZE - 1; index >= 0; index--)
    {
        printf("myArray[%d] == %d\n",index,myArray[index]);
    }
    return 0;
}

你甚至可以添加一些辅助常量：

#define ARRAY_FIRST    0
#define ARRAY_LAST     (ARRAY_SIZE -1)
于 2015-03-30T18:01:25.020 回答