enlever une variable dans une liste chaînée

Version imprimable

Bonjour à tous,

Etant en train de tenter de comprendre les notions de "liste chaînée" (il faut bien un début à tout ;) ) et malgré quelques lacunes, j'arrive un peu à sortir la tête hors de l'eau. J'ai pour l'instant créer une fonction permettant d'ajouter un élément en fin de liste sans trop de soucis. Par contre, j'essaie désespérément de créer une fonction permettant de supprimer un élément en fonction d'une variable et là, c'est le drame.

Voici donc la fonction en question :
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 struct node { char *key; char *value; char *option; struct node *p_next; }; // le code étant assez sommaire ... struct node *remove_item (struct node *p_head, char *key, char *value, char *option) { struct node *p_item = p_head; while (p_item->p_next != NULL) { /* si la variable est dans la liste, supprime */ if (!strcmp(p_item->key, key)) { free(p_item); p_item = p_item->p_next; } else { p_item = p_item->p_next; } } return p_item; }
Supposont que dans mon main(), j'ai ceci :
Code:

1 2 3 4 5 6 7 8 [...] // partie du code pas trop intéressante p_head = add_item (p_head, "directory", "/root", "\0x08"); p_head = add_item (p_head, "shell", "/bin/sh", "\0x08"); p_head = add_item (p_head, "test", "0", "\0x08"); p_head = remove_item (p_head, "test", NULL, NULL);
Je devrais obtenir une liste avec uniquement les variables "directory", "shell" (la variable "test" étant enlevée).

Au lieu de cela, j'obtiens

Citation:

# ./a.out
test = 0
#

Ce qui correspond à la dernière variable. Ce que je tente de faire est-il possible ? Je n'ai pas l'impression d'avoir un algorithme complètement nul par contre je ne vois pas où peut se poser le problème.

Des idées sur le(s) problèmes(s) ?

18/08/2008, 10h42
gl
Tu as au moins un problème ici:
Code:

1 2 3 free(p_item); p_item = p_item->p_next;
p_item ayant été libéré, tu ne peux pas accéder à p_item->p_next. Pour faire ce genre de chose, il faut stocker p_item->p_next dans une variable temporaire

En outre, ni l'élément précédent ni p_head n'étant pas mis à jour, l'élément que tu viens de libérer est bien libéré mais "reste dans la liste".
Il ne suffit pas de libérer la cellule, il fut également maintenir le chaînage de liste.

Bonjour gl,

C'est également ce que je me suis dit mais ça a l'air de fonctionner

J'ai modifié le code selon tes recommendations :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 struct node *p_item = p_head; struct node *p_temp; while (p_item != NULL) { p_temp = p_item->p_next; if (!strcmp(p_item->key, key)) { free(p_temp); p_item = p_item->p_next; } else { printf("%s = %s %s\n", p_item->key, p_item->value, p_item->option); p_item = p_item->p_next; } } return p_item;
J'en ai profité pour ajouter un printf et il semble que ça affiche la variable "directory" et "shell". Le soucis est que cette fonction est censée enlever une variable, et non afficher les autres variables (sans la variable à enlever).

Citation:

Il ne suffit pas de libérer la cellule, il faut également maintenir le chaînage de liste.

Comment procède-t-on pour chaîner p_item à p_head ?

Est-ce cela que tu veux? Je n'ai pas testé cependant...

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
struct node
{
	char *key, *value, *option;
	struct node *p_next;
};
 
 
struct node *remove_item(struct node *p_head, char *key)
{
	struct node *walk, tmp, *nodetofree;
 
	tmp.p_next = p_head;
	for (walk = &tmp; walk->p_next != NULL; walk = walk->p_next)
	{
		if (!strcmp(walk->p_next->key, key))
		{
			nodetofree = walk->p_next;
			walk->p_next = nodetofree->p_next;
			free(nodetofree);
		}
		else
		{
			/* affichage de l'élément */
			...
		}
	}
	return tmp.p_next;
}

tmp permet de traiter le cas où l'élément à supprimer est le premier de la même manière que les autres cas.

Citation:
Envoyé par bisdi
J'ai modifié le code selon tes recommendations :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 struct node *p_item = p_head; struct node *p_temp; while (p_item != NULL) { p_temp = p_item->p_next; if (!strcmp(p_item->key, key)) { free(p_temp); p_item = p_item->p_next; } else { printf("%s = %s %s\n", p_item->key, p_item->value, p_item->option); p_item = p_item->p_next; } } return p_item;
Non, tu continues a utiliser une cellule qui a été libérée (p_item->p_next a été libérée par free(tmp)puisque tmp est égale à p_item->p_next). Et le chaînage n'est toujours pas cohérent.

Une solution relativement simple consiste à ne pas travailler sur l'élément courant mais sur l'élément suivant.
Ce qui oblige à traiter de manière particulière le premier élément et en particulier de modifier l'adresse du premier élément de la liste si nécessaire, ce qui oblige:

Soit à fournir l'adresse de l'adresse du premier élément (double pointeur)
Soit à faire renvoyer par chaque fonction l'adresse du premier élément et donc à avoir des appels du style p_head=remove_item(p_head, ...)

