C не может освободить память после ее выделения в функции

Я работаю над программой, которая сравнивает время выполнения и шаги сортировки вставки и подсчета. Все работает, кроме одного: для countsort мне нужно инициализировать дополнительный массив с помощью malloc.

Моя проблема в том, что я не могу понять, как и где освободить выделенную память для моего count_array. (Я новичок в языке C) Команда malloc находится в строке 47 в функции count_sort.

код программы:

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

const int MAX_VALUE = 5000000;

void count_sort_calculate_counts(int input_array[], int len, int count_array[], unsigned int* befehle) {
    // Muss implementiert werden
    int s = 0;
    *befehle = *befehle + 1; //1 Befehl für Zuweisung von s
    *befehle = *befehle + 1; //1 Befehl für Zuweisung von i
    for(int i = 0; i < len; i++){
        *befehle = *befehle + 1; //1 Befehl für die Überprüfung von (i < len) = true
        *befehle = *befehle + 1; //1 Befehl für i++
        s = input_array[i];
        *befehle = *befehle + 1; //1 Befehl für Zuweisung von s = input_array[i]
        count_array[s] = count_array[s] + 1;
        *befehle = *befehle + 1; //1 Befehl für die Rechnung count_array[s] = count_array[s] + 1
    }
    *befehle = *befehle + 1; //1 Befehl für die Überprüfung von (i < len) = false
}

void count_sort_write_output_array(int output_array[], int len, int count_array[], unsigned int* befehle) {
    // Muss implementiert werden
    int k = 0;
    *befehle = *befehle + 1; //1 Befehl für Zuweisung von k
    *befehle = *befehle + 1; //1 Befehl für Zuweisung von j
    *befehle = *befehle + 1; //1 Befehl für Zuweisung von i
    for(int j = 0; j <= MAX_VALUE; j++){
        *befehle = *befehle + 1; //1 Befehl für die Überprüfung von (j <= MAX_VALUE) = true
        *befehle = *befehle + 1; //1 Befehl für j++
        for(int i = 0; i < count_array[j]; i++){
            *befehle = *befehle + 1; //1 Befehl für die Überprüfung von (i < count_array[j]) = true
            *befehle = *befehle + 1; //1 Befehl für i++
            output_array[k] = j;
            *befehle = *befehle + 1; //1 Befehl für Zuweisung von output_array[k] = j
            k = k + 1;
            *befehle = *befehle + 1; //1 Befehl für die Rechnung k = k + 1
        }        
        *befehle = *befehle + 1; //1 Befehl für die Überprüfung von (i < count_array[j]) = false
    }
    *befehle = *befehle + 1; //1 Befehl für die Überprüfung von (j <= MAX_VALUE) = false
}

void count_sort(int array[], int len, unsigned int* befehle) {
    // Muss implementiert werden
    int* count_array = malloc(sizeof(int) * MAX_VALUE);
    
    count_sort_calculate_counts(array, len, count_array, befehle);   
    count_sort_write_output_array(array, len, count_array, befehle);

}


void insertion_sort(int array[], int len, unsigned int* befehle) {
    // Muss implementiert werden
    int key;
    int i;
    *befehle = *befehle + 1; //1 Befehl für Zuweisung von key
    *befehle = *befehle + 1; //1 Befehl für Zuweisung von i
    *befehle = *befehle + 1; //1 Befehl für Zuweisung von j
    for (int j = 1; j <len; j++){
        *befehle = *befehle + 1; //1 Befehl für die Überprüfung von (j <len) = true
        *befehle = *befehle + 1; //1 Befehl für j++
        i = j;
        *befehle = *befehle + 1; //1 Befehl für die zuweisung i = j;
        key = array[j];
        *befehle = *befehle + 1; //1 Befehl für die zuweisung key = array[j]
        i = j - 1;
        *befehle = *befehle + 1; //1 Befehl für die Rechnung i = j - 1
        while (i >= 0 && array[i] > key){
            *befehle = *befehle + 2; //2 Befehle für die Bedingungen (i >= 0 = true) und (array[i] > key) = true
            array[i + 1] = array[i];
            *befehle = *befehle + 1; //1 Befehl für die zuweisung array[i + 1] = array[i]
            i = i - 1;
            *befehle = *befehle + 1; //1 Befehl für die Rechnung i = i - 1;
        }
        *befehle = *befehle + 2; //2 Befehle für die Bedingung (i >= 0 = false) und (array[i] > key) = false
        array[i+1] = key;
        *befehle = *befehle + 1; //1 Befehl für die zuweisung array[i+1] = key
    }
    *befehle = *befehle + 1; //1 Befehl für die Überprüfung von (j <len) = false
}


