2011-02-17 69 views
0

我陷入heapSort。我有一些代碼,但我認爲它很不對,因爲我很難編譯它。有什麼建議麼?堆排序應該相當容易實現,但我有一堆的語法錯誤。這裏是我的代碼:試圖執行HeapSort

/* Framework for Heap Sort 
* CS333 Spring 2011 
* 
*/ 
#include <stdio.h> 
#define MAX_SIZE 1000000 
int data[MAX_SIZE]; 
int n; 
int j; 

int parent(int j) { 
if(j==1) 
    return 0; 

if(j%2==0) 
    return ((j/2)-1); 
else 
    return ((j/2)); 
} 

int left(int j) { 
    return (2 * j) + 1; 
} 

int right(int j) { 
    return (2 * j) + 2; 
} 

void heapify(int data[], int j) { 
    int l = left(j), great; 
    int r = right(j); 
    if ((data[l] > data[j]) && (l < sizeof(data))) { 
    great = l; 
    } 
    else { 
    great = j; 
    } 
    if ((data[r] > data[great]) && (r < sizeof(data))) { 
    great = r; 
    } 
    if (great != j) { 
    int temp = data[j]; 
    data[j] = data[great]; 
    data[great] = temp; 
    heapify(data, great); 
    } 
} 

int BuildMaxHeap(int data[]) { 
    for (int j = (sizeof(data) - 1)/2; j >= 0; j--) { 
    heapify(data, j); 
    return data; 
    } 
} 

void HeapSort(int data[]) { 
    BuildMaxHeap(data); 
    for (int j = sizeof(data); j > 0; j--) { 
    int temp = data[0]; 
    data[0] = data[data.sizeof() - 1]; 
    data[sizeof(data) - 1] = temp; 
    sizeof(data) = sizeof(data) - 1; 
    heapify(data, 0); 
    } 

} 

int main() 
{ 
    int i; 

    /* Read in the data */ 
    n = 0; 
    while (scanf("%d", &data[n]) == 1) 
    ++n; 
    /* Sort the numbers low to high */ 

    HeapSort(data); 

    /* Print out the data */ 
    for (i = 0; i < n; ++i) 
    printf("%d", data[i]); 
} 
+1

你的錯誤是什麼? – qwertymk 2011-02-17 03:54:24

+0

全局變量`j`不需要;在函數中使用`j`的地方,都有一個局部變量。全局變量`n`不需要;它應該在`main()`中是本地的,並傳遞給需要知道要排序的元素數目的其他函數。對一百萬個整數進行排序是一件有意義的事情 - 儘管一旦你的代碼有效,它可以處理一百萬和一千個(給予或花費額外的時間)。 – 2011-02-17 05:20:52

回答

2

你的大部分問題似乎是在堆排序例行:

void HeapSort(int data[]) { 
    BuildMaxHeap(data); 
    for (int j = sizeof(data); j > 0; j--) { 

當你傳遞一個數組這樣的功能,有什麼功能接收實際上是一個指針。在指針上使用sizeof而不是告訴你指針指向的數據大小 - 它只會告訴你指針本身佔用了多少字節(通常爲4)。你可能想通過數組的大小作爲一個參數:

void HeapSort(int *data, size_t data_size) { 

和整個例程的其餘部分,你會參考data_size,不sizeof(data)

int temp = data[0]; 
data[0] = data[data.sizeof() - 1]; 
data[sizeof(data) - 1] = temp; 
sizeof(data) = sizeof(data) - 1; 

sizeof(whatever)也基本上是恆定的,而不是一個變量;你不能用它作爲任務的目標(但是,如上面建議的那樣,使用data_size將讓讓你做任務)。