Liste simplement chainée

**sorry60** · 27/11/2005, 21h12

Oui en effet je me suis apperçu en testant qu'il y avait divers probleme...ceux dont tu parles et aussi si l'element à retirer est en tete de liste, ça ne fonctionne pas

J'ai donc pensé faire plusieurs cas :

si l'element à retirer en en tete

si l'element à retirer est en queue

si la liste ne contient qu'un seul element

autres

Voila je pense que ça suffit.
Reste plus qu'à coder ça

**sorry60** · 27/11/2005, 21h47

J'ai corrigé mon 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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
/* Fonction qui retire un element precis */
void retirer(list *p, int valeur)
{
   /* Si la liste ne contient qu'un element */
   if ( (!p->pTete->pSuivant) && (p->pTete->val == valeur) )
   {
		free(p->pTete);
		p->pTete = NULL;
		p->pQueue = NULL;
		return;
	}
	/* Si l'element a supprimer est en tete de liste */
	if( p->pTete->val == valeur )
	{
		node *tmp = p->pTete->pSuivant;
		free(p->pTete);
		p->pTete = tmp;
		return;
	}
	/* Sinon */
	{
		node *prec = p->pTete;
		node *tmp = p->pTete;
 
		/* On se positionne sur l'element a supprimer */
		while( (tmp) && (tmp->val != valeur) )
		{
			prec = tmp;
			tmp = tmp->pSuivant;
		}
		if ( tmp )
		{
			/* Si l'element en en queue de liste */
			if ( p->pQueue->val == valeur )
			{
				free(p->pQueue);
				p->pQueue = prec;
			}
			else
			{
				prec->pSuivant = tmp->pSuivant;
				free(tmp);
			}
		}
		else
		{
			printf("Cet element n'est pas dans la liste.\n");
		}
	}
}

J'ai fais quelques tests, ça a l'air d'aller

Mais encore rien de certain.

**sorry60** · 27/11/2005, 22h15

J'ai testé avec ce main :

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
int main()
{
	/* notre liste bientot chainée ! */
	list maListe = {0};
 
	/* On ajoute quelques elements */
   ajouter(&maListe,1);
   ajouter(&maListe,2);
   ajouter(&maListe,3);
 
   /* On affiche */
   printf("Avant :\n");
   afficher(&maListe);
 
   /* On le retire */
   printf("On retire 2 :\n");
   retirer(&maListe,2);
   /* On affiche */
   afficher(&maListe);
 
   printf("On retire 3 :\n");
   retirer(&maListe,3);
   /* On affiche */
   afficher(&maListe);
 
   printf("On retire 1 :\n");
   retirer(&maListe,1);
   /* On affiche */
   afficher(&maListe);
 
	system("Pause");
	return 0;
}

Ca marche pas du tout :

Avant :
1
2
3
On retire 2 :
1
3
On retire 3 :
1
3
2
On retire 1 :
3
2
Appuyez sur une touche pour continuer...

Je vois pas ce qui cloche dans le code

**Emmanuel Delahaye** · 27/11/2005, 22h46

Envoyé par sorry60

Je vois pas ce qui cloche dans le code

Lorsqu'on retire le dernier élément, le précédent devient le dernier. Tu as bien mis à jour pQueue, mais dans l'élement final il manque la marque de fin.

Le système d'affichage compte dessus et crac!

**sorry60** · 27/11/2005, 23h01

Envoyé par Emmanuel Delahaye

Envoyé par sorry60

Je vois pas ce qui cloche dans le code

Lorsqu'on retire le dernier élément, le précédent devient le dernier. Tu as bien mis à jour pQueue, mais dans l'élement final il manque la marque de fin.

Le système d'affichage compte dessus et crac!

Arf le NULL oui c'est vrai

Mais comment ça se fait que le "2 reapparait alors qu'il est retiré juste avant

On retire 2 :
1
3
On retire 3 :
1
3
2 <===

**sorry60** · 27/11/2005, 23h07

Voila correction faite !

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
/* Fonction qui retire un element precis */
void retirer(list *p, int valeur)
{
   /* Si la liste ne contient qu'un element */
   if ( (!p->pTete->pSuivant) && (p->pTete->val == valeur) )
   {
		free(p->pTete);
		p->pTete = NULL;
		p->pQueue = NULL;
		return;
	}
	/* Si l'element a supprimer est en tete de liste */
	if( p->pTete->val == valeur )
	{
		node *tmp = p->pTete->pSuivant;
		free(p->pTete);
		p->pTete = tmp;
		return;
	}
	/* Sinon */
	{
		node *prec = p->pTete;
		node *tmp = p->pTete;
 
		/* On se positionne sur l'element a supprimer */
		while( (tmp) && (tmp->val != valeur) )
		{
			prec = tmp;
			tmp = tmp->pSuivant;
		}
		if ( tmp )
		{
			/* Si l'element en en queue de liste */
			if ( p->pQueue->val == valeur )
			{
				free(p->pQueue);
				p->pQueue = prec;
				p->pQueue->pSuivant = NULL;
			}
			else
			{
				prec->pSuivant = tmp->pSuivant;
				free(tmp);
				tmp = prec;
			}
		}
		else
		{
			printf("Cet element n'est pas dans la liste.\n");
		}
	}
}

Tampon "lu et approuvé" ??

**Emmanuel Delahaye** · 27/11/2005, 23h12

Envoyé par sorry60

Arf le NULL oui c'est vrai

Mais comment ça se fait que le "2 reapparait alors qu'il est retiré juste avant

On retire 2 :
1
3
On retire 3 :
1
3
2 <===

Parce que le chainage n'est pas détruit. C'est d'ailleurs dangereux, car le bloc n'est plus alloué. Il peut arriver n'importe quoi. Dans un systèmes très nerveux et très multitâche gérant des dizaines de listes en même temps (le moindre moteur de base de données, par exemple), les plantages peuvent être spéctaculaires !

**Emmanuel Delahaye** · 27/11/2005, 23h15

Envoyé par sorry60

Voila correction faite !

<...>
Tampon "lu et approuvé" ??

**sorry60** · 27/11/2005, 23h18

Envoyé par Emmanuel Delahaye

Parce que le chainage n'est pas détruit. C'est d'ailleurs dangereux, car le bloc n'est plus alloué. Il peut arriver n'importe quoi. Dans un systèmes très nerveux et très multitâche gérant des dizaines de listes en même temps (le moindre moteur de base de données, par exemple), les plantages peuvent être spéctaculaires !

Je dois faire quelque chose ? ou ce n'est pas de mon ressort...[/quote]

**sorry60** · 27/11/2005, 23h20

Envoyé par Emmanuel Delahaye

Envoyé par sorry60

Voila correction faite !

<...>
Tampon "lu et approuvé" ??

Edit: enfin il reste encore la fonction clear à faire..facile maintenant !

**sorry60** · 29/11/2005, 20h05

Je viens de pondre une fonction clear, elle semble fonctionner bien, je la poste en esperant un nouveau tampon

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
/* Fonction qui supprime entierement une liste chainée */
void clearListe (list *p)
{
	while ( p->pTete )
	{
		node *tmp = p->pTete->pSuivant;
		free(p->pTete);
		p->pTete = tmp;
	}
}