int main(int argc, char *argv[]) {
    const int WERTE[] = {10000,20000,30000,40000,50000};
    const int LEN_WERTE = 5;
    const int LEN_ALGORITHMEN = 2;

    int rc = 0;
    unsigned int befehle_array[LEN_ALGORITHMEN][LEN_WERTE];
    double laufzeit_array[LEN_ALGORITHMEN][LEN_WERTE];

    for(int j = 0; j < LEN_WERTE; ++j) {
        int n = WERTE[j];

        // Reserviere Speicher für  Arrays der Länge n
        int* array_countsort = malloc(sizeof(int) * n);
        int* array_insertionsort = malloc(sizeof(int) * n);
        
        
        // Fülle array_countsort mit Zufallswerten ..
        fill_array_randomly(array_countsort, n, MAX_VALUE);
        // ... und kopiere die erzeugten Werte in das Array
        // array_insertionsort
        copy_array_elements(array_insertionsort, array_countsort, n);

        // Teste ob beide Arrays auch wirklich die gleichen Werte
        // enthalten
        if(!check_equality_of_arrays(array_countsort, array_insertionsort, n)) {
            printf("Die Eingaben für beide Algorithmen müssen für die Vergleichbarkeit gleich sein!\n");
            return -1;
        }

        for(int i = 0; i < LEN_ALGORITHMEN; ++i) {
            unsigned int anzahl_befehle = 0;

            start_timer();

            // Aufruf der entsprechenden Sortieralgorithmen
            if(i==0) {
                    count_sort(array_countsort, n, &anzahl_befehle);
            } else if(i==1) {
                    insertion_sort(array_insertionsort, n, &anzahl_befehle);
            }

            // Speichere die Laufzeit sowie die Anzahl benötigter
            // Befehle
            laufzeit_array[i][j] = end_timer();
            befehle_array[i][j] = anzahl_befehle;
        }

        
        // Teste, ob die Ausgabe beider Algorithmen gleich sind
        if(!check_equality_of_arrays(array_countsort, array_insertionsort, n)) {
            printf("Die Arrays sind nicht gleich. Eines muss (falsch) sortiert worden sein!\n");
            rc = -1;
        }

        // Gib den Speicherplatz wieder frei
        free(array_countsort);
        free(array_insertionsort);
    }

    // Ausgabe der Anzahl ausgeführter Befehle sowie der gemessenen
    // Laufzeiten (in Millisekunden)
    printf("Parameter MAX_VALUE hat den Wert %d\n", MAX_VALUE);
    printf("\t %32s           %32s \n", "Countsort","Insertionsort");
    printf("%8s \t %16s %16s \t %16s %16s \n", "n","Befehle", "Laufzeit","Befehle","Laufzeit");

    for(int j = 0; j < LEN_WERTE; ++j) {
        printf("%8d \t ",WERTE[j]);
        for(int i = 0; i < LEN_ALGORITHMEN; ++i) {
            printf("%16u %16.4f \t ",  befehle_array[i][j], laufzeit_array[i][j]);
        }
        printf("\n");
    }
    return rc;
}

Я пытался освободить память массива count в нескольких точках программы. Компиляция работает, но если я запускаю программу, она выдает ошибку сегментации.

Также я пытался не использовать команду malloc и просто использовать

int count_array[MAX_VALUE]; 

что также дает ошибку сегментации.

запустить его под valgrind

pm100 21.11.2022 17:30

