Comment trier une liste chaînée de structures par l'un des champs?

Question

Wow maintenant je sais que je ne le fais pas. Lol.

J'ai ma structure comme ceci:

struct Medico{ 
int Id_Doctor; 
int Estado; 
char Nombre[60]; ////focus on this part of the structure, this is name. 
char Clave_Acceso[20]; 
char Especialidad[40]; 
struct Medico *next; 
}; 

Et je veux organiser la structure en fonction du nom (ordre alphabétique ..) toutes les idées sur la façon d'aborder ce problème?

par exemple

Albert Haynesworth 
Bob Marley 
Carl Johnson 

Merci beaucoup à l'avance. :) (C, Unix)

Answer 1

la mise en œuvre d'un mergesort sur une liste chaînée en C est assez facile:

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

struct node { 
    struct node *next; 
    char *data; 
}; 

struct node * 
divlist (struct node *n) { 
    int i = 0; 
    if (n) { 
     struct node *tail, *n2 = n; 
     while (1) { 
      n2 = n2->next; 
      if (!n2) break; 
      if (i++ & 1) n = n->next; 
     } 
     tail = n->next; 
     n->next = NULL; 
     return tail; 
    } 
    return NULL; 
} 

struct node * 
mergelists(struct node *a, struct node *b) { 
    struct node *n; 
    struct node **last = &n; 
    if (!a) return b; 
    if (!b) return a; 

    while (1) { 
     if (strcmp(a->data, b->data) > 1) { 
      *last = b; 
      last = &b->next; 
      b = b->next; 
      if (!b) { 
       *last = a; 
       break; 
      } 
     } 
     else { 
      *last = a; 
      last = &a->next; 
      a = a->next; 
      if (!a) { 
       *last = b; 
       break; 
      } 
     } 
    } 
    return n; 
} 

struct node * 
sortlist (struct node *n) { 
    struct node *tail = divlist(n); 
    if (!tail) return n; 
    return mergelists(sortlist(n), sortlist(tail)); 
} 

int main(int argc, char *argv[]) { 
    int i; 
    struct node *n1, *n = NULL; 
    for (i = argc; --i >= 1;) { 
     n1 = (struct node *)malloc(sizeof(*n1)); 
     n1->data = argv[i]; 
     n1->next = n; 
     n = n1; 
    } 

    n1 = n = sortlist(n); 

    while (n1) { 
     printf("%s\n", n1->data); 
     n1 = n1->next; 
    } 
    return 0; 
} 

Notez que vous devrez modifier ce code pour utiliser votre structure de données et la comparaison à droite!

Answer 2

Si vous souhaitez trier un tableau de structures, vous pouvez utiliser la fonction qsort, voir man qsort. Il faut une adresse de base du tableau, le nombre d'éléments, la taille de l'élément et la fonction la comparaison:

int compare(const void *a, const void *b) { 
    Medico *medA = (Medico*) a; 
    Medico *medB = (Medico*) b; 
    return /* compare medA and medB */; 
} 

Medico *medicos = /* initialize */; 
qsort(medicos, numberOfMedicos, sizeof(Medico), compare); 

D'oh, je viens juste remarqué le pointeur suivant record qui fait sans doute cette réponse inutile. (Je l'ai changé le titre de la question de faire la liste chaînée apparente.) Pour au moins quelque chose de cette réponse, vous pouvez toujours copier la liste dans un tableau:

Medico *medicos = calloc(sizeof(Medico), numberOfMedicos); 
Medico *current = /* first record in your linked list */; 
int i = 0; 

assert(current); 
do { 
    medicos[i++] = *current; 
    current = current->next; 
} while (current); 

// Here you can sort the array. 

free(medicos); 

Bien sûr, cela dépend du nombre des enregistrements et autres variables.

(Mon C est un peu rouillé, ne hésitez pas à corriger.)

Answer 3

C ne peut pas trier pour vous, ni maintenir une structure de données triées. Comme d'autres l'ont suggéré, vous devez le trier vous-même. Je ferais ceci quand vous créeriez un nouveau Medico, puisque l'insertion dans une liste liée est facile, et vous pouvez juste trouver où il appartient pendant que vous itérez.

Si la commande de Medico doit être différente, vous devrez trier la liste chaque fois que vous l'affichez. Vous voudrez probablement effectuer des itérations pour extraire tous les noms, puis trier le tableau résultant en utilisant un certain nombre de techniques (en fonction de la taille).

En supposant que l'ordre de la liste ne soit pas important, gardez-le dans l'ordre.

Answer 4

Cela ressemble à ce que vous voulez voir les implémentations de quicksort ou mergesort. Je crois que l'implémentation de c std lib qsort prend un tableau et non une liste liée, donc vous devrez peut-être implémenter votre propre (bien que je suis sûr que vous pourriez trouver une implémentation facilement disponible sur interwebz si vous avez fait une recherche rapide)