Corrigé 15.  Enoncé

1. Arbre de listes linéaires chaînées

Dans ce qui suit, cc désigne une chaîne de caractères et llc une liste linéaire chaînée.

a) Module CréerList (C, L)

Crée la llc L à partir de la cc C.

Soit S le type d'un maillon et Q une variable de type POINTEUR.

    L := NIL
    POUR I=1, Long(C)
        Allouer(Q, S)
        Aff_Val(Q, C(I) )
        Aff_Adr(Q, NIL)
        SI L # NIL : Aff_Adr(P, Q) SINON L := Q FSI
        P := Q
    FINPOUR


b) Module CréerChaîne (L, C)

Crée la cc C à partir de la llc L.
Q étant une variable de type POINTEUR.
    Q := L ; I := 0
    TANTQUE Q # NIL :
        I := I + 1
        C(I) := Valeur(Q)
        Q := Suivant(Q)
    FINTANTQUE

c) Module de Recherche-Insertion

On commence par définir le module Recherche (L, C, Trouv, Sauv) qui recherche la cc C dans la llc L. Si C n'est pas trouvée, Trouv prend la valeur FAUX et Sauv pointe une feuille.
Q étant une variable de type POINTEUR.

    Q := L
    Trouv := FAUX
    TANTQUE Q # NIL ET NON Trouv :
        Sauv := Q
        Créerchaîne( Valeur(Q), Chaîne)
        SI Chaîne = C :
            Trouv := VRAI
        SINON
            SI Chaîne < C : Q := Fd(Q)
            SINON Q := Fg(Q) FSI
        FSI
    FINTANTQUE

Le module d'insertion est alors le suivant :

P et R étant des variables de type POINTEUR.

    Recherche (L, C, Trouv, Sauv)
    SI NON Trouv :
        Créerlist(C, P)
        R := Créernoeud(P)
        SI C < Chaîne : Aff_Fg(Sauv, R)
        SINON Aff_Fd(Sauv, R) FSI
    SINON " C existe " FSI

d) Module récursif d'impression de toutes les chaînes de caractères en ordre croissant

Il s'agit de faire un parcours en " inordre ". A étant la racine de l'arbre.
    Imprimer( A )
    SI A # NIL :
        Imprimer(Fg( A ))
        Créerchaîne(A, C) ; Ecrire( C)
        Imprimer( Fd(A) )
    FSI

e) Algorithme récursif qui détermine le pourcentage d'octets utilisés par rapport à l'encombrement mémoire total sachant qu'un pointeur occupe 2 octets

Xg, Xd ( des réels ) et Tg, Td ( des entiers ) désignent des variables globales au module récursif suivant :

    Pourcentage ( A, Taille, P ) :

    SI A = NIL :
        Taille := 0 ; P := 0
    SINON
        Pourcentage( Fg(A), Tg,Xg)
        Pourcentage ( Fd(A), Td, Xd)
        Taille := (6 + Longueur(Info(A)) *3 ) + Tg + Td
        P := ( Longueur(Info(A)) + Xg*Tg + Xd*Td ) / Taille
    FIN


f) Au moment de la visite "inordre" d'un noeud, la pile contient uniquement les noeuds par lesquels on "sort" par la gauche.

g) Dans le module de recherche, on ajoute tout simplement l'opération Empiler (Pile, N) avant l'affectation " Q := Fg(Q) "

h) Algorithme qui imprime toutes les cc commençant par un caractère C donné

Soient :
- P : le pointeur de la plus petite chaîne de caractères commençant par le caractère C si elle existe déterminée par le module de recherche.
- Pile : la pile contenant les noeuds par lesquels l'algorithme de recherche " se dirige " par la gauche.
Q étant une variable de type POINTEUR, Continue une variable booléenne.
    Continue := VRAI
    TANTQUE Continue :
        Q := Fd(P)
        SI Q # NIL :
            TANTQUE Fg(Q) # NIL :
                Empiler( Pile, Q )
                Q := Fg(Q)
            FINTANTQUE
            { Q est le pointeur du prochain noeud }
            SI Valeur( Info(Q) ) = C :
                Créerchaîne( Info(Q), C)
                Ecrire(C)
            SINON Continue := FAUX FSI
        SINON
            Dépiler( Pile, N, Possible)
            SI Possible :
                SI Valeur( Info(Q) ) = C :
                    Créerchaîne( Info(Q), C)
                    Ecrire(C)
                SINON Continue := FAUX FSI
            SINON
                Continue := FAUX
            FSI
        FSI
    FINTANTQUE