Сортировка массива указателей на указатели

Question

У меня есть структура, содержащая int.

typedef struct n {
    int cars;
    struct n *next;
} node;

Я делаю такие узлы, как node *temp; Это потому, что я начинаю со связанного списка, а затем просматриваю его и добавляю в массив.

которые затем добавляются в массив node **arr;

Итак, у меня есть массив указателей на указатели. Мой вопрос: как я могу сделать qsort на это? Мои попытки до настоящего времени привели к:

qsort(arr, numberCars, sizeof(node), sortCars);

int sortCars(const void *i1, const void *i2){
    node *a = (node*)i1, *b = (node*)i2;
    return (a->cars - b->cars);
}

Мне трудно понять, на что в действительности указывает qsort.

Answer 1

Поскольку у вас есть массив указателей , ваша функция должна сравнивать указатели:

int sortCars(const void *i1, const void *i2){
    node *a = *(node**)i1, *b = *(node**)i2;
    return (a->cars - b->cars);
}

Кроме того, вы должны передать sizeof(node*) вместо sizeof(node).

Кстати, qsort сортирует элементы в массиве, но не эффекты next, поэтому ваш связанный список останется несортированным.

Answer 2

Функция компаратора должна возвращать int:

int sortCars(const void *i1, const void *i2)

Также вы можете сделать эту функцию более простой:

int sortCars(const void *i1, const void *i2){
    return ((*((node**) i1))->cars - (*((node**) i2))->cars);
}

Answer 3

Если узлы имеют next указатели, это указывает на связанный список. Это не то же самое, что массив. Вы уверены, что размещаете все структуры в непрерывном блоке памяти? Вот что понадобится алгоритму сортировки в качестве первого аргумента.

typedef struct n {
    int cars;
} node;

node arr[10]; // ten nodes as an array

(Как общая сортировочная функция узнает, как обновить указатели next в структуре, которую вы определили?)

Также, если arr равно node **arr, это не массив указателей на указатели. Это указатель на указатель или (примерно эквивалентный) массив массивов, указатель на массив или массив указателей.