Discussion :

[Ryzen]

Bonjour à tous,
Dans un programme, je dois insérer des valeurs dans une liste chainée ordonnée (croissante). Je vous poste la partie de mon programme qui ne marche pas. Il doit s'agir d'une erreur très bête aussi excusez-moi de ne pas la voir.

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
main.c
 liste_reservation *R=malloc(200 * sizeof(liste_reservation));
 int saisie;
float arrivee;
(...)
 
 
do {
scanf("%d", &saisie);
(...)
scanf("%f",&arrivee);       
         R=reserver(R,currenttime,arrivee);
         afficher(R);
   }
while (saisie!=4);
free(R) ;
return 0;
}
 
liste.c 
 
liste_reservation *  reserver(liste_reservation * l, float currenttime, float arrivee){
(...)
 l=inserer(arrivee,l);
return l;
}
 
 
liste_reservation * inserer(float arrivee, liste_reservation *l){
   liste_reservation * new=malloc(sizeof(liste_reservation));
   new->aterrissage=arrivee;
   if (l->size==0) {
      new->suivant=NULL;
      new->size=1;
      l=new;
   }
   else if (arrivee>=l->aterrissage) {
      new->suivant=l;
      new->size=l->size+1;
      l=new;
   }
   else {
      liste_reservation *tmp1=l;
      liste_reservation *tmp2=l->suivant;
      while ((tmp2!=NULL)&&(arrivee>tmp2->aterrissage)) {
         tmp1->size++;
         tmp1=tmp2;
         tmp2=tmp2->suivant;
//on "remonte" la liste
}
      tmp1->suivant=new; //insertion du nouvel élément à partir des 2 tmp
      new->suivant=tmp2;
   }
   return l;
}
 
void afficher(liste_reservation *l) { //parcourt la liste pour afficher les heures réservées
   liste_reservation *temp=l;
   while (temp != NULL){
      printf ("%.2f ", temp->aterrissage);
      temp = temp->suivant;
  }
}

je saisis ma valeur d'arrivee dans le main dans la chaine nulle (1ere itération), tout se passe bien... la fonction afficher me renvoie bien la valeur que j'ai saisi dans la chaine... Le probleme est après : je refais la meme chose, mais la 2e valeur a écrasé la 1ere dans le 1er maillon de la chaîne, or je ne vois pas pourquoi ma fonction inserer() ne crée pas - comme je le souhaiterai - un autre maillon pour stocker la 2e valeur (mon R=reserver() serait il en cause?...)
Vous avez une idée?
merci

[Sve@r]

Bonjour

