Нужна помощь в использовании qsort с массивом структур

ProgramBox

Нужна помощь в использовании qsort с массивом структур

Post author:admin
Запись опубликована:22 апреля, 2023
Post category:Вопросы по программированию

#c #arrays #struct #qsort

#c #массивы #структура #qsort

Вопрос:

Итак, я видел различные примеры, но я не понимаю, что они означают.

Вот моя структура

 typedef struct profile{
    char gender[1];
    double soc;
       . . .
} PROFILE;

где soc — номер социального страхования, по которому я собираюсь сортировать.

Я знаю, что вам нужна функция сравнения, но я не знаю, как придумать именно то, что мне нужно.

1. double кажется довольно бессмысленным типом для номера социального страхования. Скорее всего, это должно быть char [10] (если вы хотите разрешить ввод нестрогих числовых значений) или uint32_t .

2. Не позволяйте скептикам доставать вас. double может быть, это и не идеально, но этого вполне достаточно для хранения 9-значного целого значения. По крайней мере, вы не столкнетесь с проблемой округленных дробных представлений.

3. @Mark Ransom: Я вряд ли думаю, что «против» является подходящим термином для указания на неправильный дизайн / код! С каких это пор номер социального страхования имеет дробное представление!

4. @Mark Ransom: Я не думаю, что в Stack Overflow есть какое-либо правило, запрещающее предлагать незапрошенные советы по темам, не имеющим прямого отношения к вопросу. Если есть, я много раз нарушал его. Кроме того, я с вами не согласен. Double — это определенно неправильно.

5. @Mark Ransom: Да, это будет работать, но это не имеет особого смысла, особенно когда вы смотрите на требования к проверке для SSN в США. Кстати, британский эквивалент SSN — это номер NI, который на самом деле начинается с двух букв.

Ответ №1:

Вот пример использования qsort для массива структур в C

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

typedef struct {
    int price;
    int id;
} order;

int compare(const void *a, const void *b) {
  
    order *orderA = (order *)a;
    order *orderB = (order *)b;
  
    return (orderB->price - orderA->price);
}

int main() {
    order list[6];

    srand(time(NULL));

    printf("Before sortingn");
    for (int i = 0; i < 6; i  ) {   
        list[i].price = rand() % 10;
        list[i].id = i; 
        printf("Order id = %d Price = %dn", list[i].id, list[i].price);            
    }

    qsort(list, 6, sizeof(order), compare);

    printf("AFTER sortingn");
    for (int n = 0; n < 6; n  ) {
        printf("Order id = %d Price = %dn", list[n].id, list[n].price);    
    }       
    return 0;
}

1. Очень полезно, особенно compare() . 🙂

2. Ваша compare функция неверна: разница между ценами может быть больше, чем диапазон типов int . Например: -3 and INT_MAX выдает INT_MAX 3 для вашего выражения, которое не соответствует типу int , вызывает неопределенное поведение и на большинстве современных аппаратных средств вычисляется как отрицательное число, хотя сравнение должно возвращать положительное число.

3. Это упорядочивает от самого большого к самому маленькому. Если вы хотите обратного, вам просто нужно изменить OrderA и OrderB в возвращаемом выражении, правильно?

4. Это правильно, т. е. вы должны изменить его на return(orderA->price - orderB->price)

5. Безопасной функцией сравнения был бы возврат (orderA->price > orderB->price) - (orderA->price < orderB->price) . Смотрите en.cppreference.com/w/c/algorithm/qsort для примера

Ответ №2:

Ваш Soc почти наверняка не должен быть типа double , но в любом случае вот пример того, что должна возвращать функция сравнения:

 int compare(const void *p1, const void *p2)
{
    const struct profile *elem1 = p1;    
    const struct profile *elem2 = p2;

   if (elem1->soc < elem2->soc)
      return -1;
   else if (elem1->soc > elem2->soc)
      return 1;
   else
      return 0;
}

