ошибка при попытке освободить malloc

Question

Итак, в школе мне было поручено написать функцию, которая получает параметр int size, массив целых чисел и int flag и возвращает массив указателей, которые содержат указатели на ячейки оригинала. Массив int отсортированным образом (по возрастанию, если флаг == 1, иначе по убыванию).

Я написал это в основном по принципу сортировки слиянием, но по какой-то причине я получаю ошибку времени выполнения , которая возникает, когда программа пытается выполнить строку 123 (free temp int ** массив) есть идеи, почему это происходит и если это можно исправить?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define SIZE 100

int **pointerSort(int *arr, unsigned int size, int ascend_flag);
void ptrMerge(int arr[], int start, int mid, int end, int *ptrArr[], int flag);
void pmergeSort(int arr[], int start, int end, int *ptrArr[], int flag);

void main() {
    unsigned int size, i;
    int arr[SIZE];
    int **pointers;
    int ascend_flag;

    printf("Please enter the number of items:\n");
    scanf("%u", &size);

    for (i = 0; i < size; i++)
        scanf("%d", &arr[i]);

    scanf("%d", &ascend_flag);

    pointers = pointerSort(arr, size, ascend_flag);

    printf("The sorted array:\n"); //Print the sorted array

    //printPointers(pointers, size);
    for (i = 0; i < size; i++)
        printf("d%\t%d", *pointers[i], pointers[i]);

    free(pointers);
}

int **pointerSort(int *arr, unsigned int size, int ascend_flag) {
    int **sortedArr;

    sortedArr = (int**)malloc(size * sizeof(int*));
    pmergeSort(arr, 0, size - 1, sortedArr, ascend_flag);

    return sortedArr;
}

void pmergeSort(int arr[], int start, int end, int *ptrArr[], int flag) {

    if (start < end) {
        int mid = (start + end) / 2;

        pmergeSort(arr, start, mid, ptrArr, flag);
        pmergeSort(arr, mid + 1, end, ptrArr, flag);

        ptrMerge(arr, start, mid, end, ptrArr, flag);
    }
}

void ptrMerge(int arr[], int start, int mid, int end, int *ptrArr[], int flag) {
    int i, k = 0;
    int p = start, q = mid + 1;
    int **tempArr;

    tempArr = (int**)malloc((end - start + 1) * sizeof(int*));

    for (i = start; i <= end; i++) {
        if (arr[p] < arr[q]) {
            tempArr[k] = &arr[p];
            k++;
            p++;
        } else { //(arr[p] > arr[q])
            tempArr[k] = &arr[q];
            k++;
            q++;
        }
    }
    while (p <= mid) {
        tempArr[k] = &arr[p];
        k++;
        p++;
    }
    while (q <= end) {
        tempArr[k] = &arr[q];
        k++;
        p++;
    }

    if (flag == 1) { 
        for (i = 0; i < k; i++) 
            ptrArr[start] = tempArr[i];
            start++;
        }
    } else {
        for (i = k - 1; i >= start; i--) {
            ptrArr[start] = tempArr[i];
            start++;
        }
    }

    for (i = 0; i < k; i++)
        printf("%x\t%d\n", ptrArr[i], *ptrArr[i]);
    printf("\n");

    free(tempArr);
}

Answer 1

Вы получаете ошибку сегментации, потому что функция ptrMerge повреждает память, записывая после конца выделенного массива tempArr.

Первый l oop повторяется end - start + 1 раз, потенциально вызывая arr за пределами срезов.

l oop продолжается до p >= mid и q >= end, записывая в tempArr[k] с k большее или равное количеству элементов, выделенных с malloc().

Лог c имеет недостатки: вы сравниваете элементы arr со смещениями p и q, а не косвенно обращаетесь через массив ptrArr.

Вот измененная версия:

int **pointerSort(int *arr, int size, int ascend_flag) {
    int **sortedArr = (int**)malloc(size * sizeof(int*));
    for (int i = 0; i < size; i++) {
        sortedArr[i] = &arr[i];
    }
    pmergeSort(sortedArr, 0, size - 1, ascend_flag);
    return sortedArr;
}

void pmergeSort(int *ptrArr[], int start, int end, int flag) {
    if (start < end) {
        int mid = start + (end - start) / 2;
        pmergeSort(ptrArr, start, mid, flag);
        pmergeSort(ptrArr, mid + 1, end, flag);
        ptrMerge(ptrArr, start, mid, end, flag);
    }
}

void ptrMerge(int *ptrArr[], int start, int mid, int end, int flag) {
    int i, k, n = end - start + 1;
    int p = start, q = mid + 1;
    int **tempArr = (int**)malloc(n * sizeof(int*));

    for (k = 0; k < n; k++) {
        if (p <= mid && (q >= end || *ptrArr[p] <= *ptrArr[q])) {
            tempArr[k] = ptrArr[p++];
        } else {
            tempArr[k] = ptrArr[q++];
        }
    }
    if (flag == 1) { 
        for (k = 0; k < n; k++) 
            ptrArr[start + k] = tempArr[k];
        }
    } else {
        for (k = 0; k < n; k++) {
            ptrArr[end - k] = tempArr[k];
        }
    }
    free(tempArr);
}

Также обратите внимание, что main() должен быть определен с типом возврата int, а l oop, который печатает значения, не работает. Следует читать:

    for (i = 0; i < size; i++)
        printf("%d\t", *pointers[i]);
    printf("\n");

Answer 2

Так что вы должны использовать:

int main(void)

В это время q никогда не обновляется, так что я думаю, бесконечное l oop?

while (q <= end)
    {
        tempArr[k] = &arr[q];
        k++;
        p++;
    }

Можете ли вы предоставить мне свои входы и выход ты хочешь? Я попробовал ваш код, и я не получаю вашу ошибку.