Implémentation d'une liste chaînée
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:
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:
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 :D ). 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.
Re: Implémentation d'une liste chaînée
Citation:
Envoyé par Yux
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:
1
2
|
list_s *list_create(int (*compare)(void *, void *), void (*destroy)(void *)); |
Ou au moins mettre le pointeur à NULL...
Jc
Re: Implémentation d'une liste chaînée
Citation:
Envoyé par Yux
Je débute en C et je cherche à implémenter une liste chaînée. <...>
list.h
Code:
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:
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...)
Citation:
Le code du constructeur est le suivant :
Code:
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:
1
2
3
4
5
6
7
8
|
if (list != NULL)
{
static const list_s z = {0};
*list = z;
/* ... */
} |
Citation:
Jusqu'ici, je considère que ça va (détrompez-moi si ce n'est pas le cas :D ). 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...
Citation:
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:
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:
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).
