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

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); 
} 

Als o, вы должны пройти sizeof(node*) вместо sizeof(node).

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

Answer 2

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

typedef struct n { 
    int cars; 
} node; 

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

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

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

Answer 3

Функция сравнения должна возвращать INT:

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

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

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