C上的内存分配错误

Question

我正在尝试将一组数字从它们的中间值拆分为 2 个不同的堆。我使用堆数据结构来做到这一点。即本例中的输入为 10。显然我在分配内存时犯了一些错误，当我尝试动态分配时它给出了以下输出：

[ 4 3 2 0 1 ]

[ 0 0 0 0 0 ]

为什么第二堆总是0？

因为如果我取消注释静态内存分配并改为使用它，它会给出真实的输出：

[ 4 3 2 0 1 ]

[ 9 8 7 5 6 ]

我已经很好地测试了我的堆和其他部分，我很确定问题出在内存分配上，但我找不到错误所在。

int main(int argc, char *argv[])
{        
    int M = atoi(argv[1]);
    int pq_1_size = M / 2;
    int pq_2_size = M - pq_1_size;

    int *a;
    int *b;
    a = (int *)malloc(pq_1_size * sizeof(int));
    b = (int *)malloc(pq_2_size * sizeof(int));
    for (int i = 0; i < pq_1_size; i++) {
        a[i] = i;
    } 
    for (int j = pq_1_size; j < M; j++) {
        b[j] = j;
    }  
    //int a[5] = { 0, 1, 2, 3, 4 }; // if I use this section instead it works fine.
    //int b[5] = { 5, 6, 7, 8, 9 }; // if I use this section instead it works fine.
    Heap someHeap = { 0, {0} };
    Heap *A = &someHeap;
    buildHeap(A, a, pq_1_size);
    //buildHeap(A, a, 5);
    print(A);
    printf("\n");   

    Heap anotherHeap = { 0, {0} };
    Heap *B = &anotherHeap;
    buildHeap(B, b, pq_2_size);
    //buildHeap(B, b, 5);
    print(B);
    return 0;
}

下面是堆代码：

#define HEAPSIZE 500
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)+1)
#define parent(i) ((i)>>1)

typedef struct {
    int size;
    int element[HEAPSIZE];
} Heap;

//Swaps the values of two ints a and b
void swap(int * a, int * b) {
    int temp;
    temp = * a;
    * a = * b;
    * b = temp;
}

//Ensures that the max heap property in heap A is satisfied at and below index i
void makeHeap(Heap * A, int i) {
    int largest = A->element[i];
    int position = i;
    int l = left(i);
    if(l <= A->size && A->element[l] > largest) {
        largest = A->element[l];
        position = l;
    }
    int r = right(i);
    if(r <= A->size && A->element[r] > largest) {
        largest = A->element[r];
        position = r;
    }
    if(i != position) {
        swap(&A->element[i], &A->element[position]);
        makeHeap(A, position);
    }
}

//Get the maximum value in the heap A
int extractMax(Heap * A) {
    if(!A->size) {
        puts("error: heap empty");
        return 0;   
    }
    int max = A->element[0];
    swap(&A->element[0], &A->element[A->size]);
    --A->size; 
    makeHeap(A, 0);
    return max;
}

//Increase the key of the ith element in heap A to be k
void increaseKey(Heap * A, int i, int k) {
    if(A->element[i] >= k) {
        printf("error: %d is less than the key of %d\n", k, i);
        return;
    }
    int position = i;
    while(position != 0 && A->element[parent(position)] < k) {
        A->element[position] = A->element[parent(position)];
        position = parent(position);
    }
    A->element[position] = k;
}

//Inserts the value i into the heap A
void insert(Heap * A, int i) {
    if(A->size >= HEAPSIZE) {
        printf("error: heap full\n");
        return;
    }
    A->element[A->size] = INT_MIN;
    increaseKey(A, A->size, i);
    ++A->size;
}

//Prints the heap A as an array
void print(Heap * A) {
    int i = 0;
    printf("[ ");
    for(i = 0; i < A->size; i++) {
        printf("%d ", A->element[i]);
    }
    printf("]\n");
}

//Makes a heap out of an unsorted array a of n elements 
void buildHeap(Heap * A, int * a, int n) {
    if(n > HEAPSIZE) {
        printf("error: too many elements\n");
        return;
    }
    if(A->size) {
        printf("error: heap not empty\n");
        return;
    }
    int nbytes = n * sizeof(int);
    memcpy(A->element, a, nbytes);
    A->size = n;
    int i = 0;
    for(i = A->size/2; i >= 0; i--) {
        makeHeap(A, i);
    }
}

Answer 1

您忘记了数组使用从 0 开始的索引值。

    int pq_1_size = M / 2;
    int pq_2_size = M - pq_1_size;   << This is either M/2 or M/2+1

    a = (int *)malloc(pq_1_size * sizeof(int));
    b = (int *)malloc(pq_2_size * sizeof(int));

    for (int i = 0; i < pq_1_size; i++) {
        a[i] = i;
    } 
    for (int j = pq_1_size; j < M; j++) {
        b[j] = j;      << j is in range M/2 .. M-1 but must be in range 0..M/2-1

这意味着您正在为第二个数组写出边界，这会导致未定义的行为。您必须相应地调整索引：

    for (int j = pq_1_size; j < M; j++) {
        b[j-pq_1_size] = j;

或

    for (int j = 0; j < pq_2_size; j++) {
        b[j] = j+pq_1_size;

关于您的问题：

为什么第二个堆总是0？
那只是偶然。通过 malloc 分配的内存没有确定的内容。它可以包含任何值。你不能依赖任何东西。由于您的循环没有触及该内存的正确元素，因此您会得到这些“随机”值。
为什么使用初始化数组会起作用？
如果你使用

int b[5] = { 5, 6, 7, 8, 9 };

您有一个数组，其中包含从索引 0 开始提供的值。

C上的内存分配错误

Memory allocation mistake on C

c

arrays

dynamic-memory-allocation