使用 realloc 扩展和收缩数组

Question

我正在尝试编写一个程序，该程序首先为 100 个 int 元素动态初始化一个队列数组。每当队列已满并且另一个元素应该排队时，原始数组应该将其大小加倍，以便可以插入新元素。如果元素出队，并且队列包含的元素数量低于其实际大小的一半，则应该将队列大小减半。但是，它的大小永远不应低于 10。

我正在尝试使用 realloc 扩展和收缩数组，但是我在理解其机制时遇到了一些问题，尤其是在返回新指针时。下面是我的程序（有一些冗余printf的debugging原因）：

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



void enqueue(int arr[], int* lastElementIdx, int *length, int element);
int dequeue (int arr[], int* lastElementIdx, int *length);
void printQueue(const int arr[], int lastElementIdx);
int expandArray(int *arr, int length);
int shrinkArray(int *arr, int length, bool min);


void test1(int *arr, int* lastElementIdx, int *length)
{
    int* temp = arr;
    printf("\nprintQueue #1:\n");                   //print queue, should be empty
    printQueue(temp, *lastElementIdx);

    for(int i = 1; i <= 100; i++)                   //insert elemnts to queue
        enqueue(temp, lastElementIdx, length, i);

    printf("\nprintQueue #2:\n");                   //print queue
    printQueue(temp,*lastElementIdx);

    printf("\nAusgabe von dequeue:\n");             // dequeue array
    while(*lastElementIdx > *length/4)
        printf("\naddress: %p\tElement: %d\n", temp, dequeue(temp, lastElementIdx, length));

    free(temp);

}


void test2(int *arr, int* lastElementIdx, int *length)
{
    int *temp = arr;
    printf("\n************\nEnqueue beyond queue[N-1]:\n");
    puts("Queue aufbauen...");
    for(int i = 1; i <= 150; i++)
        enqueue(temp, lastElementIdx, length, i);

    printf("\nprintQueue:\n");
    printQueue(temp,*lastElementIdx);

    printf("\nDequeue:\n");
    while(*lastElementIdx > *length/4)
        printf("\naddress: %p\tElement: %d\n", temp, dequeue(temp, lastElementIdx, length));

    free(temp);

}



int main(int argc, char const *argv[])
{
    int startingPoint = -1, *lastElementIdx = &startingPoint, N = 100, *length = &N;
    int *queue = (int*) calloc(*length, sizeof(*queue));

    test2(queue, lastElementIdx, length);
    queue = (int*) calloc(*length, sizeof(*queue));
    test1(queue, lastElementIdx, length);


    return 0;
}

int expandArray(int *arr, int length)
{
    /*function to double the array size*/

    length *= 2;
    int *temp;
    temp = (int*) realloc(arr, sizeof(*arr)*length);
    if (!temp) {
        free(temp);
    }
    else{
        if (arr != temp) {
            free(arr);
            arr = temp;
        }
        else{
            arr = temp;
        }
    }

    printf("EXPAND ARRAY: %p\n", arr);
    return length;
}

int shrinkArray(int *arr, int length, bool min)
{
    /*function that cuts array in half*/
    int *temp;

    if (min){
        length = 10;
    }
    else{
        length /= 2;
    }

    temp = (int*) realloc(arr,sizeof(*arr)*length);
    if (!temp) {
        free(temp);
    }
    else{
        arr = temp;
    }

    printf("SHRINK ARRAY: %p\n",arr);
    return length;
}

void enqueue(int arr[], int* lastElementIdx, int *length, int element)
{
    if ( *lastElementIdx < *length - 1){        //checks if there's space for another element
        arr[*lastElementIdx + 1] = element;     //if yes, insert element after lastElementIdx
        (*lastElementIdx)++;                    //increment lastElementIdx
    }
    else{
        *length = expandArray(arr, *length);    //if not, expand array
    }
}



int dequeue (int arr[], int* lastElementIdx, int *length)
{
    printf("address before:\t%p\tLast Element: %d\tLength: %d\n", arr,*lastElementIdx, *length);
    int *p = arr;
    if(*lastElementIdx > -1){               //Checks if there is an element in the queue
        if (*lastElementIdx + 2 < *length/2 and *lastElementIdx + 2 > 10) {
            bool min = false;
            *length = shrinkArray(arr, *length, min);
        }
        else if (*lastElementIdx + 2 < 10){
            bool min = true;
            *length = shrinkArray(arr, *length, min);
        }

        (*lastElementIdx)--;        //shift position of last element
        printf("address afterw:\t%p\tLast Element: %d\tLength: %d\n", arr, *lastElementIdx,*length);
        return *(p + *lastElementIdx + 1);
    }


    return 0;
}



