Discussion :

[Yux]

Salut,

Je débute en C et je cherche à implémenter une liste chaînée. Je me suis documenté sur la question, j'ai regardé certains codes existants, et j'ai constaté que la plupart des développeurs prennent soin de différencier les éléments de la liste (les différents noeuds en particulier) des données de l'utilisateur (ce qui paraît à la base plutôt astucieux ).

Pour ce qui est de la création de la liste, j'ai écris ça :

list.h

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
/* structure élément de la liste */
typedef struct
{
  struct node_s *prev;
  struct node_s *next;
  void *data;
} node_s;
 
/* structure liste */
typedef struct
{
  int count;
  node_s *first;
  node_s *current;
  node_s *last;
  int (*compare)(void *, void *);
} list_s;
 
/* constructeur */
list_s *list_create();
 
/* destructeur */
void list_delete(list_s *);

Le code du constructeur est le suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
list_s *list_create()
{
  list_s *list;
  list = malloc(sizeof(list_s));
  if(! list)
  {
    fprintf(stderr, "Dynamic memory allocation failed");
    perror(" ");
    exit(1);
  }
  list->count = 0;
  list->first = list->current = list->last = NULL;
  return list;
}

Jusqu'ici, je considère que ça va (détrompez-moi si ce n'est pas le cas ). Là où je bloque, c'est sur le destructeur. Si j'implémente une fonction qui libère l'espace mémoire réservé pour chaque maillon de la liste, les pointeurs vers les différentes données de l'utilisateur seront perdus, et il lui sera impossible de désallouer la mémoire dédiée aux données.

En fait, j'aurais besoin d'un conseil d'ordre général, compte-tenu du fait que je cherche à écrire le code le plus générique possible (le but étant de le réutiliser dans différentes applications). Faut-il laisser le soin à l'utilisateur de libérér la mémoire allouée pour les données avant d'invoquer le destructeur ou la gestion des données doit-elle être "wrappée" (c'est très laid) par l'implémentation de la liste chaînée ?

Désolé pour ce post un peu long et merci pour vos futures réponses.

[fearyourself]

En fait, j'aurais besoin d'un conseil d'ordre général, compte-tenu du fait que je cherche à écrire le code le plus générique possible (le but étant de le réutiliser dans différentes applications). Faut-il laisser le soin à l'utilisateur de libérér la mémoire allouée pour les données avant d'invoquer le destructeur ou la gestion des données doit-elle être "wrappée" (c'est très laid) par l'implémentation de la liste chaînée ?

Pour quelqu'un qui commence par "Je débute en C", tu t'attaques à un problème déjà d'un certain niveau...

Si tu veux faire le plus générique possible, je te conseillerais de mettre un pointeur vers une fonction de destruction comme tu as fais pour la comparaison. Cette fonction sera mise en place lors de la création de la liste chaînée et appelée lors de la destruction de la liste.

Par contre, lors de ta création de ta liste, tu ne mets pas ta fonction à jour, je te conseillerais de changer le prototype de ta fonction create comme ceci:

Code :

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

1
2
 
list_s *list_create(int (*compare)(void *, void *), void (*destroy)(void *));

Ou au moins mettre le pointeur à NULL...

Jc

[ToTo13]

Bonsoir,
pour ce qui est de la question d'ordre général, il s'agit là d'une question de politique de programmation. Si tu laisses faire l'utilisateur, il faut s'assurer qu'il ne fasse pas de bétise, sinon, il faut que tu le fasse toi meme, ce qui est peut etre mieux.
Pour information, un langage comme le Java ne laisse qu'un minimum de possibilités à l'utilisateur aussi bien qu'au programmeur.
Pour ma part, je pars souvent du principe (et mon expérience me donne souvnat raison) que l'utilisateur va faire n'importe quoi, donc un minimum de liberté s'impose.

En tout cas, les débuts avec des listes chainées... faut oser.

[Emmanuel Delahaye]

Je débute en C et je cherche à implémenter une liste chaînée. <...>
list.h

Code :

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

1
2
/* structure élément de la liste */
<...>

