使用 qsort 对 C 中的结构数组进行排序

Question

让我们定义一个名为"Edge"的结构。

#include <stdio.h>
#include <stdlib.h>
struct Edge{
int first;
int second;
float score;
};
struct Edge* newEdge(int first, int second, float score){
struct Edge* edge = (struct Edge*)malloc(sizeof(struct Edge*));
edge->first = first;
edge->second = second;
edge->score = score;
return edge;
}

给定一个边数组，每个边由两个顶点和一个分数组成，我必须按其分数的降序/升序对边进行排序。我写了一个比较器函数。以下是我尝试过的。但是，它不会产生正确的输出。

int comparator_function(const void *v1, const void *v2){
struct Edge* e1 = (struct Edge*) v1;
struct Edge* e2 = (struct Edge*) v2;
if(e1->score < e2->score){
return 1;
}
return 0;
}
int main(){
struct Edge* edges[5];
edges[0] = newEdge(1, 2, 1.23);
edges[1] = newEdge(4, 3, 3.222);
edges[2] = newEdge(2, 2, 5.222);
edges[3] = newEdge(5, 1, 4.222);
edges[4] = newEdge(3, 4, 2.4);
for(int i=0;i<5;i++){
printf("%d, %d, %fn", edges[i]->first, edges[i]->second, edges[i]->score);
}
printf("nn");
qsort(edges, 5, sizeof(struct Edge*), comparator_function);
for(int i=0;i<5;i++){
printf("%d, %d, %fn", edges[i]->first, edges[i]->second, edges[i]->score);
}
return 0;
}

我得到的快速排序的输出是 -

4, 3, 3.222000
5, 1, 4.222000
2, 2, 5.222000
1, 2, 1.230000
3, 4, 2.400000

我不确定我的比较函数是否正确。任何帮助将不胜感激。

Answer 1

首先，分配

struct Edge* edge = (struct Edge*)malloc(sizeof(struct Edge*));

是错误的。您必须为结构分配，而不是指针。

它应该是

struct Edge* edge = malloc(sizeof(*edge));

或

struct Edge* edge = malloc(sizeof(struct Edge));

(另请注意，malloc()的铸造结果被认为是一种不好的做法)

然后，比较函数是错误的。

• 当第一个元素比第二个元素"小"时，您必须返回-1。
• 参数是指向元素的指针(在本例中struct Edge*)。

它应该是这样的：

int comparator_function(const void *v1, const void *v2){
/* correct casting type and add dereferencing */
struct Edge* e1 = *(struct Edge**) v1;
struct Edge* e2 = *(struct Edge**) v2;
if(e1->score < e2->score){
return 1;
}
/* add this */
if(e1->score > e2->score){
return -1;
}
return 0;
}

Answer 2

传递给qsort的比较函数应该返回：

• 小于 0，如果左侧的值较小
• 0，如果值相等
• 大于 0，如果左侧的值更大

比较函数仅返回值 0 和 1，因此左参数无法更大。 您需要添加一个额外的案例来说明这一点。

另一个问题是，由于数组元素类型struct Edge *，传递给比较函数的指针将是struct Edge **类型，因此您需要进行与此相关的更改。

int comparator_function(const void *v1, const void *v2){
struct Edge * const *e1 = v1;
struct Edge * const *e2 = v2;
if((*e1)->score < (*e2)->score){
return 1;
} else if((*e1)->score > (*e2)->score){
return -1;
} else {
return 0;
}
}

此外，您没有分配适当的内存量：

struct Edge* edge = (struct Edge*)malloc(sizeof(struct Edge*));

这只为指针分配空间，而不是整个结构。 你想要：

struct Edge* edge = malloc(sizeof(struct Edge));