Как отсортировать структуру с помощью qsort

Я пытаюсь использовать qsort для сортировки структуры, содержащей указатели. Проблема с функцией сравнения? Как мне исправить, чтобы я мог сортировать на основе cc.

Вот код:

#include <stdlib.h>
#include <string.h>

typedef enum {
    PETROL,
    DIESEL,
    ELECTRIC,
    LPG,
    BIOFUEL,
    OTHER
} fuel_t;

typedef struct car_tag {
    unsigned cc;
    fuel_t fueltype;
} car_t;


typedef struct fleet_tag {
    car_t ** cars;
    size_t n_cars;
} fleet_t;

int car_comp(const void * vp1, const void * vp2) {
    const car_t* const c1 = vp1;
    const car_t* const c2 = vp2;
    if (c1->cc > c2->cc)
        return -1;
    else if (c1->cc < c2->cc)
        return 1;
    else {
        return 0;
    }
}


int main() {
    car_t array[] = {
        { 600, PETROL},
        {1200, PETROL},
        {1000, PETROL},
        {1600, DIESEL},
        {1000, ELECTRIC}
    };

    int size = sizeof(array) / sizeof(array[0]);

    fleet_t fl;
    fl.n_cars = size;
    fl.cars = malloc(size * sizeof(car_t));

    for (int i = 0; i < size; i++) {
        car_t* pc = malloc(sizeof(car_t));
        memcpy(pc, &array[i], sizeof(car_t));
        fl.cars[i] = pc;
    }

    // how to sort cars by cc
    qsort(&fl, fl.n_cars, sizeof(car_t), car_comp);

    // sort function doesn't correctly sort fleet of cars by cc
}

c pointers qsort
person Angus Comber    schedule 07.07.2018    source источник
comment
Исправить что именно?   -  person Mad Physicist    schedule 07.07.2018
comment
@MadPhysicist Как мне исправить, чтобы я мог сортировать на основе копий   -  person Angus Comber    schedule 07.07.2018

Ответы (1)


arrow_upward
1
arrow_downward

Я не вижу необходимости в динамическом распределении и вызове memcpy для каждого автомобиля, подлежащего сортировке, в этом коде вообще.

Вы создаете слой указателей (последовательность указателей), так почему бы просто не выделить это (что вы и делаете), а затем сохранить там адреса каждого элемента из array. Затем настройте свой компаратор для адресации того, что вы отправляете: адрес указателя (указатель на указатель) и соответствующим образом настройте разыменования.

Добавьте к этому, что вы должны передавать fl.cars в qsort, а не &fl, и аргумент sizeof в нем также неверен.

Наконец, я не знаю, хотели ли вы намеренно использовать логический стек больше, чем в вашем компараторе, но это именно то, что у вас получилось.

Пример

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

typedef enum {
    PETROL,
    DIESEL,
    ELECTRIC,
    LPG,
    BIOFUEL,
    OTHER
} fuel_t;

typedef struct car_tag {
    unsigned cc;
    fuel_t fueltype;
} car_t;


typedef struct fleet_tag {
    car_t ** cars;
    size_t n_cars;
} fleet_t;

int car_comp(const void * vp1, const void * vp2)
{
    const car_t * const *pc1 = vp1;
    const car_t * const *pc2 = vp2;

    if ((*pc1)->cc > (*pc2)->cc)
        return -1;

    if ((*pc1)->cc < (*pc2)->cc)
        return 1;

    return 0;
}


int main() {
    car_t array[] = {
        { 600, PETROL},
        {1200, PETROL},
        {1000, PETROL},
        {1600, DIESEL},
        {1000, ELECTRIC}
    };

    int size = sizeof(array) / sizeof(array[0]);

    fleet_t fl;
    fl.n_cars = size;
    fl.cars = malloc(size * sizeof *fl.cars);

    for (int i = 0; i < size; i++)
        fl.cars[i] = array+i;

    // how to sort cars by cc
    qsort(fl.cars, fl.n_cars, sizeof *fl.cars, car_comp);

    for (int i=0; i<size; ++i)
        printf("%d (%u, %d)\n", i+1, fl.cars[i]->cc, fl.cars[i]->fueltype);

    free(fl.cars);

    return EXIT_SUCCESS;
}

Вывод

1 (1600, 1)
2 (1200, 0)
3 (1000, 0)
4 (1000, 2)
5 (600, 0)

qsort работает, передавая ему последовательность «вещей», длину, указывающую, сколько «вещей» существует, размер, указывающий, насколько велика каждая «вещь» в последовательности, и, наконец, функцию сравнения, которая будет передан адрес каждой "вещи" во время выполнения алгоритма.

В вашем случае ваши "вещи" - это указатели на car_t структуры. Фактически,

  • Ваша последовательность представляет собой динамический массив указателей; ваша "вещь" - это указатель на car_t.
  • Ваша длина size.
  • Ваш размер каждой «вещи» равен размеру указателя.
  • Ваш компаратор получит доступ к адресу двух ваших вещей (следовательно, два указателя, так что указатели на указатели) и будет действовать соответственно.

Таким образом, вызов становится:

qsort(fl.cars, fl.n_cars, sizeof *fl.cars, car_comp);

Наконец, обратите внимание, что исходный array остается неизменным. Сорт изменил только ваш указатель. Вероятно, это было желательно, и я надеюсь, вы понимаете, как это работает.

person WhozCraig    schedule 07.07.2018