Corrigé 17.  Enoncé

1. Insertion par position dans une liste bidirectionnelle.

Insertion d'un élément Val dans une liste bidirectionnelle L à la k-ième position

On suppose L # NIL et k > 0.

    P := L
    I := 0
    TANTQUE P # NIL ET I < (K-1) :
        P := Suivant(P)
        I := I + 1
    FINTANTQUE
    {P pointe Le K-ième élément}
    {Effectuons une insertion avant cet élément }
    Allouer(Q, Typemaillon)
    Aff_Val(Q, Val)
    SI Précédent(P) # NIL :
        Aff_Adrd(Précédent(P), Q)
    SINON
        L := Q
    FSI
    Aff_Adrg(Q, Précédent(P) )
    Aff_Adrd(Q, P)
    Aff_Adrg(P, Q)

2. Inversion d'une liste linéaire chaînée

Module récursif d'inversion

    Inverser(L) :
    SI L # NIL :
        Inverser( Suivant(L))
        Insérer ( Tête, Valeur(L) )
    FSI

Le module Insérer(Tête, Val) insère la valeur Val dans la liste pointée par Tête. Il est défini comme suit :

    Allouer(Q, Typemaillon)
    Aff_Val(Q, Val)
    Aff_Adr(Q, Tête)
    Tête := Q

Trace

Iv(L)     =     Iv(P1), Is(5)
    =    Iv(P2),Is(12), Is(5)
    =     Iv(P3), Is(14), Is(12), Is(5)
    =     Iv(Nil), Is(8), Is(14), Is(12), Is(5)
    =     Is(8), Is(14), Is(12), Is(5)

Iv désigne le module Inverser et Is le module Insérer.

3. Parcours d'un arbre binaire

Prenons l'inordre.

Algorithme récursif
   
    In(N) :
    SI N # NIL :
        In(Fg(N)) ; "Info(N)" ; In(Fd(N))
    FSI

Algorithme itératif avec 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

4. Implémentation d'une pile.

Créerpile(Pile)         :      Pile := NIL
Pilevide(Pile)           :      Pilevide := ( Pile = NIL)

Empiler(Pile, Val)   :      Allouer (Q, Typemaillon)
                                       Aff_Val(Q, Val)
                                       Aff_Adr(Q, Pile)
                                       Pile := Q

Dépiler(Pile, Val)   :     SI NON Pilevide(Pile) :
                                            Q := Pile
                                            Valeur := Info(Pile)
                                            Pile := Suivant(Pile)
                                            Libérer(Q)
                                      SINON " Pile vide" FSI



5. Recherche dans l'essai linéaire

Module de recherche

Soit T le tableau en mémoire centrale. Chaque entrée est le couple (Valeur, Occupé). Valeur est la valeur rangée et Occupé un booléen indiquant si l'entrée est occupée ou pas.

    I := H(Clé)
    Trouv, Vide := FAUX
    TANTQUE NON Trouv ET NON Vide :
        SI T(I).Valeur = Val :
            Trouv := VRAI
        SINON
            SI NON T(I).Occupé :
                Vide := VRAI
            SINON I := I-1, SI I <0 : I := I+M FSI
        FSI
    FINTANTQUE

Noter qu'il doit toujours exister une position vide dans le vecteur.

6. Arbre de recherche m-aire

Structure logique d'un noeud

Il y a n pointeurs et (n-1) clés.
On peut définir le modèle suivant sur le noeud :
Fils(Bloc, I)     : accès au i-ième fils du noeud contenu dans Bloc. 1 <= I <= n.
Clé(Bloc, I)     : accès à la i-ième clé du noeud contenu dans Bloc. 1 <= I < n.
Nbr(Bloc)     : nombre courant de fils dans Bloc.

Algorithme

    { Soit Racine le pointeur de la page racine sur le disque}
    P := Racine
    Trouv := FAUX
    TANTQUE P # NIL ET NON Trouv :
        Lirebloc(F, P, Bloc)
        I := 1 ; Trouv := FAUX
        TANTQUE I < Nbr(Bloc) ET NON Trouv :
            SI Clé(Bloc, I) >= Clé :
                Trouv := VRAI
            SINON I := I + 1 FSI
        FINTANTQUE
        SI Trouv :
            SI Clé(Bloc, I) = Clé :
                Trouv := VRAI
            SINON
                P := Fils(Bloc, I)
            FSI
        SINON P := Fils(Bloc, I) FSI
    FINTANTQUE