проблема, упорядочив структуру данных с помощью функции qsort в C - PullRequest
Новая
       21

проблема, упорядочив структуру данных с помощью функции qsort в C

1 голос
/ 12 июля 2011

Мне нужно заказать массив структуры данных, который содержит информацию, касающуюся происхождения узла, места назначения и веса. проблема не упорядочена должным образом, потому что если два значения равны 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, которая не выполняет правильное сравнение. Как изменить функцию сравнения на мой код, чтобы правильно отсортировать массив struct?

это мой полный код 

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

}

Ответы [ 3 ]

3 голосов
/ 12 июля 2011

Вам необходимо изменить функцию сравнения, чтобы правильно сравнивать записи 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;
 }
2 голосов
/ 12 июля 2011

Вы сортируете массив (э-э ...) 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;
}
0 голосов
/ 12 июля 2011

Из тонкого руководства :

void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
[...]
Аргумент сравнение является указателем нафункция сравнения, которая вызывается с двумя аргументами, указывающими на сравниваемые элементы.

Таким образом, ваша функция сравнения получит два ARRAY * аргумента, замаскированных под const void *, а ваш 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.

...