Discussion :

[Loannvrk]

Bonjour,

j'ai un long tme sur les listes chainées 'que j'ai l'impression d'avoir bine compris) cependant lors de l'exécution de mes deux fonctions de base je beug deja. Voici 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
typedef struct cellule_t cellule_t;
struct cellule_t{
	int donnee;
	cellule_t *suivant;
};
 
cellule_t *creercellule(int donnee){
	cellule_t *liste=malloc(sizeof(cellule_t));
	liste->donnee=donnee;
	liste->suivant=NULL;
	return liste;
}
 
 
void affiche_liste(cellule_t *liste){
	cellule_t *tmp = NULL;
	tmp=liste;
	while (tmp){
		printf("%d\t",tmp->donnee);
	 	tmp=tmp->suivant;
	}
	printf("\n");
}
 
cellule_t *test_liste(){
	int i=0;
	cellule_t *liste = malloc(sizeof(cellule_t));
	cellule_t *tmp = NULL;
	tmp=liste;
	for(;i<5;i++){
		tmp=creercellule(i);
                (((printf("%d\t",tmp->donnee);)))) pour bien vérifier que les donnee sont créer
		tmp=tmp->suivant;
	}
	return liste;
}
 
int main(){
	cellule_t *liste=test_liste();
	affiche_liste(liste);
	return 0;
}

Lors de l'exécution ma machine me renvoie seulement 0 ou 0 1 2 3 4 0 quand je met le printf. Je sais que je realloue de la mémoire avec ma fonction creercellule alors que le tmp en a deja une avec la tmp=liste mais je ne pense pas que cela dérange l'exécution. Ca fait bien 2h que je bloque sur ca alors que le reste de mes fonctions bien plus compliqués fonctionnent.
Merci de vos réponses.

[Bousk]

T'as essayé de dérouler ton algo à la main ? Ça prend 2mn et te montre assez efficacement le problème...

cellule_t *liste = malloc(sizeof(cellule_t)); crée une nouvelle cellule, un maillon de la chaîne
cellule_t *tmp = liste; crée une deuxième variable pointant vers le contenu de liste. Ok pourquoi pas..
for(;i<5;i++){ effectuera une action 5 fois
tmp=creercellule(i); chaque action crée une cellule par laquelle tu accèdes via tmp
tmp=tmp->suivant; } puis tmp pointe vers NULL
return liste; puis on retourne le maillon initial

Et ? À quel moment le lien entre les maillons est fait ?
Où se trouve la libération de toute cette mémoire allouée ?

[Loannvrk]

Je pense que le lien entre les chainons ce fait lorsque le pointeur tmp qui pointe vers NULL se voit justement réallouer de la mémoire par créer_cellule. On a donc en gros :
-tmp et liste qui pointe vers la premiere cellule
-tmp pointe vers une premiere cellule de donnee i grace a creer_cellule. (on lui allouer de la mémoire (une cellule) grace a malloc)
-puis tmp=tmp->suivant qui pointe vers NULL
-(la boucle reccomence) tmp pointe vers une deuxieme cellule de donnee i grace a creer_cellule
etc...
Et pour moi la mémoire alloué par les malloc reste dans le tas et ceci représente justement la liste chainée, et on accès au premier élement de cette liste avec le pointeur liste car on a ''travailler'' avec tmp et non liste donc liste pointe toujours vers la premiere cellule de ma liste. on peut ensuite parcourir la liste avec liste=liste->suivant qui pour moi parcourt la liste creer par ma fonction.

Cependant je savais que le probleme étant en effet le lien antre les maillons car ma fonction affiche_cellule n'affiche que la premiere donnee 0. Mais cependant je ne comprend toujours pas pourquoi le lien entre mes maillons n'est pas effectué.

Je viens de commencer C il a surement des énormes fautes, mais c'est comme ca que je vois mon code, et pour avancer dans quelque chose j'ai besoin de le comprendre parfaitement.

Merci beaucoup pour ta réponse en tt cas, en esperant mieux comprendre la seconde fois.

[dalfab]

Bonjour,

