Cours 2: Le type Liste.

Une liste est une suite finie, possiblement vide, d'éléments repérés par leur rang dans la liste.
Les opérations sur listes comprennent la création d'une liste vide, la consultation de l'élément de rang r , l'insertion d'un élément e au rang r , la suppression de l'élément de rang r et la consultation de la longueur de la liste (son nombre d'éléments).
Une liste doit pouvoir être parcourue séquentiellement, ce qui peut se faire en se positionnant au rang r , en avançant à l'élément suivant et en consultant l'élément courant. Le type abstrait Position permet de définir des repères sur les éléments de la liste. Les opérations du type Position sont le repérage d'un élément de rang donné et le repérage du successeur.
Voici ci-dessous la signature du type abstrait Liste .

Liste creer_liste();
Element_liste lire_liste(Liste l, unsigned int rang);
Liste supprimer_liste(Liste l, unsigned int rang);
Liste inserer_liste(Liste l, unsigned int rang, Element_liste e);
unsigned int longueur_liste(Liste l);
Position positionner_liste(Liste l, unsigned int rang);
Position suivant_liste(Liste l, Position p);
Element_liste lire_courant_liste(Liste l, Position p);
// l: Liste; e: Element_liste; r, i: unsigned int; p: Position
// préconditions:
//   positionner_liste(l, r) est-défini-ssi 0<=r<=longueur_liste(l)-1
//   lire_liste(l, r) est-défini-ssi 0<=r<=longueur_liste(l)-1
//   supprimer_liste(l, r) est-défini-ssi 0<=r<=longueur_liste(l)-1
//   inserer_liste(l, r, e) est-défini-ssi 0<=r<=longueur_liste(l)
//   (quand r == longueur_liste(l), on ajoute en fin de liste)
//   suivant_liste(l, p) est-défini-ssi
//     p!=positionner_liste(l, longueur_liste(l)-1)
//   lire_courant_liste(l, p) est-défini-ssi longueur_liste(l)>0
// axiomes:
//   longueur_liste(creer_liste()) == 0
//   0<=r<=longueur_liste(l) - 1 =>
//     longueur_liste(supprimer_liste(l, r)) == longueur_liste(l) - 1
//   0<=r<=longueur_liste(l) =>
//     longueur_liste(inserer_liste(l, r, e)) == longueur_liste(l) + 1
//   0<=r<=longueur_liste(l) - 1 && 0<=i<r =>
//     lire_liste(supprimer_liste(l, r), i) == lire_liste(l, i)
//   0<=r<=longueur_liste(l) - 1 && r<=i<=longueur_liste(l) - 2 =>
//     lire_liste(supprimer_liste(l, r), i) == lire_liste(l, i + 1)
//   0<=r<=longueur_liste(l) && 0<=i<r =>
//     lire_liste(inserer_liste(l, r, e), i) == lire_liste(l, i)
//   0<=r<=longueur_liste(l) && i == r =>
//     lire_liste(inserer_liste(l, r, e), i) == e
//   0<=r<=longueur_liste(l) && r<=i<=longueur(l) =>
//     lire_liste(inserer_liste(l, r, e), i) == lire_liste(l, i - 1)
//   0<=r<longueur_liste(l) - 1 =>
//     suivant_liste(l, positionner_liste(l, r)) == positionner_liste(l, r + 1)

Le premier axiome impose qu'une liste soit vide à sa création.
Le second axiome impose qu'après une suppression réussie, la longueur de la liste ait été diminuée d'une unité.
Le troisième axiome impose qu'après une insertion réussie, la longueur de la liste ait été augmentée d'une unité.
Le quatrième axiome impose qu'après une suppression réussie au rang r , les éléments de rangs inférieurs ne soient pas modifiés.
Le cinquième axiome impose qu'après une suppression réussie au rang r , les éléments de rangs supérieurs soient décalés au rang précédent.
Le sixième axiome impose qu'après une insertion réussie au rang r , les éléments de rangs inférieurs ne soient pas modifiés.
Le septième axiome impose qu'après une insertion réussie au rang r , l'élément de rang r soit l'élément inséré.
Le huitième axiome impose qu'après une insertion réussie au rang r , les éléments de rangs supérieurs soient décalés au rang suivant.
Le neuvième axiome impose qu'en avançant d'une position p correspondant à l'élément de rang r avant le dernier de liste, on se retrouve positionné sur l'élément de rang r+1 .

