Structures de données élémentaires

Dans cette section, nous nous intéressons à un certain nombre de structures de données.

Tableaux, pointeurs et structures

Un tableau de taille $n$ est une structure très simple constituée de $n$ emplacements consécutifs en mémoire. Il est donc possible d'accéder à un élément d'un tableau en temps constant pourvu que l'on connaisse sa position (ou indice). Un tableau est donc une structure très simple et très efficace. Il n'est cependant pas possible de modifier la taille d'un tableau, ce qui est gênant pour un certain nombre d'algorithmes. On dit cette structure est statique. Le nombre d'éléments qu'elle contient ne peut pas varier.

Comme nous l'avons vu en section 1.2, une variable est un espace mémoire nommé, de taille fixée. Il est donc possible de parler de l'adresse d'une variable (notée &var en C et que nous noterons $\char93$var dans ce cours). L'adresse d'une variable étant une valeur, elle a donc un type : c'est un pointeur. On distingue un pointeur sur un Entier, d'un pointeur sur un Caractère, d'un pointeur sur un Réel, même si ce sont tous des adresses. Le type du pointeur est nécessaire pour pouvoir le déréférencer, c'est à dire accéder à la valeur pointée par le pointeur (si add est un pointeur, la valeur pointée par add est notée *add en C et nous la noterons $\langle$add$\rangle$ dans ce cours). Un pointeur particulier est le pointeur NIL (NULL en C). Il représente une adresse inaccessible et c'est donc une valeur que l'on utilise pour dire que le pointeur n'a pas de valeur déterminée. Il est primordial de toujours initialiser ses pointeurs à la valeur NIL. Cela permet de détecter plus simplement les déréférencement de pointeurs non initialisés...On remarquera qu'un tableau peut être représenté par un pointeur (l'emplacement de son premier élément en mémoire) et un entier (sa taille).

Enfin, une structure (ou enregistrement) est un produit nommé de plusieurs types. Définissons un nouveau type
ainsi qu'une variable ind de ce type.

Il est ensuite aisé d'accéder aux différents champs de cette structure de la façon suivante:

En C, les tableaux, les pointeurs et les structures sont des structures de données de base (elles sont fournies par le langage). Nous allons maintenant voir un certain nombre d'autres structures de données qui n'existent pas au départ dans le langage C, mais que l'on peut construire assez aisément.

Liste chaînée

Définitions et exemples

Une liste chaînée est une structure de données dans laquelle les éléments sont rangés linéairement. Chaque élément est lié à son successeur et il n'est donc pas possible d'accéder directement à un élément quelconque de la liste.

Bien sûr, cette linéarité est purement virtuelle. À la différence du tableau, les éléments n'ont aucune raison d'êtres contigus ni ordonnés en mémoire.

La façon dont on met en uvre ces structures dépend des langages même si la façon dont cela est présenté ici ressemble fortement à celle du langage C. Une façon simple de se représenter une liste, consiste à se dire qu'une liste $l$ est soit vide $[]$, soit constituée d'une tête $t$ (qui est donc la valeur du premier élément de la liste) et d'une queue $q$ (qui est le reste de la liste).

La manipulation d'une liste peut donc se faire grâce aux fonctions suivante:

• 
  
• 
  
• 
  
• 
  

La liste que nous avons donné en exemple peut donc se définir par:

En terme de pointeurs et de structures, une liste d'entier peut se représenter grâce au type suivant:

La liste que nous avons donné en exemple pourrait se définir par:

Pour conclure, retenons simplement qu'il est possible d'accéder en temps constant à la tête de la liste.

Exercices

Exercice 28   Écrire une fonction qui calcule la longueur d'une liste: Voir réponse 28.

Écrire une fonction qui renvoie le $n^{\text{ème}}$ élément d'une liste: Voir réponse 28.

Écrire une fonction qui indique si un élément appartient à une liste: Voir réponse 28.

Écrire une fonction qui concatène deux listes: Voir réponse 28.

Écrire une fonction qui renverse une liste: Voir réponse 28.

Écrire une fonction qui insère un élément dans une liste triée: Voir réponse 28.

Écrire une fonction qui fusionne deux listes triées: Voir réponse 28.

Pour vous entrainer, vous pourrez évaluer la complexité en mémoire et en temps de chacune de ces fonctions et les réécrire de façons itérative.

Pile

Une pile est une structure de donnée dynamique permettant de stocker un ensemble de données. On peut donc insérer un élément ou en supprimer un, à ceci près que l'on ne peut pas choisir l'élément que l'on supprime : c'est le dernier élément inséré. L'ordre dans lequel les éléments sont supprimés est donc inverse de celui dans lequel ils sont insérés (Last In First Out). Une bonne image de cette structure de données est la pile d'assiettes : on peut rajouter une assiette sur une pile d'assiettes mais on ne peut retirer que celle du dessus sans risquer de tout casser.

