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

**pfandflasche** · 18/03/2012, 14h53

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

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** · 18/03/2012, 15h12

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** · 18/03/2012, 15h31

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** · 18/03/2012, 15h50

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** · 18/03/2012, 16h02

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

**pfandflasche** · 18/03/2012, 16h14

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.

**gerald3d** · 18/03/2012, 16h18

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 :

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

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

**diogene** · 18/03/2012, 16h31

Code :

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

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 :

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

 Insertion(v, &premier) ;

et la fonction est à modifier en conséquence :

Code :

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

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

**pfandflasche** · 18/03/2012, 16h45

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

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

**gerald3d** · 18/03/2012, 16h49

Code :

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

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

**pfandflasche** · 18/03/2012, 17h00

Même 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
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 ;
	}
}

**Trademark** · 18/03/2012, 17h04

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

**gerald3d** · 18/03/2012, 17h10

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

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

**pfandflasche** · 18/03/2012, 17h18

@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 !

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

C

Discussions similaires

Partager

Partager