Первое изменение присвоения массива

Question

Я хочу создать двоичную кучу с настраиваемым элементом, а куча использует массив struct Elem для хранения данных. Но после вставки некоторые данные теряются, в этом случае значение key.

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

#define DEFAULT_CAPACITY 16 
#define VALS 10 

const int values[VALS] = {1, 2, 3, 4, 7, 8, 9, 10, 14, 16}; 

typedef int (*compareFunction)(const void *, const void *); 

typedef struct Elem { 
    void *key; 
    void *value; 
} Elem; 

typedef struct Heap { 
    unsigned int size; 
    unsigned int capacity; 
    Elem   **array; 
    compareFunction compare; 
} Heap; 

Heap *hpCreate(compareFunction compare) 
{ 
    Heap *heap; 

    heap = (struct Heap *) malloc(sizeof(struct Heap)); 
    if (heap == NULL) return NULL; 

    if ((heap->array = (struct Elem **) malloc(0)) == NULL) { 
     free(heap); 
     return NULL; 
    } 

    heap->size = 0; 
    heap->capacity = DEFAULT_CAPACITY; 
    heap->compare = compare; 

    return heap; 
} 

Elem *hpCreateElem(void *key, void *value) 
{ 
    Elem *el; 

    el = (struct Elem *) malloc(sizeof(struct Elem)); 
    if (el == NULL) return NULL; 

    el->key = key; 
    el->value = value; 

    return el; 
} 

void hpInsert(Heap *hp, void *key, void *value) 
{ 
    Elem *el, *par; 
    int pos; 

    pos = hp->size++; 
    el = hpCreateElem(key, value); 
    par = hp->array[pos/2]; 

    while (pos > 1 && hp->compare(el->key, par->key) > 0) { 
     hp->array[pos] = hp->array[pos/2]; 
     pos = pos/2; 
     par = hp->array[pos/2]; 
    } 

    hp->array[pos] = el; 
} 

int compare_int_ptr(const void *ptr1, const void *ptr2) 
{ 
    int v1 = *((int *) ptr1); 
    int v2 = *((int *) ptr2); 

    if (v1 == v2) 
     return 0; 
    else 
     return (v1 > v2) ? 1 : -1; 
} 

int main() 
{ 
    Heap *hp; 
    Elem *el; 
    int i; 

    hp = hpCreate(compare_int_ptr); 

    for (i = 0; i < VALS; i++) { 
     hpInsert(hp, (void *) &values[i], (void *) &values[i]); 
    } 

    for (i = 0; i < VALS; i++) { 
     el = hp->array[i]; 
     printf("%d\n", *((int *) el->key)); 
    } 

    return 0; 
} 

выход производства является

4196700 
16 
14 
9 
10 
4 
3 
8 
17231984 
7 

вместо двоичного массива кучи правильно заказана как 16 9 14 7 4 8 10 3 2 1

Answer 1

Поскольку вы рассказываете вами контейнер выделенные элементы DEFAULT_CAPACITY:

heap->capacity = DEFAULT_CAPACITY; 

затем:

malloc(0) 

должно быть

malloc(DEFAULT_CAPACITY * sizeof(Elem*)) 

---

Линия:

par = hp->array[pos/2]; 

читает неинициализированный объект.