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：在空的堆中插入元素

回答

相关问题