Chapitre 3 Structures de données élémentaires

Dans ce chapitre, nous introduisons quelques structures utilisées de façon très intensive en programmation. Leur but est de gérer un ensemble fini d'éléments dont le nombre n'est pas fixé a priori. Les éléments de cet ensemble peuvent être de différentes sortes: nombres entiers ou réels, chaînes de caractères, ou des objets informatiques plus complexes comme les identificateurs de processus ou les expressions de formules en cours de calcul ... On ne s'intéressera pas aux éléments de l'ensemble en question mais aux opérations que l'on effectue sur cet ensemble, indépendamment de la nature de ses éléments. Ainsi les ensembles que l'on utilise en programmation, contrairement à ceux considérés en mathématiques qui sont fixés une fois pour toutes, sont des objets dynamiques. Le nombre de leurs éléments varie au cours de l'exécution du programme, puisqu'on peut y ajouter et supprimer des éléments en cours de traitement. Plus précisément les opérations que l'on s'autorise sur les ensembles sont les suivantes :

• tester si l'ensemble E est vide.
  
• ajouter l'élément x à l'ensemble E.
  
• vérifier si l'élément x appartient à l'ensemble E.
  
• supprimer l'élément x de l'ensemble E.
  

Cette gestion des ensembles doit, pour être efficace, répondre au mieux à deux critères parfois contradictoires: un minimum de place mémoire utilisée et un minimum d'instructions élémentaires pour réaliser une opération. La place mémoire utilisée devrait pour bien faire être très voisine du nombre d'éléments de l'ensemble E, multipliée par leur taille; c'est ce qui se passera pour les trois structures que l'on va étudier plus loin. En ce qui concerne la minimisation du nombre d'instructions élémentaires, on peut tester très simplement si un ensemble est vide et on peut réaliser l'opération d'ajout en quelques instructions, toutefois il est impossible de réaliser une suppression ou une recherche d'un élément quelconque dans un ensemble en utilisant un nombre d'opérations indépendant du cardinal de cet ensemble (à moins d'utiliser une structure demandant une très grande place en mémoire). Pour améliorer l'efficacité, on considère des structures de données dans lesquelles on restreint la portée des opérations de recherche et de suppression d'un élément en se limitant à la réalisation de ces opérations sur le dernier ou le premier élément de l'ensemble, ceci donne les structures de pile ou de file, nous verrons que malgré ces restrictions les structures en question ont de nombreuses applications.


3.1 Listes chaînées

La liste est une structure de base de la programmation, le langage LISP (LISt Processing), conçu par John MacCarthy en 1960, ou sa version plus récente Scheme [1], utilise principalement cette structure qui se révèle utile pour le calcul symbolique. Dans ce qui suit on utilise la liste pour représenter un ensemble d'éléments. Chaque élément est contenu dans une cellule, celle ci contient en plus de l'élément l'adresse de la cellule suivante, appelée aussi pointeur. La recherche d'un élément dans la liste s'apparente à un classique ``jeu de piste'' dont le but est de retrouver un objet caché: on commence par avoir des informations sur un lieu où pourrait se trouver cet objet, en ce lieu on découvre des informations sur un autre lieu où il risque de se trouver et ainsi de suite. Le langage Java permet cette réalisation à l'aide de classes et d'objets: les cellules sont des objets (c'est à dire des instances d'une classe) dont un des champs contient une réference vers la cellule suivante. La référence vers la première cellule est elle contenue dans une variable de tête de liste. Les déclarations correspondantes sont les suivantes, où l'on suppose ici que les éléments stockés dans chaque cellule dont de type entier..

class Liste {

int contenu;
Liste suivant;

Liste (int x, Liste a) {
contenu = x;
suivant = a;
}
}
L'instruction new Liste (x, a) construit une nouvelle cellule dont les champs sont x et a. La fonction Liste(x,a) est un constructeur de la classe Liste (un constructeur est une fonction non statique qui se distingue par le type de son résultat qui est celui de la classe courante et par son absence de nom pour l'identifier). L'objet null appartient à toute classe, et représentera dans le cas des listes le marqueur de fin de liste. Ainsi new Liste(2, new Liste (7, new Liste (11, null))) représentera la liste 2,7,11. Les opérations sur les ensembles que nous avons considérées ci-dessus s'expriment alors comme suit si on gère ceux-ci par des listes:

<BLOCKQUOTE></BLOCKQUOTE>static boolean estVide (Liste a) {

return a == null;
}
La procédure ajouter insère l'élément x en tête de liste. Ce choix de mettre l'élément en tête est indispensable pour que le nombre d'opérations lors de l'ajout soit indépendant de la taille de la liste; il suffit alors de modifier la valeur de la tête de liste ce qui est fait simplement par

static Liste ajouter (int x, Liste a) {

return new Liste (x, a); // L'ancienne tête se retrouve après x
}
La fonction recherche, qui vérifie si l'élément x figure bien dans la liste a, effectue un parcours de la liste pour rechercher l'élément. La variable a est modifiée itérativement par a = a.suivant de façon à parcourir tous les éléments jusqu'à ce que l'on trouve x ou que l'on arrive à la fin de la liste (a = null).

static boolean recherche (int x, Liste a) {

while (a != null) {
if (a.contenu == x)
return true;
a = a.suivant;
}
return false;
}