1. Principes des listes génériques

Une liste générique va donc se représenter visuellement de la manière suivante, ici pour une liste de réels.

et ici pour une liste de personnes.

1.1. Définition du type genlist_t

typedef struct _link {
  void* pval;
  struct _link* next;
} * genlist_t;
        

1.2. API des listes génériques

Comme pour toutes les listes, il est indispensable de pouvoir :

• insérer un élément en tete de liste
• supprimer l'élément en tete de liste
• afficher les éléments d'une liste
• connaître la longueur d'une liste
• etc...

Voici les premieres fonctions simples de l'API.

2. Insertion et suppression en tête

Pour illustrer la suite, nous utiliserons l'exemple d'une liste de personnes. Il est bien entendu que le type utilisé ici n'a aucune importance et que vous pouvez le remplacer par n'importe quel type.

Nous définisons un type person_t ainsi qu'une fonction de création d'une variable de ce type.

          typedef struct  {
            char* firstname;
            char* lastname;
            double reputation;
          }  person_t;
          

            person_t* person_new(char* name, char* surname, double s) {
              person_t* p;
                // Allocation de la structure
              p = calloc(1,sizeof(*p));
              if (p==NULL) return NULL;

                // Allocation de la chaine du nom dans la structure
                // fistname est un pointeur, aucune mémoire n'est allouée pour
                // la chaîne que doit contenir firstname
              p->firstname=calloc(strlen(name)+1,sizeof(char));

                // Copie de la chaîne name dans la structure
              strcpy(p->firstname,name);

                // Même chose pour lastname, mais avec la fonction strdup
                // plus courte à ecrire :-)
              p->lastname=strdup(surname);

                // et le réputation
              p->reputation=s;

              return p;
            }
            

2.1 Insertion en tête

A la différence de la fonction d'insertion classique, l'élément ou objet qui doit être inséré est un pointeur vers un objet qui peut être n'importe quoi i.e. de type void*.

Comme pour l'insertion classique, il faut réaliser les actions suivantes :

• Allouer la mémoire pour le maillon
• Copier le pointeur vers l'objet dans le nouveau maillon (champ val )
• Copier l'adresse de l'ancien maillon de tête dans le nouveau maillon (champ list_next )

Voici le code de la fonction d'insertion, similaire à la fonction classique :

        list_t list_add_first( void* e, list_t l ) {
          list_t p = calloc( 1, sizeof( *p ) );
          if ( NULL == p ) {
            // en cas d'erreur d'allocation, le contrat de la fonction précise :
            //      "retourne la liste non modifiée"
            return l ;
          }
          p->val  = e;
          p->next = l;
          return p;
        }
      

2.2 Suppression en tête

Au contraire de la fonction d'insertion, la fonction de suppression va libérer la mémoire allouée si l'utilisateur le souhaite, ce qui est la majorité des cas.

        void person_delete(person_t* p) {
          if(p!=NULL) {
            free(p->firstname);
            free(p->lastname);
            free(p);
          }
        }
          

La fonction de suppression en tête d'une liste générique réalise donc les actions suivantes :

• Sauvegarder l'adresse de la suite de la liste
• liberer l'objet pointé à l'aide de la fonction de libération fournie en paramètre
• liberer le maillon
• retourner l'adresse de la suite de la liste

        list_t list_del_first( list_t l, void delete(void*) ) {
          // vérification de la précondition avec assert()
          assert ( ! list_is_empty( l ) );

          list_t p = list_next(l);
          if (delete!=NULL) delete(l->val);
          free( l );
          return p;
        }
      

2.3 Exemple

Le code ci dessous illustre utilisation des fonctions d'insertion et de suppresion en tête.

Il suppose que les fonctions person_new, person_delete aient été définies comme ci-dessus par le programmeur

        int main() { list_t maliste;
          person_t* p;

          maliste=list_new();

          // Creation d'une persone
          p=person_new("Albert","Einsten",12000.8);
          // Ajout de cette personnne à une liste de personnes
          maliste=list_add_first(maliste,p);

          // Creation d'une persone
          p=person_new("Nicolas","Copernic",2000.3);
          // Ajout de cette personnne à la liste de personnes
          maliste=list_add_first(maliste,p);

          // Suppresion du premier maillon de la liste
          maliste=list_del_first(maliste,person_delete);
        }
      

3. Parcourir la liste

Là encore, aucune difficulté pour parcourir cette liste. Cela se réalise comme pour les listes classiques.

3.1 Longueur de la liste

Voici l'exemple de la fonction calculant la longueur de la liste. A chaque maillon, on incrémente un compteur qui est la valeur retournée par la liste.

        int list_length(list_t l) {
          int len = 0;
          list_t p;
          for( p=l; ! list_is_empty(p) ; p=p->next ) {
            len ++;
          }
          return len;
        }
      

3.2 Affichage de la liste

L'affichage de la liste est basé sur le même principe : on parcourt la liste maillon par maillon à l'aide d'un pointeur p, et on affiche l'objet sur lequel pointe p->val.

Mais là, petit problème !. Comme pour la fonction list_del_first, la fonction list_print ne sait pas sur quel type d'élément elle travaille.

        void list_print(list_t l, void(*print)(void* e)) {
          list_t p;
          printf("( ");
          p = l;
          while ( ! list_is_empty(p) ) {
            print( p->val );
            printf( " " );
            p = p->next ;
          }
          puts(")");
        }
      

Si nous travaillons sur des personnes pour continuer avec notre exemple, voici la fonction person_print

            void person_print(person_t* e) {
              printf("Nom : %s; ",e->firstname);
              printf("Prenom : %s; ",e->lastname);
              printf("réputation : %lf ",e->reputation);
            }
          

L'usage de cette fonction d'affichage de liste se fait de la manière suivante :

          int main() { list_t maliste;
            person_t* p;

            maliste=list_new();

            // Creation d'une persone
            p=person_new("Albert","Einsten",12000.8);
            // Ajout de cette personnne à une liste de personnes
            maliste=list_add_first(p,maliste);
            .....
            .....
            .....
            list_print(maliste,person_print);
          }
        

et là encore, en founissant une fonction d'affichage, list_print fonctionne pour des listes de n'importe Pourquoi

4. Recherche dans la liste list_lookup

Supposons que nous souhaitions rechercher le premier élément contenant le prénom Albert

Il faut donc parcourir notre liste et retourner le premier maillon qui répond au critère de recherche : ici, ce sera l'égalité du nom.

Notons que l'on pourrait aussi vouloir trouver le premier élément dont le réputation est de 1000 euros.

Nous avons donc 2 problèmes ici :

• Comme pour la fonction list_print par exemple, la fonction de recherche list_lookup ne sait pas sur quel type d'élément elle travaille.
• Le critère de recherche peut être différent selon ce que le programmeur veut trouver. Pour une même liste, on peut donc avoir plusieurs types de recherche. Dans tous les cas, nous utilisons la convention du C qui retourne 0 pour comparer des chaines.
• La ou les valeur(s) recherchées dans les objets de la liste sont des valeurs contenues dans les objets de la liste. Il y aura donc un pointeur vers un objet de ce type dans la fonction de comparaison
• La valeur retournée par notre fonction doit donner accès aux informations de l'objet stocké, soit le nom, le prénom et le réputation dans notre exemple. Les deux solutions sont :
  • retourner le pointeur sur le maillon contenant l'objet ou NULL
  • retourner le pointeur sur l'objet ou NULL
  L'implementation proposée retourne un pointeur sur le maillon répondant au critère.

        list_t list_lookup(list_t l, int (*compare)(void* e1, void* e2), void* tocmp) {
          list_t p;
          for (p = l;! list_is_empty(p); p=p->next)
            if (compare(p->val,tocmp)==0) return p;
          return NULL;
        }
      

Si nous travaillons sur des personnes, voici 4 exemples de fonctions comparant des critères différents :

            int person_cmp_firstname(person_t* e1, char* firstname) {
              return strcmp(e1->firstname,firstname);
            }
            int person_cmp_reputation(person_t* e1, double* reputation) {
              return (e1->reputation==reputation ? 0 : 1);
            }
            int person_cmp_lastname(person_t* e1, char* lastname) {
              return strcmp(e1->lastname,lastname);
            }
            int person_cmp_personn(person_t* e1, person_t* e2) {
              return person_cmp_firstname(e1,e2)
                      || person_cmp_lastname(e1,e2)
                      || person_cmp_reputation(e1,e2) ;
            }
          

L'usage de cette fonction de recherche de liste se fait de la manière suivante :

          int main() {
            list_t maliste, present;
            person_t search;

            maliste=list_new();

            // Creation et Ajout d'une personnne à une liste de personnes
            maliste=list_add_first(person_new("Albert","Einsten",12000.8),maliste);
            // Creation et Ajout d'une personnne à une liste de personnes
            maliste=list_add_first(person_new("Nicolas","Copernic",8000.7),maliste);      .....
            .....
            // Einsten est il dans la liste ?
            present = list_lookup(maliste,person_cmp_firstname,"Albert");
            if (present) {
              person_t* p;
                // S'il est present, on l'affiche
              person_print((person_t *) present->val);
              p = (person_t *) present->val;
                // Et on augmente sa réputation
              p->reputation = 15000.56;
            }
          }
        

5. Un exemple avec plusieurs types de listes

Pour conclure, voici un exemple très simpliste de programme manipulant à la fois des listes de personnes et des listes de voitures.

5.1. Les personnes

Le fichier person.h minimaliste :

              #ifndef PERSON_H
              #define PERSON_H

              #include <stdio.h>
              #include <stdlib.h>
              #include <string.h>

              typedef struct  {
                char* firstname;
                char* lastname;
                double reputation;
              } person_t;

                // Creation d'une personne
              person_t* person_new(char*, char*, double);
                // Destruction d'une personne
              void person_delete(person_t*);
                // Affichage d'une personne
              void person_print(person_t*);
                // Egalité de 2 personnes
              int person_equal(person_t*, person_t* );
                // etc..
              #endif
            

Les implémentations des fonctions dans le fichier person.c ont déjà été données dans la fiche.

5.2. Les voitures

Le fichier car.h minimaliste:

                #ifndef CAR_H
                #define CAR_H
                #include <stdio.h>
                #include <stdlib.h>
                #include <string.h>

                typedef struct  {
                  char* model;
                  int power;
                  double cost;
                } car_t;

                  // Creation d'une voiture
                car_t* car_new(char*, int, double);
                  // Destruction d'une voiture
                void car_delete(car_t*);
                  // Affichage d'une voiture
                void car_print(car_t*);
                  // Egalité de 2 voitures
                int car_equal(car_t*, car_t* );
                  // meme modele
                int car_cmp_model(car_t*, car_t* );
                  // Etc...
                #endif
              

Le fichier car.c minimaliste:

                #include "car.h"

                  // Creation d'une voiture
                car_t* car_new(char* m, int p, double c) {
                  car_t* v = calloc(1,sizeof(*v));
                  if (v) {
                    v->model=strdup(m);
                    v->power=p;
                    v->cost=c;
                  }
                  return v;
                }

                  // Destruction d'une voiture
                void car_del(car_t* v) {
                  if (v) {
                    free(v->m);
                    free(v);
                  }
                }

                  // Affichage d'une voiture
                void car_print(car_t* v) {
                  if (v) {
                    printf("Modele : %s;Puissance:%d;Prix:%lf ",v->model,v->power,v->cost);
                  }
                }

                  // etc.....
              

