Recherche du précédent pour insertion dans liste chaînée triée

Version imprimable

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:

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:

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

...j'appelle la fonction :

Code:

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...)

18/03/2012, 15h08
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?

Ceci se fait après la recherche du précédent.
Je poste tout 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
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 ;
	}
}

18/03/2012, 15h31
gerald3d
Histoire de bien structurer ton programme tu devrais écrire une fonction supplémentaire. Elle permettra d'initialiser correctement un nouvel élément :
Code:

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:

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.
18/03/2012, 15h50
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:

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.

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:

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 ; } } }

18/03/2012, 16h14
pfandflasche

Pas de changement.
Le problème, c'est que même après la fonction RechPrecedent (càd entre la création d'un nouvel élément et la création des liens), prec n'est pas NULL. C'est l'entrée-sortie qui ne fonctionne pas.
La fonction RechPrecedent semble lire prec (ce qui semble inutile, puisque c'est la sortie qui m'intéresse), et le modifie aussi dans la fonction RechPrecedent, mais le résultat n'est pas retourné à la fonction main(), et donc le programme essaie d'accéder à un prec->suivant qui n'existe pas encore.
(Certes, on pourrait mettre prec comme variable globale, mais on nous a dit que ce serait pas la meilleure solution.)
De toute façon, je pourrai demander à notre prof d'Info ou d'algo la semaine prochaine.
18/03/2012, 16h18
gerald3d

Pardon.

J'ai lu un peu rapidement la déclaration de la fonction. Ce qui t'intéresse c'est la valeur du pointeur prec. Donc il ne faut pas transmettre le pointeur mais l'adresse du pointeur prec. Le prototype devient :

Code:

void RechPrecedent(struct elem *premier, int v, struct elem **prec)

Il te faudra bien entendu modifier les appels à cette fonction en conséquence ainsi que le traitement de prec dans RechPrecedent();.
18/03/2012, 16h31
diogene
Code:

1 2 3 4 5 6 7 8 9 10 main() { .... struct elem *premier, *P ; .... premier = NULL ; do { .... Insertion(v, premier) ;
La fonction Insertion() doit pouvoir modifier premier et ce n'est pas le cas. Les arguments des fonctions sont passés par copie, et il n'est donc pas possible à la fonction de modifier ses arguments d'appel. Pour contourner cela, il faut passer l'adresse de l'argument que la fonction veut modifier. Alors, puisque la fonction sait où il se trouve, elle peut le modifier. Ici on doit avoir

Code:

Insertion(v, &premier) ;

et la fonction est à modifier en conséquence :
Code:

1 2 3 4 5 void Insertion(int v, struct elem ** premier) { ... *premier = ....; }

Qu'est-ce que j'ai oublié ? :calim2:

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
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
81
82
83
84
#include <stdio.h>
#include <stdlib.h>
 
struct elem
{
	int valeur ;
	struct elem *suivant ;
} ;
 
struct elem* new_element()
{
  struct elem* element = (struct elem *) malloc(sizeof(struct elem)) ;
  element->suivant = NULL;
 
  return element;
}
 
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 ;
    }
}
}
 
void Insertion(int v, struct elem ** premier)
{	
	struct elem *P, *prec ;
	P = new_element() ;
	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	
 
	P = premier ;
	while (P != NULL)
	{
		printf("%d", P->valeur) ;
		P = P->suivant ;
	}
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
RechPrecedent(*premier, v, &prec) ;

if (prec == NULL)
	{  
		P->suivant = *premier ;
		*premier = P ;
	}
	else
	{
		P->suivant = prec->suivant ;
		prec->suivant = P ;
	}

Même problème...

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
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
81
82
83
84
#include <stdio.h>
#include <stdlib.h>
 
struct elem
{
	int valeur ;
	struct elem *suivant ;
} ;
 
struct elem* new_element()
{
  struct elem* element = (struct elem *) malloc(sizeof(struct elem)) ;
  element->suivant = NULL;
 
  return element;
}
 
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 ;
    }
}
}
 
void Insertion(int v, struct elem ** premier)
{	
	struct elem *P, *prec ;
	P = new_element() ;
	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	
 
	P = premier ;
	while (P != NULL)
	{
		printf("%d", P->valeur) ;
		P = P->suivant ;
	}
}

18/03/2012, 17h04
Trademark

C'est normal, tu dois déréférencer "prec", *prec = Q ; et *prec = NULL.

Il ne manquait presque rien. Voila ton code opérationnel. tu pourras comparer avec le tiens :

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
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
81
82
83
84
85
86
#include <stdio.h>
#include <stdlib.h>
 
struct elem
{
  int valeur ;
  struct elem *suivant ;
} ;
 
struct elem* new_element()
{
  struct elem* element = (struct elem *) malloc(sizeof(struct elem)) ;
  element->suivant = NULL;
 
  return element;
}
 
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 ;
	}
    }
}
 
void Insertion(int v, struct elem ** premier)
{	
  struct elem *P, *prec ;
  P = new_element() ;
  P->valeur = v ;
 
  RechPrecedent(*premier, v, &prec) ;
 
  if (prec == NULL)
    {  
      P->suivant = *premier ;
      *premier = P ;
    }
  else
    {
      P->suivant = prec->suivant ;
      prec->suivant = P ;
    }
}
 
int
main(int argc, char *argv[])
{
  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	
 
  P = premier ;
  while (P != NULL)
    {
      printf("%d", P->valeur) ;
      P = P->suivant ;
    }
  return 0;
}

18/03/2012, 17h18
pfandflasche

@gerald3d, @diogene, @Trademark

Je vous remercie de votre temps et de votre patience pour mon problème.
Le programme fonctionne désormais sans problèmes !

Merci encore une fois !