qsort动态数组

Question

我正在使用我在网上找到的动态数组，其头文件如下所示：

    typedef struct {
    int size;      // slots used so far
    int capacity;  // total available slots
    void **data;     // array of data we're storing
    } Vector;

    void vector_init(Vector *vector);

    void vector_append(Vector *vector, void* value);

    void* vector_get(Vector *vector, int index);

    void vector_set(Vector *vector, int index, void* value);

    void vector_double_capacity_if_full(Vector *vector);

    void vector_free(Vector *vector);

我有另一个看起来像这样的结构：

typedef struct _item{
    char name[MaxNameSize];
    float price;
} Item;

我使用

创建了一个向量

Vector vector;
vector_init(&vector);

并使用

向其中添加了一些项目

vector_append(&vector, item);

项目类型为项目的多次。我现在想按商品价格对我的动态数组进行排序。这个我试过了，没用

qsort(vector.data, vector.size, sizeof(Item*), compare);

我的比较功能是

int compare(const void* a, const void* b){
Item* first = (Item*)a;
Item* second = (Item*)b;
    return first.price - second.price;
}

知道我哪里出错了吗？我认为这可能是我在 qsort 中提出的论点。现在它似乎只是跳过了 qsort。

Answer 1

编辑：正如 WhozCraig 所指出的，数据是一个指针数组。因此：

first 和 second 是指向指针的指针，因此您必须获取指向 Item 的指针的引用，然后使用 -> 来引用结构的字段。总之，它应该是这样的：

Item* first = *(Item**)a;
Item* second = *(Item**)b;
return first->price - second->price;

Answer 2

您对 Vector 的声明包括数据床 (void**) 的指向 void 的指针。在没有看到您的其余代码的情况下，我必须假设这意味着您正在管理一个指针向量，其中每个指针通过地址引用一个不同的对象。您在 compare 中收到的地址是 data 指针数组中的偏移地址。 IE。实际类型是 void** 作为 void* 传递。

因此，您缺少一个间接级别。无论如何，你的语法都是错误的（例如：它将是 first->price，而不是 first.price）并没有帮助，但即使那是正确的，你目前拥有的前提是 Item*作为 void* 传递是错误的。

你的比较器应该是这样的，假设你的其余代码是正确的：

int compare(const void* a, const void *b)
{
    const Item * first = *(const void * const *)a;
    const Item * second = *(const void * const *)b;
    return first->price < second->price ? -1 : second->price < first->price;
}

同样，这是对您未提供的代码做出相当大的假设，并且不能保证这会起作用，除非该代码是可靠的并且满足所做的假设多于。但是，如果您按上述方式管理此向量，它应该可以工作。

我也自行修复了比较本身。减法值似乎适用于整数类型，但当转换为最终 int 结果时，浮点数的轮子会很快下降，如果引入下溢潜力，甚至是整数类型。举个简单的例子：

#include <stdio.h>

int main()
{
    printf("%d\n", (int)(1.1f - 1.0f)); // wrong
    printf("%d\n", (1.1f < 1.0f ? -1 : 1.0f < 1.1f)); // better
    return 0;
}

输出

0
1

如果转换一个更大的整数类型值，它也可能最终出现在实现定义的土地中（假设你减去 long long 并且结果小于 INT_MIN)。坚持使用我展示的表格可以避免陷阱

if (a < b) return -1;
return (b < a); // will be 1 or 0, depending on whether b < a or not.

因此比较器始终returns -1、0 或 1 并符合 qsort 的要求，同时这样做并避免浮点数到 int 转换的不准确性或潜力 underflow/overflow.

祝你好运。

qsort动态数组

qsort a dynamic array

c

vector

qsort