Pas mal. Tu débutes en C, mais visiblement, tu ne débutes pas en programmation... Un détail, j'aurais mis :

Code :

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

1
2
 
  int (*compare)(void const *, void const *);

Quand au style, je dirais qu'il m'est assez familier ! (Mais je mets un p_ devant les pointeurs...)

Le code du constructeur est le suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
list_s *list_create()
{
  list_s *list;
  list = malloc(sizeof(list_s));
  if(! list)
  {
    fprintf(stderr, "Dynamic memory allocation failed");
    perror(" ");
    exit(1);
  }
  list->count = 0;
  list->first = list->current = list->last = NULL;
  return list;
}

Il est préférable que tous les éléments soient initialisé, surtout les pointeurs.

Code :

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

1
2
3
4
5
6
7
8
 
   if (list != NULL)
   {
     static const list_s z = {0};
     *list = z;
 
      /* ... */
   }

Jusqu'ici, je considère que ça va (détrompez-moi si ce n'est pas le cas ). Là où je bloque, c'est sur le destructeur. Si j'implémente une fonction qui libère l'espace mémoire réservé pour chaque maillon de la liste, les pointeurs vers les différentes données de l'utilisateur seront perdus, et il lui sera impossible de désallouer la mémoire dédiée aux données.

Il suffit de sauvegarder l'adresse du suivant avant de détruire le courant... Rien de mystérieux... Sinon, une boucle récursive fait ça très bien en quelques lignes... Il suffit de placer le free() au bon endroit... Mais, la récursion a ses limites, alors attention... Préférer quand même une solution itérative...

En fait, j'aurais besoin d'un conseil d'ordre général, compte-tenu du fait que je cherche à écrire le code le plus générique possible (le but étant de le réutiliser dans différentes applications). Faut-il laisser le soin à l'utilisateur de libérér la mémoire allouée pour les données avant d'invoquer le destructeur ou la gestion des données doit-elle être "wrappée" (c'est très laid) par l'implémentation de la liste chaînée ?

En fait la statégie est simple : chacun son boulot.

Les données appartiennent à l'utilisateur. Il en est responsable. En aucun cas, le gestionnaire générique ne doit libérer brutalement le bloc pointé par node.data, car il ne sait pas ce qu'il y a derrière...

En général, je créée une fonction list() ou traverse() qui permet de parcourir la liste complètement en appelant un fonction utilisateur de type

Code :

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

typedef int list_f (void *p_user, void *p_data);

p_user est l'éventuel contexte utilisateur
p_data est l'adresse du bloc de donnée courant. Si il faut libérer quelquechose, c'est ici.

Prototype de list() :

Code :

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

int list (list_s self, list_f *pf, void *p_user);

Ensuite, on appelle le destructeur qui s'occupe des libérer les maillons (node_s) et la liste (list_s).

[Emmanuel Delahaye]

pour ce qui est de la question d'ordre général, il s'agit là d'une question de politique de programmation. Si tu laisses faire l'utilisateur, il faut s'assurer qu'il ne fasse pas de bétise, sinon, il faut que tu le fasse toi meme, ce qui est peut etre mieux.

En programmation générique, la bibliothèque ne sait pas quelle est la structure des données. Si ça se trouve, node.data pointe vers une chaine

free (chaine) -> UB

ou vers un objet complexe (une liste, par exemple)

free (list) -> 140.000 nodes sont irrémédiablement perdus !

Ce n'est donc pas à elle de prendre ce genre d'initiative.

La programmation générique facilite certaines choses, mais apporte d'autres contraintes. Cependant, une couche d'abstraction intermédiaire peut simplifier le travail de l'utilisateur. Comme souvent, il faut voir le code générique comme un outil permettant de construire des fonctions utilisateur plus facilement et surtout avec de larges parties du code déjà validées. On l'utilise rarement directement en plein milieu d'une application. Trop gore...

[loufoque]

Je ne suis pas certain que le compteur soit utile.
À quoi te sert-il ?

[Emmanuel Delahaye]

Je ne suis pas certain que le compteur soit utile.
À quoi te sert-il ?