Pour que le lien entre les maillons soit effectué, il faut forcément l'écrire quelque part. Aucune ligne de ton code n'effectue ce lien.
Un pointeur, c'est une mémoire qui contient l'adresse d'une autre mémoire. Le pointeur qui est dans tes maillons doit donc à un moment être rempli avec l'adresse du maillon suivant.
Par exemple, ligne 33 tu écris tmp=tmp->suivant;. Juste avant tmp contient l'adresse du maillon qui vient d'être créé. Donc le code lit la valeur de tmp->suivant qui à cet instant ne peut être que NULL, d'où ceci revient à écrire tmp=NULL;. On vient de modifier la valeur d'une variable locale, la ligne ne sert donc à rien!
Je ne connais que trois manières de comprendre comment gérer un chaînage:
- faire un dessin
- faire un dessin
- ou bien faire un dessin.

Code :

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

1
2
3
4
5
6
7
8
9
10
 avant, on a un maillon :
+---------+------+
| valeur1 | NULL |
+---------+------+
 après, on a deux maillons chaînés
+---------+------+      +---------+------+
| valeur2 |   --------->| valeur1 | NULL |
+---------+------+      +---------+------+
             ^
             |Il a fallu écrire dans cette case, l'adresse du maillon suivant

Chaque itération de ta boucle doit produire

Code :

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

1
2
3
4
5
6
7
8
9
10
11
      +------+      +---------+------+
liste:|   --------->| valeur1 | NULL |   A la fin de la première itération on a ça
      +------+      +---------+------+
 
      +------+      +---------+------+      +---------+------+
liste:|   --------->| valeur2 |   --------->| valeur1 | NULL |   A la seconde, on a ça
      +------+      +---------+------+      +---------+------+
 
      +------+      +---------+------+      +---------+------+      +---------+------+
liste:|   --------->| valeur3 |   --------->| valeur2 |   --------->| valeur1 | NULL |
      +------+      +---------+------+      +---------+------+      +---------+------+

Et avant d'entrer dans la boucle on a :

Code :

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

1
2
3
      +------+
liste:| NULL |        Donc avant la boucle, il n'y pas eu d'allocation!
      +------+

[Sve@r]

Bonjour

Code c :

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

1
2
3
4
5
for(;i<5;i++){
	tmp=creercellule(i);
	(((printf("%d\t",tmp->donnee);)))) pour bien vérifier que les donnee sont créer
	tmp=tmp->suivant;
}

j'ai un long tme sur les listes chainées 'que j'ai l'impression d'avoir bine compris)

En tout cas, t'as bien compris que les parenthèses servaient à grouper certaines opérations. Tout comme Gauvain qui double ses 360° pour doubler les procédures de sécurité, t'as triplé tes parenthèses. Ainsi vraiment aucun risque que printf() soit combiné avec autre chose (d'autant plus qu'il n'y a rien d'autre...). Sauf que t'en as fermé une de plus (probablement aussi pour plus de sécurité je présume...)
Sinon, mis à part la compréhension des listes chainées, as-tu bien compris aussi le rôle de l'opérateur "égal" (opérateur d'affectation !!!) ?

[Loannvrk]

Merci pour vos réponses, c'est vrai que j'ai pas été très vif sur ce probleme...
J'ai donc vite refait ma fonction qui marche. Je vous laisse juger si vous pensez que j'ai compris mes erreurs ou j'ai juste eu de la chance.

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
cellule_t *creercellule(int donnee){
	cellule_t *liste=malloc(sizeof(cellule_t));
	liste->donnee=donnee;
	liste->suivant=NULL;
	return liste;
}
 
 
void affiche_liste(cellule_t *liste){
	cellule_t *tmp = liste;
	while (tmp){
		printf("%d - >\t",tmp->donnee);
	 	tmp=tmp->suivant;
	}
	printf("NULL\n");
}
 
cellule_t *test_liste(){
	int i=0;
	cellule_t *tmp = creercellule(i);
	cellule_t *liste = tmp;
	for(i=1;i<5;i++){
		tmp->suivant=creercellule(i);
		tmp=tmp->suivant;
	}
	return liste;
}
int main(){
	cellule_t *liste=test_liste();
	affiche_liste(liste);
	return 0;
}

