[C] Listes chainées et allocation mémoire

Listes chainées et allocation mémoire [C] - C++ - Programmation

Marsh Posté le 12-11-2002 à 02:02:07    

Bonsoir tout le monde,
 
Je me remets au C à l'occasion d'un petit projet d'études, mais j'ai des problèmes très basiques en ce qui concerne la gestion de la mémoire.
 
Par exemple, ajout d'un élement en tête d'une liste chainée :
 
 

Code :
  1. void addql(data** head, data* element){
  3. pixel* courant = *head;
  6. if( *head == NULL ){
  7.  *head = createElement(0,0,0);
  8.  *head = element;
  9. }
  10. else{
  11.  while(courant->next != NULL)
  12.   courant = courant->next;
  14.  courant->next = element;
  16. }
  17.         //free(courant);
  19. }

 
 
element est alloué grâce à la fonction qui suit avant de rentrer ds addql
 
Voici ma fonction createElement :
 

Code :
  1. data* createPixel(int x, int y, int yesno){
  2. data* newData;
  3. newData = (data*)malloc(sizeof(data));
  4. newData->next=NULL;
  6. if( yesno == 1 ){ /*on initialise data avec les valeurs x et y */
  7.  newData->x = x;
  8.  newData->y = y;
  9. }
  11. return newData;
  12. }


 
Ma structure data :
 

Code :
  1. typedef struct _data{
  2. int x;
  3. int y;
  4. struct _data* next;
  5. }data;

 
 
Pour afficher :
 

Code :
  1. void showList(data* head){
  2. int i=0;
  3. data* elementCourant = head;
  5. if ( elementCourant == NULL ){
  6.  printf("Impossible d'afficher la liste : liste vide" );
  7.  return;
  8. }
  10. while( elementCourant != NULL ){
  11.  printf("\nElement %d : %d %d",i,elementCourant->x,elementCourant->y);
  12.  i++;
  13.  elementCourant = elementCourant->next;
  14. }
  15.         //free(elementCourant);
  17. }


 
 
 
Voici donc mes questions :
        - est-ce l'utilisation d'une fonction du type createElement est une bonne idée ou pas ?
         
        - ou et quand faire des free dans mon cas ? Ci-dessus, dans le code de addql, si je mets un free(courant), je perds mon contexte et lorsque j'affiche ma liste avec showList, je boucle infiniment.  
 
        - je fais des free à la fin de mon main, mais lorsque je travaille sur des grosses listes, je suis sur d'avoir de groossses fuites de mémoire car mon programme est tué par le système après un gros swappage de dd ;)(je travaille sous GNU/Linux).
 
 
Merci d'avance à tous et bonne soirée !
 
A+


Message édité par Evadream -jbd- le 12-11-2002 à 02:04:15
Reply

Marsh Posté le 12-11-2002 à 02:02:07   

Reply

Marsh Posté le 12-11-2002 à 11:25:09    

Chuis reveillé !

Reply

Marsh Posté le 12-11-2002 à 11:39:35    

1) Oui, sans aucun doute permis.
2) Le free sert à libérer la mémoire, comme malloc l'a allouée. Donc, tu dois désallouer ta liste lorsque tu ne t'en sers plus.
Typiquement, crée une nouvelle fonction detruisListe, qui sera appellée par l'utilisateur (lorsqu'il n'a plus besoin d'une liste). Par contre, il ne faut pas désallouer la mémoire dans showList. Par définition, c'est une fonction qui ne modifie pas la liste (or désallouer, c'est détruire, donc par définition, c'est modifier).
 
3) Pas nécessairement. C'est peut-être le signe d'une très grosse occupation mémoire du programme, ou d'un plantage ailleurs. De toute façon, ce n'est pas une fuite mémoire qui peut faire planter un programme lorsqu'il se termine (par contre, en cours d'exécution, parce que la machine manque de mémoire, je ne dis pas).
 
Petit conseil supplémentaire : si tu n'as pas de type booléen sous la main, crée t-en un :

Code :
  1. typedef int BOOL;
  3. #define FALSE 0
  4. #define TRUE  1


 
Par contre, ton paramètre yesno dans la fonction createPixel est une mauvaise idée. Il faut toujours initialiser tes champs, et si tu ne sais pas à quelles valeurs initialiser, initialise à zéro.


Message édité par BifaceMcLeOD le 12-11-2002 à 11:59:14
Reply

Marsh Posté le 12-11-2002 à 11:41:14    