Освободите его, когда закончите его использовать. Определенно не раньше, и желательно не слишком много позже. Если вы понимаете свой собственный код, вы поймете, когда закончите работу с массивом. Освободите его там.

Tom Karzes 21.11.2022 17:31
for(int j = 0; j <= MAX_VALUE; j++){ наверное должно быть for( int j = 0; j < MAX_VALUE; j++){ Это обычное выключение из-за одной ошибки, которая приводит к выходу за границы доступа. Он получит доступ к count_array за пределами допустимого диапазона.
Avi Berger 21.11.2022 17:43

Причина, по которой вы получаете ошибку сегментации, заключается в том, что 5000000 слишком велики для массива в стеке. Вам действительно нужен такой большой массив?

Barmar 21.11.2022 17:43
array[i + 1] = array[i]; будет обращаться за пределы массива, когда i является последним индексом массива.
Barmar 21.11.2022 17:44
free(count_array) должен быть в конце count_sort(). Массив не сохраняется ни одной из функций, которые он вызывает, поэтому освободите его после завершения использования.
Barmar 21.11.2022 17:49

Я тоже так думал, но я получаю ошибку сегментации, если освобождаю count_attay в конце, если countsort(). Так запутанно для меня :/

weito 21.11.2022 17:56

Тогда вы злоупотребляете памятью где-то еще в одной или обеих функциях, вызываемых из count_sort(). Вы, должно быть, записываете за пределы и повреждаете управляющую информацию о распределении памяти.

Jonathan Leffler 21.11.2022 18:04

@weito имейте в виду, что как только вы вышли за пределы массива (динамически выделенного или нет), все ставки сняты, может произойти что угодно, например, немедленный сбой вашей программы, позже сбой вашей программы в явно не связанной части или вашем коде, или может показаться, что он работает нормально. Неопределенное поведение Google C.

Jabberwocky 21.11.2022 18:16
==1291== Conditional jump or move depends on uninitialised value(s) эта строка valgrind должна сказать мне, что что-то выходит за рамки, верно?
weito 21.11.2022 18:24
Шаблоны Angular PrimeNg
Шаблоны Angular PrimeNg
Как привнести проверку типов в наши шаблоны Angular, использующие компоненты библиотеки PrimeNg, и настроить их отображение с помощью встроенной...
Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript
Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript
Если вы веб-разработчик (или хотите им стать), то вы наверняка гик и вам нравятся "Звездные войны". А как бы вы хотели, чтобы фоном для вашего...
Документирование API с помощью Swagger на Springboot
Документирование API с помощью Swagger на Springboot
В предыдущей статье мы уже узнали, как создать Rest API с помощью Springboot и MySql .
Начала с розового дизайна
Начала с розового дизайна
Pink Design - это система дизайна Appwrite с открытым исходным кодом для создания последовательных и многократно используемых пользовательских...
Шлюз в PHP
Шлюз в PHP
API-шлюз (AG) - это сервер, который действует как единая точка входа для набора микросервисов.
14 Задание: Типы данных и структуры данных Python для DevOps
14 Задание: Типы данных и структуры данных Python для DevOps
проверить тип данных используемой переменной, мы можем просто написать: your_variable=100
0
10
89
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий
  1. Как указал @AviBerger, это может быть связано с тем, что вы обращаетесь к count_array[MAX_VALUE], тогда как последним легально доступным элементом является MAX_VALUE-1.
  2. Убедитесь, что функция fill_array_randomly заполняет массив только неотрицательными целыми числами, потому что в функции count_sort_calculate_counts в операторе count_array[s] = count_array[s] + 1; вы обращаетесь к input_array[i]-му элементу массива count_array, и если input_array[i] отрицательно, то может возникнуть эта ошибка.

3. Мне пришлось заполнить массив count числами int перед его использованием. < for(int i = 0; i < MAX_VALUE; i++) count_array[i] = 0; >

weito 22.11.2022 14:08

@weito вы могли бы использовать calloc

Cinverse 22.11.2022 15:12

Другие вопросы по теме