C：在空的堆中插入元素

我應該編寫一個代碼，它將stdin中的數字插入到第一個空的最大堆中。我的代碼沒有得到正確的元素順序，我發現它甚至不會在第三個數字前輸入while循環。有人願意幫忙嗎？提前致謝！C：在空的堆中插入元素

int heap_insert(heap* h, int key) { 

    if (h->size==MAX_HEAP_SIZE){ 
     return(-1); 
    } 

    h->size=h->size+1; 
    int i=h->size-1; 
    h->array[i]=key;     
    int parent=(i-1)/2; 

    while (i>1 && h->array[parent]< key) { 
     h->array[i]= h->array[parent]; 
     i = parent; 
     h->array[i]=key; 
    } 
return(0); 
}

來源

2016-01-21 Meowzen

請格式化/縮進您的代碼。有例如最後缺少'}。 – jofel

我已經縮進了......但實際上不止一個缺失的大括號。這個函數成功返回什麼？哪裏？ – kdopen

對不起，你修好了。它不會返回任何東西，它只是填充已在主函數中聲明的堆。 – Meowzen

它並不甚至第三個數字

這部分之前進入while循環可以回答。你的循環不會去，直到i等於或大於2 ...

while (i > 1 && h->array[parent]< key) { 
     ^^^^^

下面是設置i的代碼。

h->size = h->size+1; 
int i = h->size-1;

該代碼更易於理解，像這樣：

int i = h->size; 
h->size++;

第一次通過，i將是0（假設h->size被初始化爲0，則沒有表現出你的堆初始化代碼）。第二次將是1.第三次將是2，然後最後循環可以運行。

我猜你希望i >= 1在while循環中，所以它會繼續第二次調用。

至於爲什麼它不工作，首要的問題是你忘在循環改變parent。

/* i and parent initialized */ 
int i=h->size-1; 
... 
int parent=(i-1)/2; 

while (i>1 && h->array[parent]< key) { 
    h->array[i]= h->array[parent]; 

    /* i is changed, but where's parent? */ 
    i = parent; 

    h->array[i]=key; 
}

下面是它應該的樣子。我已將i更改爲僅用於循環索引的更多描述性new。

/* new and parent initialized */ 
int new = h->size; 
... 
int parent = (new-1)/2; 
while(new != 0 && h->array[parent] < key) { 
    h->array[new] = h->array[parent]; 
    h->array[parent] = key; 

    /* new AND parent changed */ 
    new = parent; 
    parent = (new-1)/2; 
}

下面是完整的代碼，加上我做了堆的大小動態的，因爲固定大小的結構是最好的避免了柺杖。

#include <stdio.h> 
#include <stdlib.h> 

typedef struct { 
    int size; 
    int max_size; 
    int *array; 
} heap; 

#define INIT_HEAP_SIZE 4 

static heap *heap_init() { 
    heap *h = calloc(1, sizeof(heap)); 

    h->max_size = INIT_HEAP_SIZE; 
    h->array = calloc(h->max_size, sizeof(int)); 

    return h; 
} 

static void heap_destroy(heap *h) { 
    free(h->array); 
    free(h); 
} 

static void heap_grow(heap *h) { 
    h->max_size *= 2; 
    h->array = realloc(h->array, h->max_size * sizeof(int)); 
} 

static void heap_insert(heap* h, int key) { 
    if (h->size >= h->max_size) { 
     heap_grow(h); 
    } 

    int new = h->size; 
    h->size++; 

    h->array[new] = key; 

    int parent = (new-1)/2; 
    while(new != 0 && h->array[parent] < key) { 
     h->array[new] = h->array[parent]; 
     h->array[parent] = key; 

     new = parent; 
     parent = (new-1)/2; 
    } 

    return; 
} 

int main(void) { 
    heap *h = heap_init(); 

    heap_insert(h, 23); 
    heap_insert(h, 11); 
    heap_insert(h, 42); 
    heap_insert(h, 5); 
    heap_insert(h, 99); 

    for(int i = 0; i < h->size; i++) { 
     printf("%d: %d\n", i, h->array[i]); 
    } 

    heap_destroy(h); 
}

來源

2016-01-21 18:34:45 Schwern

非常感謝！這比我需要的更多哈哈！但它現在的作品，真的很感謝你的努力:) – Meowzen

它不會因爲直到進入第3號的我是不大於1的第3號碼前輸入while循環。在第一個數字i = 0，然後1然後2.

對於循環，這裏是我的建議，解決問題：假設你輸入值3,5,7。一旦輸入5，你需要一個交換。 5應該成爲新的根，3應該是一個孩子。（所以maxheap屬性保留）然後，當輸入7時，另一個交換是按順序的。這次與5.7成爲根，3和5是孩子。這是什麼告訴你有關指數？如果我們插入10,16,1也會發生什麼？更多掉期？如果你正確地回答這些問題，while循環應該很容易解決。（提示：你需要從孩子開始不斷交換，並移動到下一個父，直到一切都按順序）

來源

2016-01-21 18:32:19 SenselessCoder

C：在空的堆中插入元素

回答

相關問題