Encore merci pour tes judicieux et précieux conseils !
 

Reply

Marsh Posté le 12-11-2002 à 16:14:59    

BifaceMcLeOD a écrit a écrit :

 
Petit conseil supplémentaire : si tu n'as pas de type booléen sous la main, crée t-en un :

Code :
  1. typedef int BOOL;
  3. #define FALSE 0
  4. #define TRUE  1






 
Pour ma culture, tu peux me dire a quoi ca sert ?  
Car perso je trouve ca non seulement inutile, mais limite dangereux. Tant que tu ne t'en sers que dans des affectations, pas de probleme, mais si tu commences a ecrire des trucs comme ce qui suit, c'est euh...
 

Code :
  1. if(blabla == TRUE) {
  2. ...
  3. } else {
  4. ...
  5. }


 
 
sachant que si blabla = 2, par exemple, ca fera pas du tout ce que ca semble faire.

Reply

Marsh Posté le 12-11-2002 à 17:55:09    

Je reconnais que cela n'apporte rien d'autre qu'une aide à la lecture (mais c'est déjà beaucoup).
 
Maintenant, si tu es rigoureux, tu sais que le "if" accepte un booléen (et pas un entier). Donc si "blabla" est de type booléen, il est inutile (voire, en C/C++, effectivement, dangereux) de le comparer avec une des 2 constantes booléennes pour obtenir un booléen, puisque c'en est déjà un.
 
