Qsort（）在结构上不起作用

问题描述：

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

我有结构中声明如下：

然后我创建变量指针和n结构，其中n处于图中的边数分配内存：

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

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

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]; 
}

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

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

我想有一些与指针，但我不与他们相当有信心。

有什么建议吗？我会欣赏你的帮助。

'常量edges_t * ptr_a'

用'return ptr_a-> data [2] - ptr_b-> data [2];'替换'return ptr_b-> data [2] data [2];'。 –

我假设'n == num_edges'？ –

答

简而言之：你比较函数是错误的。援引a qsort() manual：

比较函数必须返回一个整数比小于零，等于，或大于，如果第一自变量被认为是比上述第二分别小于，等于，或更大。如果两个成员比较相等，则它们在已排序数组中的顺序是未定义的。

所以，如果你要返回0，这两个元素被认为是相等的。

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

此行确实回报0如果*ptr_b值比*ptr_a更大。

正确的方式做到这一点如下：

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; 
}

答

从C标准（7.22.5.2的qsort函数）

3数组的内容被分类到根据到一个比较函数升序指向COMPAR，这被称为与 2指向被比较对象的论据。 如果第一个参数被认为分别小于，等于到或大于第二个，函数应返回小于，等于或大于零的整数。

这样定义的函数，例如下面的方式

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]); 
}

答

看来你比较器功能被错误地执行。它永远不会返回负的结果，只是布尔值（比较运算）转换为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（）在结构上不起作用

相关推荐