c - 重新分配(): invalid next size and double free

Question

作为一项家庭作业，我应该创建 2 个函数，使您能够将元素插入和弹出到充当队列的数组中。我们应该动态分配内存。我的程序几乎可以正常工作，但有时在添加和删除太多元素时，我会收到类似“realloc(): invalid next size”、double free(当我只调用了一次 free 函数时)和一些元素的错误队列的开头设置为 0。例如，如果我先添加 100 个元素，然后删除 90 个并尝试添加另外 20 个，我得到“free():无效的下一个大小(快速):0x0000000001ea6010”。 我在这里做错了什么？

根据下面的建议，我更改了我的函数以将双指针作为数组的输入。然而，这现在给了我一个段错误 - 这意味着现在我根本不知道要寻找什么......

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

void enqueue(int **arr, int* lastElementIdx, size_t* totalElements, int element) {
    if (*lastElementIdx >= *totalElements) {        // check if memorry is sufficient, otherwise double
        *totalElements *= 2;

        int* temp = realloc(arr, (*totalElements * sizeof(int)));

        if (temp == NULL) {         // just in case realloc fails
            printf("Allocation error\n");
        } else {
            *arr = temp;
        }
    }

    if (*lastElementIdx <= *totalElements) {
        *lastElementIdx += 1;       // once everything is done: add element
        *arr[*lastElementIdx] = element;
    }
}

int dequeue(int **arr, int* lastElementIdx, size_t* totalElements) {
    if (*lastElementIdx > -1) {     // if queue is not empty...
        int deleted = *arr[0];      // save deleted value first (in case it's still needed)
        for (int i = 0; i <= *lastElementIdx; i++) {    // shift all elements
            *arr[i] = *arr[i + 1];
        }
        *lastElementIdx -= 1;   // index is now decreased by 1

        if (((*totalElements / 2) >= 10) && ((*lastElementIdx + 1) < (*totalElements / 2))) {   // cut memory in half if not needed
            *totalElements /= 2;

            *arr = realloc(arr, (*totalElements * sizeof(int)));
            int* temp = realloc(arr, (*totalElements * sizeof(int)));
            if (temp == NULL) {     // in case realloc fails
                printf("Allocation error\n");
                return 0;
            } else {
                *arr = temp;
            }
        }

        return deleted;
    } else {        // if queue is empty, print that there's nothing to dequeue
        printf("There are no elements inside the queue\n");
        return 0;
    }
}

void printQueue(int arr[], int lastElementIdx) {
    for (int i = 0; i <= lastElementIdx; i++) {     // print entire queue
        printf("[%d] = %d\n", i, arr[i]);
    }
    printf("\n");
}

int main (void) {

    size_t totalElements = 10;      // number of needed elements at the time
    int lastElementIdx = -1;        // index of last element in queue at the time
    int *arr = calloc(totalElements, sizeof(int));
    int **arrpointer = &arr;

    for (int i = 1; i < 101; i++) {
        enqueue(arrpointer, &lastElementIdx, &totalElements, i);
    }

    printQueue(arr, lastElementIdx);

    for (int i = 0; i < 90; i++) {
        dequeue(arrpointer, &lastElementIdx, &totalElements);
    }

    printQueue(arr, lastElementIdx);

    for (int i = 1; i < 21; i++) {
        enqueue(arrpointer, &lastElementIdx, &totalElements, i);
    }

    printQueue(arr, lastElementIdx);

    free(arr);

    return EXIT_SUCCESS;

}

Answer 1

当您扩展或收缩队列的存储空间时，您需要将指向存储空间的指针返回给调用者。这是因为 realloc() 不一定就地调整内存块的大小——它可能会在别处创建一个新的、大小不同的 block 。即使调整为较小的 block ，也允许这样做，而不仅仅是调整为较大的 block 时。

您对变量 temp 的使用表明您已意识到此问题，但正如@DerkHermann 首次观察到的那样，您对结果指针的处理不当。也许你打算按照以下方式写一些东西

arr = temp;

相反。然而，即使这样还不够。 C 仅按值传递，因此如果您修改函数参数 arr 的值，该修改仅在函数中可见(它在 arr 中接收一个 调用者传递的值的副本)。在 realloc() 分配新 block 的情况下，会给调用者留下一个无效指针。

如果您希望您的enqueue() 和dequeue() 函数能够调整队列存储的大小，那么您必须将指针传递给该存储< em>间接地。考虑到您现在所处的位置，最直接的方法是传递一个双指针，以便您可以修改它的引用:

void enqueue(int **arr, int* lastElementIdx, size_t* totalElements, int element) {
    /* ... */
    *arr = temp;
    /* ... */
}

但是请注意，您传递的是三个独立的指针，它们代表队列的状态。创建一个将这些细节组合在一个包中的 struct 类型，并将指针传递给该类型的对象会更简洁:

struct queue {
    int *arr;
    size_t capacity;
    size_t last_element_index;
};

void enqueue(struct queue *queue, int element) {
    /* ... */
    queue->arr = temp;
    /* ... */
}