Discussion :

[tomjr]

Bonjour,

Pour un projet que j'ai à réaliser en C, je me sers d'une liste chaînée. J'arrive facilement à supprimer le premier élément de la liste. Mais j'aimerais faire une méthode qui parcours la liste et qui supprime l'élément passé en paramètre.

Je me demande si c'est réalisable avec une liste simplement chaînée ou si je suis obligé de passer par une liste doublement chaînée?

Voici le code qui me pose problème:

Ma structure :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
typedef struct listeEntiers
        {
                int valeur;
                struct listeEntiers *prec;
        } listeEntiers ;

Ma méthode pour ajouter :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
void AddEntiers(listeEntiers **p, int Val)
{
	listeEntiers *element = malloc(sizeof(listeEntiers));
	if(!element) exit(EXIT_FAILURE);     /* Si l'allocation a échouée. */
	element->valeur = Val;
	element->prec = *p;
	*p = element;       /* Le pointeur pointe sur le dernier élément. */
}

La méthode pour supprimer qui me pose problème :

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 DeleteEntier(listeEntiers **sl, int i)
{
 
	listeEntiers *tmp;
	listeEntiers *tmp2;
	listeEntiers *tmp3;
	tmp2=(*sl);
	while((*sl) && (*sl)->valeur!=i)
	{
		(*sl)=(*sl)->prec;
		tmp3=(*sl);
		tmp2->prec=tmp3;
		tmp2=tmp2->prec;
	}
 
	tmp = (*sl)->prec;
	free(*sl);
	tmp2->prec=tmp;
	*sl = tmp2;
}

C'est mon premier projet en C alors je galère un peu!

[Gui13]

Parcours ta liste en gardant en mémoire 3 noeuds: le noeud courant, le noeud précédant et le noeud suivant.

Quand le noeud courant contient l'entier que tu cherches, fais pointer suivant->prec ver le noeud précédant que tu as mémorisé.

[tomjr]

Je viens d'essayer mais ça ne marche toujours pas.

Ma liste est constituée de 10-9-8-7. Je souhaite effacer le 8 par exemple. Et bien suite à l'exécution de la méthode ma liste ne contient que 9-7. Le 10 à lui aussi disparu car il n'a été mémorisé nulle part.

Faut-il que je change ma structure pour pointer à la fois vers le suivant et vers le précédent?

C'est peut-être ma méthode qui ne marche pas, voici le nouveau code:

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
void DeleteEntier(listeEntiers **sl, int i)
{
 
	listeEntiers *courant;
	listeEntiers *suivant;
	listeEntiers *precedent;
	courant=(*sl);
	while((*sl) && (*sl)->valeur!=i)
	{
		precedent=(*sl);
		(*sl)=(*sl)->prec;
		courant=(*sl);
		suivant=(*sl)->prec;
	}
	precedent->prec=suivant;
	free(*sl);
	(*sl)=(precedent);
}

[Fabllot]

Bonjour,
c'est normal, tu parcours ta liste avec ton pointeur passé en paramètre... Comme tu le modifies, tu perds la valeur d'origine.

[tomjr]

Et comment je fais pour remédier à ça?

[mualki]

Bonjour,

Si tu ne vois pas comment y remédier je te conseille vivement de revoir les pointeurs avant d'essayer de faire des listes chaînées.

Pour te répondre :
Tu te déplaces dans ta liste à l'aide du pointeur que tu souhaite modifier, du coup lorsque tu te déplaces dans ta liste tu modifies ce pointeur, donc à chaque déplacement tu perds un élément de ta liste.

Ce que Gui13 te suggérait était de te déplacer dans ta liste à l'aide de l'élément courant.

[ironzorg]

Si c'est une pile, un simple pop suffit (ne touche rien). En revanche, visiblement tu veux pop des maillons de la liste en plein milieu de celle ci (contrairement a une pile qui pop seulement le dernier maillon push). Deux solutions:
1) Tu calcules la place du maillon dans la liste (sa position, par exemple 3eme). Tu reparcours la liste et tu sauvegardes le 2eme et le 4eme pour les relier et pop le 3eme.

2) Tu ajoutes un champ *next dans tes maillons et tu l'utilises pour recuperer directement le maillon suivant.

Inconvenients: la methode 1 prend du temps, la 2 prend de la memoire. Perso je prefere faire des listes avec un prev et un next pour des raisons pratiques.

EDIT: Un exemple de la deuxieme methode

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
 
typedef struct	s_list
{
  void		*data;
  struct s_list *prev;
  struct s_list *next;
}		t_list;
 
void		pop_link(t_list *node)
{
  t_list	*next;
  t_list	*prev;
 
  if (!node)
    return;
 
  next = node->next;
  prev = node->prev;
 
  free(node);
 
  if (prev)
    prev->next = next;
  if (next)
    next->prev = prev;
}

[tomjr]

Entre temps j'ai contourné le problème en ajoutant dans une liste temporaire tous les nœuds qui ne contiennent pas la valeur passée en paramètre. C'est surement un peu tordu, mais ça m'a l'air de marcher.

Merci pour vos réponses rapides!