A connaitre le nombre d'éléments sans être obligé de parcourir la liste à chaque fois ? Si il y en a 140.000, ca peut finir par ne pas être négligeable... Tout ce qui est précalculé est bon à prendre...

D'ailleurs personellement, je préfère les tableaux dynamiques souples aux listes chainées... Beaucoup plus efficace...

http://emmanuel-delahaye.developpez.com/clib.htm
Module FARR (Flexible ARRays)

[Yux]

Merci à tous pour vos réponses

Emmanuel, je ne comprend pas trop ce que tu entends par contexte utilisateur. Je pensais en ce qui me concerne à un pointeur unique vers le type de donnée chaîné.

D'ailleurs personellement, je préfère les tableaux dynamiques souples aux listes chainées... Beaucoup plus efficace...

he he, si tu pouvais en dire plus... :o

[Emmanuel Delahaye]

D'ailleurs personellement, je préfère les tableaux dynamiques souples aux listes chainées... Beaucoup plus efficace...

he he, si tu pouvais en dire plus... :o

J'ai donné un lien...

[fearyourself]

he he, si tu pouvais en dire plus... :o

Il l'a fait:

http://emmanuel-delahaye.developpez.com/clib.htm
Module FARR (Flexible ARRays)

Par contre, je viens de regarder le code, cela m'étonne que tu n'as pas fait de fonction qui libéres la mémoire, enfin autant que possible.

Explication, suppose que pendant un court moment tu as besoin de 40000 éléments mais pendant 90% du temps, tu as seulement besoin de 100 éléments. Pourquoi n'avoir pas fait une fonction qui permet de dire: "C'est bon tu peux libérer un peu de mémoire"?

Flemme? Pas l'utilité?

En fait, je viens de REregarder ton code, tu n'as pas de fonction qui permet d'enlever un élément, ceci explique donc cela...

Jc

[Yux]

En fait, je viens de REregarder ton code, tu n'as pas de fonction qui permet d'enlever un élément, ceci explique donc cela...

Houla, pas de conclusion hâtive ! Ma question portait sur le destructeur, je n'ai mis que le code concerné

[fearyourself]

En fait, je viens de REregarder ton code, tu n'as pas de fonction qui permet d'enlever un élément, ceci explique donc cela...

Houla, pas de conclusion hâtive ! Ma question portait sur le destructeur, je n'ai mis que le code concerné

Hmm, je parlais du code d'Emmanuel et de ses tableaux dynamiques souples

[PRomu@ld]

Explication, suppose que pendant un court moment tu as besoin de 40000 éléments mais pendant 90% du temps, tu as seulement besoin de 100 éléments. Pourquoi n'avoir pas fait une fonction qui permet de dire: "C'est bon tu peux libérer un peu de mémoire"?

C'est un garbage collector que tu veux ...

[Emmanuel Delahaye]

C'est un garbage collector que tu veux ...

Horrible ! Je suis pour la résponsabilité, pas pour l'assistanat !

[fearyourself]

Explication, suppose que pendant un court moment tu as besoin de 40000 éléments mais pendant 90% du temps, tu as seulement besoin de 100 éléments. Pourquoi n'avoir pas fait une fonction qui permet de dire: "C'est bon tu peux libérer un peu de mémoire"?

C'est un garbage collector que tu veux ...

Oui, je sais mais cela m'étonne que dans une implémentation d'un tableau dynamique souple, on ne mette pas une solution pour réduire la taille du tableau, c'est tout...

Emmanuel disait:

D'ailleurs personellement, je préfère les tableaux dynamiques souples aux listes chainées... Beaucoup plus efficace...

Lorsque je pense à une implémentation d'une liste chaînée, il y a généralement:

- création
- ajout
- suppression
- destruction
- appartient
- estvide

Il est largement possible de faire ceci avec un tableau dynamique souple mais je me demandais juste pourquoi il n'avait pas implémenté DANS sa version, des fonctions de suppressions et après ajouter une petite fonction pour libérer la mémoire si le tableau était trop grand..

