Corrigé 21.  Enoncé

1. Suppression dans une liste linéaire chaînée bidirectionnelle

Suppression d'un élément pointé par p dans une liste linéaire chaînée bidirectionnelle

    SI P # NIL :
        SI Précédent(P) # NIL :
            Aff_Adrd( Précédent(P), Suivant(P) )
        SINON L := Suivant (P) FSI
        SI Suivant(P) # NIL :
            Aff_Adrg( Suivant(P), Précédent(P) )
        FSI
        Libérer(P)
    FSI

2. Parcours "inordre" avec une pile

Algorithme itératif de parcours "inordre" avec utilisation d'une pile

    Créerpile(Pile)
    Possible := VRAI
    TANTQUE Possible :
        TANTQUE P # NIL :
            Empiler (Pile, P)
            P := Fg(P)
        FINTANTQUE
        SI NON Pilevide(Pile) :
            Dépiler(Pile, P)
            " Info(P) "
            P := Fd(P)
        SINON
            Possible := FAUX
        FSI
    FINTANTQUE

3. Expression arithmétique sous forme d'un arbre binaire

Voir C18. Exercice 1.


4. Essai linéaire externe

Schéma d'un fichier h-code avec l'essai linéaire

Structure d'un bloc

    TYPE Typebloc = STRUCTURE
        Nb     : ENTIER
        Tab     : TABLEAU[1..B] DE Typearticle
    FIN

Module de recherche

F désigne le fichier et Bloc une zone mémoire de type Typebloc.

    H := Hash(Clé) { Hash est une fonction de hachage }
    Lirebloc( F, H, Bloc)
    Continue := VRAI
    TANTQUE Continue :
        { Rechercher dans le bloc }
        Trouv := FAUX ; I := 1
        TANTQUE NON Trouv ET I <= Bloc.Nb
            SI Bloc.Tab(I) = Clé :
                Trouv := VRAI
            SINON
                I := I + 1
            FSI
        FINTANTQUE
        SI Trouv :
            Continue := FAUX
        SINON
            SI Bloc.Nb < B:
                Continue := FAUX
            SINON
                H := H - 1; SI H < 0 : H:=H+M FSI
                Lirebloc(F, H, Bloc)
            FSI
        FSI
    FINTANTQUE


Module d'insertion

Soit Trouv et H les paramètres donnés par le module de recherche. Bloc contient le dernier bloc lu.

    SI Trouv :
        "Insertion impossible"
    SINON
        N := N + 1
        SI N = M*B - 1 :
            "Débordement"
        SINON
            Bloc.Nb := Bloc.Nb + 1
            Bloc.Tab(Bloc.Nb) := Clé
            Ecrirebloc(F, H, Bloc)
        FSI
    FSI

5. Arbre B

Définition : voir dans la partie II. Se référer au corrigé 22. Exercice 6.