Realloc 处理超出其范围的数据

Question

我的 C 代码出现了非常不寻常的行为。我正在实现一个最小和最大堆，如果达到堆容量，它们应该动态改变大小。问题是当我调用 realloc 来增加堆的元素数组时，它以下列方式运行（假设两个堆都处于最大容量）：

如果我只在其中一个堆中添加一个新元素，重新分配会完美无缺。
如果我在两个堆中添加一个新元素（一个接一个），第二个会完美地重新分配，但第一个的数据会被一些垃圾值和一些垃圾值损坏零。

请看下面的相关功能。（问题发生在主函数的第 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);
}

Answer 1

您的（否则相当整洁的）程序中有两个主要错误：

首先，您必须为 malloc 和 realloc 提供以字节为单位的大小，这意味着除非您分配 char 的数组，否则某处应该有一个 sizeof(T) .你在分配初始数组时这样做，但在重新分配时忘记了它。

其次，您使用从一开始的索引来访问数组。在 C 中，数组是从零开始的。这也适用于分配在堆上的数据。第一个索引是 0，最后一个有效索引是 heap->size - 1.

这意味着当你追加一个元素时，你使用当前大小作为插入索引然后增加大小。（当然你必须首先检查 tere 是否是 space，但是你这样做了。）所以：

// ... 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你的记忆在你用过它之后。

Realloc 处理超出其范围的数据

Realloc manipulating data out of its scope

c

pointers

realloc

data-structures