Actualmente estoy implementando algún algoritmo en gráficos y uso una estructura para mantener la información sobre cada borde en el gráfico: su vértice de origen, su vértice de destino y su peso.

Tengo mi estructura declarada de la siguiente manera:

typedef struct edge {
   int data[3]; //src, dest, weight
} edge_t, *edge_p; 

Luego creo un puntero variable y asigno memoria para estructuras n, donde n es un número de aristas en un gráfico:

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

Luego lleno la estructura localEdges con los valores de otra estructura allEdges del mismo tipo:

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

Y luego necesito ordenar el contenido de localEdges por orden ascendente del campo de datos [2] (por peso de borde ascendente). Mi función de comparación es esta:

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

Y la llamada a la función es la siguiente:

qsort(localEdges, n, sizeof(edge_t), myComp);

Sin embargo, eso no funciona. La matriz procesada localEdges tiene algunos datos colocados incorrectamente. Por ejemplo:

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

Cuando debe ser:

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

Supongo que hay algo con punteros, pero no estoy muy seguro con ellos.

¿Alguna sugerencia? Apreciaré tu ayuda.

1
Indie_Cube 20 oct. 2017 a las 17:36

3 respuestas

La mejor respuesta

En resumen: su función de comparación es incorrecta. Citando un manual qsort():

La función de comparación debe devolver un número entero menor que, igual o mayor que cero si el primer argumento se considera respectivamente menor, igual o mayor que el segundo. Si dos miembros se comparan como iguales, su orden en la matriz ordenada no está definido.

Entonces, si está devolviendo 0, los dos elementos se consideran iguales.

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

Esta línea devuelve 0 si el valor en *ptr_b es mayor que el de *ptr_a.

La forma correcta de hacerlo es la siguiente:

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;
}
3
user2371524user2371524 20 oct. 2017 a las 14:45

Parece que su función de comparación está implementada incorrectamente. Nunca devuelve un resultado negativo, solo el valor bool (operación de comparación) convertido a 0 y 1. ¿Podría intentar algo como eso?

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;
}
0
Yury Schkatula 20 oct. 2017 a las 14:47

Del Estándar C (7.22.5.2 La función qsort)

3 Los contenidos de la matriz se ordenan en orden ascendente según a una función de comparación señalada por compar, que se llama con dos argumentos que apuntan a los objetos que se comparan. La función devolverá un número entero menor que, igual o mayor que cero si el primer argumento se considera respectivamente menor que, igual ao mayor que el segundo.

De este modo, defina la función, por ejemplo, de la siguiente manera

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] );
}
2
Vlad from Moscow 20 oct. 2017 a las 14:45