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

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2019
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2019
    Messages : 3
    Points : 1
    Points
    1

    Par défaut Tri Liste doublement chainée

    Je me suis inspiré de ce codage de tri d'entier pour pouvoir l'effectuer avec des caractères, je cherche à trier des noms. Ne pouvant pas utiliser les deux dernières avec des caractères j'ai utilisé la fonction strcpy mais le résultat n'est pas ce que j'attendais .En effet, il place toujours le dernier nom en premier et après c'est un bordel. L'affichage des prénoms et numéro également sont mal placé. Ca fait plusieurs jours je suis bloqué, j'ai procédé à de nombreux test mais rien ne marche. Merci d'avance.
    Code inspiré:
    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
     
    void trier(liste la)
    {// ici on va ranger les elements dans l'ordre croisssant avant de les afficher.
       liste temp, temp1, temp3;
       int min;
       for(temp=la ; temp!=NULL ; temp=temp->next)
       {
         temp3=temp;
         min=temp->val;
         for(temp1=temp->next ; temp1!=NULL ; temp1=temp1->next)
         {
            if(min > temp1->val)
            {
               temp3=temp1; // le 3è temporaire est l'adresse de l'élement où se trouve le minimum
               min=temp3->val;
            }
         }
         temp3->val=temp->val; //echange des 2 elements...
         temp->val=min;
       }
    }
    Mon codage:
    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
     
    void tri_stable(t_elem *prem)
    {
        t_elem *temp, *temp1, *temp2;
      char* min;
       for(temp=prem ; temp!=NULL ; temp=temp->suiv)
       {
         temp2=temp;
         min=temp->nom;
         for(temp1=temp->suiv ; temp1!=NULL ; temp1=temp1->suiv)
         {
            if(strcmp(temp1->nom,min)<0)
            {
               temp2=temp1;
               min=temp2->nom;
            }
         }
         strcpy(temp2->nom,temp->nom);
         strcpy(temp->nom,min);
    printf("\nNom : %s\n",temp->nom);
            printf("Prenom : %s\n",temp->prenom);
            printf("Numero : %s\n\n",(temp->numero));
     
     
       }
    }
    Voici ma structure, ma fonction ajouter et mon main:

    Structure :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
    typedef struct elem
    {
        char nom[50];   //nom du client
        char prenom[50]; //prenom du client
        char numero[11]; //numero telephone du client
     
     
        struct elem *suiv;
        struct elem *prec;
    } t_elem;
    Ajouter :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void ajout_debut(t_elem **prem, t_elem *e) //Ajouter un element au debut
    {
        if (*prem) //Si deja des elements
        {
            e->suiv=*prem;
            e->prec=NULL;
            (*prem)->prec=e; //Lien vers precedent
            *prem=e;
        }
        else           //Si liste vide
            *prem=e;
    }
    Main :
    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
    int main()
    {
        t_elem *premier=NULL; //premier element
        t_elem *e;      //nouvel element
        int fin=0;
        int choix;
     
        printf("Operateur telephonique\n");
        printf("------------------------\n");
        while(fin!=1)
        {
            printf("1 Ajouter\n"
               "2 Afficher\n"
               "3 Trier\n");
               scanf("%d",&choix);
            switch(choix)
            {
            case 1: // Ajouter
                init_elem(&e,premier);
                ajout_debut(&premier,e);
                break;
     
            case 2: // Afficher chaine
                //Afficher la liste :
                afficher_chaine(premier);
                break;
     
            case 3:
                tri_stable(premier);
                break;
     
            }
        }
    }

  2. #2
    Responsable Systèmes


    Homme Profil pro
    Technicien maintenance
    Inscrit en
    août 2011
    Messages
    10 599
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Technicien maintenance
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : août 2011
    Messages : 10 599
    Points : 23 653
    Points
    23 653

    Par défaut

    Pour trier une liste chainée, tu n'auras aucune copie de chaine à faire. Tu devras juste changer les valeurs des pointeurs de chainage.

    En gros, actuellement, pour insérer un élément dans ta liste, tu vas parcourir celle-ci jusqu'à trouver le dernier élément de la liste (suiv avec valeur NULL). Si tu mets tes phrases dans un fichier texte par exemple, tu lira toutes les lignes avant d'écrire la nouvelle quand il n'y a plus de lignes à lire.

    Pour insérer ton élément en fin de liste, Ton élement->prec devra contenir l'adresse du dernier élément de la liste (soit tu le connais, soit tu connais le 1er élément et parcoure la liste jusqu'au dernier élément), suiv du dernier élément avant le tien devra être positionné sur l'adresse de ton élément, qui terminera la chaine via ton element->suiv sur NULL. Ton élément sera alors le dernier de la liste.

    Il est possible de faire la même chose en faisant en sorte que ton élément ajouté soit le 1er de la liste, c'est même mieux car tu n'as pas à parcourir la liste pour faire un ajout, juste à faire pointer element->suiv de ton élément sur le 1er élément avant ajout et element->prec de celui-ci sur l'élément que tu ajoutes.

    Pour trier ta liste, nous allons faire un tri simple, le tri à bulles. On prend le 1er élément et on le compare au suivant, si le premier est plus grand, on inverse les deux éléments. Au niveau de la liste sera consistera à inverser prec et suiv des 2 éléments de la liste. Si l’élément en cours est plus petit que le suivant, tu passes au suivant. Après toutes les passes la liste sera triée (autant de passe que de membre de la liste).

    Le plus efficace est de faire le tri lors de l'insertion dans la liste. Plutôt que d'aller à la fin de la liste, tu vas la parcourir jusqu'à l'emplacement ou il doit être (ou la chaine est plus grande, ton élément devra être juste avant). Ton tableau est donc trié en permanence, le positionnement étant fait lors de l'insertion.

    Pour aller plus loin et faire une insertion triée plus rapide, tu pourras regarder du coté des arbres binaires.
    Ma page sur developpez.com : http://chrtophe.developpez.com/ (avec mes articles)
    Mon article sur la création d'un système : http://chrtophe.developpez.com/tutoriels/minisysteme/
    Mon article sur le P2V : http://chrtophe.developpez.com/tutoriels/p2v/
    Consultez nos FAQ : Windows, Linux, Virtualisation

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2019
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2019
    Messages : 3
    Points : 1
    Points
    1

    Par défaut

    Vous dites inverser les 2 elements c'est ce que j'ai essayé de faire en utilisant strcpy. Est ce qu'il yaurait une autre manière pour procéder?

    J'ai pas compris votre explication sur le tri à insertion, pouvez vous m'expliquez avec un exemple svp?

    Je ne peux pas utiliser le tri à insertion vu que le tri se fait à partir du menu, c'est pourquoi je veux trier directement les noms par ordre croissant .

  4. #4
    Responsable Systèmes


    Homme Profil pro
    Technicien maintenance
    Inscrit en
    août 2011
    Messages
    10 599
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Technicien maintenance
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : août 2011
    Messages : 10 599
    Points : 23 653
    Points
    23 653

    Par défaut

    Regardes les tutoriaux suivants :
    https://chgi.developpez.com/pile/
    https://chgi.developpez.com/dblist/

    Sur l’un des deux, tu as un lien pour une liste triée.
    Ma page sur developpez.com : http://chrtophe.developpez.com/ (avec mes articles)
    Mon article sur la création d'un système : http://chrtophe.developpez.com/tutoriels/minisysteme/
    Mon article sur le P2V : http://chrtophe.developpez.com/tutoriels/p2v/
    Consultez nos FAQ : Windows, Linux, Virtualisation

  5. #5
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2019
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2019
    Messages : 3
    Points : 1
    Points
    1

    Par défaut

    Je suis vraiment désolé mais les tutoriaux m'aident pas, en effet ce sont des tri d'entiers et je travaille avec des caractères, dans le tutoriel le tri se fait avec une simple liste chaînée. Je n'arriverai pas à reproduire sans savoir gérer les 2 pointeurs prev et next.

Discussions similaires

  1. liste doublement chainée
    Par Ucom-C++ dans le forum C
    Réponses: 11
    Dernier message: 07/06/2007, 13h34
  2. Réponses: 2
    Dernier message: 24/03/2007, 12h48
  3. Problème sur les listes doublement chainée
    Par Traouspont dans le forum C
    Réponses: 5
    Dernier message: 05/01/2007, 12h02
  4. Pb Liste doublement chainée template
    Par ederf dans le forum Langage
    Réponses: 5
    Dernier message: 19/11/2006, 10h35
  5. Liste doublement chainée
    Par sorry60 dans le forum C
    Réponses: 23
    Dernier message: 03/12/2005, 17h12

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