STRUCTURES SÉQUENTIELLES 2 SIMPLES

 LISTES LINÉAIRES

Exemple Imaginons la gestion d’un tableau contenant les références des livres d’une bibliothèque. Ce tableau est rangé dans l’ordre alphabétique. Lorsqu’un nouveau livre est acheté, son insertion dans le tableau en respectant l’ordre requiert de déplacer toutes les références qui suivent la position d’insertion, pour dégager de la place. Le coût d’une telle opération est élevé et peut devenir prohibitif dans certains cas. Pour éviter ce type de problème, il faudrait que le passage d’une case d’un tableau à la suivante ne se fasse plus à partir d’un indice absolu qu’on incrémente, mais en notant localement dans une case du tableau l’indice de la case suivante. On va présenter ici les listes linéaires qui sont la forme la plus commune d’organisation des données. On organise en liste linéaire des données qui doivent être traitées séquentiellement. De plus une liste est évolutive, c’est-à-dire qu’on veut pouvoir ajouter et supprimer des données.

Définition

Une liste linéaire est une structure de données correspondant à une suite d’éléments. Les éléments ne sont pas indexés dans la liste, mais pour chaque élément (sauf le dernier) on sait où se trouve l’élément suivant. Par conséquent, on ne peut accéder à un élément qu’en passant par le premier élément de la liste et en parcourant tous les éléments jusqu’à ce qu’on atteigne l’élément recherché.

Représentation Représentation tabulaire

On peut représenter une liste par deux tableaux : • le tableau 2.1 contient les éléments de la liste, dans un ordre quelconque. • le tableau 2.2 est organisé de façon suivante : si la case d’indice i du premier tableau contient l’élément dont le suivant se trouve dans la case d’indice j, alors la case d’indice i de second tableau contient l’entier j. On peut extraire les éléments du premier tableau dans l’ordre alphabétique si on connaît le point de départ : 1 dans notre cas. Ce point de départ doit évidemment être précisé à l’entrée de  chaque algorithme utilisant la représentation en question. Dans la case 1 du deuxième tableau on trouve 3, qui est l’indice du deuxième élément du premier tableau, etc. Finalement, dans la case 2 du deuxième tableau on trouve 5, et dans la case 5 du premier tableau on a le marqueur de fin. Si on insère ‘c’ dans le premier tableau, on peut l’insérer dans la première case libre (c’est la case 0), et il n’y a que deux changements à faire au niveau du deuxième tableau. On met 0 dans la case 3, et on met 2 dans la case 0. Les tableaux 2.3 et 2.4 présentent les résultats.  Cette représentation n’est pas très intéressante : les fonctions de traitement sont relativement lourdes. Représentation chaînée On utilise des pointeurs pour chaîner entre eux les éléments successifs, et la liste est alors déterminée par l’adresse de son premier élément. On va définir des enregistrements (structures) dont un des champs est de type pointeur vers une structure chaînée du même type. Exemple de définition d’une structure chaînée Pseudo code formel STRUCTURE nœud nom : caractère[20] prenom : caractère[20] *suiv : nœud TYPE *ptr_nœud : nœud Implantation C typedef struct nœud { char nom[20]; 36 2.1. Listes linéaires char prenom[20]; struct nœud *suiv; } nœud; typedef nœud* ptr_nœud; La liste vide est représentée par le pointeur NULL. Figure 2.1 Liste (simplement) chaînée Cette représentation n’impose pas une longueur maximum sur les listes ; elle permet de traiter facilement la plupart des opérations sur les listes : le parcours séquentiel, l’insertion et la suppression d’un élément à une place quelconque, la concaténation de deux listes, se font par une simple manipulation des pointeurs. Cependant le calcul de la longueur nécessite le parcours de toute la liste ; de même, l’accès au k ième élément n’est plus direct : on doit parcourir k–1 pointeurs à partir de la tête pour trouver le k ième élément. Avant de passer aux exemples de fonctions qui traitent les listes chaînées il faut faire un petit rappel sur les variables dynamiques.

 Variables dynamiques

• C’est une variable dont la place mémoire est allouée en cours d’exécution. • On ne prend de la place mémoire que lorsqu’on en a besoin. • Cette place mémoire est allouée explicitement, c’est-à-dire par une instruction du langage. • La désallocation est également effectuée par l’intermédiaire d’une instruction. • Il n’est donc pas nécessaire de réserver dès la compilation tout un espace mémoire. • On utilise la place juste lorsqu’on en a besoin, puis on peut la réutiliser par autre chose. Exemples Les exemples sont toujours donnés en langage algorithmique. Les données, les données modifiées et les sorties sont systématiquement précisées en préambule des déclarations. À titre d’illustration, une réalisation (ou implantation, ou implémentation) est donnée en C99 pour chacun des types abstraits et algorithmes proposés.

Structures séquentielles simples

Définition d’une structure de liste simplement chaînée Pseudo code formel STRUCTURE place info : T *suiv : place TYPE *list : place Implantation C typedef struct place { content; struct place *succ; } place; typedef place *list; Tester la présence d’un élément dans une liste chaînée Spécification de l’algorithme « recherche (a) » FONCTION recherche(l: liste<élément>, x: élément): booléen VAR trouve: booléen ; p: place DEBUT trouve ← faux SI ¬ estvide(l) ALORS p ← tête(l) TANTQUE ¬ dernier(p) ∧ trouve = faux FAIRE SI contenu(p) = x ALORS trouve ← vrai SINON p ← succ(p) // itération vers la cellule suivante FINSI FAIT SI contenu(p) = x ET trouve = faux ALORS trouve ← vrai FINSI FINSI RETOURNER trouve FIN Réalisation en C Données : list l : la liste de recherche, int k : l’élément recherché Résultat : type booléen (int en C) int containsElement(list l, int k) { int found = 0; if (l == NULL) return found; while ((l->succ != NULL) & (! found)) { 38 2.1. Listes linéaires if (l->content == k) found = 1; else l = l->succ; } if (l->content == k) found = 1; return found; }