如何使用 qsort 对结构进行排序

Question

我正在尝试使用 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
}

Answer 1

我认为这段代码中的每辆待分类汽车都不需要动态分配和 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 的工作原理是给它提供一个 "things" 的序列，一个长度表示有多少 "things"，一个大小表示每个 "thing" [=41] =]在序列中，最后是一个比较器函数，它将在算法执行期间提供每个"thing"的地址。

在你的例子中，你的 "things" 是指向 car_t 结构的指针。事实上，

你的序列是一个动态指针数组；您的 "thing" 是指向 car_t.
你的长度是size.
你每个"thing"的大小是一个指针的大小。
你的比较器将访问你的两个东西的地址（因此，两个指针，所以指针指向指针），并采取行动因此。

因此调用变为：

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

最后注意，原来的array保持不变。这种类型只改变了你的指针床。这可能是可取的，我希望你能理解它是如何工作的。

如何使用 qsort 对结构进行排序

How to sort struct using qsort

c

pointers

qsort