Voici une implémentation possible du type Liste . La liste est représentée par un tableau d'éléments. Une conséquence de ce choix est que la liste a une taille maximale. Cette taille est définie dans le fichier liste_en_table.h .
Le fichier liste_en_table.h est la spécification que doit importer tout algorithme employant une liste implémentée comme une table. Cette spécification regroupe la spécification de liste (donnée ci-dessus) et la définition de la taille maximale.
Ainsi, on peut imposer, pour les listes en tables, une précondition à l'insertion pour éviter d'aller au delà de la taille maximale. En rendant cette taille maximale visible dans le fichier liste_en_table.h on permet aux utilisateurs de listes en tables de vérifier la précondition avant de tenter l'insertion.
Rappelons que le code de vérification des préconditions est inhibé (mis en commentaire) une fois l'implémentation validée.

// fichier liste_en_table.c
#include <stdio.h>
#include "liste_en_table.h"
typedef Element_liste *Table;
typedef struct {unsigned int longueur; Table t;} St;
Liste creer_liste() {
 St *s;
 s = (St *) malloc(sizeof(St));
 s->t = (Table) malloc(sizeof(Element_liste)*TAILLE_LISTE);
 s->longueur = 0;
 return (Liste) s;
}
Element_liste lire_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "lire_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 return (((St *)l)->t[rang]);
}
Liste supprimer_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 unsigned int i;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "supprimer_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 free(((St *)l)->t[rang]);
 for (i=rang+1; i<longueur_liste(l); i++)
  ((St *)l)->t[i-1] = ((St *)l)->t[i];
 ((St *)l)->longueur--;
 return l;
}
Liste inserer_liste(Liste l, unsigned int rang, Element_liste e) {
// précondition: 0<=rang<=longueur_liste(l)
// contrainte d'implémentation: rang+1<TAILLE_LISTE
 unsigned int i;
 if (rang >= TAILLE_LISTE) {
  fprintf(stderr, "inserer_liste: rang %d >= TAILLE liste %d\n",
    rang, TAILLE_LISTE);
  exit(1);
 }
 if (rang > longueur_liste(l)) {
  fprintf(stderr, "inserer_liste: rang %d > longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 for (i=longueur_liste(l); i>rang; i--) {
  ((St *)l)->t[i] = ((St *)l)->t[i-1];
 }
 ((St *)l)->t[rang] = e;
 ((St *)l)->longueur++;
 return l;
}
unsigned int longueur_liste(Liste l) {
 return (((St *)l)->longueur);
}
Position positionner_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "positionner_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 return (Position) &(((St *)l)->t[rang]);
}
Position suivant_liste(Liste l, Position p) {
// précondition: p!=positionner_liste(l, longueur_liste(l)-1)
 Position q;
 q = positionner_liste(l, longueur_liste(l) - 1);
 if (p == q) {
  fprintf(stderr, "suivant_liste: pas de suivant\n");
  exit(1);
 }
 return (Position) ((Table) p + 1);
}
Element_liste lire_courant_liste(Liste l, Position p) {
// précondition: longueur_liste(l)>0
 if (longueur_liste(l) == 0) {
  fprintf(stderr, "lire_courant_liste: liste vide\n");
  exit(1);
 }
 return (*((Element_liste *)p));
}

Notons que les opérations lire_liste , positionner_liste , suivant_liste et lire_courant_liste ne nécessitent pas de parcours de la liste. On dit que ce sont des accès directs .
En revanche, les opérations inserer_liste et supprimer_liste effectuent un décalage des éléments qui suivent le point d'insertion ou de suppression. Ce décalage est un parcours. On dit que ce sont des opérations qui font un accès séquentiel .
Ces remarques sur la complexité des opérations sont une conséquence de l'implémentation de la liste en table. Une autre implémentation en liste chaînée (donnée plus loin) simplifierait les insertions en tête et suppressions en queue, mais au détriment des autres opérations.

Voici le fichier liste_en_table.h .

// fichier liste_en_table.h
#ifndef LISTE_EN_TABLE
#define TAILLE_LISTE 1024
#include "liste.h"
#endif
#define LISTE_EN_TABLE

Voici le fichier liste.h .