C'était de la curiosité, rien de plus rien de moins.... Fermons la parenthèse! Si j'ai du mal à dormir ce soir, demain je créérais un nouveau sujet...



[EDIT] Bien sur je vois que cela dépasserait le cadre d'un tableau... Mais bon, tant qu'à faire... [/EDIT]

[loufoque]

D'ailleurs personellement, je préfère les tableaux dynamiques souples aux listes chainées... Beaucoup plus efficace...

Certaines opérations sont plus coûteuses avec les tableaux dynamiques qu'avec les listes chaînées. Par exemple déplacer un élément ou supprimer un élément au milieu (requiert un memmove), redimensionner (requiert un realloc) ou faire des fusions.

L'intérêt des tableaux c'est surtout l'accès "aléatoire".

[Emmanuel Delahaye]

Lorsque je pense à une implémentation d'une liste chaînée, il y a généralement:

- création
- ajout
- suppression
- destruction
- appartient
- estvide

Il est largement possible de faire ceci avec un tableau dynamique souple mais je me demandais juste pourquoi il n'avait pas implémenté DANS sa version, des fonctions de suppressions et après ajouter une petite fonction pour libérer la mémoire si le tableau était trop grand..

A l'évidence ce n'est pas le même usage.
Si on doit ajouter supprimmer et si on se contente de l'accès séquentiel : -> liste
Si on veut un accès aléatoire et un ajustage de la taille automatique : -> tableaux souples.

Evidemment, on pourrait avoir un tableau indexé, avec des enregisrement marqués 'à supprimmer' que l'on virerai pendant les temps morts... Si j'ai besoin de ça, je prends SQLlite...

Moi, je voulais juste des tableaux que l'on peut agrandir sans se fatiguer, et accéder rapidement. C'est tout...

[Yux]

J'ai regardé le lien, et en l'état actuel de mes connaissances, c'est un peu trop costaud...

Moi, j'en suis encore à écrire ce genre de chose :

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
void list_delete(list_s *list)
{
  if(list->count == 0)
  {
    free(list);
  }
  else
  {
    node_s *a, *b;
    a = list->first;
    b = list->first->next;
    while(1)
    {
      if(b != NULL)
      {
        free(a);
        a = b;
        b = a->next;
      }
      else
      {
        free(a);
        break;
      }
    }
  }
}

...et ça m... grave !

C'est le destructeur que j'ai essayé de mettre en oeuvre d'après vos conseils. A la compilation, j'obtiens les warnings suivants :

list.c: Dans la fonction « list_delete »:
list.c:30: attention : affectation d'un type pointeur incompatible
list.c:37: attention : affectation d'un type pointeur incompatible

Je ne travaille qu'avec des pointeurs sur des structures de type node_s, je ne comprend pas à quoi est due cette erreur... Pour info, la ligne 30 est la suivante :

Code :

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

b = list->first->next;

et la 37 (vous l'auriez deviné) est :

Code :

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

b=a->next;

Please help

[Emmanuel Delahaye]

...et ça m... grave !

Ben oui, tu scies la branche sur laquelle tu es assis...

Code :

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

1
2
3
4
 
   p_old  = p;
   p = p->next;
   free (p_old);

Attention, il y a un petit bug dans la définition de node.

Correction, simplification, mise au point...

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
 
#include <stdlib.h>
 
/* structure élément de la liste */
typedef struct node
{
   struct node *prev;
   struct node *next;
   void *data;
}
node_s;
 
/* structure liste */
typedef struct
{
   int count;
   node_s *first;
   node_s *current;
   node_s *last;
   int (*compare)(void *, void *);
}
list_s;
 
static void list_delete(list_s *list)
{
   struct node *p = list->first;
 
   while (p != NULL)
   {
      struct node *old = p;
      p = p->next;
      free(old);
   }
   free(list);
}
 
int main (void)
{
 
   /* ... */
 
   return 0;
}

[Yux]

Ben oui, tu scies la branche sur laquelle tu es assis...

Oui, effectivement...

Merci beaucoup pour ta réponse détaillée, Emmanuel. Je passe en résolu.