Un exemple

Un exemple simple fera mieux comprendre le système et son intérêt. La structure de liste chaînée est sans doute déjà connue du lecteur. Il s’agit d’une suite de noeuds, contenant chacun un pointeur vers un autre noeud et un élément d’information d’un type quelconque (nommé element dans la suite). L’intérêt de cet agencement réside dans sa fluidité ; il est très facile par exemple de supprimer ou d’ajouter un élément.

Voici un exemple d’implantation d’une structure noeud, brique de base d’une liste chaînée, sans méthode pour le moment :

typedef long element;    // (par exemple)				struct noeud {     noeud *suivt;    // le suivant dans la liste     element elm;     // information contenue     };

Une liste chaînée est cependant fragile. Si par erreur on modifie l’un des pointeurs, la liste sera coupée, les informations perdues et le programme complètement égaré.

Nous allons donc blinder notre structure afin de limiter les risques :

struct noeud {     private :     noeud *suivt;    // le suivant dans la liste     element elm;     // information contenue     public :     noeud *suivant(void) { return suivt; }     element &contenu(void) { return elm; }     };

Nos deux champs sont à présent privés, de sorte que l’écriture suivante :

noeud no;no.suivt = 0;

provoque une erreur Error : 'noeud::suivt' is not accessible, 'noeud::suivt' n’est pas accessible.

On ne peut plus dans notre exemple que lire le contenu (le champ elm) du noeud, ou connaître le suivant de la liste, à l’aide des méthodes. C’est évidemment un peu excessif, car il n’est dès lors plus possible de modifier la liste. Nous allons ajouter une fonction qui insère un élément dans la liste, et une autre qui le supprime :

struct noeud {     private :     noeud *suivt;   // le suivant dans la liste     element elm;    // information contenue     public :     noeud *suivant(void) { return suivt; }     element &contenu(void) { return elm; }     noeud* supprime_svt(void);     noeud* insere(element e);     };noeud* noeud::supprime_svt(void);// supprime le noeud suivant et // renvoie un pointeur sur le nouveau suivant {     if (!suivt) return 0;     // pas de suivant     noeud *s = suivt;     suivt = s->suivt;     delete s;     return suivt;}noeud* noeud::insere(element e)// insère un nouvel élément de valeur e derrière this.// renvoie 0 si plus de mémoire, sinon suivt.{     noeud *nouveau = new noeud;     if (!nouveau) return 0;    // plus de mémoire     nouveau->suivt = suivt;     nouveau->elm = e;     return suivt = nouveau;}

Contrairement aux précédentes, ces fonctions n’ont pas été écrites en ligne, car elles sont un peu plus complexes (mais on aurait tout de même pu le faire, elles ne contiennent pas de boucle).

Exercice 6.1	Quel fondement essentiel manque dans notre liste chaînée, qui la rend inutilisable ? Comment résoudre le problème (un meilleur moyen est donné plus loin dans le chapitre) ?
Voir solution

À part la réserve mentionnée dans l’exercice, notre type de base pour liste chaînée est assez au point, et évitera bien des erreurs. Nous ferons mieux par la suite, mais voyons encore quelques notations.

Précédent

Sommaire

Suivant