// fichier liste.h
#include "element_liste_def.h"
#include "liste_def.h"
Liste creer_liste();
Element_liste lire_liste(Liste l, unsigned int rang);
Liste supprimer_liste(Liste l, unsigned int rang);
Liste inserer_liste(Liste l, unsigned int rang, Element_liste e);
unsigned int longueur_liste(Liste l);
Position positionner_liste(Liste l, unsigned int rang);
Position suivant_liste(Liste l, Position p);
Element_liste lire_courant_liste(Liste l, Position p);
// l: Liste; e: Element_liste; r, i: unsigned int; p: Position
// préconditions:
//   positionner_liste(l, r) est-défini-ssi 0<=r<=longueur_liste(l)-1
//   lire_liste(l, r) est-défini-ssi 0<=r<=longueur_liste(l)-1
//   supprimer_liste(l, r) est-défini-ssi 0<=r<=longueur_liste(l)-1
//   inserer_liste(l, r, e) est-défini-ssi 0<=r<=longueur_liste(l)
//   (quand r == longueur_liste(l), on ajoute en fin de liste)
//   suivant_liste(l, p) est-défini-ssi
//     p!=positionner_liste(l, longueur_liste(l)-1)
//   lire_courant_liste(l, p) est-défini-ssi longueur_liste(l)>0
// axiomes:
//   longueur_liste(creer_liste()) == 0
//   0<=r<=longueur_liste(l) - 1 =>
//     longueur_liste(supprimer_liste(l, r)) == longueur_liste(l) - 1
//   0<=r<=longueur_liste(l) =>
//     longueur_liste(inserer_liste(l, r, e)) == longueur_liste(l) + 1
//   0<=r<=longueur_liste(l) - 1 && 0<=i<r =>
//     lire_liste(supprimer_liste(l, r), i) == lire_liste(l, i)
//   0<=r<=longueur_liste(l) - 1 && r<=i<=longueur_liste(l) - 2 =>
//     lire_liste(supprimer_liste(l, r), i) == lire_liste(l, i + 1)
//   0<=r<=longueur_liste(l) && 0<=i<r =>
//     lire_liste(inserer_liste(l, r, e), i) == lire_liste(l, i)
//   0<=r<=longueur_liste(l) && i == r =>
//     lire_liste(inserer_liste(l, r, e), i) == e
//   0<=r<=longueur_liste(l) && r<=i<=longueur(l) =>
//     lire_liste(inserer_liste(l, r, e), i) == lire_liste(l, i - 1)
//   0<=r<longueur_liste(l) - 1 =>
//     suivant_liste(l, positionner_liste(l, r)) == positionner_liste(l, r + 1)

Voici le fichier element_liste_def.h .

// fichier element_liste_def.h
#ifndef ELEMENT_LISTE_DEF
typedef void *Element_liste;
#endif
#define ELEMENT_LISTE_DEF

Voici le fichier liste_def.h .

// fichier liste_def.h
#ifndef LISTE_DEF
typedef void *Liste;
typedef void *Position;
#endif
#define LISTE_DEF

Voici un fichier main_table.c mettant en œuvre la manipulation d'une liste d'entiers en table. Le programme propose un menu de toutes les opérations fournies par la spécification d'une liste. Il peut servir à mettre au point les implémentations des diverses opérations.
Remarquons que les appels aux diverses opérations sont précédés d'une vérification des préconditions (ce qui est indispensable puisqu'une fois le code de liste_en_table.c validé, la vérification interne des préconditions sera inhibée).
En particulier, on s'assure avant d'insérer en liste, que celle-ci n'est pas pleine. Pour cela, on dispose de la constante TAILLE_LISTE.

// fichier main_table.c
#include <stdio.h>
#include "element_int_liste.h"
#include "liste_en_table.h"
#define TAILLE_REP 128
main() {
 Liste l;
 Element_liste e;
 Position p = NULL;
 int i, j;
 char rep[TAILLE_REP];
 l = creer_liste();
 do {
  afficher_menu();
  fgets(rep, TAILLE_REP, stdin);
  if (rep[0] == 'q') exit(0);
  switch (rep[0]) {
   case 's':
     sscanf(&rep[1], "%d", &i);
     if (i>=longueur_liste(l)) printf("trop loin\n");
     else l = supprimer_liste(l, i);
     break;
   case 'i':
     sscanf(&rep[1], "%d %d", &i, &j);
     if (longueur_liste(l)>=TAILLE_LISTE) printf("liste pleine\n");
     else if (j>longueur_liste(l)) printf("trop loin\n");
     else {
       e = creer_element_liste();
       e = ecrire_element_liste(e, i);
       l = inserer_liste(l, j, e);
     }
     break;
   case 'r':
     sscanf(&rep[1], "%d", &i);
     if (i>=longueur_liste(l)) printf("trop loin\n");
     else printf("%d\n", lire_element_liste(lire_liste(l, i)));
     break;
   case 'l':
     printf("%d\n", longueur_liste(l));
     break;
   case 'p':
     sscanf(&rep[1], "%d", &i);
     if (i>=longueur_liste(l)) printf("trop loin\n");
     else p = positionner_liste(l, i);
     break;
   case 'c':
     if (p == NULL) printf("pas positionné\n");
     else if (longueur_liste(l) == 0) printf("liste vide\n");
     else printf("%d\n", lire_element_liste(lire_courant_liste(l, p)));
     break;
   case 'n':
     if (p == NULL) printf("pas positionné\n");
     else if (longueur_liste(l) == 0) printf("liste vide\n");
     else if (p == positionner_liste(l, longueur_liste(l)-1))
             printf("trop loin\n");
     else p = suivant_liste(l, p);
     break;
  }
 } while (1);
}
afficher_menu() {
 printf("menu:\n");
 printf("  (q)uitter\n");
 printf("  (i)nsérer (j) en (k)\n");
 printf("  (s)upprimer de (j)\n");
 printf("  (l)ongueur de la liste\n");
 printf("  (r)ead (i)\n");
 printf("  se (p)ositionner en (i)\n");
 printf("  se positionner sur (n)ext\n");
 printf("  afficher (c)ourant\n");
}

