définit la notion d’arbres (informations arborescentes). La plupart
des algorithmes utilisent la récursivité qui s’impose pleinement pour le traitement des arbres. Les algorithmes sont concis, naturels, faciles à concevoir et à
comprendre dès lors que le concept de récursivité est maîtrisé. De nombreux exemples
concrets sont donnés dans ce but. La fin du chapitre présente les arbres
ordonnés (les éléments sont placés dans l’arbre suivant un critère d’ordre) pouvant
servir d’index pour retrouver rapidement des informations à partir d’une clé. En cas
d’ajouts ou de retraits, on peut être amené à réorganiser la structure d’un arbre (le
rééquilibrer) pour que les performances ne se dégradent pas trop.
Manifestement, les fonctions premier et prochain nécessitent un « pointeur sur un élément courant ». Il sera membre donnée de la classe liste. Nous conviendrons (classiquement) que la fin de liste est matérialisée par un nœud comportant un pointeur « nul ». La classe liste devra disposer d’un constructeur dont le rôle se limitera à l’initialiser à une « liste vide », ce qui s’obtiendra simplement en plaçant un pointeur nul comme adresse de début de liste (cette façon de procéder simplifie grandement l’algorithme d’ajout d’un élément en début de liste, puisqu’elle évite d’avoir à distinguer des autres le cas de la liste vide).
RÉCURSIVITÉ DES PROCÉDURES : DÉFINITION
La récursivité est une méthode de description d’algorithmes qui permet à une procédure de s’appeler elle-même (directement ou indirectement). Une notion est récursive si elle se contient elle-même en partie, ou si elle est partiellement définie à partir d’elle-même
Algorithme d’instanciation ou d’appel d’une fonction
Précisons comment doivent être aménagées les règles de recherche d’une fonction surdéfinie, dans le cas où il existe un ou plusieurs patrons de fonctions. Lors d’un appel de fonction, le compilateur recherche tout d’abord une correspondance exacte avec les fonctions « ordinaires ». S’il y a ambiguïté, la recherche échoue (comme à l’accoutumée). Si aucune fonction « ordinaire » ne convient, on examine alors tous les patrons ayant le nom voulu (en ne considérant que les paramètres de type). Si une seule correspondance exacte est trouvée, la fonction correspondante est instanciée (du moins, si elle ne l’a pas déjà été) et le problème est résolu. S’il y en a plusieurs, la recherche échoue
Insertion dans une liste ordonnée L’insertion dans une liste ordonnée
se fait toujours suivant le même algorithme. Cependant la comparaison de l’objet à insérer par rapport aux objets déjà dans la liste dépend de l’objet de l’application. La comparaison peut porter sur des entiers, des réels, des chaînes de caractères, ou même sur plusieurs champs (nom et prénom par exemple). La fonction locale enOrdre() suivante indique si objet1 et objet2 sont en ordre (croissant si ordreCroissant est vrai, décroissant sinon). Elle utilise la fonction comparer() qui fournit une valeur si , égale à 0 si objet1 = objet2, et supérieure à 0 sinon.