Ce qui n'est pas très élégant. Au passage ta fonction ne renvoie pas l'adresse du premier comme on pourrait si attendre mais systématiquement NULL puisque la condition de sortie de la boucle est p_item == NULL

Personnellement, je n'aime pas trop le fait d'utiliser le premier élément de la liste pour désigner la liste comme tu le fais. Je préfère avoir une structure qui contient les nœuds d'un côté (ta structure node) et une structure correspondant à la liste elle même contenant l'adresse du premier élément, et éventuellement d'autres éléments comme le nombre d'élément ou l'adresse du dernier élément (pas très utile pour une liste par contre, quasi-indispensable pour une file).

Sinon, il y a potentiellement un autre souci avec ton code (mais n'ayant pas le code des fonctions d'ajout, je ne peux pas le garantir) : il est possible qu'il y ait une fuite mémoire à cause des éléments key, value et option de ton nœud, en effet ce sont des pointeurs, ce qui laisse supposé que la mémoire nécessaire est allouée lors de l'ajout de l'élément mais il n'y a pas de libération.

Bonjour,

gl t'explique quasi tout en effet :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct node *p_item = p_head;
	struct node *p_temp;
	
        //traite avant le while si tu veux supprimer p_head
	while (p_item->p_next != NULL)
	{
		p_temp = p_item->p_next;
		if (!strcmp(p_item->key, key))
		{
			free(p_temp);
			p_item = p_item->p_next;
		}
		else
		{
			printf("%s = %s %s\n", p_item->key, p_item->value, p_item->option);
			p_item = p_item->p_next;
		}
	}
	return p_item;/*tu es sûr ? Tu veux renvoyer la tête de la liste chaînée non ?*/

22/08/2008, 14h15
3DArchi

Bonjour,
Pour débuter un petit tour vers les tutos, ça peut être intéressant:
http://nicolasj.developpez.com/articles/listesimple/
et notamment les petits dessins (III.E) expliquant le déchainage de l'élément supprimé.

Bonjour à tous,

Citation:

Envoyé par 3DArchi: c'est vrai qu'avec les schémas, c'est toujours plus simple pour commencer, merci :king:

Citation:

Envoyé par stephl: un peu dans le genre

Citation:

Envoyé par gui80: mauvais copier/coller avec une autre fonction de test :oops:

Citation:

Envoyé par gl

Non, tu continues a utiliser une cellule qui a été libérée (p_item->p_next a été libérée par free(tmp)puisque tmp est égale à p_item->p_next). Et le chaînage n'est toujours pas cohérent.

Une solution relativement simple consiste à ne pas travailler sur l'élément courant mais sur l'élément suivant.
Ce qui oblige à traiter de manière particulière le premier élément et en particulier de modifier l'adresse du premier élément de la liste si nécessaire, ce qui oblige:

Soit à fournir l'adresse de l'adresse du premier élément (double pointeur)
Soit à faire renvoyer par chaque fonction l'adresse du premier élément et donc à avoir des appels du style p_head=remove_item(p_head, ...)

Ce qui n'est pas très élégant. Au passage ta fonction ne renvoie pas l'adresse du premier comme on pourrait si attendre mais systématiquement NULL puisque la condition de sortie de la boucle est p_item == NULL

J'ai effectué quelques modifications pour travailler sur l'élément suivant :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 struct node *remove_item (struct node *p_head, char *key) { struct node *nextElement = p_head->p_next; while (nextElement != NULL) { if (!strcmp(nextElement->key, key)) { p_head = nextElement->p_next; free(nextElement); nextElement = NULL; return p_head; } else { p_head = nextElement; } } return p_head; }
J'ai l'impression maintenant que le problème se trouve dans le "else".

Pour ce qui est de la fonction add_item, il s'agit d'une fonction décrite ici sous le nom add_end.

Citation:

Personnellement, je n'aime pas trop le fait d'utiliser le premier élément de la liste pour désigner la liste comme tu le fais. Je préfère avoir une structure qui contient les nœuds d'un côté (ta structure node) et une structure correspondant à la liste elle même contenant l'adresse du premier élément, et éventuellement d'autres éléments comme le nombre d'élément ou l'adresse du dernier élément (pas très utile pour une liste par contre, quasi-indispensable pour une file).

J'essaie de tester cette méthode justement pour pouvoir mieux maitriser les listes chainées.

Citation:

Sinon, il y a potentiellement un autre souci avec ton code (mais n'ayant pas le code des fonctions d'ajout, je ne peux pas le garantir) : il est possible qu'il y ait une fuite mémoire à cause des éléments key, value et option de ton nœud, en effet ce sont des pointeurs, ce qui laisse supposé que la mémoire nécessaire est allouée lors de l'ajout de l'élément mais il n'y a pas de libération.

J'ai rectifié le problème mais en supposant que j'utilise le même prototype de mon premier post, à savoir struct node *remove_item (struct node *p_head, char *key, char *value, char *option), le fait d'utiliser la fonction comme ceci remove_item(p_head, "shell", NULL, NULL); ne corrige pas justement le défaut :question: