Corrigé 8

Prérequis

Corrigé 8.1 : La liste chaînée

Pour la classe ListeChainee, la méthode insere crée un nouveau nœud si la racine a pour valeur null (Java)/None (Python). Dans le cas contraire, elle transmet la création au nœud référencé par la racine. Il en est de même pour les deux autres méthodes affiche et recherche qui invoquent la méthode correspondante si la racine référence un objet.

La classe NoeudListeChainee introduit les mêmes méthodes. Dans la méthode insere, si la clef à insérer est la même que celle du nœud, la valeur associée est simplement mise à jour. Dans le cas contraire, si nous sommes en tête de liste, un nouveau nœud est créé, sinon l’insertion est transmise au nœud suivant.

La méthode affiche affiche le contenu du nœud, puis demande au nœud suivant, s’il existe, de s’afficher à son tour. La méthode recherche teste si la clef recherchée est celle du nœud. Dans le cas contraire, la recherche continue au niveau du nœud suivant.

La classe ListeChainee en Java s’écrit comme suit.

public class ListeChainee { 
    NoeudListeChainee racine; 
 
    public void insere(int nouvelleClef, String donnee) { 
        Donnee nouvelleDonnee = new Donnee(nouvelleClef, donnee); 
        if (racine == null) 
            racine = new NoeudListeChainee(nouvelleDonnee); 
        else 
            racine.insere(nouvelleDonnee); 
    } 
 
    public void affiche() { 
        if (racine != null) 
            racine.affiche(); 
    } 
 
