如何使用 qsort 对结构进行排序 [英] How to sort struct using qsort

问题描述

我正在尝试使用 qsort 对包含指针的结构进行排序.是比较函数的问题吗?如何修复以便我可以根据抄送进行排序.

I am trying to use qsort to sort a struct containing pointers. Is the problem with the comparison function? How do I fix so I can sort based on the 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
}

推荐答案

我完全不认为需要为这段代码中的每辆待排序汽车进行动态分配和 memcpy 调用.

I don't see the need for the dynamic allocation and memcpy invoke for each to-be-sorted car in this code at all.

您正在构建一个指针床(一系列指针)，那么为什么不直接分配它(您正在做的)，然后将 array 中每个元素的地址存储在那里.然后，调整您的比较器以解决您发送的内容:指针的地址(指向指针的指针)并相应地设置取消引用

You're building a pointer bed (a sequence of pointers) so why not just allocate that (which you're doing), and then store the addresses of each element from array there. Then, tailor your comparator to address what you're sending: an address of a pointer (pointer to pointer) and setup the dereferences accordingly

此外，您应该将 fl.cars 传递给 qsort，而不是 &fl，并且其中的 sizeof 参数也是错误的.

Add to that, you should be passing fl.cars to qsort, not &fl, and the sizeof argument therein is also wrong.

最后，我不知道您是否有意在比较器中使用大于逻辑堆栈，但这正是您最终得到的.

Finally, I don't know if you intentionally wanted to use a greater-than logic stack in your comparator, but that is exactly what you ended up with.

示例

#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 的工作原理是向它提供一系列事物"，长度表示有多少事物"，大小表示序列中每个事物"的大小 是，最后是一个比较器函数，它将在算法执行期间提供每个事物"的地址.

qsort works by feeding it a sequence of "things", a length stating how many "things" there are, a size noting how big each "thing" in the sequence is, and finally a comparator function which will be fed the address of each "thing" during execution of the algorithm.

就您而言，您的事物"是指向 car_t 结构的指针.事实上，

In your case, your "things" are pointers to car_t structures. In fact,

• 你的序列是一个动态的指针数组；你的东西"是一个指向 car_t 的指针.
• 你的长度是size.
• 每个事物"的大小就是指针的大小.
• 您的比较器将访问您的两个事物的地址(因此，两个指针，因此是指向指针的指针)，并采取相应的行动.

• Your sequence is a dynamic array of pointers; your "thing" is a pointer to a car_t.
• You length is size.
• Your size of each "thing" is the size of a pointer.
• Your comparator will access the address of two of your things (therefore, two pointers, so pointers to pointers), and act accordingly.

因此，调用变为:

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

最后，请注意原来的 array 保持不变.排序只修改了你的指针床.这可能是可取的，我希望您了解它的工作原理.

Finally, note that the original array remains unchanged. The sort modified your pointer bed only. That was probably desirable, and I hope you understand how it works.

这篇关于如何使用 qsort 对结构进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！