Спасибо, что указали на const void *.

Вот полный пример (заархивирован): Сортировка структур с помощью функции C qsort()

1. -1 поскольку вы не можете передать это в qsort без сложного приведения, параметры должны быть const , и это может быть записано проще как return (int)(elem1->soc - elem2->soc);

2. @Mitch — Тогда плакат использует странный компилятор. Но вы исправили свой код, поэтому я отозвал свой отзыв.

3. @ChrisLutz: простой метод вычитания в общем случае некорректен. Смотрите мой ответ для встречных примеров.

4. Статью MS теперь можно найти по адресу jeffpar.github.io/kbarchive/kb/073/Q73853 И обратите внимание, что в compare не используются указатели void.

Ответ №3:

Строгая версия компаратора принимает два постоянных указателя void:

 int compare(const void *v1, const void *v2)
{
    const struct profile *p1 = v1;
    const struct profile *p2 = v2;
    if (p1->gender > p2->gender)
        return( 1);
    else if (p1->gender < p2->gender)
        return(-1);
    else if (p1->soc > p2->soc)
        return( 1);
    else if (p1->soc < p2->soc)
        return(-1);
    else
        return(0);
}

Сначала сравнивается поле gender, затем поле soc. Вот как вы обрабатываете любое сравнение из нескольких частей.

1. Ваша функция сравнения сексистская! (Кроме того, soc сравнение можно было бы выполнить как return (int)(p1->soc - p2->soc); . Приведение не требуется, если OP (разумно) изменяет тип soc на int .)

2. @Chris: напротив — моя функция совершенно благородна; дамы перед джентльменами, разве вы не знаете? Механизм вычитания работает до тех пор, пока не может быть переполнения; механизм сравнения работает независимо.

3. Замеченный при изучении недавнего вопроса, я удивлен предложением @ ChrisLutz с его представителем. 1 для JL.

4. Почему вы должны создавать указатели того типа, который вы ожидаете v1 и v2 которым вы должны быть? (Почему они не могут быть стандартными переменными). Почему вы установили указатели на const ? (Я попробовал это без const , и это сработало нормально.)

5. @Connor: Вы можете создавать локальные переменные соответствующего типа, но это создает ненужную копию того, что могло бы быть большой структурой. Код не собирается изменять то, на что он смотрит (и не должен изменять это), поэтому указатели должны быть на постоянные данные. Указатели const в интерфейсе определены стандартом. Вы можете отказаться от постоянства, но зачем вам это нужно? Это будет работать, но это не так безопасно.

Ответ №4:

Чтобы отсортировать массив, используйте qsort() и передайте функцию сравнения.

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

 typedef struct profile {
    char gender[1];
    double soc;
    int price;
    ...
} PROFILE;

int compare_price(const void *a, const void *b) {
    const PROFILE *oa = a;
    const PROFILE *ob = b;

    return (oa->price > ob->price) - (oa->price < ob->price);
}

int compare_soc(const void *a, const void *b) {
    const PROFILE *oa = a;
    const PROFILE *ob = b;

    return (oa->soc > ob->soc) - (oa->soc < ob->soc);
}

Примечания:

простое вычитание значений приводит к некорректным результатам, если разница не укладывается в int тип. Например, -2 и INT_MAX невозможно корректно сравнить с методом вычитания. Это также не сработало бы для значений с плавающей запятой.
описанный выше метод может быть использован для всех сопоставимых типов, включая, double за NaN исключением.

Если вы хотите обработать NaN , вот как сгруппировать их в конце:

 #include <math.h>

int compare_soc_nan_at_the_end(const void *a, const void *b) {
    const PROFILE *oa = a;
    const PROFILE *ob = b;

    if (isnan(oa->soc)) {
        return isnan(ob->soc) ? 0 : 1;
    } else
    if (isnan(ob->soc)) {
        return -1;
    } else {
        return (oa->soc > ob->soc) - (oa->soc < ob->soc);
    }
}