IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Trier une liste chaînée de caractères


Sujet :

C

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2014
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2014
    Messages : 1
    Points : 1
    Points
    1
    Par défaut Trier une liste chaînée de caractères
    Bonjour a tous,
    J'ai besoin dans un programme en C de trier une liste chaînée de caractère dans l'ordre alphabétique
    (Trier une liste de mot pour les mettre comme dans un dictionnaire)

    Et j'ais pas vraiment d'idée de comment faire sa...

    Voila donc si quelqu'un a une idée d'une méthode simple et rapide merci !

  2. #2
    Membre régulier Avatar de ekieki
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Avril 2014
    Messages
    34
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 65
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Enseignant Chercheur

    Informations forums :
    Inscription : Avril 2014
    Messages : 34
    Points : 103
    Points
    103
    Par défaut
    Si c'est une liste de caractères, ce n'est pas une liste de mots.

    Un moteur de recherche quelconque te donnera des milliers de réponses pour "trier liste chainée".

  3. #3
    Membre actif
    Étudiant
    Inscrit en
    Juin 2010
    Messages
    70
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2010
    Messages : 70
    Points : 204
    Points
    204
    Par défaut
    Tu voulais dire trier une liste chainé de chaines de caractère.

    Tu as besoins d'une comparaison de deux chaines de caractères
    (
    elle existe déjà dans <string.h> -> int strcmp(const char *s1, const char *s2);
    negatif -> alors s1<s2
    0 -> s1=s2
    positif -> si > s2
    )



    Tu as besoins d'une fonction pour échanger deux maillons.
    (dans ce cas il faut connaitre les prédécesseurs)

    -De manière générale:
    Pour éviter la gestion du premier élément, tu peux stocker le pointeur du dernier élément de la liste
    et faire que le suivant du dernier soit le premier (liste chaînée circulaire).
    Du coup l'échange devient plus simple à utiliser

    Ici la data est un pointeur
    du coup il est aussi très interessant d'échanger les pointeurs des chaines (plus rapide)


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    //echange de 2 noeuds d'une liste chainé circulaire
    void echangerMaillon(liste* maillonPrecedent_1,liste* maillonPrecedent_2)
    {
     liste* tmp=maillonPrecedent_1->suivant;//on sauvegarde le lien vers le premier élément à échanger
     maillonPrecedent_1->suivant=maillonPrecedent_2->suivant;//on fait pointer vers le deuxième élément
     maillonPrecedent_2->suivant=tmp;//fin de l'échange
    }

  4. #4
    Expert éminent sénior
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 627
    Points : 10 551
    Points
    10 551
    Par défaut
    Non, je pense qu'il faut supprimer la liste chainée

    Liste chainée -> Tableau, Dictionnaire ou autre -> Tri -> Liste chainée

    En théorie
    • Le passage de "Liste chainée -> Tableau, Dictionnaire ou autre" coûte un parcours complet de sa liste et n insertions.
    • Le tri, c'est simple c'est libre
    • Le reconstruction en liste chainée, c'est un parcours complet de sa collection et des insertions en premier (donc cacahuète )



    Ou alors faire un tri à bulles, mais niveau temps cela risque d'être assez long

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    procédure tri_bulle(Liste liste)
        si liste vide retourner fin si
     
        Element* l0
        Element* l1
        Element* l2
     
        booléen échange_effectué
     
        faire  
            échange_effectué <- faux
     
            l0 <- NULL
            l1 <- liste
            l2 <- l1.suivant
     
            tant que l2 non NULL faire
                 si l1.mot après l2.mot faire
                     échange_effectué <- vrai
     
    // Pour échanger il faut 3 maillons
    // consécutifs pour refaire les liens
                     echanger_2_maillons(l0, l1, l2)
     
                 fin si
     
                 l0 <- l1
                 l1 <- l1.suivant
                 l2 <- l1.suivant
            fin tant que
        tant que échange_effectué
    fin procédure

  5. #5
    Membre actif
    Étudiant
    Inscrit en
    Juin 2010
    Messages
    70
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2010
    Messages : 70
    Points : 204
    Points
    204
    Par défaut
    Avec les listes chaînées les insertions ont une complexité constante
    (contrairement à un tableau où il faut déplacer tous les éléments suivant l'insertion)

    Le prix à payer est lors de l'accès au n-ième élément
    (là c'est linéaire)

    le quicksort peut être appliqué à une liste simplement chaînée ( avec quelques modifs bien sûr :p )

  6. #6
    Expert éminent sénior
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 627
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 627
    Points : 10 551
    Points
    10 551
    Par défaut
    Effectivement, on peut choisir d'autres tris, mais il faut un peu oublier les/ certaines optimisations

    Approximatif, non testé, ... surtout que je fais les fins d'intervalle avec 1 de plus (fin.suivant)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    procédure tri_rapide(Liste liste)
        si liste vide retourner fin si
     
        Element* l0  // Maillon avant pivot
        Element* l01 // Maillon avant l1
        Element* l1
        Element* fin
        Element* pivot
     
        Pile pile
        Intervalle intervalle
     
    //  Intervalle(début, fin.suivant, précédent de début)
        pile.empiler( Intervalle(liste, NULL, NULL) )
     
        faire
            intervalle = pile.depiler()
     
            pivot <- intervalle.debut
            l0  <- NULL
            l01 <- pivot
            l1  <- pivot.suivant
            fin <- intervalle.fin
     
            tant que l1 non NULL et l1 != fin faire
                si pivot.mot après l1.mot faire
                    l01.suivant <- l1.suivant
     
                    si l0 non vide faire
                        l0.suivant <- l1
                    sinon
                        si intervalle.precedent non NULL
                            intervalle.precedent.suivant <- l1
                        sinon
                            liste <- l1
                        fin si
                    fin si
     
                    l1.suivant <- pivot
                    l0 <- l1
     
                    l1 <- l01.suivant
                sinon
                    l1 <- l01
                    l1 <- l1.suivant
                fin si
            fin tant que
     
            si l0 non NULL et intervalle.debut != l0 vide faire
                si intervalle.debut.suivant != l0 faire
                    pile.empiler( Intervalle(intervalle.debut, pivot, intervalle.precedent) )
                sinon
                    tester_echanger_mot(l0, intervalle.debut)
                fin si
            fin si
     
            si pivot != fin faire
                si pivot.suivant != fin faire
                    pile.empiler( Intervalle(pivot.suivant, fin, pivot) )
                sinon
                    tester_echanger_mot(pivot.suivant, fin)
                fin si
            fin si
        tant que pile non vide
    fin procédure

  7. #7
    Membre régulier Avatar de ekieki
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Avril 2014
    Messages
    34
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 65
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Enseignant Chercheur

    Informations forums :
    Inscription : Avril 2014
    Messages : 34
    Points : 103
    Points
    103
    Par défaut Une liste chainee de caractères est une catastrophe
    * Une liste chainée de caractères est une catastrophe en terme d'espace mémoire utilisé.

    Pour 1 caractère de "charge utile" dans un élément de liste il faut
    - 1 octet pour le caractère
    - 8 octets pour le pointeur sur l'élément (si on est en 64 bits)
    - 7 octets de "padding" pour la structure
    - 8 ou 16 octets supplémentaires pour les besoins de de l'allocation dynamique.

    Soit un gaspillage de l'ordre de 95 %, record d'incompétence qui sera difficile à battre.

    * un tri de liste basé sur les plus mauvais algorithmes sur les tableaux (insertion, bulles, sélection) sera encore très mauvais si on le transpose sur les chaines.

    Pourtant, il est facile de faire des tris en n.log n sur les listes chainées. La méthode où l'on coupe les données en 2 pour les trier (récursivement) et fusionner ensuite est plus facile à réaliser sur les listes que sur les tableaux, parce qu'on n'a pas la problématique de "fusion sur place".

Discussions similaires

  1. Réponses: 1
    Dernier message: 23/03/2013, 14h26
  2. Réponses: 3
    Dernier message: 23/12/2009, 21h11
  3. Trier une liste (tableau) de chaînes de caractères
    Par nariman45 dans le forum Pascal
    Réponses: 11
    Dernier message: 20/12/2008, 23h22
  4. [Debutant(e)]Trier une liste
    Par LeDébutantJava dans le forum Collection et Stream
    Réponses: 8
    Dernier message: 19/08/2004, 13h44
  5. Insertion d'un noeud dans une liste chaînée
    Par habib106 dans le forum Assembleur
    Réponses: 8
    Dernier message: 07/04/2004, 23h34

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo