Bibliothèque de listes chainées

**gege2061** · 16/12/2004, 18h53

Bonjour,
j'ai codé une petite bibliothèque pour la gestion des listes chainées et j'aurai voulue savoir si tout marché bien, pas de bug caché ou d'erreur de programmation... Voivi le code:
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
typedef struct _list
{
  struct _list *prev;
  struct _list *next;
  void *data;
} list;
 
list *list_append( list *, void * );
list *list_remove( list *, const void * );
list *list_next( list * );
list *list_prev( list * );
list *list_first( list * );
list *list_last( list * );
void list_free( list * );
size_t list_length( list * );

list.c

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
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
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
 
list *list_append( list *l, void *data )
{
list *m;
/* --- --- */
  m = malloc( sizeof( *m ) );
  if( m == NULL )
  {
    fprintf( stderr, "Memoire insufisante\n" );
    list_free( l );
    exit( EXIT_FAILURE );
  }
  m->data = data;
  if( l == NULL )
  {
    m->prev = m->next = NULL;
    l = m;
  }
  else
  {
    l = list_last( l );
    m->prev = l;
    m->next = NULL;
    l->next = m;
  }
/* --- --- */
return( list_first( l ) );
}
 
list *list_remove( list *l, const void *lost_data )
{
list *p, *n;
/* --- --- */
  if( l == NULL )
    return( NULL );
  p = l->prev;
  n = l->next;
  lost_data = l->data;
  free( l );
  p->next = n;
  n->prev = p;
/* --- --- */
return( list_first( l ) );
}
 
list *list_next( list *l )
{
/* --- --- */
  if( l == NULL )
    return( NULL );
/* --- --- */
return( l->next );
}
 
list *list_prev( list *l )
{
/* --- --- */
  if( l == NULL )
    return( NULL );
/* --- --- */
return( l->prev );
}
 
list *list_first( list *l )
{
/* --- --- */
  if( l == NULL )
    return( NULL );
  while( l->prev != NULL )
    l = l->prev;
/* --- --- */
return( l );
}
 
list *list_last( list *l )
{
/* --- --- */
  if( l == NULL )
    return( NULL );
  while( l->next != NULL )
    l = l->next;
/* --- --- */
return( l );
}
 
void list_free( list *l )
{
list *p;
/* --- --- */
  l = list_last( l );
  while( l != NULL )
  {
    p = list_prev( l );
    free( l );
    l = p;
  }
  l = NULL;
/* --- --- */
return;
}
 
size_t list_length( list *l )
{
int n = 0;
/* --- --- */
  l = list_first( l );
  while( l != NULL )
  {
    n++;
    l = list_next( l );
  }
/* --- --- */
return( n );
}

Merci.

**Caine** · 16/12/2004, 20h22

Bonsoir,
A première vue rien ne me choque, cette implémentation en vaut une autre

On a eu la même idée en lisant les topics je vois

Les pages sources vont avoir foison de listes chaînées

Cependant, ça manque un peu de commentaires tout ça

**Emmanuel Delahaye** · 17/12/2004, 00h08

Envoyé par gege2061

j'ai codé une petite bibliothèque pour la gestion des listes chainées et j'aurai voulue savoir si tout marché bien, pas de bug caché ou d'erreur de programmation... Voici le code:

Ca a l'air pas mal. J'ai pas compris comment fonctionne list_remove(). A quoi sert le 2 eme parametre ?

**rolkA** · 17/12/2004, 03h42

... En effet l'expression " lost_data = l->data; " modifie simplement la valeur du pointeur lost_data, mais l'utilisateur de la fonction ne peut pas la récupérer.... je veux dire, c'est comme faire ceci:

Code :

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

1
2
3
4
void func(int i)
{
     i = 2;
}

Ici le paramètre réel ne change pas de valeur, seul le paramètre formel i change de valeur.

Si tu veux que l'appelant de list_remove récupère le pointeur data qui était stocké dans l'élément à retirer, il faut que tu modifie un pointeur, en demandant un double pointeur comme argument:

Code :

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

1
2
3
4
5
6
7
 
list *list_remove( list *l, const void **lost_data ) 
{
...
if (lost_data != NULL) *lost_data = l->data;
...
}

A condition bien sûr que j'aie compris ce que tu voulais faire.

**Caine** · 17/12/2004, 08h43

Bravo Rolka, je pense que c'est effectivement ce qu'il veut faire, mais dans ce cas, l'argument lost_data n'a pas besoin d'être const

**rolkA** · 17/12/2004, 08h47

Envoyé par Caine

Bravo Rolka, je pense que c'est effectivement ce qu'il veut faire, mais dans ce cas, l'argument lost_data n'a pas besoin d'être const

j'ai l'habitude de mettre const tout ce qui peut l'être ;-) (sauf si c'est débile comme const void** const lost_data comme argument)
Ici, const void** lost_data signifie que **lost_data ne peut pas être modifié, et çà, çà me paraît tout à fait logique, car la fonction n'est pas censée avoir le droit de modifier les données sur lesquelles pointait le membre data.

**Caine** · 17/12/2004, 08h49

La donnée d'accord, mais le pointeur void * doit être changé

Hors dans le cas de

Code :

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

1
2
 
const void **Data

Je ne suis pas sûr de qui est la constante exactement

[edit]
Non c'est bon, le const semble bien s'appliquer à la donnée pointée du void **, ta méthode est correcte.

Mais, là où je m'interroge sur le code original, c'est sur le test à NULL de lost_data !
[/edit]

**rolkA** · 17/12/2004, 08h52

Rq: j'ai édité mon message.

Envoyé par Caine

La donnée d'accord, mais le pointeur void * doit être changé

Hors dans le cas de

Code :

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

1
2
 
const void **Data

Je ne suis pas sûr de qui est la constante exactement

Là c'est l'expression "**Data" qui est constante.

Quelques autres possibilités:

Code :

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

1
2
3
4
 
const void * const * Data // **Data constant, et *Data aussi
void * const * Data // On peut modifier **Data, mais pas *Data
void ** const Data // On peut tout modifier sauf Data

Or dans notre cas on veut modifier le pointeur " *data_lost ".

**rolkA** · 17/12/2004, 08h58

Envoyé par Caine

là où je m'interroge sur le code original, c'est sur le test à NULL de lost_data !

Pareil, je ne réfléchis pas, c'est du code réflexe:
on on écris *lost_data, donc je vérifie si lost_data est bien différent de NULL... Sinon plantage au cas où il est NULL... C'est possible, imagine que l'utilisateur ne souhaite pas récupérer le pointeur ? Il pourra alors passer la valeur NULL en toute sécurité

mat.M · 17/12/2004, 09h41

j'ai l'habitude de mettre const tout ce qui peut l'être

const est un mot clé du C++ , pas du C si je ne me trompe ?

Sinon pour faire dans la facilité , si le compilateur de l'initiateur de ce post supporte le C++ il peut utiliser la STL

**rolkA** · 17/12/2004, 09h44

Envoyé par mat.M

j'ai l'habitude de mettre const tout ce qui peut l'être

const est un mot clé du C++ , pas du C si je ne me trompe ?

Non, const est standard en C... C++ l'étend aux classes et aux fonctions membres, mais çà existe aussi en C... Tiens le prototype de la focntion strcpy par exemple:

Code :

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

1
2
 
char *strcpy(char *dest, const char *src);

Envoyé par mat.M

Sinon pour faire dans la facilité , si le compilateur de l'initiateur de ce post supporte le C++ il peut utiliser la STL

Yavait pas un brin de C++ dans ce thread

.... Restons dans le C

mat.M · 17/12/2004, 13h54

Tiens le prototype de la focntion strcpy par exemple:

oui mais d'où obtiens-tu ce prototype ????
Dans une aide pour ....C++ ( genre MSDN ) qui couvre aussi le C ??
Est-ce que Kernigan et Ritchie parlent-ils de "const" dans leur ouvrage de programmation du C ?? ( "Le Langage C" )

**rolkA** · 17/12/2004, 13h56

ce n'est qu'un exemple, const C'EST du C standard un point c'est tout, qu'est-ce que tu veux que je te dise ? j'ai n'ai pas la norme mais j'ai le dernier draft paper accessible gratuitement et çà parle de const partout....

Et ce prototype est tiré de la "C runtime library référence" de mon compilo, avec préicisions "C ANSI" (C89 pour mon compilo, donc çà fait quand même bien longtemps).

Qu'est-ce qu'il te faut de plus, qu'Emmanuel confirme ??? Et bien va voir ses sources (http://emmanuel-delahaye.developpez.com/clib.htm) et tu verras aussi du const là où il faut... une interview de K&R peut-être ?

**Trap D** · 17/12/2004, 14h17

Salut
mat.M >> si tu te souviens des prototypes de fonctions du C de K&R c'était ça par exemple :

Code :

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

1
2
3
4
 
main(argc, argv)
int argc;
char *argv[];

Il n'était pas question de const char *.
Je viens de voir sur un site que const existe depuis la norme ANSI.

**Emmanuel Delahaye** · 17/12/2004, 15h39

Envoyé par mat.M

Tiens le prototype de la focntion strcpy par exemple:

oui mais d'où obtiens-tu ce prototype ????

Dans la norme ou dans n'importe quel fichier d'aide pour compilateur C 'ANSI'.

Est-ce que Kernigan et Ritchie parlent de "const" dans leur ouvrage de programmation du C ?? ( "Le Langage C" )

Pas dans l'édition originale, car 'const' (comme 'void') n'existe que depuis la normalisation du C (ANSI 1989, ISO 1990). Ce mot clé est décrit dans le Kernighan et Ritchie ed.2. Il serait temps de se mettre à jour... On en est à C99...

**gege2061** · 17/12/2004, 16h13

Prenons les choses dans l'ordre:

Cependant, ça manque un peu de commentaires tout ça

C'est l'un de mes principaux défauts!

J'ai pas compris comment fonctionne list_remove(). A quoi sert le 2 eme parametre ?

C'est pour que l'utilisateur puisse récupérer son pointer sur les données misent dans la liste.

Pareil, je ne réfléchis pas, c'est du code réflexe:
on on écris *lost_data, donc je vérifie si lost_data est bien différent de NULL... Sinon plantage au cas où il est NULL... C'est possible, imagine que l'utilisateur ne souhaite pas récupérer le pointeur ? Il pourra alors passer la valeur NULL en toute sécurité

Moi non plus sur ce coup la j'ai pas réfléchie!

Merci de votre aide.

**Emmanuel Delahaye** · 17/12/2004, 16h54

Envoyé par gege2061

Cependant, ça manque un peu de commentaires tout ça

C'est l'un de mes principaux défauts!

Ca ne me gène pas si le code est clair, ce qui, dans l'ensemble, est le cas ici.

J'ai pas compris comment fonctionne list_remove(). A quoi sert le 2 eme parametre ?

C'est pour que l'utilisateur puisse récupérer son pointer sur les données misent dans la liste.

Dans ce cas, il faut soit retourner le pointeur, soit passer l'adresse du pointeur. Rien de tout cela n'est fait ici.

**gege2061** · 17/12/2004, 17h03

Envoyé par Emmanuel Delahaye

Dans ce cas, il faut soit retourner le pointeur

Je ne peut pas, je retoune déjà la nouvelle liste.

Envoyé par Emmanuel Delahaye

soit passer l'adresse du pointeur.

Je vais rectifier, merci.

mat.M · 17/12/2004, 17h09

ce n'est qu'un exemple, const C'EST du C standard un point c'est tout, qu'est-ce que tu veux que je te dise ? j'ai n'ai pas la norme mais j'ai le dernier draft paper accessible gratuitement et çà parle de const partout....

eh oh du calme !
Les autres personnes ont démontré AVEC CALME (emannuel et Trap D ) que const existait depuis C99