使用realloc扩展和缩小数组 [英] Extending and shrinking array using realloc

问题描述

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

I'm trying to write a program which first dynamically initialises a queue array for 100 int elements. Whenever the queue is full and another element is supposed to be queued, the original array is supposed to double it's size so new elements can be inserted. In case elements are dequeued, and the amount of elements the queue consists of falls below half of its actual size, the queue size is supposed to be cut in half. However, its size should never fall below 10.

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

I'm trying to expand and shrink the array with realloc, however I'm having some problems understanding its mechanics, especially when returning a new pointer. Here is my program (with some redundant printf for debugging reasons):

#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个错误.第一个在这里:

However I keep getting 2 errors. The first one is here:

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

对对象0x1001013b0说错误:未分配指针被释放.我首先实现了这一行，因为一段时间后，我发现重新分配的内存的指针地址有时会发生变化.如果我删除该 if语句，但仍然出现错误，则此行:

saying error for object 0x1001013b0: pointer being freed was not allocated. I implemented this line in the first place, because after a while I figured out the pointer address of the reallocated memory changes sometimes. If I delete that if statement I still keep getting an error, this time being in this line:

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

消息为: malloc:对象0x100500000的错误:未分配要重新分配的指针

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

I should also add, that in both cases, sometimes the program is executed without any problems. In the latter case, the error is alternating between the realloc line in expandArray and the one in shrinkArray. I don't really understand why this happens, and how to handle the situation when realloc returns a new pointer address. Inspired by similar posts, I tried different approaches, like passing int **arr instead of int *arr to both expandArray and shrinkArray. I also tried different methods to free the original array after realloc like

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

总是带有相同的错误消息.我希望在每个测试函数之后释放内存，并在调用第二个测试函数之前在 main函数中为队列数组分配新的内存，以解决此问题，而实际上并不能解决问题.

always with the same error message. And I hoped freeing the memory after each test function and allocating new memory in the main function for the queue array before calling the second test functions would solve the problem, when in fact it didn't.

我真的很感谢对此的任何帮助.

I really appreciate any kind of help on this.

推荐答案

realloc 无法正常工作. realloc 为您完成这项工作.它需要一个指向动态内存的指针，然后更改动态内存的大小，然后返回该指针，为此可能的新内存已分配，内存中的数据被移动，旧内存被释放.

realloc does not work as you expected. realloc does the job for you. It takes a pointer to a dynamic memory changes size of dynamic memory an returns the pointer, for this possibly new memory is allocated, data in memory is moved and old memory is freed.

像这样修改您的代码:

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 .

Finally you have to adapt functions enqueue and dequeue too, similar to expandArray and 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;
}

这篇关于使用realloc扩展和缩小数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！