Discussion :

[m@tix]

Bonjour,

J'ai créé jusque là un code consistant à répertorier différents objets, chacun contenu dans un maillon. En clair, voici un petit schéma:



Jusque là, tout va bien, voici le code correspondant pour le moment:

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
#include <stdio.h>
 
typedef struct objet {
	int a;
	int b;
} un_objet;
 
typedef struct maillon {
	un_objet * infos;
	struct maillon * suivant;
} un_maillon;
 
un_maillon *ajouterElement(un_maillon *le_maillon, un_objet *l_objet) {
	un_maillon *nouveau_maillon = malloc(sizeof(un_maillon));
 
	nouveau_maillon->suivant = NULL;
	nouveau_maillon->infos = malloc(sizeof(un_objet));
	nouveau_maillon->infos->a = l_objet->a;
	nouveau_maillon->infos->b = l_objet->b;
 
	if (le_maillon == NULL)
		return nouveau_maillon;
	else {
		un_maillon *maillon_courant = le_maillon;
		while (maillon_courant->suivant != NULL)
			maillon_courant = maillon_courant->suivant;
		maillon_courant->suivant = nouveau_maillon;
		return le_maillon;
	}
}
 
int main(void)
{
	un_maillon *le_maillon = NULL;
	un_objet l_objet = { 12, 56 };
 
	le_maillon = ajouterElement(le_maillon, &l_objet);
 
	printf("%d\t%d", le_maillon->infos->a, le_maillon->infos->b);
 
	return 0;
}

Seulement, on m'impose d'inclure dans mon code une structure liste supplémentaire définie ainsi:

Code :

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

1
2
3
4
5
6
7
struct liste{
 
	un_maillon * premier_maillon;
	un_maillon * dernier_maillon;
	un_maillon * maillon_courant; // pour se déplacer dans la liste sans perdre la place du premier maillon
 
};

On aurait alors un schéma comme le suivant:



J'ai essayé d'implanter au code ci-dessus cette structure et les changements que cela entraîne, mais curieusement, je n'y parviens pas... Pouvez-vous me montrer svp?

Merci d'avance!

[diogene]

A l'heure actuelle, tu utilises pour décrire ta liste un simple pointeur sur le premier maillon le_maillon

Code :

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

