Leçons de niveau 13

Récursivité dans l'algorithmique et la programmation/Structure de données récursives

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Structure de données récursives
Icône de la faculté
Chapitre no 3
Leçon : Récursivité dans l'algorithmique et la programmation
Chap. préc. :Algorithmes récursifs
Chap. suiv. :Algorithmes récursifs avancés

Exercices :

Structure de données récursives
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Récursivité dans l'algorithmique et la programmation : Structure de données récursives
Récursivité dans l'algorithmique et la programmation/Structure de données récursives
 », n'a pu être restituée correctement ci-dessus.

La structure de donnée récursive est monnaie courante dans l'informatique de tous les jours; elle apparaît dès que l’on parle de liste, file, arbre, graphe, ... Peu de langages de programmation n'en permettent pas l'utilisation, que ce soit explicitement par l'intermédiaire de pointeurs, ou implicitement par des références. Nous nous bornerons ici à en décrire succinctement le principe, et à en présenter les plus courantes.

Principe[modifier | modifier le wikicode]

La plupart des langages permettent de créer de nouveaux types de données qui sont la réunion de plusieurs autres types de données (struct en C/C++, record en Pascal, classes pour les langages objets, ...). Rendre un type auto référant, consiste simplement à créer un type T et à le munir d'au moins un membre dont le type sera T. Évidemment, tout comme pour les algorithmes, le cas où un type T contient un membre de type S, et que ce dernier contient un membre de type T est englobé par le définition. La représentation classique d'une instance de ce type est formalisée par

La partie données est l'information maintenue par ce type, la case blanche représente une référence vers ce même type et la flèche indique que cette référence est utilisée et pointe vers l'instance concernée. Si la référence ne pointe pas vers une instance alors cela est formalisé ainsi :

Une telle instance indique une terminaison (fin de la liste, feuille d'un arbre)

Représente une instance d'un type agrégeant une chaîne de caractères, trois références. Cette instance contient contient la chaîne de caractères Chat. Les deux premières références ne sont pas utilisées, on dit que leur valeur est nulle, elles ne pointent nulle part. La dernière référence pointe vers une instance du même type contenant la chaîne de caractère Chien. L'ordre des références est en général important.

Les listes chaînées[modifier | modifier le wikicode]

Chaînage simple[modifier | modifier le wikicode]

Les listes simplement chaînées permettent de représenter des listes d'éléments quelconques.

Une instance particulière appelée tête de liste est une référence sur le premier élément de la liste. La liste d'entiers (5, 2, 17, 8) pourrait être représentée ainsi :

On dispose entre autres des fonctions d'accès suivantes pour écrire nos algorithmes :

Chaînage double[modifier | modifier le wikicode]

Si dans la définition du nœud on ajoute une référence , avec la contrainte que pour un nœud N qui n'est ni la tête ni la queue suivant(precedent(N))=precedent(suivant(N))=N, alors on obtient une liste doublement chaînée. Elle peut se parcourir aussi bien de la tête vers la queue que dans l'autre sens.


Pile, file, etc.[modifier | modifier le wikicode]

Les piles et les files sont simplement des listes simplement ou doublement chaînées, seules leurs fonctions d'accès diffèrent. En ce qui concerne la pile, on peut uniquement empiler (ajouter en tête), et dépiler (récupération de la valeur de tête, destruction de celle-ci). Quant à la file, on peut seulement enfiler (ajouter en tête) et défiler (récupération de la valeur de queue, destruction de celui-ci). Parmi les implémentations particulières de listes, on pourra citer, les ensembles (chaque valeur est présente une et une seule fois dans la liste), les listes de hashage, les matrices creuses.

Remarques[modifier | modifier le wikicode]

Les listes apportent un comportement dynamique qui fait parfois défaut aux tableaux. Les tableaux de dimension supérieure à 1 peuvent avantageusement être remplacés par des listes de listes.

Les arbres[modifier | modifier le wikicode]

Les arbres binaires[modifier | modifier le wikicode]

Un arbre binaire représente une structure hiérarchique, comme un arbre généalogique. Le nœud de l'arbre est composé de deux références (tout comme un nœud de liste doublement chaînée), on les nomme souvent FG pour fils gauche et FD pour fils droit. Il faut voir ces liens comme un chemin que l’on emprunte à partir de la racine jusqu'à un nœud. La seule contrainte à propos de ce chemin est qu’il ne doit en exister qu'un à partir de la racine vers un nœud quelconque.

On définit des propriétés telles que le degré d'un nœud (nombre de reférences utilisées, i.e. n'ayant pas une valeur nulle), la hauteur d'un arbre (nombre maximum de descendants), le niveau d'un nœud (distance le séparant de la racine). Un nœud de degré 0 est appelé feuille, un nœud de degré supérieur à 0 est appelé nœud interne.

Début de l'exemple
Fin de l'exemple


Arbres n-aires[modifier | modifier le wikicode]

Un arbre qui est composé de nœuds pouvant avoir au maximum n références est dit arbre n-aire. On le retrouve dans l'arborescence du disque dur, par exemple. Un arbre unaire est une liste, on dit qu’il a dégénéré en liste. Tout arbre n-aire peut être transformé en arbre binaire.

Graphes[modifier | modifier le wikicode]

Si l’on construit une structure avec un nombre quelconque de références, sans contraintes particulières (cycle, connexité, ...) alors on obtient un graphe. Un exemple courant de graphe est une carte routière où les villes sont les nœuds et les routes les références. Les graphes sont des outils d'une puissance extraordinaire, mais leur maîtrise est complexe (mais pas compliqué).