Как выполнить qsort массив указателей на char в C?

Предположим, что у меня есть массив указателей на char в C:

char *data[5] = { "boda", "cydo", "washington", "dc", "obama" };

И я хочу отсортировать этот массив с помощью qsort:

qsort(data, 5, sizeof(char *), compare_function);

Я не могу придумать функцию сравнения. По какой-то причине это не работает:

int compare_function(const void *name1, const void *name2)
{
    const char *name1_ = (const char *)name1;
    const char *name2_ = (const char *)name2;
    return strcmp(name1_, name2_);
}

Я много искал и обнаружил, что мне пришлось использовать ** внутри qsort:

int compare_function(const void *name1, const void *name2)
{
    const char *name1_ = *(const char **)name1;
    const char *name2_ = *(const char **)name2;
    return strcmp(name1_, name2_);
}

И это работает.

Может ли кто-нибудь объяснить использование *(const char **)name1 в этой функции? Я этого не понимаю. Почему двойной указатель? Почему моя оригинальная функция не работала?

Спасибо, Бода Сидо.

Ответы

Ответ 1

Если это помогает держать вещи прямо в вашей голове, тип, который вы должны наложить указатели на ваш компаратор, совпадает с исходным типом указателя данных, который вы передаете в qsort (что qsort docs вызывает base). Но для того, чтобы qsort был общим, он просто обрабатывает все как void*, независимо от того, что это на самом деле.

Итак, если вы сортируете массив из int, вы передадите int* (преобразованный в void*). qsort вернет вам два указателя void* к компаратору, который вы конвертируете в int*, и разыщите, чтобы получить значения int, которые вы фактически сравниваете.

Теперь замените int на char*:

если вы сортируете массив из char*, вы пройдете в char** (преобразован в void*). qsort вернет вам два указателя void* к компаратору, который вы конвертируете в char**, и разыщите, чтобы получить значения char*, которые вы действительно сравниваете.

В вашем примере, поскольку вы используете массив, char**, который вы передаете, является результатом того, что массив char* "затухает" с указателем на его первый элемент. Поскольку первый элемент является char*, указателем на него является char**.

Ответ 2

Представьте, что ваши данные были double data[5].

Ваш метод сравнения получит указатели (double *, переданные как void *) на элементы (double).
Теперь замените double на char * снова.

Ответ 3

qsort достаточно общий, чтобы сортировать массивы, состоящие из других вещей, кроме указателей. Вот почему параметр размера есть. Он не может передавать элементы массива непосредственно в функцию сравнения, поскольку во время компиляции он не знает, насколько они велики. Поэтому он передает указатели. В вашем случае вы получаете указатели на char *, char **.

Ответ 4

Функция сравнения принимает указатели на тип объекта, который в массиве, который вы хотите отсортировать. Поскольку массив содержит char *, ваша функция сравнения принимает указатели на char *, aka char **.

Ответ 5

из man qsort:

The  contents of the array are sorted in ascending 
order according to a comparison function pointed to by
compar, which is called with two arguments that **point**
to the objects being compared.

Итак, похоже, что функция сравнения получает указатели на элементы массива. Теперь указателем на char * является char ** (то есть указатель на указатель на символ).

Ответ 6

char *data[5] = { "boda", "cydo", "washington", "dc", "obama" };

- это оператор, запрашивающий компилятор для массива размером 5 указателей на символы. Вы инициализировали эти указатели для строковых литералов, но для компилятора он по-прежнему представляет собой массив из пяти указателей.

Когда вы передаете этот массив в qsort, массив указателей распадается на указатель, указывающий на первый элемент, в соответствии с правилами передачи параметров массива C.

Поэтому вы должны обработать один уровень косвенности, прежде чем сможете перейти к реальным массивам символов, содержащим константы.

Ответ 7

@bodacydo - это программа, которая может объяснить, что пытаются передать другие программисты, но это будет в контексте "целых чисел"

#include <stdio.h>


int main()
{
    int i , j;
    int *x[2] = {&i, &j};

    i = 10; j = 20;

    printf("in main() address of i = %p, address of j = %p \r\n", &i, &j);

    fun(x);
    fun(x + 1);

    return 0;
}


void fun(int **ptr)
{
    printf("value(it would be an address) of decayed element received = %p, double dereferenced value is %d \r\n",*ptr, **ptr);
    printf("the decayed value can also be printed as *(int **)ptr = %p \r\n", *(int **)ptr );
}

Ответ 8

Может быть, мне проще дать вам пример кода от меня. Я пытаюсь отсортировать массив TreeNodes, и первые несколько строк моего компаратора выглядят так:

int compareTreeNode(const void* tt1, const void* tt2) {
   const TreeNode *t1, *t2;
   t1=*(const TreeNode**)tt1;
   t2=*(const TreeNode**)tt2;

После этого вы делаете сравнение, используя t1 и t2.