Comment écrire une fonction de comparaison pour qsort de stdlib?

J'ai une structure:

struct pkt_
{
  double x;
  double y;
  double alfa;
  double r_kw;
};

typedef struct pkt_ pkt;

Un tableau de ces structures:

pkt *tab_pkt;

tab_pkt = malloc(ilosc_pkt * sizeof(pkt));

Ce que je veux faire est de trier tab_pkt par tab_pkt.alfa et tab_pkt.r:

qsort(tab_pkt, ilosc_pkt, sizeof(pkt), porownaj);

Où porownaj est une fonction de comparaison, mais comment l'écrire? Voici mon "sketch" de celui-ci:

int porownaj(const void *pkt_a, const void *pkt_b)
{
  if (pkt_a.alfa > pkt_b.alfa && pkt_a.r_kw > pkt_b.r_kw) return 1;
  if (pkt_a.alfa == pkt_b.alfa && pkt_a.r_kw == pkt_b.r_kw) return 0;
  if (pkt_a.alfa < pkt_b.alfa && pkt_a.r_kw < pkt_b.r_kw) return -1;
}

j'ai ajouté le qsort tag, étant donné que ce problème est sur le qsort fonction de prédicat. je pense que d'autres ppl avec qsort va avoir des problèmes avec elle maintenant et puis.
Par la même, la même fonction peut être utilisée avec brecherche(); en effet, il est généralement une erreur si vous n'utilisez pas le même comparateur de fonction pour les deux qsort() d'un tableau et brecherche() du même tableau - en supposant que vous utilisez les deux fonctions.

OriginalL'auteur diminish | 2008-11-29

c compare qsort sorting

12

Quelque chose comme cela devrait fonctionner:
```
int porownaj(const void *p_a, const void *p_b)
{
  /* Need to store arguments in appropriate type before using */
  const pkt *pkt_a = p_a;
  const pkt *pkt_b = p_b;

  /* Return 1 or -1 if alfa members are not equal */
  if (pkt_a->alfa > pkt_b->alfa) return 1;
  if (pkt_a->alfa < pkt_b->alfa) return -1;

  /* If alfa members are equal return 1 or -1 if r_kw members not equal */
  if (pkt_a->r_kw > pkt_b->r_kw) return 1;
  if (pkt_a->r_kw < pkt_b->r_kw) return -1;

  /* Return 0 if both members are equal in both structures */
  return 0;
}
```
Rester à l'écart de silly astuces comme:
```
return pkt_a->r_kw - pkt_b->r_kw;
```
de retour de l'onu-valeurs normalisées, sont difficile à lire, ne fonctionnent pas correctement pour les nombres à virgule flottante, et ont parfois délicate cas de coin qui ne fonctionnent pas correctement, même pour des valeurs entières.

arg. je savais void* n'a pas besoin d'un cast en C lorsqu'elle est affectée à quelque chose de T* . mais n'était pas sûr de savoir si elle s'applique également à const void* 😀 je vais mémoriser que c'est aussi possible 🙂
Je vais commenter en faveur de la "bête truc" que vous avez mentionné, mais ensuite je suis venu à mon sens :b +1
Ouais; j'ai fait plusieurs erreurs dans ma solution. J'ai complètement oublié que nous avons affaire avec des doubles ici, pas des entiers. Un entier soustraction est beaucoup plus rapide que les trois plus si, qui est pourquoi j'ai utilisé cette méthode.
Je comparés il y a longtemps et a constaté que très peu, le cas échéant, la différence de performances. Le principal problème est que la méthode ne gère pas de dépassement d'entier, c'est à dire si a-b > INT_MAX le comportement n'est pas défini, la méthode donne également la mauvaise réponse dans certains cas particuliers.
Et le "coin des affaires" ne pas être tout ce que l'extrême. si a > (INT_MAX/2 + 1) et b < -(INT_MAX/2 + 1), alors (a - b) est une garantis de débordement, et donc un comportement indéterminé.

OriginalL'auteur Robert Gamble
1

Il y a deux parties à ce problème - comment écrire le code, et comment comparer les types de paquets. Vous devez vous assurer de toujours renvoyer une valeur. Votre code doit également toujours être telle que:
```
porownaj(&pkt_a, &pkt_b) == -porownaj(&pkt_b, &pkt_a)
```
Votre contour de comparaison ne gère pas les cas tels que:
```
pkt_a->alfa >  pkt_b->alfa && pkt_a->r_kw <= pkt_b->r_kw
pkt_a->alfa <  pkt_b->alfa && pkt_a->r_kw >= pkt_b->r_kw
pkt_a->alfa == pkt_b->alfa && pkt_a->r_kw != pkt_b->r_kw
```
Il y a un problème - est-il approprié de comparer les valeurs à virgule flottante exacte de l'égalité? Cela dépend de votre application.

Mécaniquement, vous devez convertir la const void pointeurs vers const structure de pointeurs. J'utilise le cast explicite - C++ exige, et j'essaie de faire mon code acceptable pour un compilateur C++, même quand il est vraiment C du code.
```
int porownaj(const void *vp1, const void *vp2)
{
     const pkt *pkt_a = (const pkt *)vp1;
     const pkt *pkt_b = (const pkt *)vp2;

     if (pkt_a->alfa >  pkt_b->alfa && pkt_a->r_kw >  pkt_b->r_kw) return 1;
     if (pkt_a->alfa == pkt_b->alfa && pkt_a->r_kw == pkt_b->r_kw) return 0;
     if (pkt_a->alfa <  pkt_b->alfa && pkt_a->r_kw <  pkt_b->r_kw) return -1;
     return 0;
 }
```
Cela ne veut pas traiter avec les morceaux que je ne peut pas résoudre car je ne suis pas partie de l'information nécessaire. Notez que, en général, multi-dimensionnelle des objets (comme des nombres complexes, ou (x,y) ou (x,y,z) les coordonnées) ne peuvent tout simplement pas être comparés pour supérieur ou inférieur ou égal à.

OriginalL'auteur Jonathan Leffler
0

Oui, je suis le tri par alfa et r_kw décide si pkt est d'abord (première valeur sera la plus grande (ou plus petite) alfa et r_kw je pense). Voilà comment je comprends le problème, je ne suis pas sûr à 100%.

OriginalL'auteur diminish

Vous devez vous connecter pour publier un commentaire.