Discussion :

[Traouspont]

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)

[koala01]

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

[Traouspont]

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);
}

[Traouspont]

je me permet un petit up car je suis un peux coincé là

[Thierry Chappuis]

je me permet un petit up car je suis un peux coincé là

A quel niveau?

Thierry

[Traouspont]

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à