Supprimer valeur liste chaînée

Version imprimable

Bonjour à tous,

J'essaye actuellement de coder une fonction supprimant la première instance d'une valeur passé en paramètre sur une liste chaînée.

Voici mon code :

Code:

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
 
typedef struct cell
{
    void *donnee;
    struct cell *next;
} cell;
 
 
typedef struct liste
{
    cell *first; // Une liste est caractérisé par une cell de tête et de queue
    cell *last;
} liste;
 
 
int suppression_premiere_instance(liste *l, void *valeur)
{
    cell *curr = l -> first; //curr est la première cellule
    cell *prev; //on crée une cellule prev
	if (l -> first == NULL) //cas si la liste est vide
	{
	    return 0;
	}
	else if (curr -> donnee == valeur) //cas si la valeur recherchée est au début de la liste
	{
	    l -> first = curr -> next;
	    free(curr);
	    return 1;
	}
    while ((curr -> next) != NULL) //autre cas. Tant qu'on est pas arrivé au bout de la liste
    {
       if (curr -> donnee == valeur) //si la valeur de la cellule est égale à la valeur recherchée
        {
            prev -> next = curr -> next; //on fait pointer prev vers la cellule pointé par curr
            free(curr); //on libère la cellule courante
            return 1;
        }
    curr = curr -> next; //on avance dans la liste
    }
}

Ca compile correctement mais ça ne fonctionne pas, je ne comprend pas vraiment pourquoi. Un coup de pouce ? :ccool:

Cordialement,

KhaaB

prev n'est jamais initialisé.

On a sans doute d'ailleurs intérêt à tester sur le maillon suivant et se dispenser de prev :
Code:

1 2 3 4 while ((curr -> next) != NULL) //autre cas. Tant qu'on est pas arrivé au bout de la liste { if (curr -> next->donnee == valeur) //si la valeur de la cellule est égale à la valeur recherchée {

Oui, pourquoi pas :

Code:

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 suppression_premiere_instance(liste *l, void *valeur)
{
    cell *curr = l -> first;
    cell *cnext = curr -> next;
	if (l -> first == NULL)
	{
	    return 0;
	}
	else if (curr -> donnee == valeur)
	{
	    l -> first = curr -> next;
	    free(curr);
	    return 1;
	}
    while (cnext != NULL)
    {
       if (cnext -> donnee == valeur) //Si curr -> next -> donnee
        {
            curr -> next = cnext -> next; //On fait pointer curr vers cnext next
            free(cnext);
            return 1;
        }
    curr = cnext;
    }
    return NULL;
}

Mais ne marche pas, qu'est ce qui ne va pas ? :calim2:

24/11/2012, 16h39
Invité

Bonjour,

Code:

cell *cnext = curr -> next;

et si ta liste est vide (curr == NULL) ?

Sinon, tu n'effectues plus de parcours ici, tu mets à chaque itération curr à cnext.
24/11/2012, 16h44
KhaaB
Le cas où la liste est vide est pris en charge ici :
Code:

1 2 3 4 if (l -> first == NULL) { return 0; }
Je ne comprend pas ce que tu as dis Winjerome, cnext = curr -> next, il y a bien un parcours effectué non ?
24/11/2012, 16h51
Invité

Sauf que tu le prends en charge après.
Si ta liste est vide, tu auras cell *curr = l -> first; qui sera NULL, or ligne suivante, tu tentes de prendre curr -> next;.

Citation:

Envoyé par KhaaB

, cnext = curr -> next, il y a bien un parcours effectué non ?

Je ne vois pas de telle ligne dans ton while, d'où ma remarque.

C'est juste, le cas de la liste vide et de la première cellule marche ici, mais autrement non :

Code:

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
int suppression_premiere_instance(liste *l, void *valeur)
{
    cell *curr = l -> first;
	if (l -> first == NULL)
	{
	    return 0;
	}
	else if (curr -> donnee == valeur)
	{
	    l -> first = curr -> next;
	    free(curr);
	    return 1;
	}
    else
    {
        cell *cnext = curr -> next;
        while (cnext != NULL)
        {
           if (cnext -> donnee == valeur)
            {
                curr -> next = cnext -> next;
                free(cnext);
                return 1;
            }
        curr = cnext;
        }
    }
 
}

Ca ne marche pas, on a le même problème sur cnext qui reste inchangé à l'intérieur de la boucle while.
Je voulais dire un code du style

Code:

1
2
3
4
5
6
7
8
9
10
11
    while (curr->next != NULL)
    {
       if (curr->next->donnee == valeur)
        { 
            cell * p = curr->next ;            
            curr->next = p->next;
            free(p);
            return 1;
        }
        cur = cur->next;
    }

25/11/2012, 17h23
KhaaB

Oh oui, forcément quand on voit la réponse ça devient évident...merci d'avoir pris le temps de m'aider.

Cordialement,

KhaaB