Discussion :

[pfandflasche]

Bonjour,
Je veux écrire une insertion dans une liste chaînée.
Exemple : 2 - 3 - 5 . Je veux insérer le 4.
Donc je dois rechercher le précédent, càd le 3.

J'ai essayé, mais il se plante tout le temps.

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
struct elem
{
	int valeur ; 	struct elem *suivant ;
} ;
 
void RechPrecedent (struct elem *premier, int v, struct elem *prec)
{
	struct elem *Q ;
	char trouve ;
 
	Q = premier ;
	prec = NULL ;
	trouve = 0 ;
 
	while ((trouve == 0) && (Q != NULL))
	{
		if (Q->valeur > v)
		{
			trouve = 1 ;
		}
		else
		{
			prec = Q ;
			Q = Q->suivant ;
		}
	}
}

Après avoir créé mon nouvel élément...

Code :

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

P = (struct elem *) malloc(sizeof(struct elem)) ;

...j'appelle la fonction :

Code :

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

RechPrecedent(premier, v, prec) ;

Pourquoi est-ce que la fonction RechPrecedent ne me sort pas prec == NULL au début, puisqu'on ne rentre même pas dans la boucle (premier == Q == NULL) ?
(Et on nous a dit que travailler avec des variables globales serait trop sale...)

[gerald3d]

Lorsque tu crées un nouvel élément il faut impérativement initialiser suivant à NULL. Sinon n'importe quelle valeur différente de 0 peut être affectée. L'as-tu fait avant d'aller plus loin?

[pfandflasche]

Ceci se fait après la recherche du précédent.
Je poste tout 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <stdlib.h>
 
struct elem
{
	int valeur ;
	struct elem *suivant ;
} ;
 
void RechPrecedent(struct elem *premier, int v, struct elem *prec)
{
    struct elem *Q ;
	char trouve ;
 
	Q = premier ;
	prec = NULL ;
	trouve = 0 ;
 
	while ((trouve == 0) && (Q != NULL))
	{
		if (Q->valeur > v)
		{
			trouve = 1 ;
		}
		else
		{
			prec = Q ;
			Q = Q->suivant ;
		}
	}
}
 
void Insertion(int v, struct elem *premier)
{	
	struct elem *P, *prec, *Q ;
	P = (struct elem *) malloc(sizeof(struct elem)) ; // new(P)
	P->valeur = v ;
 
	RechPrecedent(premier, v, prec) ;
 
	if (prec == NULL)
	{   
		P->suivant = premier ;
		premier = P ;
	}
	else
	{
		P->suivant = prec->suivant ;
		prec->suivant = P ;
	}
}
 
main()
{
	int v ;
	struct elem *premier, *P ;
	char rep ;
 
	premier = NULL ;
	do
	{
		printf("Valeur : ") ;
		scanf("%d", &v) ;
		getchar() ;
 
		Insertion(v, premier) ;
		printf("Continuer ? ") ;
		scanf("%c", &rep) ;
		getchar() ;
	}
	while ((rep == 'o') || (rep == 'O')) ;	
 
	//affichage de toute la liste
	P = premier ;
	while (P != NULL)
	{
		printf("%d", (*P).valeur) ;
		P = P->suivant ;
	}
}

[gerald3d]

Histoire de bien structurer ton programme tu devrais écrire une fonction supplémentaire. Elle permettra d'initialiser correctement un nouvel élément :

Code :

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

1
2
3
4
5
6
7
struct elem* new_element()
{
  struct elem* element = (struct elem *) malloc(sizeof(struct elem)) ;
  element->suivant = NULL;

  return element;
}

À partir de là, dans la fonction main() tu écris premier = NULL ;. Si ta liste a pour référence l'élément premier elle ne contiendra jamais quoi que ce soit. Écris plutôt :

Code :

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

1
2
3
struct elem *premier, *P ;
 
premier = new_element();

Et à chaque fois que tu crées un nouvel élément fais de la même manière.

[pfandflasche]

La création d'un nouvel élément se fait dans la fonction Insertion, c'est du moins ce que nous avons noté en algorithmique.

Code :

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

1
2
     X--------->[  v  |  X---]------> [  v  |  /  ]
  premier

Au départ, premier est NULL.
On créé un nouvel objet, new(P).

Puis, on fait une recherche du précédent, mais puisqu'il y en n'a pas (la liste est vide), la sortie de RechPrecedent devrait être prec == NULL.
P->suivant prendra donc l'adresse de premier (qui est NULL), et premier prendra l'adresse de P.

Si l'insertion ne se faisait pas au début, on aurait un prec non NULL, puis
P->suivant prendrait prec->Suivant...
et prec->Suivant prendrait P.

Mais puisque la fonction RechPrecedent ne sort pas le résultat correct (il devrait m'indiquer prec == NULL), le programme se plante.

J'ai fait les changements que t'as indiqué, mais c'est toujours le même problème.

[gerald3d]

Revois alors l'écriture de la fonction void RechPrecedent(struct elem *premier, int v, struct elem *prec);.

Lorsque tu parcours la liste le seul moyen que tu ais pour savoir si tu es à la fin c'est la valeur du pointeur de l'élément courant égale à NULL. Donc ce ne doit être que la seule condition que l'on doit trouver dans while(); :

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
void RechPrecedent(struct elem *premier, int v, struct elem *prec)
{
  struct elem *Q = premier ;
 
  prec = NULL ;
 
  while (Q != NULL)
  {
    if (Q->valeur > v) break;
    else
    {
      prec = Q ;
      Q = Q->suivant ;
    }
}
}