Как отсортировать массив `int **` в C с помощью собственного qsort - PullRequest
Новая
       79

Как отсортировать массив `int **` в C с помощью собственного qsort

0 голосов
/ 24 января 2020

Мне не удалось найти ни одного вопроса по этому поводу, и я думаю, что немного схожу с ума, пытаясь выяснить это.

У меня есть следующий код: 

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <time.h>

int cmp_int(const void *a, const void *b)
{
  return * (int *)a - * (int *)b;
}

int main(int argc, char *argv[])
{
  int n = 10;
  int **arr = calloc(n, sizeof(int *));
  srand((unsigned int) time(NULL));
  for (int i = n-1; i >= 0; i--) {
    arr[i] = calloc(1, sizeof(int));
    *(arr[i]) = rand() % 1000;
  }
  for (int i = 0; i < n; i++)
    printf("%d ", *(arr[i]));
  printf("\n");
  qsort(arr, 10, sizeof(void *), cmp_int);
  for (int i = 0; i < n; i++)
    printf("%d ", *(arr[i]));
  printf("\n");
  free(arr);
  return 0;
}

Это супер баси c, верно? Согласно man-странице, первый аргумент - это указатель на базовый элемент, а третий аргумент - это размер. Тем не менее, я не могу получить массив в качестве отсортированного результата. Я все еще не совсем понимаю, каким должен быть первый и третий аргумент qsort, поскольку я подозреваю, что именно в этом и заключается ошибка.

Любая помощь приветствуется.

Спасибо.

Редактировать: я должен добавить, что этот код, очевидно, не проверяет ошибки и что я пытался протестировать qsort с массивом целых чисел с двумя указателями, так что пока да, я мог бы использовать обычный массив, который не был предназначен для этого код (на самом деле это часть большего сегмента в отдельной программе).

Ответы [ 2 ]

4 голосов
/ 24 января 2020

Ваша программа заставляет мою голову болеть. Причина, по которой вы не получаете правильную сортировку, заключается в том, что функция сравнения неверна. Чтобы получить верный результат, он должен быть return **(int **)a - **(int **)b;.

Однако исправлять проблему таким образом не стоит. Список по крайней мере некоторых из проблем:

  • Если вы не используете argc и argv, не объявляйте их.
  • Приведение в srand вызов не нужен.
  • int сравнение по вычитанию - плохая идея, поскольку оно может переполниться.
  • calloc возврат всегда должен проверяться на нулевые (нехватки) результаты.
  • calloc совсем не нужен. Используйте массив переменной длины.
  • Нет необходимости выделять массив указателей для целых. Просто выделите массив целых. Тогда ваше сравнение работает как есть.
  • В вызове qsort используется жесткая константа 10, а не n.
  • Менее подвержен ошибкам давать размер элемента путем разыменования имени массива. .
  • В конце вы освобождаете массив spine, но не целочисленные элементы.
  • Вы должны выделить функцию для печати массива.

Вот версия, которая обращается к ним. 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int cmp_int(const void *va, const void *vb)
{
  int a = *(int *)va, b = *(int *) vb;
  return a < b ? -1 : a > b ? +1 : 0;
}

void print(int *a, int n) {
  for (int i = 0; i < n; ++i) printf("%d ", a[i]);
  printf("\n");
}

int main(void)
{
  int n = 10, a[n];
  srand(time(0));
  for (int i = 0; i < n; ++i) a[i] = rand() % 1000;
  print(a, n);
  qsort(a, n, sizeof a[0], cmp_int);
  print(a, n);
  return 0;
}
2 голосов
/ 24 января 2020

Проблема, с которой вы столкнулись, заключается в том, что вам не удалось учесть один дополнительный уровень косвенности, созданный выделением блока указателей с int **arr = calloc (n, sizeof *arr);, а затем выделением памяти для одного int каждому указателю с arr[i] = calloc (1, sizeof *arr[i]).

Поскольку функция сравнения int compare (const void *a, const void *b) для qsort ожидает указатель на элементы сортируемого массива, как a, так и b выше будут указатель на -поинтер от до int в вашем случае, требующем разыменования 2-х уровней косвенности, прежде чем можно будет сравнивать целочисленные значения.

Вместо cmp_int вам действительно нужна функция сравнения cmp_int_ptr. Это может быть записано как: 

int cmp_int_ptr (const void *a, const void *b)
{
    int *ai = *(int * const *)a,
        *bi = *(int * const *)b;

    return (*ai > *bi) - (*ai < *bi);
}

( примечание: два уровня косвенности в приведении (int * const *) ..., которое также может быть записано как (int **), но для соответствуют типу параметра (const void *) * правильное значение (int * const *))

Установка этого на место, добавление проверок для каждого выделения и очистка спецификации размера шрифта calloc с использованием самого разыменованного указателя для установки type-size, вы можете сделать: 

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <time.h>

int cmp_int_ptr (const void *a, const void *b)
{
    int *ai = *(int * const *)a,
        *bi = *(int * const *)b;

    return (*ai > *bi) - (*ai < *bi);
}

int main (void) {

    int n = 10;
    int **arr = calloc (n, sizeof *arr);

    if (!arr) {
        perror ("calloc-arr");
        return 1;
    }

    srand((unsigned int) time(NULL));

    for (int i = 0; i < n; i++) {
        if (!(arr[i] = calloc (1, sizeof *arr[i]))) {
            perror ("calloc-arr[i]");
            return 1;
        }
        *(arr[i]) = rand() % 1000;
    }

    for (int i = 0; i < n; i++)
        printf (" %d", *(arr[i]));
    putchar ('\n');

    qsort (arr, 10, sizeof *arr, cmp_int_ptr);

    for (int i = 0; i < n; i++) {
        printf (" %d", *(arr[i]));
        free (arr[i]);              /* don't forget to free your int allocated */
    }
    putchar ('\n');

    free(arr);                      /* now free pointers */
}

Пример использования / Вывод 

$ ./bin/qsortptrtoint
 654 99 402 264 680 534 155 533 397 678
 99 155 264 397 402 533 534 654 678 680

Посмотрите вещи и дайте мне знать, если у вас есть вопросы.

...