5.3. Des listes de personnes et de voitures

              #include "list.h"
              #include "car.h"
              #include "person.h"
              int main() {
                person_t personne;
                car_t voiture;

                  // Creation des variables listes de quelquechose
                list_t liste_de_personnes, liste_de_voitures;
                  // Un poiteur sur un maillon
                list_t present=NULL;

                  // Initalisation de la liste de personnes
                liste_de_personnes=list_new();

                // Creation et Ajout d'une personnne à une liste de personnes
                liste_de_personnes=list_add_first(person_new("Albert","Einsten",12000.8),liste_de_personnes);
                // Creation et Ajout d'une personnne à une liste de personnes
                liste_de_personnes=list_add_first(person_new("Nicolas","Copernic",8000.7),liste_de_personnes);

                            // Initalisation de la liste de personnes
                liste_de_voitures=list_new();
                  // Creation et Ajout d'une personnne à une liste de personnes
                liste_de_voitures=list_add_first(car_new("Megane",140,25000.10),liste_de_voitures);
                  // Creation et Ajout d'une personnne à une liste de personnes
                liste_de_voitures=list_add_first(car_new("207",82,18000.7),liste_de_voitures);

                // Einsten est il dans la liste de personnes ?
                present = list_lookup(liste_de_personnes,person_cmp_firstname,"Einsten");
                if (present) {
                  person_t* p;
                    // S'il est present, on l'affiche
                  person_print((person_t *) present->val);
                  puts("");
                  p = (person_t *) present->val;
                    // Et on augmente sa réputation
                  p->reputation = 15000.56;
                }
                // On affiche la liste de personnes
                printf("La liste des personnes : \n");
                list_print(liste_de_personnes,person_print);

                  // On peut ecrire la meme chose avec les voitures.
                present = list_lookup(liste_de_voitures,car_cmp_model,"207");
                if (present) {
                  car_t* p;
                    // S'il est present, on l'affiche
                  car_print((car_t *) present->val); puts("");
                  p = (car_t *) present->val;
                    // Et on change sa puissance
                  p->power = 56;
                }
                // On affiche la liste de voitures
                printf("La liste des voitures : \n");
                list_print(liste_de_voitures,car_print);
              }
            

6. Une petite visite plus générique

Si vous observez attentivement le code des différentes fonctions ci-dessus, vous pouvez observez que la plupart de ces fonctins sont construites sur un modèle à peu près identique.

Elles réalisent 2 choses :

• elles parcourent la liste
• elles réalisent une action sur l'objet pointé par le maillon. Par exemple, afficher cet objet.
• elles réalisent une action sur le maillon lui-même. Par exemple, libérer la mémoire du maillon>

Il existe plusieurs solutions pour profiter de cette similitude, en réalisant une fonction list_visit qui prend paramètres 2 fonctions :

• Une fonction qui réalise l'action sur l'objet pointé par le maillon.
• Une fonction qui réalise l'action sur le maillon.

Voici le code de la fonction list_visit ainsi que celui des fonctions pour déterminer la longueur d'une liste et de destruction d'une liste

            
            size_t list_visit( list_t l, action_t exec_on_value, action_t exec_on_link, void *parm ) {
              size_t ret = 0;
                while ( !list_is_empty( l ) ) {
                  list_t   next = list_next( l );
                  ret += exec_on_value ? (size_t)exec_on_value( list_first( l ), parm ) : 0;
                  ret += exec_on_link  ? (size_t)exec_on_link ( l              , parm ) : 0;
                  l = next;
                }
                return ret;
              }

              // Action pour compter un maillon : juste retourner 1
              int    count_link( void *e, void *parm ) {   return 1;  }
              // Compter les maillons ne realise aucune action sur l'objet d'ou le premier paramètre NULL
              size_t        list_length( list_t l ) {
                return list_visit( l, NULL, count_link, NULL );
              }

              //Action pour liberer un maillon
              int    delete_link( void *link, void *unused ) {
                free( link );
                return 0;
              }
              // liberer la liste : la fonction delete est celle qui doit liberer un objet.
              // C'est person_delete dans.
              list_t        list_delete( list_t l, action_t delete ) {
                list_visit( l, delete, delete_link, NULL );
                return list_new();
              }
            

7. Conclusion

Vous venez de voir comment réaliser des listes dont le code de base sera le même pour toutes les listes que vous utiliserez.