Realloc манипулирует данными вне своей области - PullRequest
Новая
       8

Realloc манипулирует данными вне своей области

0 голосов
/ 28 марта 2019

Я испытываю очень необычное поведение в моем C-коде. Я реализую минимальную и максимальную кучу, которая должна динамически изменять размер, если достигнута куча. Проблема заключается в том, что когда я вызываю realloc для увеличения массива элементов кучи, он действует следующим образом (предположим, что обе кучи имеют максимальную емкость):

  1. Если я добавлю новый элемент только в одну из куч, перераспределение будет работать отлично.

  2. Если я добавлю новый элемент в обе кучи (одна за другой), второй будет идеально перераспределен, но данные первого будут испорчены некоторыми значениями мусора и некоторыми нулями.

См. Соответствующие функции ниже. (Проблема возникает с 8-й и 9-й строкой основной функции).

Я не понимаю, почему вызов функции insert в другой куче может изменить значения предыдущей.

Я не знаю, работает ли функция realloc или моя функция печати. Спасибо за помощь. 

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

#define leftChild(x) (x << 1)
#define rightChild(x) ((x << 1) + 1)
#define parent(x) (x >> 1)


typedef int T;

typedef struct {
    int size;
    int capacity;
    T *elements;
}   Heap;

void swap(Heap *heap, int a, int b) {
    T temp = heap->elements[a];
    heap->elements[a] = heap->elements[b];
    heap->elements[b] = temp;
}

Heap *newHeap(int capacity) {
    Heap *heap = malloc(sizeof(Heap));
    heap->capacity = capacity;
    heap->size = 0;
    heap->elements = malloc(sizeof(T) * (capacity + 1));
    return heap;
}

void increaseKey(Heap *heap, int i, T key) {
    heap->elements[i] = key;
    while (i > 1 && heap->elements[parent(i)] < heap->elements[i]) {
        swap(heap, parent(i), i);
        i = parent(i);
    }
}

void decreaseKey(Heap *heap, int i, T key) {
    heap->elements[i] = key;
    while (i > 1 && heap->elements[parent(i)] > heap->elements[i]) {
        swap(heap, parent(i), i);
        i = parent(i);
    }
}

void insert(Heap *heap, T key, bool isMinHeap) {
    if (heap->size >= heap->capacity) {
        heap->elements = realloc(heap->elements, heap->capacity * 2);
        heap->capacity = heap->capacity * 2;
    }
    heap->size++;
    heap->elements[heap->size] = 0;
    if (isMinHeap) decreaseKey(heap, heap->size, key);
    else increaseKey(heap, heap->size, key);
}

void printHeap(Heap *heap) {
    int i;
    printf("[");
    for (i = 1; i < heap->size; i++) {
        printf("%d,", heap->elements[i]);
    }
    if (heap->size != 0) {
        printf("%d", heap->elements[heap->size]);
    }
    printf("]\n");
}

int main(void) {
    Heap *minHeap = newHeap(5);
    Heap *maxHeap = newHeap(5);
    for (int i = 0; i < 5; i++) {
        insert(minHeap, i, true);
        insert(maxHeap, i, false);
    }
    printf("now start\n");
    insert(minHeap, 10, true);
    insert(maxHeap, 10, false);
    printHeap(minHeap);
    printHeap(maxHeap);
}

1 Ответ

2 голосов
/ 28 марта 2019

В вашей (в остальном довольно аккуратной) программе есть две основные ошибки:

Во-первых, вы должны предоставить размер в байтах для malloc и realloc, что означает, что где-то должно быть sizeof(T), если только вы не выделите массивы char. Вы делаете это при выделении исходного массива, но забываете его при перераспределении.

Во-вторых, вы используете индекс на основе одного для доступа к массиву. В C массивы начинаются с нуля. Это также относится к данным, размещенным в куче. Первый индекс 0, а последний действительный индекс heap->size - 1.

Это означает, что когда вы добавляете элемент, вы используете текущий размер в качестве индекса вставки, а затем увеличиваете размер. (Конечно, вы должны сначала проверить, есть ли пространство, но вы это делаете.) Итак: 

// ... allocate if necessary ...

heap->elements[heap->size] = 0;
if (isMinHeap) decreaseKey(heap, heap->size, key);
else increaseKey(heap, heap->size, key);

heap->size++;

Это обычный шаблон, который часто встречается при добавлении содержимого в массив: array[size++] = stuff;.

Наконец, вам, вероятно, придется обновить функции, которые определяют родителя и потомков: 

parent(n) == (n - 1) / 2;
left(n) == 2*n + 1;
right(n) == 2*n + 2;

Не забудьте free свою память после того, как вы ее использовали.

...