Блог

Ниже приведена функция для сортировки слиянием. но при выполнении я сталкиваюсь с ошибкой. Выделенная память (aux) освобождалась каждый раз в функции merge , почему она будет изменяться после освобождения?

 a.out(65287,0x1112bedc0) malloc: Incorrect checksum for freed object
0x7ff9a4c05888: probably modified after being freed. Corrupt value:
0xb00000003 a.out(65287,0x1112bedc0) malloc: *** set a breakpoint in
malloc_error_break to debug Abort trap: 6
  

 void merge(int arr[], int lo, int mid, int hi) {
    int i = lo; 
    int j = mid   1;
    int *aux = (int *)malloc((hi - lo   1) * sizeof(int));
    for (int k = lo; k <= hi; k  ) {
        aux[k] = arr[k];
    }   
    for (int k = lo; k <= hi; k  ) {
        if (i > mid)
            arr[k] = aux[j  ];
        else if (j > hi)
            arr[k] = aux[i  ];
        else if (aux[i] > aux[j])
            arr[k] = aux[j  ];
        else
            arr[k] = aux[i  ];
    } 
    free(aux);
}

void mergesort1(int arr[], int lo, int hi) {
    if (lo >= hi)
        return;
    int mid = lo   (hi - lo) / 2;
    mergesort1(arr, lo, mid);
    mergesort1(arr, mid   1, hi);
    merge(arr, lo, mid, hi);
}
  

позвоните с:

 mergesort1(arr, 0, 9);
  

malloc((hi - lo 1) * sizeof(int)) выделяет пространство для элементов, проиндексированных от 0 до hi-lo , но for (int k = lo; k <= hi; k ) … aux[k] = … обращается к элементам с индексами от lo до hi , таким образом записывая данные за пределы выделенной памяти.

aux Массив не инициализирован должным образом: for (int k = lo; k <= hi; k ) { aux[k] = arr[k]; } должно быть:

     for (int k = lo; k <= hi; k  ) {
        aux[k -lo] = arr[k];
    }
  

Ваш код выполняет запись за пределы выделенного массива, что потенциально приводит к повреждению данных, используемых malloc() и free() для отслеживания выделенной памяти.

Обратите внимание, что i и j также должны инициализироваться по-разному, и включение верхней границы в алгоритм сортировки слиянием сбивает с толку. Если hi исключено, код проще, так как никаких 1 / -1 корректировок не требуется:

 void merge1(int arr[], int lo, int mid, int hi) {
    int i = 0; 
    int j = mid -= lo;
    int n = hi - lo;
    int *aux = (int *)malloc(n * sizeof(int));
    for (int k = 0; k < n; k  ) {
        aux[k] = arr[lo   k];
    }   
    for (int k = lo; k < hi; k  ) {
        if (i >= mid)
            arr[k] = aux[j  ];
        else if (j >= n)
            arr[k] = aux[i  ];
        else if (aux[i] > aux[j])
            arr[k] = aux[j  ];
        else
            arr[k] = aux[i  ];
    } 
    free(aux);
}

void mergesort1(int arr[], int lo, int hi) {
    if (hi - lo < 2)
        return;
    int mid = lo   (hi - lo) / 2;
    mergesort1(arr, lo, mid);
    mergesort1(arr, mid, hi);
    merge1(arr, lo, mid, hi);
}
  

вызовите с помощью: mergesort1(arr, 0, 10); , что проще, потому что 10 — это длина массива.

Код может быть дополнительно упрощен с помощью арифметики указателей:

 void merge2(int arr[], int mid, int hi) {
    int *aux = malloc(n * sizeof(*aux));
    for (int i = 0; i < n; i  ) {
        aux[i] = arr[i];
    }   
    for (int i = 0, j = mid, k = 0; i < mid;) {
        if (j >= n || aux[i] <= aux[j])
            arr[k  ] = aux[i  ];
        else
            arr[k  ] = aux[j  ];
    } 
    free(aux);
}

void mergesort2(int arr[], int n) {
    if (n < 2)
        return;
    int mid = n / 2;
    mergesort2(arr, mid);
    mergesort2(arr   mid, n - mid);
    merge2(arr, mid, n);
}
  

вызов с помощью: mergesort2(arr, 10); , где 10 — длина массива.