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 :

Problème sur les listes doublement chainée


Sujet :

C

  1. #1
    Futur Membre du Club
    Inscrit en
    Juin 2006
    Messages
    12
    Détails du profil
    Informations forums :
    Inscription : Juin 2006
    Messages : 12
    Points : 5
    Points
    5
    Par défaut Problème sur les listes doublement chainée
    Bonjour à tous,
    je suis en train d'essayer d'utiliser le tuto sur les listes doublement chainées :
    lien
    et j'ai voulu rajouter une fonction qui me permet de trouver une chaine spécifique dans la pile et de supprimer l'élément de la pile correspondant.
    Je ne poste que la fonction en question, pour le reste, je n'ai rien ajouté par rapport au tuto.
    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
    int dll_findDelete (dll_s **pile, void *data)
    {
        dll_first (pile);
        int i =0;
        int size = dll_sizeof(*pile);
        for (i=0;i<size;i++)
        {
        	if (dll_data (*pile) != NULL)
            {
                if (!strcmp(data,((char *) dll_data (*pile))))
                {
                    dll_remove (pile);
                    i=size;
                }
            }
            if (i!=size)
            {
                dll_next (pile);
            }
        }
        return ((i!=size)?1:0);
    }
    Mon problème est que lorsque je recherche une valeur existante, tout fonctionne, la fonction trouve l'élément et le supprime, là ou cela se gatte c'est lorsque je recherche une donnée qui ne se trouve pas dans la pile, en effet, tout semble se passer correctement (en gros ça plante pas et j'ai bien le retour comme quoi elle n'est pas présente) sauf que si je tente d'accéder à nouveau a ma pile, celle ci est vide ...

    Merci de m'éclairer sur mon erreur parce que là je vois pas ou je me suis planté (même si je me doute que j'ai du m'emmeler entre les pointeurs et les pointeurs de pointeurs)

  2. #2
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 626
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 626
    Points : 30 684
    Points
    30 684
    Par défaut
    Salut,

    Il serait déjà pas mal d'avoir la structure de ta liste doublement chainée, et, de toi à moi, il me semble que tu te complique inutilement la tache...

    En effet, si tu as créé une liste doublement chainée de manière cohérente, tu devrais avoir une structure du genre de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    typedef struct sdll
    {
        /* les informations propre à ta liste */
        sdll* previous;
        sdll* next;
    }dll_s;
    Si tu as travaillé correctement, le premier élément de la liste a le pointeur previous et le dernier élément de la liste a le pointeur next qui pointent sur NULL...

    Comme, a priori, tu es susceptible de passer n'importe quel élément de la liste comme "point de départ", le plus simple reste de:
    • rechercher l'élément dans une direction
    • si l'élément n'a pas été trouvé, rechercher l'élément dans l'autre
    • si on trouve l'élément, le supprimer


    Ce qui donnerait un code ressemblant à
    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
     
    /* Il n'est pas nécessaire d'utiliser un pointeur de pointeur: 
        un pointeur simple fait tres bien l'affaire ;) */
    int dll_findDelete (dll_s *pile, void *data)
    {
        /* il nous faut un pointeur de travail 
           qu'on initialise directement sur l'élément passé en parametre */
        dll_s *travail= pile;
        /* une première boucle qui cherche "en avant" */
        while(strcmp(data,travail->data)!=0 && travail !=NULL)
        {
            travail=travail->next;
        }
        /* si on n'a pas trouvé l'élément (travail vaut NULL), 
           on cherche dans l'autre sens */
        if(travail==NULL)
        {
            /* on réinitialise travail sur l'élément passé en parametre
                et on cherche "en arriere" */
            travail=pile;
            while(strcmp(data,travail->data)!=0 && travail !=NULL)
            {
                 travail=travail->next;
            }
        }
        /* Si travail ne vaut pas NULL ici, c'est qu'on a trouvé l'élément...
           on le supprime */
        if(travail !=NULL)
        {
            dll_remove(travail);
            /* on renvoie la réussite */
            return 0;
        }
        /* si on arrive ici, l'élément n'a pas été trouvé... on renvoie l'échec */
        return 1;
    }
    Le tout, avec une fonction dll_remove qui va bien:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    void dll_remove(dll_s *torem)
    {
        /* retrait de torem de la liste */
        if(torem->previous!=NULL)
            torem->previous->next=torem->next;
        if(torem->next!=NULL)
            torem->next->previous=torem->previous;
        /* si il y a des libérations de mémoire à faire avant de libérer 
            celle allouée à torem, n'oublie pas de le faire ici ;) */
       (...)
        /* et libération de la mémoire allouée à torem */
        free(torem);
    }
    Et le tour est joué

    Nota: j'ai considéré que data était la chaine à tester... mais ce pourrait tres bien etre, en fonction de la structure de ta liste, ou de la structure de data, quelque chose comme
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    strcmp(data, travail->data.name)
    ou
    strcmp(data,travail->data)
    dans les deux boucles qui servent à rechercher l'élément à supprimer
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  3. #3
    Futur Membre du Club
    Inscrit en
    Juin 2006
    Messages
    12
    Détails du profil
    Informations forums :
    Inscription : Juin 2006
    Messages : 12
    Points : 5
    Points
    5
    Par défaut
    Re,
    merci pour ta réponse, j'avais effectivement testé cela mais j'avais un autre problème à ce moment là, c'est que lorsque je supprime le dernier élément de ma pile, je n'ai plus que cet élément dans ma pile (oui celui que je suis sensé avoir supprimé )
    voici plus de code, pour la structure, j'utilise celle du tuto et pour les fonction "dll_xxx", elles viennent elles aussi du code donné dans le tuto.
    la structure dans listedouble.h:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    typedef struct dll dll_s;
    struct dll
    {
        struct dll *prev;
        struct dll *next;
        void *data;
    };
    dll_remove dans listedouble.c
    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
    void dll_remove (dll_s **pp_dll)
    {
        if (pp_dll != NULL && *pp_dll != NULL)
        {
            dll_s *p_l = *pp_dll;
            dll_s *p_p = p_l->prev;
            dll_s *p_n = p_l->next;
     
            if (p_p != NULL)
                p_p->next = p_n;
            if (p_n != NULL)
                p_n->prev = p_p;
            free (p_l);
            p_l = NULL;
            if (p_n != NULL)
                *pp_dll = p_n;
            else
                *pp_dll = p_p;
        }
    }
    le main (enfin la partie qui nous intéresse):
    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
    int main()
    {
        char strTest[TAILLEMAX][9] = {"chaine 1",
                                      "chaine 2",
                                      "chaine 3",
                                      "chaine 4"};
     
        int i =0;
        int trouve = 0;
        // creation de la pile
        dll_s* pile = dll_new ();
     
        for (i=0;i<TAILLEMAX;i++)
        {
            dll_insert (&pile,strTest[i]);
        }
        printf ("pile apres insertion:\n");
        list_print(pile);
        trouve = dll_findDelete (pile,"chaine 4");
        //dll_last(&pile);         /*si je decommente ça et que je commente ma */ 
        //dll_remove(&pile);    /*fonction il n'y a pas de soucis*/
        printf ("pile apres recherche et suppression:\n");
        list_print(pile);
        // Suppression de la pile
        dll_delete (&pile);
        return EXIT_SUCCESS;
    }
    Et enfin la fameuse fonction revue (et corrigée ?):
    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
    int dll_findDelete (dll_s *p_l, void *data)
    {
        int i;
        int size = dll_sizeof (p_l);
        dll_s *travail= p_l;
        dll_first (&travail); // retour au début de la pile
     
        for (i = 0; i < size; i++)
        {
            if (dll_data (travail) != NULL)
            {
                if (!strcmp(data,((char *) dll_data (travail))))
                {
                    dll_remove (&travail);
                    i=size; // pour sortir en cas de découverte
                }
            }
            dll_next (&travail); // j'avance d'1 élément dans la pile
        }
        return ((i!=size)?1:0);
    }

  4. #4
    Futur Membre du Club
    Inscrit en
    Juin 2006
    Messages
    12
    Détails du profil
    Informations forums :
    Inscription : Juin 2006
    Messages : 12
    Points : 5
    Points
    5
    Par défaut
    je me permet un petit up car je suis un peux coincé là

  5. #5
    Expert confirmé
    Avatar de Thierry Chappuis
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Mai 2005
    Messages
    3 499
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : Suisse

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Industrie Pharmaceutique

    Informations forums :
    Inscription : Mai 2005
    Messages : 3 499
    Points : 5 360
    Points
    5 360
    Par défaut
    Citation Envoyé par Traouspont
    je me permet un petit up car je suis un peux coincé là
    A quel niveau?

    Thierry
    "The most important thing in the kitchen is the waste paper basket and it needs to be centrally located.", Donald Knuth
    "If the only tool you have is a hammer, every problem looks like a nail.", probably Abraham Maslow

    FAQ-Python FAQ-C FAQ-C++

    +

  6. #6
    Futur Membre du Club
    Inscrit en
    Juin 2006
    Messages
    12
    Détails du profil
    Informations forums :
    Inscription : Juin 2006
    Messages : 12
    Points : 5
    Points
    5
    Par défaut
    Ben en fait, lorsque je supprime le dernier élément de ma liste, il ne reste plus que celui ci dans la liste et les trois autres ne sont plus accessible (quand j'utilise la fonction que j'ai fait (findDelete), lorsque je le fait en me placant sur le dernier element (ddl_last) et que je fait dll_remove ça marche sans problème , c'est donc bien au niveau de ma fonction qu'il ya un soucis mais je vois pas le truc là

Discussions similaires

  1. Question sur les listes doublement chainées.
    Par entropie67 dans le forum C
    Réponses: 2
    Dernier message: 09/02/2015, 15h12
  2. polynomes creux et les listes doublements chainées
    Par mustapha_smist dans le forum C
    Réponses: 3
    Dernier message: 11/05/2011, 09h52
  3. Problème sur les listes
    Par scary dans le forum Prolog
    Réponses: 11
    Dernier message: 31/03/2010, 08h17
  4. Butte sur un code sur les listes doublement chainées
    Par minibus dans le forum Débuter
    Réponses: 2
    Dernier message: 05/08/2009, 11h35
  5. petit problème sur les listes chaînées
    Par poche dans le forum C
    Réponses: 14
    Dernier message: 19/03/2007, 16h53

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