C'est une catastrophe ce code. Je vois du malloc de partout, tu as une liste (donc plusieurs maillons alloués au fil du temps) mais tu ne fais qu'un seul free(), tu nommes tes variables "R", tu as du tmp1, du tmp2 tout ça pour gérer une insertion, tu as un élément "size" (ok tu te dis que créer un élément de gestion c'est une bonne idée ce qui est vrai sauf que l'élément de gestion de la liste on ne le met pas dans le maillon ce qui fait que ton type "liste_reservation" on ne sait pas trop s'il représente la liste ou seulement un de ses maillons !!!)

Il se peut que l'erreur soit toute conne mais rien que la chercher dans ta gestion catastrophique ça va me gonfler et ça ne t'aidera absolument pas.

Mon conseil: commence par te créer une bonne base. Déjà tes types tu les nommes "t_xxx", ça te laissera le champ libre pour nommer tes variables "xxx" et surtout ça facilitera la relecture. Donc tu crées un type pour ton maillon, et aussi un type pour ta liste elle-même. Dans ta liste tu pourras y mettre ton champ "size" et ton premier maillon, et ta fonction d'insertion (qui recevra un pointeur sur ta liste) pourra insérer le nouveau maillon où elle veut, y compris avant le premier puisqu'elle pourra modifier ce premier. Ainsi t'auras plus à faire toutes ces jongleries avec tes fonctions qui reçoivent un maillon en paramètre, le modifient et en renvoient un nouveau. Ca te fera moins de paramètre et une gestion plus saine facilitant en plus l'évolutivité (je vois d'ici l'horreur si on te demande ensuite un nouveau chainage permettant de parcourir la liste dans les deux sens...)

Désolé, quand ça part mal, vaut mieux tout refaire plutôt que continuer dans l'erreur...

[Ryzen]

Bonjour,
Tu me déprimes un peu, c'est rare que j'arrive à faire une liste sans segfault (mais les listes chainées c'est pas mon truc...)
Pour les free je suis bien d'accord, il faut free chaque intermédiaire new.
Pour la taille ça parait logique aussi, mais dès que j'commence à créer une autre structure pour la liste ou des sentinelles, ça m'embrouille.

Pour les tmp1 et tmp2, existe-t-il une autre méthode pour insérer dans une liste ordonnée? Peut-être qu'on peut remplacer le tmp2 par tmp1->suivant (sans conviction) mais l'algo en lui-même est pas "bon"?

[skeud]

Faut reconnaitre que le code est imbitable ^^. Pour résoudre les problème de liste chainée, le plus simple est (et souvent oublié):

Pose sur papier les action que tu veux faire (pas du code, juste du "logi-code").
Pour chaque action, fait les pseudo-code (grace à ça tu trouveras des noms de variable qui seront beaucoup plus parlant que tmp1 etc ....).
Une fois le pseudo-code de fait, tu peux écrire le code correspondant.

Nombre de débutant ne passe pas par cette méthode en voyant les ancien coder directement, la différence c'est que les ancien posent leur pseudo-code dans la tête ou utilise du pseudo-code déjà fait afin de coder.

Je vais donc t'aider, dans un premier temps, définis les action que tu dois faire et le pseudo-code associé, poste le ici, et on te dira les soucis qu'il peut y avoir .
Ensuite je t'aiderais à coder chacune des actions .

[Sve@r]

C'est rare que j'arrive à faire une liste sans segfault (mais les listes chainées c'est pas mon truc...)

Ben faudra que ça le devienne... ou alors envisager une autre branche de l'informatique. Par exemple webdesigner ou bien admin réseau ou ...

C'est dommage parce qu'il y a de l'idée. Tu penses à décomposer ton problème en fonctions, une fonction de réservation, une autre d'insertions, une autre d'affichage. Bon c'est pas un découpage super efficient mais il existe au-moins !!!

Pour les tmp1 et tmp2, existe-t-il une autre méthode pour insérer dans une liste ordonnée? Peut-être qu'on peut remplacer le tmp2 par tmp1->suivant (sans conviction) mais l'algo en lui-même est pas "bon"?

Non ça ne peut pas fonctionner. Déjà parce que ton tout premier test c'est regarder si l->size vaut 0 or nulle part t'as initialisé ce l->size. Donc ta "toute première" insertion ne se fait pas correctement.
Sinon pour la remontée de ta liste ça "a l'air" bon mais punaise, tu pouvais pas leur donner un nom plus explicite style "avant" et "apres" ? Et c'est quoi cette indentation !!! Désolé mais un code ça s'écrit fonctionnellement mais aussi proprement, ne serait-ce que pour pouvoir se relire (et faciliter la lecture aux autres).

Ceci dit tu fais un malloc au tout début que tu stockes dans R puis tu écris R=inserer(). Et dans inserer() tu refais un autre malloc que tu renvoies. Donc de toute façon ton premier malloc (déjà inutile) est quoi qu'il arrive perdu.

Perso, si je devais faire ça, je commencerais par écrire une fonction "reservation()" qui se charge d'allouer un maillon et le remplir avec les valeurs qu'il aura à transporter. La fonction ne fait rien de plus et renvoie le pointeur alloué.
Ensuite une fonction "insertion()" qui se chargerait de placer le maillon à sa bonne place. Elle reçoit en paramètre la liste (un vrai type "t_liste" bien conçu), le maillon à placer et ne renvoie rien vu que la liste elle-même ne change pas (c'est éventuellement son premier élément qui change mais c'est la fonction qui se charge de ça).

Ensuite, ton main() se charge de faire saisir les valeurs et pour chaque valeur saisie, appelle reservation() puis inserer(). Il peut même aller directement appeler inserer(&liste, reservation()) puisque reservation() renvoie le maillon à insérer (un petit bémol tout de même car il faut penser à gérer le cas où l'allocation mémoire échoue mais ça c'est du détail qui pourra être fait ensuite...)

[edit]Tiens, un exemple fonctionnel de liste chainée tel que je l'envisagais hier

Code c :

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
 
typedef struct s_noeud {
	int valeur;
	struct s_noeud *suivant;
} t_noeud;
 
typedef struct {
	t_noeud *premier;
	size_t size;
} t_liste;
 
void liste_init(t_liste *liste)
{
	printf("liste_init (%p)\n", liste);
	liste->premier=NULL;
	liste->size=0;
}
 
void liste_affiche(t_liste *liste)
{
	t_noeud *courant;
 
	printf("liste_affiche (%p)\n", liste);
	if (liste->size == 0)
	{
		printf("liste vide\n");
		return;
	}
 
	printf("taille liste: %zu, premier=%p\n", liste->size, liste->premier);
 
	for (courant=liste->premier; courant != NULL; courant=courant->suivant)
		printf("noeud %p, valeur=%d, suivant=%p\n", courant, courant->valeur, courant->suivant);
}
 
t_noeud *noeud_ajout(int valeur)
{
	t_noeud *noeud;
 
	// Allocation mémoire
	if ((noeud=malloc(sizeof(t_noeud))) == NULL) return NULL;
 
	// Remplissage
	noeud->valeur=valeur;
	noeud->suivant=NULL;
	return noeud;
}
 
t_liste *liste_insere(t_liste *liste, t_noeud *noeud)
{
	t_noeud *courant;
 
	// Check paramètres entrés
	if (noeud == NULL) return NULL;
 
	// Un élément de plus
	liste->size++;
 
	// Liste vide
	if (liste->premier == NULL)
	{
		liste->premier=noeud;
		return liste;
	}
 
	// Premier élément
	if (noeud->valeur < liste->premier->valeur)
	{
		// Le noeud mémorise le premier comme étant son successeur et prend sa place en tant que premier
		noeud->suivant=liste->premier;
		liste->premier=noeud;
		return liste;
	}
 
	// Remontée de la liste en s'arrêtant sur le dernier noeud inférieur à la valeur à insérer
	// Le cas "premier élément" étant déjà traité, on peut alors regarder un noeud "plus loin" que le noeud courant ce qui placera le noeud courant toujours un noeud "en arrière" de l'endroit où la valeur devient plus grande
	for (courant=liste->premier; courant->suivant != NULL && courant->suivant->valeur < noeud->valeur; courant=courant->suivant);
 
	// Le courant est maintenant juste avant le point où le noeud doit s'insérer
	noeud->suivant=courant->suivant;
	courant->suivant=noeud;
	return liste;
}
 
void liste_free(t_liste *liste)
{
	t_noeud *courant;
 
	printf("liste_free (%p)\n", liste);
	courant=liste->premier;
	while (courant != NULL)
	{
		liste->premier=courant;
		courant=courant->suivant;
		printf("free(%p)\n", liste->premier);
		free(liste->premier);
	}
}
 
int main()
{
	t_liste liste;
 
	// Initialisation
	liste_init(&liste);
 
	// Petits tests de bon fonctionnement sur liste vide
	liste_affiche(&liste);
	liste_free(&liste);
 
	// Insertion
	liste_insere(&liste, noeud_ajout(5));
	liste_insere(&liste, noeud_ajout(7));
	liste_insere(&liste, noeud_ajout(8));
	liste_insere(&liste, noeud_ajout(6));
	liste_insere(&liste, noeud_ajout(2));
	liste_insere(&liste, noeud_ajout(4));
	liste_insere(&liste, noeud_ajout(1));
	liste_insere(&liste, noeud_ajout(3));
 
	// Affichage
	liste_affiche(&liste);
 
	// Libération
	liste_free(&liste);
}

En dehors de son bon fonctionnement, on peut faire la différence avec ton code par

• des noms de variables et de fonctions clairs et explicites, avec une petite homogénéisation des noms d'action. Les actions s'appliquant sur la liste commencent par "liste_" et les actions s'appliquant sur un noeud commencent par "noeud_"
• un code aéré, avec une indentation propre pour essayer de donner une lecture agréable
• des commentaires sur chaque petite action individuelle. En plus d'aider un relecteur extérieur à comprendre, ils aident surtout à organiser et focaliser sa pensée sur l'action en cours de programmation

Et cette façon de faire permet (si on veut) de travailler sur plusieurs listes en parallèle
Exemple de 3 listes (seul le main a changé, rien d'autre)

Code c :

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
int main()
{
        // Gestion de 3 listes en parallèle
        // La liste[0] gèrera les nombres entre 0 et 9 
        // La liste[1] gèrera les nombres entre 10 et 99
        // La liste[2] gèrera les nombres entre 100 et 999
        t_liste liste[3];
        size_t i;
        int val;
 
        for (i=0; i < 3; i++)
                liste_init(&liste[i]);
 
        srand(time(NULL) ^ getpid());
 
        // On boucle jusqu'à ce que toutes les listes aient 4 noeuds
        while (liste[0].size < 4 || liste[1].size < 4 || liste[2].size < 4)
        {
                val=rand() % 1000;
                i=val < 100 ?(val < 10 ?0 :1) :2;
                if (liste[i].size < 4)
                        liste_insere(&liste[i], noeud_ajout(val));
        }
 
        for (i=0; i < 3; i++)
        {
                printf("\nListe %zu\n", i);
                liste_affiche(&liste[i]);
        }
        for (i=0; i < 3; i++)
                liste_free(&liste[i]);
}

Et tout est parfaitement géré au niveau mémoire, chaque liste ne gère que ce qui la concerne.

En espérant que tu en feras ton profit...

[Ryzen]

Bonjour!
C'est pas une question de branche, tout s'apprend plus ou moins rapidement selon les gens!
C'est vrai que mon code était pas très clair, enfin disons que sur le coup je voulais surtout qu'il marche (tu vas me dire mettre un nom explicite à la place de tmp1 aurait pas été plus long... exact). Pour l'indentation mon excuse est un copier coller "manuel" (sacrilège?) "en plusieurs fois" sur vim.

Tu as raison pour le type liste, j'ai sûrement par moment confondu l'élément et la liste (puisque si tu ne fais qu'un type, il y a des element* et des element **) mais ça avait tendance à m'embrouiller sur les quelques codes que j'avais vu (mais là c'est compréhensible!).
En tout cas ton code est clair, j'aurais du penser à utiliser un for pour parcourir la chaîne (et pas un while plutôt dégueulasse avec un compteur) et ta façon de diviser le code est meilleure : chaque fonction s'occupe d'une petite étape (et c'est surement plus simple à débugguer).

En tout cas merci!

[gerald3d]

...
En tout cas ton code est clair, j'aurais du penser à utiliser un for pour parcourir la chaîne (et pas un while plutôt dégueulasse avec un compteur) et ta façon de diviser le code est meilleure : chaque fonction s'occupe d'une petite étape (et c'est surement plus simple à débugguer).

En tout cas merci!

En même temps ce n'est pas n'importe qui qui t'as répondu . Il lui arrive même de se mettre à écrire comme parle Maitre Yoda, c'est dire... (http://www.developpez.net/forums/d14...p/#post8057746)