Énoncé 8 : Structures de données complexes

Énoncé 8.1 : La liste chaînée

Durée estimative : 50 minutes

Nous considérons une classe Donnee suivante qui permet d’associer dans un même objet, une clef de type entier et une donnée de type chaîne de caractère.

Voici la version Java de cette classe :

public class Donnee { 
    public int clef; 
    public String valeur; 
 
    public Donnee(int clef, String valeur) { 
        this.clef = clef; 
        this.valeur = valeur; 
    } 
 
    public String toString() { 
        return clef + " " + valeur; 
    } 
} 

Ainsi que la version Python équivalente :

class Donnee: 
    def __init__(self, clef: int, valeur: str): 
        self.clef: int = clef 
        self.valeur: str = valeur 
 
    def __str__(self) -> str: 
        return f"{self.clef} {self.valeur}" 

Écrivez en Java/Python les classes ListeChainee et NoeudListeChainee qui gèrent l’ensemble des nœuds d’une liste chaînée. La classe ListeChainee introduit la racine de la liste ainsi que les méthodes suivantes destinées...

Énoncé 8.3 : L’arbre binaire de recherche

Durée estimative : 75 minutes

Pour cet exercice, vous travaillez sur une nouvelle structure de données : l’arbre binaire de recherche. Vous vous basez sur la structure de classes introduite dans l’exercice 8.1.

Écrivez en Java/Python les classes ArbreBinaire et NoeudArbreBinaire, qui possèdent les mêmes méthodes insere, recherche et affiche que les classes ListeChainee et NoeudListeChainee de l’exercice 8.1.

La méthode affiche doit produire un résultat indenté pour montrer la forme de l’arbre. Par exemple, pour le dernier arbre de la figure de la page suivante, l’affichage doit être le suivant (les nœuds gauches apparaissent avant les nœuds droits) :

 7 7 
10 10 
  11 11 
   14 14 
15 15 

Reprenez ensuite le programme principal de l’exercice 8.1 en l’adaptant pour utiliser la classe ArbreBinaire.

Indice

L’insertion dans un arbre binaire se fait en recherchant la valeur de la clef de la donnée à insérer dans l’arbre binaire. Si elle n’est pas trouvée, l’algorithme consiste à ajouter un sous-nœud au dernier nœud parcouru de la recherche. Ce sous-nœud est inséré à gauche si la valeur de la clef de la donnée à insérer...

Énoncé 8.4 : L’arbre B (ou B-arbre)

Durée estimative : 100 minutes

Nous travaillons à nouveau sur une nouvelle structure de données : l’arbre B. Nous nous basons encore une fois sur la structure de classes introduite dans l’exercice 8.1. Il convient donc d’écrire en Java/Python les classes ArbreB et NoeudArbreB qui possèdent les mêmes méthodes insere, recherche et affiche que les classes ListeChainee et NoeudListeChainee de l’exercice 8.1.

Comme l’insertion dans un arbre B est un algorithme complexe, nous fournissons celui-ci ci-après. Vous trouverez d’abord la version Java, puis la version Python, et pour chaque langage, d’abord la classe ArbreB, puis la classe NoeudArbreB.

En Java, la classe ArbreB ainsi que les attributs et le constructeur de cette classe.

public class ArbreB { 
    NoeudArbreB racine; 
    int ordre; 
 
    public ArbreB(int ordre) { 
        this.ordre = ordre; 
        racine = new NoeudArbreB(ordre); 
    } 
 
    public void insere(int nouvelleClef, String donnee) { 
        Donnee nouvelleDonnee = new Donnee(nouvelleClef, donnee); 
        NoeudArbreB noeudDroitNouvelleDonnee = new NoeudArbreB(ordre); 
        nouvelleDonnee = racine.insere(nouvelleDonnee,  
noeudDroitNouvelleDonnee); 
        if (nouvelleDonnee == null)  
            return; 
        NoeudArbreB nouvelleRacine = new NoeudArbreB(ordre); 
        nouvelleRacine.donnees[0] = nouvelleDonnee; 
        nouvelleRacine.enfants[0] = racine; 
        nouvelleRacine.enfants[1] = noeudDroitNouvelleDonnee; 
        nouvelleRacine.nbrDonnees = 1; 
        racine = nouvelleRacine; 
    } 
 
    // méthodes affiche et recherche à écrire 
} 

Pour la classe NoeudArbreB en Java, la méthode insere, le constructeur et les attributs sont décrits à la suite.

public class NoeudArbreB { 
    Donnee...

Énoncé 8.6  : Les expressions postfixées

Durée estimative : 35 minutes

L’exercice consiste à écrire un interpréteur d’expressions postfixées dans lesquelles les opérateurs sont placés après les opérandes. Par exemple, au lieu d’écrire 2 + 3, il faut écrire 2 3 +. Au lieu de 2 + 3 * 5, il faut écrire 2 3 5 * +. Le principe est qu’un opérateur remplace les deux derniers opérandes par le résultat de l’opération. Ainsi 2 3 5 * + est transformé en 2 15 + puis 17.

Écrivez en Java/Python la classe ExpressionPostFixee qui permet de calculer des expressions postfixées. Cette classe est basée sur l’utilisation d’un objet de la classe Pile. Une pile de taille 5 permet de calculer des expressions très complexes.

La classe ExpressionPostFixee introduit quatre méthodes :