qsort для сравнения строк в алфавитном порядке

Question

Я использую qsort(), который поставляется с библиотекой stdlib.h, чтобы отсортировать массив структур строк.

Это по существу массив строк, но со структурой, которая содержит массив.

Например:

typedef struct node { 
    char name[MAX_SIZE + 1]; 
} Node; 

Тогда мой массив узлов, который содержит имена будут:

Node nodes_list[MAX_SIZE + 1]; 

Мой вопрос, я хочу, чтобы отсортировать nodes_list так, когда я печатаю следующее:

for (i = 0; i < size; i++) { 
    printf("%s\n", nodes_list[i].name); 
} 

распечатывает все имена в алфавитном порядке.

Я хотел бы сделать сортировку списка с помощью qsort и моя функция компаратора заключается в следующем:

int compare(const void *a, const void *b) { 
    const char **ia = (const char **)a; 
    const char **ib = (const char **)b; 
    return strcmp(*ia, *ib); 
} 

при запуске функции с qsort:

qsort(nodes_list, size, sizeof(Node), compare); 

я получаю ошибку сегментации (ядро сбрасывали).

Я знаю, что получаю ошибку сегментации с помощью этого фрагмента кода, потому что без него я могу напечатать список имен в порядке. Не отсортировано, конечно.

Может кто-нибудь помочь?

Answer 1

Ваша функция сравнения неверна для вашего формата массива.

Вот простой перечень вы можете следовать, чтобы получить типы и размеры прямо при использовании QSort:

1. Третий аргумент QSort должен быть sizeof *x где x является первым аргументом.
2. Первое, что внутри функции qsort должно быть объявлением пары указателей, инициализированных копированием аргументов функции. Не должно быть никакого броска. Броски от void * не нужны.
3. Вы можете подумать, что вам нужен актерский состав из-за const, но если вы это сделаете, это потому, что вы положили const в неправильном месте. Чтобы назначить const void * успешно без трансляции, тип назначения должен иметь ровно один * после ключевого слова const. const char * и char const * в порядке (и эквивалентны друг другу); const char *const * также в порядке (и другой); const char ** неправильный. И если вы не можете поставить const до *, потому что у вас нет *, потому что вы typedef'ed указатель типа, вот почему вы не должны этого делать.
4. Помимо добавления const, тип указателей, объявленных в начале функции сравнения, должен быть точно таким же, как тип первого аргумента для qsort, после применения правила «переход от блока к указателю», если первый аргумент qsort - это имя массива.

В вашем случае, первый аргумент QSort является nodes_List, который является массивом Node, поэтому применить правило затухающих к-указатель, и вы получите Node *, а затем добавить const и вы получите:

const Node *a_node = a; 
const Node *b_node = b; 

Теперь у вас есть хорошая пара правильно типизированных указателей, и вы просто сравнить их очевидным образом:

return strcmp(a_node->name, b_node->name); 

Чтобы объяснить, почему правило # 4 работает, у вас есть внимательно посмотреть на макет памяти. Предположим, что MAX_SIZE равно 15, так что MAX_SIZE + 1 - хороший раунд 16, ваш тип Node содержит 16-байтовый массив символов, а ваш nodes_list содержит 16 из них, в общей сложности 16 * 16 = 256 байт. Предположим, что node_list находится по адресу памяти 0x1000. Тогда макет:

+---------------+---------------+    +---------------+ 
| nodes_list[0] | nodes_list[1] |...............| nodes_list[15]| 
+---------------+---------------+    +---------------+ 
^    ^       ^   ^
0x1000   0x1010       0x10f0   0x1100 

Адреса 0x1000 по 0x10ff фактически являются частью объекта. 0x1100 - задний край - один байт за конец.

Предположим далее, что массив наполовину полон (size в 8), и она заполняется этими строками 8:

Hotel Foxtrot Echo Charlie Golf Delta Bravo Alpha 

и неиспользуемые участки заполняются 0-х. Объект состоит из этих 256 байт (я добавил пробелы и разрывы строк для целей иллюстрации)

H o t e l \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
F o x t r o t \0 \0 \0 \0 \0 \0 \0 \0 \0 
E c h o \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
C h a r l i e \0 \0 \0 \0 \0 \0 \0 \0 \0 
G o l f \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
D e l t a \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
B r a v o \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
A l p h a \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
... 128 more \0's 

Теперь вы передаете QSort начальный адрес этого блока памяти (первый ARG, nodes_list, 0x1000) плюс 2 части информации о ее внутренней структуре: количество элементов (2 arg, size, 8) и количество элементов (3-й аргумент, sizeof Node, 16). С этой информацией известно, что элементы массива расположены по адресам 0x1000, 0x1010, 0x1020, ... 0x1070. Он выбирает пару из них - какая пара, которую он выбирает, зависит от того, какой алгоритм сортировки он использует - скажем, для простоты это глупый вид пузыря, который начинается с сравнения первых двух элементов.

qsort вызывает функцию сравнения с адресами элементов, 0x1000 и 0x1010. Он не знает своих типов, но знает свои размеры. Каждый из них представляет собой элемент массива, занимающий 16 байтов.

Ваша функция сравнения получает a=0x1000 и b=0x1010. Они являются указателями на 16-байтовые объекты - в частности, каждый из них указывает на struct Node. Если вы поступите неправильно и отбросите их до char **, что произойдет? Ну, вы получите char ** со значением 0x1000, и вам нужно разыскать то, что char **, чтобы получить char *, чтобы перейти к strcmp, так что вы делаете это разыменование и в конечном итоге загружаете байты 'H', 'o', 't', 'e' в качестве значения указателя (при условии, что ваши указатели составляют 4 байта длинный). На большой машине с ASCII в качестве кодировки это указатель на адрес памяти 0x486f7465, который вы передаете strcmp. strcmp аварии. Результатом попытки struct Node ** является в основном то же самое.

Еще одна хорошая вещь, чтобы знать, как qsort использует информацию о размере члена при переупорядочении массива. Третий arg - это не только размер объекта, на который действует сравнение, но и размер объекта, который перемещается как единица при переупорядочении массива. После того, как функция сравнения вернет 1 (strcmp («Отель», «Фокстрот»)), наша гипотетическая реализация сортировки пузырьков qsort заменит объекты на 0x1000 и 0x1010, чтобы поместить их в правильном порядке. Он будет делать это с помощью серии из 3 memcpy по 16 байт каждый. Он должен переместить все эти дополнительные \0, потому что он не знает, что они бесполезны. Эти 16-байтовые объекты непрозрачны для qsort. Это может послужить основанием для того, чтобы рассмотреть возможность создания вторичного массива указателей и qsorting вместо основного массива, когда ваш основной массив имеет очень большие объекты.