c - qsort 没有正确排序内容，kruskal 算法

Question

我正在尝试使用 qsort 对结构数组进行排序，但它没有正确对内容进行排序。 结构节点由起始顶点、结束顶点以及从顶点“a”到达顶点“b”的成本组成。

我正在编写克鲁斯卡尔算法的代码

#include <stdio.h>
#include <stdlib.h>

int v, e;

typedef struct node {
    int a;
    int b;
    int cost;
} node;

int compare(const void *a, const void *b) {
    const node *x = *(node **)a;
    const node *y = *(node **)b;
    return (x->cost > y->cost) ? 1 : 0;
}

int main() {
    scanf("%d %d", &v, &e);
    int i;
    node *arr[e];
    for (i = 0; i < e; i++) {
        int a, b, cost;
        scanf("%d %d %d", &a, &b, &cost);
        arr[i] = (node *)malloc(sizeof(node));
        arr[i]->a = a;
        arr[i]->b = b;
        arr[i]->cost = cost;
    }
    qsort(arr, e, sizeof(node *), compare);
    printf("\n\n");
    for (int i = 0; i < e; i++) {
        printf("%d %d %d\n", arr[i]->a, arr[i]->b, arr[i]->cost);
    }
    return 0;
}

输入:

9 14
2 5 4
7 8 7
0 1 4
1 7 11
0 7 8
7 6 1
6 5 2
5 4 10
3 5 14
3 4 9
2 3 7
1 2 8
2 8 2
8 6 6

输出:

2 5 4
2 8 2
0 1 4
8 6 6
6 5 2
7 6 1
7 8 7
2 3 7
1 2 8
0 7 8
3 4 9
5 4 10
1 7 11
3 5 14

前几行未按照输出正确排序。请帮帮我。

Answer 1

比较函数必须返回以下值之一:负值、零值或正值，具体取决于第一个比较的元素是否大于、等于或小于第二个比较的元素以进行降序排序。

所以这个函数定义

int compare(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return (x->cost > y->cost)?1:0;
}

不正确。

相反，您可以编写以下方式(前提是您要按降序对数组进行排序

int compare(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return ( x->cost < y->cost ) - ( y->cost < x->cost );
}

如果您想按升序对数组进行排序，则比较函数可以如下所示

int compare(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return ( y->cost < x->cost ) - ( x->cost < y->cost );
}

这是一个演示程序。

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int a;
    int b;
    int cost;
}node;

int ascending(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return ( y->cost < x->cost ) - ( x->cost < y->cost );
}

int descending(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return ( x->cost < y->cost ) - ( y->cost < x->cost );
}

int main(void) 
{
    node * arr[] =
    {
        malloc( sizeof( node ) ), malloc( sizeof( node ) ), malloc( sizeof( node ) )
    };

    const size_t N = sizeof( arr ) / sizeof( *arr );

    arr[0]->a = 2;
    arr[0]->b = 5;
    arr[0]->cost = 4;    

    arr[1]->a = 7;
    arr[1]->b = 8;
    arr[1]->cost = 7;    

    arr[2]->a = 0;
    arr[2]->b = 1;
    arr[2]->cost = 4;

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d %d %d\n", arr[i]->a, arr[i]->b, arr[i]->cost );
    }    
    putchar( '\n' );
    
    qsort( arr, N, sizeof( *arr ), ascending );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d %d %d\n", arr[i]->a, arr[i]->b, arr[i]->cost );
    }    

    putchar( '\n' );

    qsort( arr, N, sizeof( *arr ), descending );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d %d %d\n", arr[i]->a, arr[i]->b, arr[i]->cost );
    }    

    putchar( '\n' );

    for ( size_t i = 0; i < N; i++ )
    {
        free( arr[i] );
    }    
}

程序输出为

2 5 4
7 8 7
0 1 4

2 5 4
0 1 4
7 8 7

7 8 7
2 5 4
0 1 4