Et c'est vrai dans tous les langages, pas seulement en C++. Exemple, en Java, écrire "if (isOpen == false) ..." est tout aussi stupide. Il faut écrire "if (!isOpen) ..." ; c'est plus simple, et toujours clair à lire et à transcrire dans une langue humaine ("if not is-open..." = "si ce n'est pas ouvert..." : c'est clair, non ?).
 
De toute façon, en C/C++, ce que j'ai donné revient à un simple #define, donc le problème que tu soulèves reste si on utilise 1 et 0 au lieu de TRUE et FALSE. La différence, c'est que quand tu lis BOOL dans le programme, c'est tout de suite plus clair que la variable derrière est booléenne. Et justement, ce sera une bonne raison pour ne pas faire de comparaison explicite dans le "if"...


Message édité par BifaceMcLeOD le 12-11-2002 à 17:57:02
Reply

Marsh Posté le 13-11-2002 à 00:04:31    

Bonjour, me revoilà car j'ai un problème de compréhension :
 
Prenons cette fonction :
 

Code :
  1. void addql(data** head, data* element){
  3. data* courant = *head;
  6. if( *head == NULL ){
  7. *head = createElement(0,0,0);
  8. *head = element;
  9. }
  10. else{
  11. while(courant->next != NULL)
  12.   courant = courant->next;
  13.  
  14. courant->next = element;
  15.  
  16. }
  17.        //free(courant);  
  19. }


 
 
Si j'ajoute 1000 élements à ma liste, je vais créer 1000 fois un pointeur data* courant, il ne faut pas que je le désalloue ? Si je fais un free sur ce pointeur, je désalloue la mémoire pointée, donc *head c'est ca ?
 
Je viens de me rendre compte que ce que je viens de dire est idiot car dès que je sors de ma fonction, courant n'existe plus  comme tout autre variable local à cette fonction ? Il ne faut donc pas désalloué courant sous peine de perdre *head, c'est ca ?
 
 
Je m'inquiete, je dois avoir un réel problème de conception de mon programme, car dès que je dépasse une certaine valeur de taille de données, mon processus est tué par le sytème. Je sais que mon algorithme est vraiment naif, mais c'est la première fois que je travaille avec des entités aussi "grosses, je n'ai donc jamais été confronté à ce genre de problèmes =)
 
 
Merci d'avance à tous !
 
A+


Message édité par Evadream -jbd- le 13-11-2002 à 00:21:50
Reply

Marsh Posté le 13-11-2002 à 03:57:39    

BifaceMcLeOD a écrit a écrit :

Maintenant, si tu es rigoureux, tu sais que le "if" accepte un booléen (et pas un entier).


Yep !
==true en C++ est tout aussi foireux que ==TRUE en C, mais c'est la comparaison inutile qui est en trop, pas le type booléen qui est très bien.


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Marsh Posté le 13-11-2002 à 10:26:17    

Evadream -jbd- a écrit a écrit :

Bonjour, me revoilà car j'ai un problème de compréhension :
 
Prenons cette fonction :
 

Code :
  1. void addql(data** head, data* element){
  3. data* courant = *head;
  6. if( *head == NULL ){
  7. *head = createElement(0,0,0);
  8. *head = element;
  9. }
  10. else{
  11. while(courant->next != NULL)
  12.   courant = courant->next;
  13.  
  14. courant->next = element;
  15.  
  16. }
  17.        //free(courant);  
  19. }


 
 
Si j'ajoute 1000 élements à ma liste, je vais créer 1000 fois un pointeur data* courant, il ne faut pas que je le désalloue ? Si je fais un free sur ce pointeur, je désalloue la mémoire pointée, donc *head c'est ca ?
 
Je viens de me rendre compte que ce que je viens de dire est idiot car dès que je sors de ma fonction, courant n'existe plus  comme tout autre variable local à cette fonction ? Il ne faut donc pas désalloué courant sous peine de perdre *head, c'est ca ?
 
 
Je m'inquiete, je dois avoir un réel problème de conception de mon programme, car dès que je dépasse une certaine valeur de taille de données, mon processus est tué par le sytème. Je sais que mon algorithme est vraiment naif, mais c'est la première fois que je travaille avec des entités aussi "grosses, je n'ai donc jamais été confronté à ce genre de problèmes =)
 
 
Merci d'avance à tous !
 
A+




Attends, attends, j'ai peut-être été trop vite dans mes réponses hier.
Dans le principe, définir une fonction qui rassemble toutes les instructions qui initialisent un noeud, c'est bien. Maintenant, si la question, c'est "est-ce qu'appeler cette fonction createElement comme c'est fait ici, c'est approprié ?", la réponse est différente. Et je crains que ce soit non. Je détaille.
 
if( *head == NULL ){
Ici on suppose que head est un pointeur valide. Admettons. Si ce pointeur est NULL, on rentre dans le bloc "then" du "if". OK.
 
*head = createElement(0,0,0);
Par l'appel à createElement, on alloue de la mémoire et on l'initialise. Puis on afecte l'adresse de cette zone mémoire à la zone mémoire pointée par head, qui contient elle-même l'adresse d'une autre zone mémoire (double pointeur). OK.
 
*head = element;
On affecte l'adresse mémoire contenu dans element à *head. La précédente adresse que contenait *head est donc perdue, puisqu'on ne l'a pas gardée ailleurs ==> fuite mémoire. En l'occurrence, l'appel à createElement est ici inutile.
 
Maintenant, voyons ta question.
 
Si j'ajoute 1000 élements à ma liste, je vais créer 1000 fois un pointeur data* courant, il ne faut pas que je le désalloue ? Si je fais un free sur ce pointeur, je désalloue la mémoire pointée, donc *head c'est ca ?
Oui, dans le principe : si tu alloues, il y a un jour où tu devras désallouer. Mais ici, addql ne devrait pas avoir à faire d'allocation mémoire, car cette fonction suppose que tout est déjà alloué comme il faut : en particulier "element" qui est un pointeur valide sur une structure de type "data" .
 
Attention, par définition, un "pointeur courant" est un pointeur qui se balade sur des noeuds existants. On ne fait pas d'allocation directe dans ce pointeur, et donc on ne fait pas de désallocation dessus. Il est juste un moyen d'accéder aux différents élements d'une liste (ou d'une structure plus complexe).
Par contre, il est possible que tu doives faire des allocations dans des zones mémoires pointées par ton pointeur baladeur. Dans ce cas, ce sont tes noeuds qui reçoivent les adresses des nouvelles zones mémoires, pas ton pointeur baladeur lui-même.
 
Ici, si tu retires l'appel à "createElement", ta fonction "addql" me paraîtra correcte.


Message édité par BifaceMcLeOD le 13-11-2002 à 10:31:54
Reply

Marsh Posté le 13-11-2002 à 10:39:00    

Clair, net et précis.
 
Encore merci pour tes explications !

Reply

Marsh Posté le 13-11-2002 à 10:39:00   

Reply

Marsh Posté le 22-11-2002 à 01:14:55    

Hello tout le monde !
 
J'ai tout remis à plat, et, on se moque pas... je ne désallouais pas la mémoire de mes listes lorsque je ne les utilisais plus...
 
J'ai fait des fonctions pour désallouer l'ensemble d'une liste ( et pas slt la tete.... :D) et avec tous les conseils que j'ai eu, je suis arriver à un résultat propre !
 
Merci encore !
 
A+

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed