Corrigé 9. Enoncé

1. Hachage

Soient L, I et S les méthodes respectives d'essai linéaire, chaînage interne et chaînage séparé.

Définition des structures de données

    L :
        TYPE T1 = STRUCTURE
            Vide : BOOLEEN
            Cle : Typeqq
        FIN

    I :
        TYPE T2 = STRUCTURE
            Vide : BOOLEEN
            Cle : Typeqq
            Lien : ENTIER
        FIN

    S :
        TYPE T2 = STRUCTURE
            Vide : BOOLEEN
            Cle : Typeqq
            Lien : POINTEUR(Pt)
        FIN

Avec Pt défini comme suit :

    TYPE Pt = STRUCTURE
        Info : Typeqq
        Suiv : POINTEUR(Pt)
    FIN

Pour les trois méthodes, le tableau est défini comme suit:

    VAR T : TABLEAU(0..9) DE Ti;
    i = 1, 2, 3.

Remplissage du tableau par chaque méthode

Etats successifs du tableau après suppression de a et i dans le cas du chaînage interne

2. Arbres de recherche binaire

Construction de l'arbre

Listage des clés
Inordre         : 3, 8, 9, 10, 11, 12, 13, 15, 20, 35, 66
Préordre         : 12, 8, 3, 9, 11, 10, 15, 13, 20, 35, 66
Postordre         : 3, 10, 11, 9, 8, 13, 66, 35, 20, 15, 12

Algorithme récursif de parcours en ordre décroissant

    D(P) :
    SI P # NIL :
        D(Fd(P))
        Ecrire( Info(P) )
        D(Fg(P))
    FSI

Etat de la pile

Feuilles    Contenus de la pile                

    3     12, 8
    10     12, 11
    13         15
    66        vide

Fonction qui donne le suivant d'une feuille donnée

Soit Pt le pointeur d'une feuille F et � une pile contenant le chemin de la racine vers cette feuille. Soit Feuille(P) un prédicat égal à VRAI si P est une feuille, FAUX sinon.

    Continue := VRAI
    TANTQUE Continue :
        Remonter := VRAI
        Depiler(�, P, Possible)
        TANTQUE Remonter ET Possible :
            SI Pt = Fd(P) :
                Pt := P
                Depiler(�, P, Possible)
            SINON Remonter := FAUX FSI
        FINTANTQUE
        SI NON Possible :
            "Pas de suivant"
            Suivant := NIL
            Continue := FAUX
        SINON
            Si Fd(P) # NIL :
                Empiler(�, P)
                P := Fd(P)
                TANTQUE Fg(P) # NIL :
                    Empiler(�, P)
                    P := Fg(P)
                FINTANTQUE
                SI Feuille(P) :
                    Pt := P ; Continue := FAUX
                SINON Empiler(�, P) ; Pt := NIL FSI
            SINON
                Pt := P   
            FSI
        FSI
    FINTANTQUE