L'opération d'insertion dans une pile est généralement appelée Empiler. L'opération de suppression est souvent appelée Dépiler. Nous allons mettre en uvre la structure de pile à l'aide d'un tableau.

Cependant, dans cette mise en uvre, comme on inclue notre pile dans un tableau, la taille de la pile est bornée. On peut s'affranchir de cette limitation en utilisant une simple liste chaînée. En effet, empiler un élément consiste simplement à rajouter un maillon, dépiler un élément consiste à en enlever un et à ce que la pile soit représentée par la queue de la liste précédente, tester si la pile est vide consiste à regarder s'il y a un maillon. Le type utilisé pourrait alors ressembler à ceci:

On peut alors écrire les fonctions précédentes très simplement:

Liste doublement chaînée

Une liste doublement chaînée est similaire à une liste chaînée à ceci près qu'il est également possible d'accéder à son prédécesseur.

Bien sûr, cette linéarité est purement virtuelle. Tout comme pour la liste chaînée, les éléments n'ont aucune raison d'êtres contigus ni ordonnés en mémoire.

En terme de pointeurs et de structures, ce type peut donc se définir de la façon suivante.

La liste que nous avons donné en exemple pourrait se définir par

File

Une file est une structure de donnée dynamique différant d'une file par l'ordre d'extraction des éléments. Le premier élément inséré est le premier à être extrait d'une file. Les éléments sont donc supprimés dans le même ordre que celui dans lequel ils ont été insérés (First In First Out). Une bonne image de cette structure de données est la file d'attente au cinéma, au RU ou dans un supermarché : on fait la queue et, à moins de tricher, il n'est pas possible de sortir de la queue avant les personnes qui ont commencé à faire la queue avant vous.

L'opération d'insertion dans une pile est généralement appelée Enfiler. L'opération de suppression est souvent appelée Défiler. Cette structure peut, comme pour une pile, se mettre en uvre avec un tableau mais elle souffrira des même limitations que pour la pile. Le plus simple consiste à utiliser une liste doublement chaînée:

Une file où auraient été enfilées successivement les valeurs 12, 25, 4 et 7 se représenterait donc ainsi :

Bien sûr, une fois de plus, cette linéarité est purement virtuelle:

Arbres

Un arbre est un ensemble de nuds (appelés aussi parfois sommets) reliés par des arêtes tel que chaque nud (à part la racine qui en a 0) ait exactement une arête pointant vers lui. La racine est donc un nud particulier puisqu'il n'a pas de prédécesseur. Les feuilles sont les noeuds sans sucesseurs.

Arbres binaires

Un arbre binaire est un arbre tel que chaque noeud a au plus deux fils (ou successeurs). Il peut donc se représenter à l'aide de la structure suivante:

Encore une fois, cette organisation est purement virtuelle. L'arbre suivant

est peut-être stocké ainsi en mémoire...

Exercice 29   La récursivité se prête extrèmement bien à ce type de structure. Pour preuve, écrivons la recherche d'une valeur dans un arbre binaire.

Voir réponse 29.

Écrire une fonction qui calcule le nombre de nuds d'un arbre donné. Voir réponse 29.

Écrire une fonction qui calcule la somme des valeurs des nuds d'un arbre donné. Voir réponse 29.

Écrire une fonction qui calcule la plus grande des valeurs des nuds d'un arbre donné. Voir réponse 29.

On suppose disposer du contructeur
qui, étant donné un entier val et deux arbres gauche et droit, construit un arbre dont la racine est étiquetée par val et dont le fils droit est droit et le fils gauche gauche. Ce constructeur, en association avec l'
, permet de construire n'importe quel arbre binaire.

Exercice 30   Il est alors aisé d'écrire une fonction qui convertit une liste en un arbre. Voir réponse 30.

Évidemment, ce n'est pas la seule façon de transformer une liste en arbre. On aurait également pu mettre les valeur sur la gauche de l'arbre. L'idéal (pour l'équilibrage de l'arbre) étant de mettre à chaque étape la moitié de la liste à gauche et l'autre moitié à droite...

On peut également écrire simplement une fonction qui transforme un arbre en liste.

Voir réponse 30.

Arbres $n$-aires

Un arbre où chaque nud a au plus $n$ sommet est appelé arbre $n$-aire. Il peut bien évidemment se représenter par la structure suivante:

Quand il n'est pas possible de borner le degré de l'arbre, il suffit d'utiliser une des structures dynamiques que nous avons vu en début de section (liste, file, ...).