Расширение и сокращение массива с использованием 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 в expandArray и номером в shrinkArray. Я действительно не понимаю, почему это происходит, и как справиться с ситуацией, когда realloc возвращает новый адрес указателя. Вдохновленный подобными сообщениями, я пробовал разные подходы, например, прохождение 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

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

Answer 2

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

arr - это параметр функции. Таким образом, это всего лишь копия того, что есть в вызывающем. Изменение этого типа внутри функции изменяет только аргумент функции. Вызывающий абонент сохраняет старое значение.

Понадобится:

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

---

Поздравляем. Вы только что разблокировали значок 2-звездочного программиста.