Ca m'affiche 0 - > 1 - > 2 - > 3 - > 4 - > NULL

[Loannvrk]

Meme avec un dessin je ne comprend pas la segfault que je me prends dans ce 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
cellule_t *maximum(cellule_t *liste){
	cellule_t *tmp = liste;
	cellule_t *tmp2 = liste;
	cellule_t *tmp3 = NULL;
	while (tmp2){
		tmp2 = tmp2->suivant;
		if (tmp->donnee > tmp2->donnee){
			tmp3=tmp;
		}
		else {
			tmp3=tmp2;
		}
		tmp = tmp->suivant;
		tmp2 = tmp->suivant;
	}
	return tmp3;
}

desolé mais j'ai encore du mal avec les listes j'ai limpression.

[Sve@r]

J'ai donc vite refait ma fonction qui marche. Je vous laisse juger si vous pensez que j'ai compris mes erreurs ou j'ai juste eu de la chance.

Ben mis à part que dans affiche_liste() tu peux remplacer ton while() par un for() (ok c'est du détail mais si on peut faire aussi bien tout en écrivant moins tout en restant lisible c'est toujours mieux), ton truc est correct. Ta fonction test_liste() est un peu confuse en première lecture (pourquoi créer le suivant ?) mais quand on la regarde mieux, on comprend sa logique qui est correcte. Tu peux quand-même l'améliorer en lui mettant le nombre de cellules à créer en paramètre.

Toutefois, quand on manipule une liste, c'est toujours utile de créer une structure dédiée à la liste elle-même. Tu verras qu'ensuite ça t'aide à gérer plus facilement certains cas (comme par exemple quand on doit changer le premier élément).

Meme avec un dessin je ne comprend pas la segfault que je me prends dans ce 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
cellule_t *maximum(cellule_t *liste){
	cellule_t *tmp = liste;
	cellule_t *tmp2 = liste;
	cellule_t *tmp3 = NULL;
	while (tmp2){
		tmp2 = tmp2->suivant;
		if (tmp->donnee > tmp2->donnee){
			tmp3=tmp;
		}
		else {
			tmp3=tmp2;
		}
		tmp = tmp->suivant;
		tmp2 = tmp->suivant;
	}
	return tmp3;
}

Tu vérifies que tmp2 existe, ok. Ensuite tu te positionnes sur son suivant et là, sans vérification, tu traites ce suivant Es-tu certain que ce suivant existe ???

desolé mais j'ai encore du mal avec les listes j'ai limpression.

Ici un exemple complet de liste chainée.

[Loannvrk]

Merci pour ta réponse, je commence à m'y faire.

[Loannvrk]

Sinon as tu un moyen qui me permettrait d'avoir une meuilleur compréhension algorithmique? J'entends par la comment la machine fonctionne, comment elle "réflechit", les méthodes mises en place pour qu'elle fonctionne, etc.. Je pense que ma comprehension en info passe beaucoup par ca.

merci

[Sve@r]

Sinon as tu un moyen qui me permettrait d'avoir une meuilleur compréhension algorithmique? J'entends par la comment la machine fonctionne, comment elle "réflechit", les méthodes mises en place pour qu'elle fonctionne, etc.. Je pense que ma comprehension en info passe beaucoup par ca.

Ben justement, ce qu'il faut que tu comprennes, c'est que la machine ne réfléchit pas. Elle se contente d'exécuter bêtement les opérations que tu lui donnes à faire. C'est donc à toi, qui ne dispose que d'opérations basiques (calculs, mémorisation de valeurs) de les organiser pour arriver au résultat.
Quand tu auras compris ça tu seras à 80% du but. Tu gagneras encore 15% quand tu pourras dérouler ton code "à la main", c'est à dire prendre un papier et y modéliser tes variables et leurs valeurs au fur et à mesure que tu lis ton code (tu aurais fait ça, tu aurais vu de suite le souci avec while (tmp2 /* test tmp2 existe */){tmp2 = tmp2->suivant /* positionnement sur son suivant */; if (tmp->donnee > tmp2->donnee /* examen du contenu du suivant sans vérifier son existence !!! */) ...). Et les 5% restant c'est juste de l'habitude.