    public Donnee recherche(int clef) { 
        if (racine != null) ...

Corrigé 8.2 : La table de hachage

La classe TableHachage est présentée à la suite. La méthode fonctionHachage qui met en œuvre la fonction de hachage prend une clef en paramètre et renvoie le modulo de cette clef avec la taille du tableau.

La méthode insere calcule la fonction de hachage de la clef à insérer. Si la valeur de la table à l’indice correspondant est null (Java)/None (Python), une nouvelle liste chaînée est créée. Ensuite, la clef et les données sont insérées dans la liste référencée par la table.

La méthode affiche demande à toutes les listes présentes dans le tableau de s’afficher. Enfin, la méthode recherche demande à la liste présente à l’indice donné par la fonction de hachage d’effectuer la recherche.

Pour Java, la classe TableHachage se présente ainsi :

public class TableHachage { 
    final int tailleTable = 10; 
 
    ListeChainee table[] = new ListeChainee[tailleTable]; 
 
    public int fonctionHachage(int nouvelleClef) { 
        return nouvelleClef % tailleTable; 
    } 
 
    public void insere(int nouvelleClef, String donnee) { 
        int i = fonctionHachage(nouvelleClef); 
        if (table[i] == null) ...

Corrigé 8.3 : L’arbre binaire de recherche

La classe ArbreBinaire possède des méthodes semblables à celles de la classe ListeChainee introduite dans l’exercice 8.1. Cette classe possède un attribut pour référencer le nœud racine de type NoeudArbreBinaire. Si ce nœud n’existe pas, il est créé à la première insertion. Dès que ce nœud existe, les méthodes d’insertion, d’affichage et de recherche lui délèguent le travail.

Au niveau de la classe NoeudArbreBinaire, les méthodes sont basées sur l’ordre des clefs. L’insertion au niveau d’un nœud de l’arbre ressemble à l’insertion au niveau d’un nœud d’une liste chaînée. Cependant, l’ajout du nouveau nœud se fait soit sur l’enfant gauche soit sur l’enfant droit. L’enfant choisi dépend de la comparaison entre la clef à insérer et la clef du nœud. Si la clef à insérer est inférieure, l’insertion est réalisée à gauche et si la clef à insérer est supérieure, l’insertion est réalisée à droite.

La méthode affiche prend en paramètre une marge gauche qui correspond à la profondeur du nœud. L’enfant gauche est affiché en premier. L’enfant droit est affiché après l’affichage de la donnée du nœud.

La méthode recherche se base également sur la comparaison entre la clef recherchée et la clef du nœud pour continuer la recherche vers l’enfant gauche ou l’enfant droit.

La classe ArbreBinaire écrite en Java est présentée à la suite.

public class ArbreBinaire { 
    NoeudArbreBinaire racine; 
 
    public void insere(int nouvelleClef, String donnee) { 
        Donnee nouvelleDonnee = new Donnee(nouvelleClef, donnee); 
        if (racine == null) 
            racine = new NoeudArbreBinaire(nouvelleDonnee); 
        else 
            racine.insere(nouvelleDonnee); 
    } 
 
 ...

Corrigé 8.4 : L’arbre B (ou B-arbre)

Les méthodes insere des classes ArbreB et NoeudArbreB sont fournies dans l’énoncé.

La méthode insere de la classe ArbreB invoque la méthode insere de la racine qui est de type NoeudArbreB. Si celle-ci renvoie une nouvelle donnée à insérer et donc un nouveau nœud droit, ceci signifie que la racine doit être scindée. Une nouvelle racine est alors créée, qui référence l’ancienne racine et le nouveau nœud droit et contient pour seule donnée celle qui a été renvoyée par la méthode insere de la racine.

La méthode insere de la classe NoeudArbreB commence par examiner si la donnée doit être insérée dans un nœud enfant. Dans ce cas, il est possible que cette opération renvoie une nouvelle donnée à insérer (la variable noeudDroitNouvelleDonnee (Java)/noeud_droit_nouvelle_donnee (Python) référence alors le nouveau nœud à référencer).

La suite de la méthode consiste à insérer la donnée au bon endroit dans le nœud. La technique d’insertion décale les données déjà présentes vers la droite en gardant la donnée la plus à droite et le nœud enfant correspondant dans les variables nouvelleDonnee et noeudDroitNouvelleDonnee (Java)/nouvelle_donnee et noeud_droit_nouvelle_donnee (Python). Si le nœud n’est pas complet, cette donnée située à droite est insérée. Dans le cas contraire, il y a scission, un nouveau nœud est créé qui va contenir à sa droite cette donnée. La valeur située au milieu (indicée par l’ordre dans le nœud) est renvoyée ainsi que le nouveau nœud qui vient d’être créé.

Les méthodes affiche et recherche de la classe ArbreB se contentent d’invoquer la méthode correspondante de la racine. La méthode affiche de la classe NoeudArbreB affiche d’abord le premier enfant du nœud puis pour chaque donnée, sa valeur et l’enfant associé.

Dans la classe NoeudArbreB, la méthode recherche commence par rechercher la plus petite clef supérieure à...

Corrigé 8.5 : La pile

La classe Pile en Java est illustrée ci-dessous. La méthode empile ajoute au sommet du tableau la nouvelle valeur si le tableau n’est pas complet. La méthode depile renvoie la valeur située au sommet de la pile.

public class Pile { 
    String[] tableau; 
    int sommet; 
 
    public Pile(int taille) { 
        tableau = new String[taille]; 
        sommet = 0; 
    } 
 
    public boolean empile(String valeur) { 
        if (sommet < tableau.length) { 
            tableau[sommet] = valeur; 
            sommet++; 
            return true; 
        } else 
            return false; 
    } 
 
    public String depile() { 
        if (sommet > 0) { 
            sommet--; 
            return tableau[sommet]; 
        } 
        return null; 
    } 
} 

Le programme principal de test se trouve à la suite.

import java.util.Scanner; ...

Corrigé 8.6 : Les expressions postfixées

La classe ExpressionPostfixee repose sur l’utilisation d’une pile. La méthode empileValeur (Java)/empile_valeur (Python) empile la valeur dans la pile en la convertissant en une chaîne de caractères.

Les méthodes add et mult dépilent deux opérandes, puis les convertissent en deux entiers, calculent le résultat de l’opération et l’empilent sous forme d’une chaîne de caractères.

La classe ExpressionPostfixee en version Java est détaillée ci-dessous.

public class ExpressionPostfixee { 
    final int taille = 5; 
    Pile pile = new Pile(taille); 
 
    public boolean empileValeur(int valeur) { 
        return pile.empile(Integer.toString(valeur)); 
    } 
 
    public void add() { 
        int a, b; 
        String valeur = pile.depile(); 
        if (valeur != null) 
            a = Integer.parseInt(valeur); 
        else 
            a = 0; 
        valeur = pile.depile(); 
        if (valeur != null) 
            b = Integer.parseInt(valeur); 
        else 
            b = 0; 
        pile.empile(Integer.toString(a...