使用陣列創建堆時出錯

我試圖在C中使用數組創建Binary Min Heap。我編寫了代碼並多次嘗試用「筆和紙」來執行它，它似乎工作。你能幫我理解爲什麼它會失敗嗎？使用陣列創建堆時出錯

這裏是庫代碼：

#include <stdlib.h> 

void swapInt(int *a, int *b) { 
    int aux = *a; 
    *a = *b; 
    *b = aux; 
} 

typedef struct intHeapArray { 
    int *array; 
    int size; 
} IntHeapArray; 

IntHeapArray newIntHeapArray (int dim) { 
    IntHeapArray new; 
    new.array = (int*) malloc(sizeof(int)*dim); 
    new.size = 0; 
    return new; 
} 

int findFather (int index) { 
    return (index - 1)/2; 
} 

int findLeftChild (int index) { 
    return index * 2 + 1; 
} 

int findRightChild (int index) { 
    return index * 2 + 2; 
} 

int minFatherChilds (IntHeapArray h, int index) { 
    int leftchild = findLeftChild(index); 
    int rightchild = findRightChild(index); 
    if (rightchild >= h.size) 
     rightchild = leftchild; 
    if (h.array[index] > h.array[leftchild]) 
     index = leftchild; 
    if (h.array[index] > h.array[rightchild]) 
     index = rightchild; 
    return index; 
} 

void reorganizeIntHeapArray (IntHeapArray *h, int index) { 
    int father, leftchild, child; 
    father = findFather(index); 
    while (index > 0 && h->array[index] < h->array[father]) { 
     swapInt(&h->array[index], &h->array[father]); 
     index = father; 
    } 
    leftchild = findLeftChild(index); 
    while (leftchild < h->size && index != minFatherChilds(*h, index)) { 
     child = minFatherChilds(*h, index); 
     swapInt(&h->array[index], &h->array[child]); 
     index = child; 
    } 
} 

void enqueueIntHeapArray (IntHeapArray *h, int val) { 
    h->array[h->size] = val; 
    h->size++; 
    reorganizeIntHeapArray(h, h->size - 1); 
}

下面是從主腳本調用：

#include <stdio.h> 
#include "heap.h" 

void printIntArray (int *a, int dim) { 
    int i; 
    printf("["); 
    for (i = 0; i < dim - 1; i++) 
     printf("%d, ", a[i]); 
    printf("%d]\n", a[dim-1]); 
} 

int main() { 
    IntHeapArray h; 
    int n, i, val; 

    printf("How many value would you like to add to the heap? "); 
    scanf("%d", &n); 

    h = newIntHeapArray(n); 

    printf("Insert values:\n"); 
    for (i = 0; i < n; i++) { 
     scanf("%d", &val); 
     enqueueIntHeapArray(&h, val); 
    } 

    printf("This is your heap:\n"); 
    printIntArray(h.array, h.size); 

    return 0; 
}

代碼編譯。試試這個輸入：6 3 8 9 2 0。它會打印：[3, 2, 0, 9, 6, 8]這顯然是錯誤的。但我真的不明白我錯在哪裏。

來源

2012-06-09 Zagorax

要求陌生人通過檢查發現代碼中的錯誤並不富有成效。您應該使用調試器來逐步執行您的程序，並確定其行爲與您期望的不同之處。 –

你認爲應該打印什麼？你爲什麼不在問題中這麼說？準確地說，這是個好主意。 –

我沒有寫出它應該打印的內容，因爲我鏈接了關於Binary Min Heap的頁面。輸出應該是：[0，3，2，9，6，8]。這是根據「筆和紙」執行（我希望它是正確的）。當然，我應該有0作爲第一個值。最低值必須是該數據結構中的第一個值。 – Zagorax

我發現了錯誤。重新組織堆函數必須改爲：

void reorganizeIntHeapArray (IntHeapArray *h, int index) { 
    int father, leftchild, child; 
    father = findFather(index); 
    while (index > 0 && h->array[index] < h->array[father]) { 
     swapInt(&h->array[index], &h->array[father]); 
     index = father; 
     father = findFather(index); 
    } 
    leftchild = findLeftChild(index); 
    while (leftchild < h->size && index != minFatherChilds(*h, index)) { 
     child = minFatherChilds(*h, index); 
     swapInt(&h->array[index], &h->array[child]); 
     index = child; 
     leftchild = findLeftChild(index); 
    } 
}

我只更新索引值，而不是父親的。所以在第一次切換之後，它將h-> array [index]與自己進行比較，而不是與其新的父親進行比較。

編輯：它仍然是錯的。我在第二次做了同樣的錯誤，我在第一次做了。我沒有更新左值。現在應該是正確的。

來源

2012-06-10 13:44:18 Zagorax

非常好，感謝您的反饋！ – sarnold

使用陣列創建堆時出錯

回答

相關問題