Corrigé 2.  Enoncé

1. Files d'attente

Le modèle des files d'attente est l'ensemble suivant :
Modèle = { Creerfile(F), Filevide(F), Enfiler(F, Val), Defiler(F, Val) }

Définition du type file d'attente

    TYPE S = STRUCTURE
        Element : Typeqq
        Suiv     : POINTEUR(S)
    FIN
    TYPE Filedattente = STRUCTURE
        Tete, Queue : POINTEUR(S)
    FIN

Implémentation au moyen des listes linéaires chaînées

çà revient à traduire les opérations du modèle de file d'attente au moyen des opérations du modèle des listes linéaires chaînées.

Creerfile ( F )      :    F.Tete := NIL

Filevide( F)         :    Filevide := ( F.Tete = NIL )

Enfiler (F , Val)  :    Allouer (P, S)
                                 Aff_Val(P, Val)
                                  Aff_Adr(P, NIL)
                                 SI NON Filevide(F) :
                                     Aff_Adr(F.Queue, P)
                                SINON     
                                     F.Tete := P
                                    F.Queue := P
                                 FSI
   

Defiler ( F, Val) :    SI NON Filevide(F)
                                    P := F.Tete   
                                     Val := Valeur(F.Tete)
                                     F.Tete := Suivant(F.Tete)
                                     Liberer(P)
                                 SINON " Underflow" FSI


2. Parcours d'un arbre ternaire

Modèle

Chaque noeud peut avoir 3 fils : fils gauche, fils centre( par exemple) et fils droit.

Le modèle sur les arbres ternaires peut être défini comme suit :
Modèle = { Creernoeud(Val), Liberer(N), Info(N), Aff_info(N, Val), Fg(N), Fc(N), Fd(N), Aff_fg(N, M), Aff_fc(N, M), Aff_fd(N, M) }

Les opérations sont réparties en classes comme suit :

Allocation     : Creernoeud(Val)
Libération     : Liberernoeud(N)
Consultation    : Info(N), Fg(N), Fd(N), Fc(N)
Mise à jour     : Aff_fg(N, M), Aff_fc(N, M), Aff_fd(N, M)

Algorithme de parcours d'un arbre ternaire niveau par niveau

En entrée     : un arbre non vide de racine Racine.
En sortie     : la liste des noeuds de l'arbre niveau par niveau.

L'algorithme utilise une file d'attente F.

    " Info(Racine) "
    Creerfile(F)
    Enfiler(F, Racine)
    TANTQUE NON Filevide(F) :
        Defiler(F, Noeud)
        " Info(Noeud) "
        Enfiler(Fg(Noeud)
        Enfiler(Fc(Noeud)
        Enfiler(Fd(Noeud)
    FINTANTQUE


3. Listes linéaires chaînées en représentation contigu�

Définition de la structure

    TYPE T = STRUCTURE
        Info    : Typeqq
        Lien    : ENTIER
        Vide     : BOOLEEN { Position vide }
    FIN
    VAR T : TABLEAU ( 1 : Max ) DE T ;

Initialement les champs Vide de tous les éléments sont à VRAI. ( pour indiquer des positions disponibles)

L'indice -1 représente NIL.

Une liste sera définie par l'indice de son premier élément dans le tableau T.

L'implémentation du modèle de listes linéaires chaînées au moyen de tableaux revient à traduire les opérations du modèle de listes linéaires chaînées au moyen du modèle sur les tableaux avec la seule opération d'indexation.

Le module Allouer ( P ) rend dans P l'indice d'une position vide sinon la valeur -1 ( s'il n y a pas de place ). Ceci revient à chercher une entrée libre P dans le tableau T. Une solution simple consiste à balayer le tableau linéairement du début vers la fin jusqu'à la rencontre d'une entrée libre.

        I := 1 ; Trouv := FAUX
        TANTQUE I <= Max ET NON Trouv :
            SI T(I).Vide : Trouv := VRAI
            SINON I := I + 1 FSI
        FINTANTQUE
        SI NON Trouv : P := - 1 { ou NIL }
        SINON
            P := I
            T(I).Vide := FAUX
        FSI

Les autres opérations en bref :

Libérer(P)        : T(P).vide := VRAI
Valeur(i)         : valeur := t(i).info
Suivant(I)        : Suivant := T(I).Lien
Aff_Adr(I,J)    : T(I).Lien := J
Aff_val(i, val): t(i).info := val

Recherche d'un élément

En entrée : la liste I et l'élément Elément à rechercher.
En sortie : Trouv ( existence de l'élément )
Si Trouv est VRAI
    - P : indice de l'élément recherché,
    - Q : indice de l'élément qui précède l'élément recherché.
Si Trouv est FAUX
    - Q : indice du dernier élément de la liste.

L'algorithme est le suivant :
    Q := NIL
    Trouv := FAUX
    P := I { Tête de liste }
    TANTQUE P <>NIL ET NON Trouv :
        SI Valeur(P) = Element
            Trouv := VRAI
        SINON
            Q := P ; P := Suivant(P)
        FSI
    FINTANTQUE

Insertion d'un élément en fin de liste

En entrée : la liste I et l'élément Elément à insérer
En sortie : la liste I avec l'élément Elément inséré à la fin.

    Recherche( I, Elément, Trouv, Q, P)
    SI NON Trouv :
        Allouer( R)
        SI R <> NIL
            Aff_Adr( Q, R)
            Aff_Val(R, Element)
            Aff_Adr(R,, NIL)
        SINON "Debordement" FSI
    SINON "Double" FSI

Supprimer un élément donné de la liste

En entrée     : la liste I et l'élément Elément à supprimer.
En sortie    : la liste I avec l'élément Elément supprimé.

    Recherche(I, Element, Trouv, Q, P) :
    SI Trouv :
        R := P
        SI Q <> NIL
            Aff_Adr(Q, Suivant(P))
        SINON
            R := I
            I:= Suivant(I) { C'est le premier élément }                 

        FSI
        Liberer ( R)
    SINON " L'élément n'existe pas " FSI