Qsort() 不适用于结构

Question

我目前正在图上实现一些算法，我使用一个结构来保存关于图中每条边的信息：它的源顶点、它的目标顶点和它的权重。

我的结构声明如下：

typedef struct edge {
   int data[3]; //src, dest, weight
} edge_t, *edge_p;

然后我创建一个变量指针并为 n 结构分配内存，其中 n 是图中的边数：

edge_p localEdges = (edge_p)malloc(n*sizeof(edge_t));

然后我用另一个相同类型的结构 allEdges 的值填充结构 localEdges：

for (int i = 0; i < num_edges; i++) {
    localEdges[i].data[0] = allEdges[i].data[0];
    localEdges[i].data[1] = allEdges[i].data[1];
    localEdges[i].data[2] = allEdges[i].data[2];
}

然后我需要按 data[2] 字段的升序（按边权重升序）对 localEdges 的内容进行排序。我的比较功能是这样的：

int myComp (const void *a, const void *b)
{
    const edge_t * ptr_a = (const edge_t *)a;
    const edge_t * ptr_b = (const edge_t *)b;
    return ptr_b->data[2] < ptr_a->data[2];
}

函数调用如下：

qsort(localEdges, n, sizeof(edge_t), myComp);

但是，这不起作用。处理后的 localEdges 数组有一些数据放置错误。例如：

localEdges[0].data[2] = 1
localEdges[1].data[2] = 2
localEdges[2].data[2] = 1
localEdges[3].data[2] = 2
localEdges[4].data[2] = 3
localEdges[5].data[2] = 3
localEdges[6].data[2] = 4

什么时候应该是：

localEdges[0].data[2] = 1
localEdges[1].data[2] = 1
localEdges[2].data[2] = 2
localEdges[3].data[2] = 2
localEdges[4].data[2] = 3
localEdges[5].data[2] = 3
localEdges[6].data[2] = 4

我猜有些东西有指针，但我对它们不太有信心。

有什么建议吗？我会感谢你的帮助。

Answer 1

来自 C 标准（7.22.5.2 qsort 函数）

3 The contents of the array are sorted into ascending order according to a comparison function pointed to by compar, which is called with two arguments that point to the objects being compared. The function shall return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

因此定义函数例如下面的方式

int myComp (const void *a, const void *b)
{
    const edge_t * ptr_a = (const edge_t *)a;
    const edge_t * ptr_b = (const edge_t *)b;

    return ( ptr_b->data[2] < ptr_a->data[2] ) - ( ptr_a->data[2] < ptr_b->data[2] );
}

Answer 2

简而言之：你的比较功能是错误的。引用 a qsort() manual:

The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second. If two members compare as equal, their order in the sorted array is undefined.

因此，如果您 returning 0，则这两个元素被认为是相等的。

return ptr_b->data[2] < ptr_a->data[2];

如果 *ptr_b 中的值大于 *ptr_a 中的值，则此行执行 return 0。

正确的做法如下：

int myComp (const void *a, const void *b)
{
    const edge_t * ptr_a = (const edge_t *)a;
    const edge_t * ptr_b = (const edge_t *)b;
    if (ptr_a->data[2] < ptr_b->data[2]) return -1;
    if (ptr_a->data[2] > ptr_b->data[2]) return 1;
    return 0;
}

Answer 3

您的比较器功能似乎未正确实现。它永远不会 returns 负结果，只是 bool 值（比较操作）转换为 0 和 1。你可以尝试这样的事情吗：

int myComp (const void *a, const void *b)
{
    const edge_t * ptr_a = (const edge_t *)a;
    const edge_t * ptr_b = (const edge_t *)b;
    return (ptr_b->data[2] < ptr_a->data[2]) ? -1 : 
        (ptr_b->data[2] > ptr_a->data[2]) ? 1 : 0;
}

Qsort() 不适用于结构

Qsort() doesn't work on a struct

c

algorithm

pointers

struct

qsort