使用 realloc 扩展和收缩数组

Question

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

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

#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

我还应该补充一点，在这两种情况下，有时程序都可以毫无问题地执行。在后一种情况下，错误在 expandArray 中的 realloc 行和 shrinkArray 中的行之间交替出现。我真的不明白为什么会这样，以及当 realloc returns 一个新的指针地址时如何处理这种情况。受类似帖子的启发，我尝试了不同的方法，比如将 int **arr 而不是 int *arr 传递给 expandArray 和 shrinkArray。我还尝试了不同的方法来释放 realloc 之后的原始数组，比如

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

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

我真的很感激任何形式的帮助。

Answer 1

int foo(int *arr, ... ) {
  arr = ...
}

arr是一个函数参数。因此只是调用者中的一个副本。像函数内部那样更改它只会更改函数参数。调用者保留旧值。

你需要：

int foo(int **arr, ... ) {
  *arr = ...
}

恭喜。您刚刚解锁了 2 星程序员徽章。

Answer 2

realloc 没有像您预期的那样工作。 realloc 为您完成这项工作。它需要一个指向动态内存的指针，更改动态内存的大小和 returns 指针，因为可能会分配新内存，移动内存中的数据并释放旧内存。

像这样调整您的代码：

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;
}

Answer 3

 #include<stdio.h>
 #include<stdlib.h>
 int main(){
 int *a,*b,*a1;
 int n,i,k=0;
 scanf("%d",&n);
 a=(int *)malloc(n*sizeof(int));
 b=(int *)malloc(n*sizeof(int));
printf("Enter a");
for(i=0;i<n;i++){
    scanf("%d",&a[i]);
}
printf("Enter b");
for(i=0;i<n;i++){
    scanf("%d",&b[i]);
}
a1=(int*)realloc(a,(2*n)*sizeof(int));
for(i=n;i<(2*n);i++)
{
    a1[i]=b[k];
    k++;
}

for(i=0;i<(2*n);i++)
    printf("%d",a1[i]);
}

使用 realloc 扩展和收缩数组

Extending and shrinking array using realloc

c

arrays

pointers

realloc