1
2
3
int main(void)
{
	un_maillon *le_maillon = NULL;

Il s'agit de remplacer ce pointeur par une struct liste pour décrire ta liste.
ajouterElement() va utiliser cette structure. Il n'a plus besoin de renvoyer la tête de liste, mais il peut utilement renvoyer un pointeur sur l'élément ajouté ou NULL en cas d'échec. Ceci permet de traiter une erreur possible dans l'allocation.

Code :

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

1
2
3
4
5
6
7
8
int main(void)
{
   struct liste liste = {NULL,NULL,NULL};
   un_maillon *le_maillon = NULL;
   un_objet l_objet = { 12, 56 };
   le_maillon = ajouterElement(&liste, &l_objet);
   if(le_maillon != NULL)
....

ajouterElement() devient :

Code :

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

un_maillon *ajouterElement(struct liste * liste , un_objet *l_objet) ;

Dans son code, la variable de tête de liste (anciennement le_maillon) est maintenant liste->premier_maillon.
Il faut ajouter la gestion de liste->dernier_maillon et (selon le cahier des charges) celle de liste->maillon_courant.

[m@tix]

Merci pour la réponse!
Avant que je ne tente de faire les modifications qui s'imposent dans le code, je souhaiterais comprendre ce que signifie:

Code :

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

struct liste liste = {NULL,NULL,NULL};

Pourquoi trois "NULL"?

Ensuite, étant donné qu'on me demande de faire une fonction pour initialiser une liste, je pense que la ligne de code ci-dessus va devenir inutile.. non? Concernant cette fonction, cela est-il acceptable?

Code :

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

1
2
3
4
5
6
7
8
int Initialiser_Liste(une_liste * la_liste)
{
	la_liste->premier_maillon = NULL;
	la_liste->dernier_maillon = NULL;
 
	return 0;
 
}

Si oui, comment l'inclure dans le main de test?

Code :

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

1
2
3
4
5
6
7
8
int main(void)
{
   Initialiser_Liste(??);
   un_maillon *le_maillon = NULL;
   un_objet l_objet = { 12, 56 };
   le_maillon = ajouterElement(&liste, &l_objet);
   if(le_maillon != NULL)
....

[diogene]

Pourquoi trois "NULL"?

Pour initialiser les trois pointeurs de struct liste à NULL.

Ensuite, étant donné qu'on me demande de faire une fonction pour initialiser une liste,

Deux options possibles :

- la fonction initialise une liste déjà créée (initialiser les TROIS pointeurs):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
void Initialiser_Liste(struct liste* liste)
{
    liste->premier_maillon = NULL;
    liste->dernier_maillon = NULL;
    liste->maillon_courant= NULL;
}
 
int main(void)
{
   struct liste liste ; // la liste est créée ici
   Initialiser_Liste(&liste);
....

- La fonction crée et initialise la liste (et on écrira en même temps une fonction pour détruire la liste ainsi créée). Elle doit donc être créée par allocation dynamique :

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
struct liste * Initialiser_Liste(void)
{
   struct liste * liste =  malloc(......); // Créer
   if(liste != NULL)
  {	
       liste->premier_maillon = NULL;   // initialiser
        ...
   }
   return liste ;
}
void Detruire_Liste(struct liste * liste)
{
...
}
 
int main(void)
{
   struct liste liste * liste =  Initialiser_Liste() ; // la liste est créée ici
   if(liste != NULL)
   {
    ....
    Detruire_Liste(liste);
    liste = NULL; //par précaution
   }
    else
    {
       ....
     }
 
....

[m@tix]

A première vue, je pense que la seconde solution serait la plus appropriée! J'ai complété ton code, en espérant ne pas m'être trompé..

Code :

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

1
2
3
4
5
6
7
8
9
10
11
struct liste * Initialiser_Liste(void)
{
   struct liste * liste = (struct liste *)malloc(sizeof(liste)); // Créer
   if(liste != NULL)
  {	
       liste->premier_maillon = NULL;   // initialiser
       liste->dernier_maillon = NULL;
       liste->maillon_courant = NULL;
 
   }
   return liste ;

Par contre, est-il vraiment nécessaire de faire une fonction pour la détruire? Si oui pourquoi? Aussi, pourquoi avoir choisi de retourner la liste? Enfin, que retourne exactement cette fonction, et pourquoi?

Ah, si, autre chose: la condition if(liste != NULL) est-elle vraiment indispensable? Après tout, vu que la liste vient tout juste d'être crée, à priori elle est vide non? Et puis même si ce n'était pas le cas (et justement j'ai envie de dire..), pourquoi ne pas l'initialiser?

[Pouet_forever]

Le cast du malloc est inutile !
Et il serait judicieux de ne pas appeler ta structure du même nom le pointeur

Code :

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

struct liste * l_liste = malloc(sizeof(liste));

Par contre, est-il vraiment nécessaire de faire une fonction pour la détruire? Si oui pourquoi? Aussi, pourquoi avoir choisi de retourner la liste? Enfin, que retourne exactement cette fonction, et pourquoi?

Ah, si, autre chose: la condition if(liste != NULL) est-elle vraiment indispensable? Après tout, vu que la liste vient tout juste d'être crée, à priori elle est vide non? Et puis même si ce n'était pas le cas (et justement j'ai envie de dire..), pourquoi ne pas l'initialiser?

Oui, toute mémoire allouée avec un malloc doit être libérée.

Si tu ne retournes pas la liste, ta structure est créée dans la fonction et est accessible ... nul part :p
D'où l'intérêt de renvoyer un pointeur sur cette structure
Elle renvoie un pointeur sur 'struct liste'.

Oui, la condition est nécessaire, parce qu'un malloc peut échouer et donc ton programme planterais
La liste viens d'être créée oui, mais comme elle a été allouée dynamiquement par un malloc elle contient n'importe quoi, d'où la nécessité d'initialiser les champs à NULL. Tu peux aussi utiliser calloc à la place de malloc qui initialise la mémoire allouée à 0.

Voilà, je crois que j'ai répondu à toutes tes questions

[m@tix]

Bonsoir Pouet_forever!

Le cast du malloc est inutile !

cast = ?

Oui, toute mémoire allouée avec un malloc doit être libérée.

passer par un free(...) ne serait-il pas plus simple?

Du coup, je ne vois pas bien ce qui ne va pas dans la fonction d'initialisation présentée dans mon dernier post..

[Pouet_forever]

Le cast c'est forcer le type.
Mettre (struct liste *) avant le malloc ne sert à rien

Quand je dis que toute mémoire doit être libérée je parlais justement du free
Il faut libérer tout ce que tu as alloué.

Ta fonction est correcte, je dirais simplement que si ton malloc échoue tu renvoies un pointeur sur NULL

[m@tix]

Le cast c'est forcer le type.
Mettre (struct liste *) avant le malloc ne sert à rien

On m'a appris à faire comme ça en fait.. ça ne cause aucun dégât de l'y mettre?

Quand je dis que toute mémoire doit être libérée je parlais justement du free
Il faut libérer tout ce que tu as alloué.

Ta fonction est correcte, je dirais simplement que si ton malloc échoue tu renvoies un pointeur sur NULL

Bon, finalement:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
struct liste * Initialiser_Liste(void)
{
   struct liste * la_liste = malloc(sizeof(liste)); // Créer
   if(la_liste != NULL)
  {	
       la_liste->premier_maillon = NULL;   // initialiser
       la_liste->dernier_maillon = NULL;
       la_liste->maillon_courant = NULL;
 
   }
   return liste ;

Ok?
Concernant le cas où le malloc échouerait, je ne vois pas tellement quoi modifier..

[diogene]

On m'a appris à faire comme ça en fait.. ça ne cause aucun dégât de l'y mettre?

Non. C'est inutile en C simplement (mais il faut le mettre en C++)

- Sur ton code :

Code :

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

1
2
3
4
5
   struct liste * la_liste = malloc(sizeof(struct liste)); // Créer
// ou encore
   struct liste * la_liste = malloc(sizeof *la_liste);
....
   return la_liste;

Concernant le cas où le malloc échouerait, je ne vois pas tellement quoi modifier..

Au moins, le main() (ou la fonction appelante) serait prévenue et pourrait émettre un message d'avertissement à l'utilisateur

- Sur le fait de faire une fonction de destruction :

C'est logique : tu as une fonction de construction avec pour pendant la fonction de destruction. Si tu modifies plus tard la construction de l'objet en rajoutant par exemple d'autres membres à la structure, tu n'as qu'à modifier aussitôt le code de destruction sans avoir à chercher où dans ton code tu détruits les objets pour faire les modifications . Les opérations liées à la construction/destruction de la liste sont alors parfaitement localisées dans le code à un seul endroit.

Ici, cette fonction ne contient qu'un free() ?
Peut-être. Mais tu peux aussi avoir envie de détruire en même temps que l'objet liste le contenu de la liste (si tu détruits l'objet liste alors que la liste n'est pas vide, c'est grave : tu auras une fuite mémoire).

[SofEvans]

Non. C'est inutile en C simplement (mais il faut le mettre en C++)

Ah ?

Je ne crois pas que le malloc soit particulierement appriecer en C++.
Pour ce que je sache, les malloc peuvent etre ecris mais ne doivent pas l'etre !

On utilise plus malloc/free en C++ mais new/delete.

Et on fait :
struct liste *la_liste = new (struct liste);

[diogene]

Je ne crois pas que le malloc soit particulierement appriecer en C++...

Je ne pense pas effectivement (et à juste titre), mais le propos ne porte pas ici sur les états d'âmes des programmeurs C++.

[m@tix]

Bonsoir!

Merci pour vos réponses! Du coup, j'ai tenté de refaire le code, mais il semblerait qu'il y ait encore quelques problèmes... Lors du test (voir code), j'ai une "erreur de segmentation"...

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
un_maillon * Ajouter_Objet_Fin(une_liste * la_liste, un_objet * l_objet)
{
 
	if (la_liste->premier_maillon == NULL)
	{
 
		un_maillon * nouveau_maillon = malloc(sizeof(un_maillon));
		nouveau_maillon->suivant = NULL;
		la_liste->premier_maillon = nouveau_maillon;
		nouveau_maillon->infos = malloc(sizeof(un_objet));
		nouveau_maillon->infos = l_objet;
		return nouveau_maillon;
	}
 
	else
	{
		un_maillon * maillon_courant = NULL;
		un_maillon * nouveau_maillon = malloc(sizeof(un_maillon));
 
		while (maillon_courant->suivant != NULL)
			maillon_courant = maillon_courant->suivant;
 
		maillon_courant->suivant = nouveau_maillon;
		nouveau_maillon->infos = malloc(sizeof(un_objet));
		nouveau_maillon->infos = l_objet;
 
		nouveau_maillon->suivant = NULL;
 
		return nouveau_maillon;
 
	}
 
}
 
 
int main(void)
{
 
	un_maillon * le_maillon = NULL;
 
	un_objet * objet_test = Creer_Objet("a","b","c",45);
 
	une_liste * la_liste = Initialiser_Liste();
 
	le_maillon = Ajouter_Objet_Fin(&la_liste,&objet_test);
 
 
	if (la_liste->premier_maillon != NULL)
	{
		printf("%s\n", le_maillon->infos->nom);
		printf("%s\n", le_maillon->infos->carac);
                printf("%s\n", le_maillon->infos->lieu);
		printf("%d\n", le_maillon->infos->quantite);
 
	}
 
return 0;
 
}

Où est le problème? Je tiens à préciser que la fonction Creer_Objet fonctionne parfaitement..

[souviron34]

là tu dupliques de la place(malloc) et du code pour rien.. Et il n'y a pas de tests que les allocations échouent ou non..

Moi je ferais plutôt :

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
un_maillon * Ajouter_Objet_Fin(une_liste * la_liste, un_objet * l_objet)
{
     un_maillon * nouveau_maillon = malloc(sizeof(un_maillon));
     if ( nouveau_maillon != NULL )
       {
	  nouveau_maillon->suivant = NULL;
 	  nouveau_maillon->infos = l_objet; / * Pourquoi recréer ? Il suffit de copier le pointeur */
          if ( la_liste->premier_maillon == NULL )
              la_liste->premier_maillon = nouveau_maillon ;
          else
            {
               un_maillon *elt=la_liste->premier_maillon ;
               while ( elt->suivant != NULL )
                 {
                    elt = elt->suivant ;
                 }
               elt->suivant = nouveau_maillon ;
             }
       }
    return nouveau_maillon ;
 }

enfin dans le main tu testes sur premier_maillon mais tu veux afficher le_maillon...

[diogene]

Quelques remarques compléméntaires sur ton code :

-

Code :

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

1
2
nouveau_maillon->infos = malloc(sizeof(un_objet));
nouveau_maillon->infos = l_objet;

On ne peut jamais avoir ce genre de choses : la deuxième ligne fait que la valeur retournée par le malloc est écrasée. La zone mémoire retournée par malloc devient inaccessible. La première ligne a alors comme seul effet de provoquer une fuite mémoire.

-

Code :

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

1
2
while (maillon_courant->suivant != NULL)
      maillon_courant = maillon_courant->suivant;

La création de la structure une_liste est justement faite pour éviter d'avoir à parcourir la liste à chaque fois. Si on prend soin de maintenir le pointeur dernier_maillon à chaque insertion/suppression, on évite ce parcours.

- Lors de ton appel

Code :

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

     le_maillon = Ajouter_Objet_Fin(&la_liste,&objet_test);

les arguments sont faux et si ton compilateur avait un niveau d'avertissement bien réglé, il te l'aurait signalé : la_liste est du type une_liste * donc &la_liste est du type une_liste ** alors que l'argument attendu par la fonction est du type une_liste *. De même pour objet_test. C'est la cause du plantage.
Tu devrais avoir :

Code :

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

      le_maillon = Ajouter_Objet_Fin(la_liste,objet_test);

- Ta fonction Ajouter_Objet_Fin() devient en regroupant le code et en exploitant le membre dernier_maillon :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
un_maillon * Ajouter_Objet_Fin(une_liste * la_liste, un_objet * l_objet)
{
  un_maillon * nouveau_maillon = malloc(sizeof(un_maillon));
  if(nouveau_maillon != NULL)
  {
     nouveau_maillon->infos = l_objet;
     nouveau_maillon->suivant = NULL;
     if (la_liste->premier_maillon == NULL) // liste vide
         la_liste->premier_maillon = nouveau_maillon;
     else la_liste->dernier_maillon->suivant = nouveau_maillon; //chaînage avec le dernier de la liste
     la_liste->dernier_maillon = nouveau_maillon; // nouveau_maillon est toujours le dernier de la liste
  }
  return nouveau_maillon;
}

[souviron34]

oui mais dans la solution que tu proposes c'est une liste doublement chaînée.. Il faisait une liste simplement chaînée

A part ça, c'est plus détaillé que ce que j'avais mis, mais en gros c'est la même chose...

[m@tix]

Merci pour vos réponses! Comme le dit souviron34, je préfère rester sur les listes simplement chaînées.

Quelques questions sur ton code souviron34; au début, pourquoi faire:

Code :

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

if ( nouveau_maillon != NULL )

?

En effet, moi je pensais distinguer les cas où la liste est vide, c'est à dire lorsque le premier maillon pointe sur null, et le cas où elle ne l'est pas. Dans ce que tu fais, je comprends que tu regardes si le maillon que tu viens de créer est nul ou pas... Pourquoi donc? Quel est l'intérêt par rapport à ce que je viens de dire? Et puis venant d'allouer de la mémoire pour ce nouveau maillon avec le malloc, il peut être nul comme non nul je crois.. Du coup je ne comprends pas trop ce les cas que tu distingues.

Enfin, que représente le pointeur elt concrètement, et quelle est son utilité?

Merci d'avance!

[SofEvans]

Si le nouveau maillon est NULL il ne faut pas l'inserer dans la liste, sinon c'est toutes la liste qui est compromise.
C'est le cas ou malloc echoue.

EDIT : Elt sert a trouver la fin de ta liste simplement chainé de maniere a inserer le nouveau maillon en fin de liste.

[diogene]

oui mais dans la solution que tu proposes c'est une liste doublement chaînée.. Il faisait une liste simplement chaînée

Cette "solution" n'est pas spécialement pour une liste doublement chaînée !! Seul un pointeur de chaînage est utilisé.

A part ça, c'est plus détaillé que ce que j'avais mis, mais en gros c'est la même chose...

Oui, j'ai simplement tenu compte du type définissant la liste mentionné dans le premier post.

[Médinoc]

Pour l'ajout dans les listes chaînées simples, j'ai plutôt tendance à conseiller le parcours indirect:

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
un_maillon ** GetDernierPtr(une_liste *pListe)
{
	un_maillon **ppMaillon = &pListe->premier_maillon;
	while(*ppMaillon != NULL)
		ppMaillon = &(*ppMaillon)->suivant;
	return ppMaillon;
}
 
void AjouterEnDernier(une_liste *pListe, un_maillon *pNouveauMaillon)
{
	un_maillon **ppDernier = GetDernierPtr(pListe);
	*ppDernier = pNouveauMaillon;
}