使用 C 中的 qsort 函数对数据结构进行排序的问题

Question

我需要订购一组数据结构，其中包含与节点起点、目的地和权重相关的信息。问题是排序不正确，因为如果两个值等于 array.originNode 只是采用您获得的第一个值，而不是按照应有的顺序排序。

这就是我的代码对结构进行排序的方式

0 1 30
1 3 22
2 3 20
3 5 20
3 4 15

Process returned 0 (0x0)   execution time : 0.015 s

这是它应该如何排序的方式

0 1 30
1 3 22
2 3 20
3 4 15
3 5 20

我认为问题是我作为参数传递给 qsort 的函数，它没有进行正确的比较。如何将比较函数更改为我的代码以正确对结构数组进行排序？

这是我的完整代码

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <unistd.h>

 typedef struct dataNodes{
   int originNode;
   int destinationNode;
   int weight;
   struct dataNodes *next;
} ARRAYS;


  int function (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}


int main() {
ARRAYS array[6];
int n = 5, i;

array [0].originNode = 3;
array [1].originNode = 3;
array[2].originNode = 1;
array[3].originNode = 0;
array[4].originNode = 2;


array [0].destinationNode = 4 ;
array [1].destinationNode = 5;
array[2].destinationNode = 3;
array[3].destinationNode = 1;
array[4].destinationNode = 3;


array [0].weight = 15;
array [1].weight = 20;
array[2].weight = 22;
array[3].weight = 30;
array[4].weight = 20;


              qsort(array,n,sizeof(array[0]),function);
    for(i=0; i<n; i++)
    {
    printf("%d %d %d\n",array[i].originNode,array[i].destinationNode,
    array[i].weight);
    }
return 0;

}

Answer 1

您需要更改比较函数才能正确比较 ARRAY 记录。首先比较originNode，如果相同则比较destinationNode。

int function (const void * a, const void * b)
{
    const ARRAYS *ap = a;
    const ARRAYS *bp = b;
    if( ap->originNode < bp->originNode )
        return -1;
    else if( ap->originNode > bp->originNode )
        return 1;
    else if( ap->destinationNode < bp->destinationNode )
        return -1;
    else if( ap->destinationNode > bp->destinationNode )
        return 1;
    else
        return 0;
 }

Answer 2

您正在对一个（呃...）ARRAYS 数组进行排序。因此，您传入的排序函数应该比较 ARRAYS 对象。您的代码将其视为int。

进行二次排序时，需要在主字段相等的情况下，比较对应的次字段。对您想要比较的任何其他字段执行相同的操作。

因此，就您而言，此排序功能可能适合您：

int sort_ARRAYS (const void * a, const void * b)
{
    /* the arguments are pointers to ARRAYS objects */
    const ARRAYS *x = a;
    const ARRAYS *y = b;
    int cmp;

    /* primary */
    cmp = x->originNode - y->originNode;
    if (cmp != 0) return cmp;

    /* secondary */
    cmp = x->destinationNode - y->destinationNode;
    if (cmp != 0) return cmp;

    /* tertiary */
    return x->weight - y->weight;
}

Answer 3

来自精细手册：

void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
[...]
compar 参数是指向比较函数的指针，使用两个指向要比较的元素的参数来调用该函数。

因此，您的比较函数将接收两个伪装为 const void * 的 ARRAY * 参数，并且您的 function 只需要适当地转换它们：

int
function(const void * a, const void * b) {
    ARRAYS *aa = (ARRAYS *)a;
    ARRAYS *bb = (ARRAYS *)b;
    return aa->originNode - bb->originNode;
}

如果您想要一个辅助排序键，然后检查是否 aa->originNode == bb->originNode 并比较辅助键（如果为真）；如果需要的话，对于第三键也是如此。

您当前的代码是偶然运行的。这：

return ( *(int*)a - *(int*)b );

实际上是在比较 ARRAYS* 参数的第一个元素，它之所以有效，是因为 (a) 结构的开头没有填充，并且 (b) originNode 位于开头，它实际上是一个int。