Voici enfin le makefile pour construire main_table .

# fichier make_liste_en_table
main_table: main_table.o liste_en_table.o element_int_liste.o
        cc -o main_table main_table.o liste_en_table.o element_int_liste.o
main_table.o: main_table.c liste.h liste_en_table.h liste_def.h element_liste_def.h element_int_liste.h
        cc -c main_table.c
liste_en_table.o: liste_en_table.c liste.h liste_en_table.h liste_def.h element_liste_def.h
        cc -c liste_en_table.c
element_int_liste.o: element_int_liste.c element_int_liste.h element_liste_def.h
        cc -c element_int_liste.c

Voici une seconde implémentation des listes en chaîne. La liste est représentée par une chaîne de cellules. Chaque cellule regroupe un Element et un pointeur sur la cellule suivante (NULL en fin de chaîne). Une chaîne vide est un simple pointeur NULL.
Quelques remarques concernant l'implémentation: il n'y a plus de taille maximale (hormis celle de la mémoire de la machine). Lors des suppressions, il ne faut pas omettre de récupérer la place de la cellule supprimée (C n'a pas de mécanisme de ramasse-miettes ). C'est le rôle de free .
Notons que des opérations en accès direct dans la représentation en table sont maintenant des opérations séquentielles. C'est le cas du calcul de la longueur de la liste. Il faut noter à ce sujet que toutes les préconditions reposent sur la longueur. Elles effectuent donc un parcours complet de la liste. Elles sont désactivées dans liste_en_chaine.c mais doivent être contrôlées avant tout appel d'opération. Il est alors beaucoup plus efficace de tenir à jour un compteur du nombre d'éléments de la liste.

// fichier liste_en_chaine.c
#include <stdio.h>
#include "liste.h"
typedef struct C {Element_liste e; struct C *s;} Cellule;
typedef Cellule *Chaine;
Liste creer_liste() {
 Chaine l;
 l = NULL;
 return (Liste) l;
}
Element_liste lire_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 Chaine c;
 unsigned int i;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "lire_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 c = (Chaine)l;
 for (i=0; i<rang; i++) c = c->s;
 return c->e;
}
Liste supprimer_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 Chaine c, p;
 unsigned int i;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "supprimer_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 c = (Chaine)l;
 if (rang == 0) {
  c = c->s;
  free(l);
  return (Liste)c;
 }
 for (i=0; i<rang; i++) {
  p = c;
  c = c->s;
 }
 p->s = c->s;
 free(c);
 return l;
}
Liste inserer_liste(Liste l, unsigned int rang, Element_liste e) {
// précondition: 0<=rang<=longueur_liste(l)
 Chaine c, p, q;
 unsigned int i;
 if (rang > longueur_liste(l)) {
  fprintf(stderr, "inserer_liste: rang %d > longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 c = (Chaine)l;
 if (rang == 0) {
  p = (Chaine) malloc(sizeof(Cellule));
  p->e = e;
  p->s = c;
  return (Liste)p;
 }
 for (i=0; i<rang; i++) {
  p = c;
  c = c->s;
 }
 q = (Chaine) malloc(sizeof(Cellule));
 q->e = e;
 q->s = c;
 p->s = q;
 return l;
}
unsigned int longueur_liste(Liste l) {
 unsigned int i = 0;
 Chaine c;
 c = (Chaine)l;
 while (c != NULL) {
  i++;
  c = c->s;
 }
 return i;
}
Position positionner_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 Chaine c;
 unsigned int i;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "positionner_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 c = (Chaine)l;
 for (i=0; i<rang; i++) c = c->s;
 return (Position)c;
}
Position suivant_liste(Liste l, Position p) {
// précondition: p!=positionner_liste(l, longueur_liste(l)-1)
 Chaine c;
 Position q;
 q = positionner_liste(l, longueur_liste(l) - 1);
 if (p == q) {
  fprintf(stderr, "suivant_liste: pas de suivant\n");
  exit(1);
 }
 c = ((Chaine)p)->s;
 return (Position)c;
}
Element_liste lire_courant_liste(Liste l, Position p) {
// précondition: longueur_liste(l)>0
 if (longueur_liste(l) == 0) {
  fprintf(stderr, "lire_courant_liste: liste vide\n");
  exit(1);
 }
 return ((Chaine)p)->e;
}

Voici un programme de mise en œuvre de liste en chaîne. Il est très peu différent de la mise en œuvre de liste en table: on tient à jour un compteur du nombre d'éléments en liste pour éviter les appels à la fonction longueur.
Notons que la mise en œuvre de l'opération longueur fait un appel plutôt que de consulter le compteur puisqu'il s'agit de vérifier le fonctionnement de l'opération longueur .

// fichier main_chaine.c
#include <stdio.h>
#include "element_int_liste.h"
#include "liste.h"
#define TAILLE_REP 128
main() {
 Liste l;
 Element_liste e;
 Position p = NULL;
 unsigned int longueur;
 int i, j;
 char rep[TAILLE_REP];
 l = creer_liste();
 longueur = 0;
 do {
  afficher_menu();
  fgets(rep, TAILLE_REP, stdin);
  if (rep[0] == 'q') exit(0);
  switch (rep[0]) {
   case 's':
     sscanf(&rep[1], "%d", &i);
     if (i>=longueur) printf("trop loin\n");
     else {
      l = supprimer_liste(l, i);
      longueur --;
     }
     break;
   case 'i':
     sscanf(&rep[1], "%d %d", &i, &j);
     if (j>longueur) printf("trop loin\n");
     else {
       e = creer_element_liste();
       e = ecrire_element_liste(e, i);
       l = inserer_liste(l, j, e);
       longueur++;
     }
     break;
   case 'r':
     sscanf(&rep[1], "%d", &i);
     if (i>=longueur) printf("trop loin\n");
     else printf("%d\n", lire_element_liste(lire_liste(l, i)));
     break;
   case 'l':
     printf("%d\n", longueur_liste(l));
     break;
   case 'p':
     sscanf(&rep[1], "%d", &i);
     if (i>=longueur) printf("trop loin\n");
     else p = positionner_liste(l, i);
     break;
   case 'c':
     if (p == NULL) printf("pas positionné\n");
     else if (longueur == 0) printf("liste vide\n");
     else printf("%d\n", lire_element_liste(lire_courant_liste(l, p)));
     break;
   case 'n':
     if (p == NULL) printf("pas positionné\n");
     else if (longueur == 0) printf("liste vide\n");
     else if (p == positionner_liste(l, longueur-1))
             printf("trop loin\n");
     else p = suivant_liste(l, p);
     break;
  }
 } while (1);
}
afficher_menu() {
 printf("menu:\n");
 printf("  (q)uitter\n");
 printf("  (i)nsérer (j) en (k)\n");
 printf("  (s)upprimer de (j)\n");
 printf("  (l)ongueur de la liste\n");
 printf("  (r)ead (i)\n");
 printf("  se (p)ositionner en (i)\n");
 printf("  se positionner sur (n)ext\n");
 printf("  afficher (c)ourant\n");
}

Voici enfin le makefile du programme main_chaine .

# fichier make_liste_en_chaine
main_chaine: main_chaine.o liste_en_chaine.o element_int_liste.o
        cc -o main_chaine main_chaine.o liste_en_chaine.o element_int_liste.o
main_chaine.o: main_chaine.c liste.h liste_def.h element_liste_def.h element_int_liste.h
        cc -c main_chaine.c
liste_en_chaine.o: liste_en_chaine.c liste.h liste_def.h element_liste_def.h
        cc -c liste_en_chaine.c
element_int_liste.o: element_int_liste.c element_int_liste.h element_liste_def.h
        cc -c element_int_liste.c