Forum Programmation.c Listes chainées doubles et tri

Posté par  .
Étiquettes : aucune
0
5
nov.
2005
Salut,
Je suis de retour.. et les questions aussi :)

je dois manipuler des structures du type

typedef struct cotation
{
char nom[50];
int valeur_titre;
char date[10];
int nombre_titres;
struct cotation *precedent;
struct cotation *suivant;

} COTATION;

en utillisant les listes chainées et il faut que je puisse les trier selon le nom, date, etc.
Je voulais utiliser un arbre binaire au début avec un classement par nom mais après il me sera difficile d'effectuer le tri suivant une autre variable.
Si j'utilises des listes chainées doubles "simples", il faut également un premier critère de tri...
Exemple si je veux trier par date (indépendamment du reste), mes listes chainées classées par nom ne servent plus à grand chose...

ami du c, si tu es dans le coin!

  • # Séparer données et organisation

    Posté par  . Évalué à 3.

    Une solution consiste à séparer les données et les structures de classement. Par exemple, si tu veux utiliser des listes chainées, tu déclares les structures suivantes: 
    typedef struct cotation
{
    char nom[50];
    int valeur_titre;
    char date[10];
    int nombre_titres;
} COTATION;

typedef struct chaine
{
    struct chaine *precedent;
    struct chaine *suivant;
    COTATION *donnee;
} CHAINE;

CHAINE liste_nom;
CHAINE liste_date;
    Tu as donc autant de liste chainées que de critères de tri. Lorsque tu dois ajouter un élément, tu crées une nouvelle structure COTATION et tu l'insères dans chacune des listes chainées. Ensuite, il ne te reste plus qu'à utiliser la liste correspondant au critère de tri. Evidemment, si tu préfères des arbres binaires, l'idée de base est la même, il suffit de remplacer les listes chainées par des arbres.

  • # tri avec un comparateur en argument

    Posté par  (site web personnel) . Évalué à 4.

    Commence par séparer les données de la structure de la liste comme le propose netsurfeur, après pour trier tu n'as plus qu'à écrire une fonction qui prend un pointeur de fonction type "int comparateur(COTATION *c1, COTATION *c2)" et qui l'utilise pour déterminer l'ordre de la liste. Ta fonction aura comme prototype un truc genre:
    void sort_list(CHAINE *list, int (*comparator)(const COTATION*,const COTATION*))
    Après quand tu veux trier ta liste selon l'un ou l'autre critère, tu appelles toujours la même fonction mais tu lui passe un comparateur différent.

    En fait j'ai écrit cett e fonction il y a quelques jours. C'est du C++ qui marche sans doute pas (finalement j'ai utilisé la STL) mais l'idée y est: http://krunch.servebeer.com/~krunch/vrac/cours/05-06-1linf/c(...) (la méthode StringNode::qsort()). Tu trouvera sans doute un exemple plus propre (et fonctionnel) en lisant le code du qsort() de la glibc mais qui lui s'applique aux tableaux.

    Rien à voir mais il y a aussi moyen de gagner de la place en ne stockant qu'un seul pointeur par noeud: tu xor les deux pointeurs et tu utilises l'adresse d'où tu viens pour "décoder" l'adresse suivante. En plus avec ce truc ta liste est inversible en temps constant. http://www.chiark.greenend.org.uk/~sgtatham/algorithms/revli(...)
    (c'était la minute hors sujet mais c'est toujours bon à savoir)

    pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

  • # Les questions à se poser

    Posté par  . Évalué à 1.

    Les questions à se poser avant de partir sur du code trop compliqué, c'est de savoir combien de structure de type COTATION tu auras à manipuler au cours de ton programme (ie 10, 100, 10000, 1000000, plus ?), et si tu auras besoin de souvent les trier. Tant qu'il y a moins de qques milliers d'enregistrements dans tes listes, et que tu ne fais pas des milliers de tris par seconde, je ne chercherais pas à optimiser cette partie du code dans un premier temps, et je ferais mes tris chaque fois que c'est nécessaire. Sinon, pour tout ce qui est arbre, liste chainée, .... je te recommande fortement de jeter un oeil à ce que te propose la glib.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.