void printQueue(const int arr[], int lastElementIdx)
{
    while( lastElementIdx > -1){
        printf("%d\t", *(arr + lastElementIdx));
        lastElementIdx--;   
    }   
}

但是我不断收到 2 个错误。第一个在这里：

if (arr != temp) {
            free(arr);
            arr = temp;
        }

说error for object 0x1001013b0: pointer being freed was not allocated。我首先实现了这一行，因为一段时间后我发现重新分配的内存的指针地址有时会发生变化。如果我删除它，if statement我仍然会收到错误消息，这次是在这一行：

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

消息是： malloc: *** error for object 0x100500000: pointer being realloc'd was not allocated

我还应该补充一点，在这两种情况下，有时程序的执行都没有任何问题。在后一种情况下，错误在 realloc 行 inexpandArray和 one in之间交替出现shrinkArray。我真的不明白为什么会发生这种情况，以及如何处理realloc返回新指针地址的情况。受到类似帖子的启发，我尝试了不同的方法，比如传递int **arr而不是传递int *arr给两者expandArray和shrinkArray。我还尝试了不同的方法来在重新分配后释放原始数组，例如

temp = (int*) realloc(arr,sizeof(*arr)*length);
if (!temp) {
    free(temp);
}
else{
    free(arr);
    arr = temp;
}

总是有相同的错误信息。我希望在每个测试函数之后释放内存并main function在调用第二个测试函数之前在队列数组中分配新内存可以解决问题，但实际上并没有。

我真的很感激在这方面的任何帮助。

Answer 1

realloc没有按预期工作。realloc为你做这项工作。它需要一个指向动态内存的指针来改变动态内存的大小并返回该指针，因为这可能会分配新内存，移动内存中的数据并释放旧内存。

像这样调整你的代码：

int expandArray(int **arr, int length)
                 // ^^ pointer to array input and output
{
    int newLength = length * 2;
    int *temp = realloc( *arr, sizeof(int) * newLength); 
    // If the function fails to allocate the requested block of memory,
    // a null pointer is returned,
    // and the memory block pointed to by argument ptr is not deallocated
    if ( temp != NULL ) {
        *arr = temp;
        length = newLength;
    }

    printf("EXPAND ARRAY: %p\n", *arr);
    return length;
}

int shrinkArray(int **arr, int length, int min)
                 // ^^ pointer to array input and output 
{
    int newLength;
    if (min){
        newLength= 10;
    }
    else{
        newLength = length / 2;
    }

    int *temp = realloc( *arr, sizeof(int) * newLength ); 
    // If the function fails to allocate the requested block of memory,
    // a null pointer is returned,
    // and the memory block pointed to by argument ptr is not deallocated
    if ( temp != NULL ) {
       *arr = temp;
        length = newLength;
    }

    printf("SHRINK ARRAY: %p\n",*arr);
    return length;
}

最后，您必须适应功能，enqueue并且dequeue也类似于expandArray和shrinkArray。

void enqueue(int **arr, int* lastElementIdx, int *length, int element);
              // ^^
int dequeue (int **arr, int* lastElementIdx, int *length);
              // ^^

void enqueue(int **arr, int* lastElementIdx, int *length, int element)
{
    if ( *lastElementIdx < *length - 1){        // checks if there's space for another element
        (*arr)[*lastElementIdx + 1] = element;  // if yes, insert element after lastElementIdx
        (*lastElementIdx)++;                    // increment lastElementIdx
    }
    else{
        *length = expandArray(arr, *length);    // if not, expand array
    }
}

int dequeue (int **arr, int* lastElementIdx, int *length)
{
    printf("address before:\t%p\tLast Element: %d\tLength: %d\n", arr,*lastElementIdx, *length);
    if( *lastElementIdx > -1 ){   // Checks if there is an element in the queue
        if ( *lastElementIdx + 2 < *length/2 && *lastElementIdx + 2 > 10) {
            *length = shrinkArray( arr, *length, 0 );
        }
        else if ( *lastElementIdx + 2 < 10 ){
            *length = shrinkArray( arr, *length, 1 );
        }
        (*lastElementIdx)--;   // shift position of last element
        printf("address afterw:\t%p\tLast Element: %d\tLength: %d\n", *arr, *lastElementIdx,*length);
        return *(*arr + *lastElementIdx + 1);
    }
    return 0;
}