用 C 中的结构进行 qsort

Question

我必须编写一个使用 qsort 函数对向量进行排序的程序笛卡尔平面中的点。每个点由一对坐标（x，y）。点必须按 x 轴升序排序。使用相同的 x 轴， y轴按降序排列。

这是示例输入：

5 (Struct numbers)
2 5
12 2
2 7
3 4
2 2

输出：

现在，这是我的代码：

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

typedef struct x_y
{
    int x;
    int y;
}coordinates;
typedef coordinates *coordinatesList;

int compare(const void *a, const void *b)
{
    coordinates *a1 = (coordinates *)a;
    coordinates *b1 = (coordinates *)b;
    if (a1->x > b1->x)
        return 1;
    else if (a1->x < b1->x)
        return (-1);
    else if (a1->x == b1->x)
    {
        if (a1->y < b1->y)
            return 1;
        else if (a1->y > b1->y)
            return (-1);
        else
            return 0;
    }
}

int main()
{
    int n, i;
    scanf("%d", &n);
    coordinatesList *A = (coordinatesList*)malloc(n * sizeof(coordinates));
    for (i = 0; i < n; i++)
    {
        A[i] = (coordinatesList)malloc(sizeof(coordinates));
        scanf("%d%d", &A[i]->x, &A[i]->y);
    }
    qsort(A, n, sizeof(coordinates*), compare);
    for (i = 0; i < n; i++)
        printf("%d %d\n", A[i]->x, A[i]->y);
    return 0;
}

他的错误输出是：

如果我尝试按元素分隔结构：

int compare(const void *a, const void *b)
{
    coordinates *a1 = (coordinates *)a;
    coordinates *b1 = (coordinates *)b;
    int a_x = a1->x;
    int a_y = a1->y;
    int b_x = b1->x;
    int b_y = b1->y;
    if (a_x > b_x)
        return 1;
    else if (a_x < b_x)
        return (-1);
    else if (a_x == b_x)
    {
        if (a_y < b_y)
            return 1;
        else if (a_y > b_y)
            return (-1);
        else
            return 0;
    }
}

...给我一个不同的错误输出：

Answer 1

compare函数获取的是待排序元素的指针，所以这里获取的是坐标指针。正确的开头是：

int compare(const void *a, const void *b)
{
    const coordinates *a1 = *(const coordinates **)a;
    const coordinates *b1 = *(const coordinates **)b;

我添加了 const 是因为你不应该丢弃 const-ness，即使在这里无关紧要。如果您在编译时使用警告，您会注意到。

你还应该在调用qsort时使用sizeof(coordinates)，而不是sizeof(coordinates*)，否则排序函数无法知道你的元素有多大，但这两个可能这里有相同的值。

Answer 2

对于根据 C 标准的初学者，不带参数的函数 main 应声明为

int main( void )

在此声明中

coordinatesList *A = (coordinatesList*)malloc(n * sizeof(coordinates));

您必须使用表达式 sizeof( coordinatesList ) 而不是表达式 sizeof( coordinates )。

在函数compare中你必须写

int compare(const void *a, const void *b)
{
    const coordinatesList a1 = *( const coordinatesList *)a;
    const coordinatesList b1 = *( const coordinatesList *)b;
    //...

这是一个演示程序

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

typedef struct x_y
{
    int x;
    int y;
} coordinates;

typedef coordinates *coordinatesList;

int compare( const void *a, const void *b )
{
    const coordinatesList a1 = *( const coordinatesList * )a;
    const coordinatesList b1 = *( const coordinatesList * )b;

    if ( a1->x < b1->x )
    {
        return -1;
    }
    else if ( b1->x < a1->x )
    {
        return 1;
    }
    else
    {
        if ( a1->y < b1-> y )
        {
            return 1;
        }
        else if ( b1->y < a1->y )
        {
            return -1; 
        }
        else
        {
            return 0;
        }
    }
}

int main(void) 
{
    const size_t N = 5;

    coordinatesList *A = malloc( N * sizeof( coordinatesList ) );

    for ( size_t i = 0; i < N; i++ )
    {
        A[i] = malloc( sizeof( coordinates ) );
    }

    A[0]->x = 2;  A[0]->y = 5;
    A[1]->x = 12; A[1]->y = 2;
    A[2]->x = 2;  A[2]->y = 7;
    A[3]->x = 3;  A[3]->y = 4;
    A[4]->x = 2;  A[4]->y = 2;

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d\t%d\n", A[i]->x, A[i]->y );
    }
    putchar( '\n' );

    qsort( A, N, sizeof( coordinatesList ), compare );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d\t%d\n", A[i]->x, A[i]->y );
    }
    putchar( '\n' );

    return 0;
}

它的输出是

用 C 中的结构进行 qsort

qsort with structs in C

c

struct

quicksort

qsort