Corrigé 8.  Enoncé

1. Files d'attente dans un tableau circulaire

Définition du type des files d'attente considérées

    TYPE Typefile = STRUCTURE
        Tête    : ENTIER {Pointe le premier élément de la file}
        Long     : ENTIER {Longueur courante de la file }
        Tab     : TABLEAU(1..Max) DE Typeqq
    FIN
Typeqq désigne un type quelconque.

Traduction des opérations du modèle

Dans les procédures suivantes, F désigne une file d'attente et Val un élément du type Typeqq.

Créerfile (F)        :        F.Long := 0 ; F.Tête := 1
                                      {Ou n'importe quelle valeur dans [1,Max]}

Filevide(F)          :        Filevide := (F.Long = 0)

Filepeine(F)       :        Filepleine := (F.Long = Max)

Enfiler(F, Val)   :        SI NON Filepleine(F) :
                                        Queue :=(F.Tête+F.Long - 1)Mod Max + 1
                                        {Queue: variable temporaire }
                                        F.Tab(Queue) := Val
                                        F.Long := F.Long +1
                                    SINON "Overflow" FSI

Défiler(F, Val)  :        SI NON Filefile(F):
                                        Val := F.Tab(F.Tête)
                                         F.Tête := (F.Tête Mod Max) + 1
                                         F.Long := F.Long - 1
                                   SINON "Underflow" FSI

2. Listes linéaires chaînées circulaires (llcc)

Création d'une llcc à partir d'un grand nombre représenté dans un vecteur

Il s'agit d'écrire le module Créer_llcc( V, L, Liste) o�:
V     : vecteur contenant le nombre sous forme de caractères.
L     : nombre de caractères du nombre.
Liste     : liste à créer.
    Allouer (Liste, S)
    { S est le type du maillon à créer }
    Aff_Val(Liste, -1)
    Q := Liste
    TANTQUE L > 0 :
        {Récupérer les 5 derniers caractères dans le vecteur C}
        I:= 1
        TANTQUE I <= 5 ET L >= 1 :
            C(I) := V(L)
            I := I + 1 ; L := L - 1
        FINTANTQUE
        { Les convertir }
        Convert1( C, I-1, Nombre)
        Allouer(P, S)
        Aff_Val(P, Nombre)
        Aff_Adr(Q, P)
        Aff_Adr(P, Liste) { Circularité }
        Q := P
    FINTANTQUE

Le module Convert1(C, I, N) de conversion d'une chaîne de caractères représentée dans un vecteur en un entier est le suivant :

En entrée :
    C : vecteur contenant la chaîne de caractères.
    I : nombre de caractères ( 1 <= I <= 5).

En sortie :
    N : nombre correspondant.
Corps :

    N := 0
    POUR J=1, I : N := N + Ch(C(J))*10 j-1 FINPOUR

Ch désigne la fonction qui associe un chiffre à un caractère.


Restauration du nombre à partir de sa représentation interne

Il s'agit ici de faire l'opération inverse c'est à dire écrire le module Restaurer(Liste, V, L) o� :

Liste     : la liste chaînée représentant le grand nombre.
V     : vecteur à constituer.
L     : nombre de caractères du nombre.

    P := Suivant(Liste)
    TANTQUE Valeur(P) <> -1 :
        Convert2 ( Valeur(P), C, I)
        Mise_deC_dansV
        P := Suivant(P)
    FINTANTQUE
    Mise_a_jour_deV

Le module Convert2(N, C, I) de conversion d'un entier N en une chaîne de caractères C de longueur I représentée dans un vecteur est défini comme suit :

En entrée :
    N : un entier.
En sortie :
    C : vecteur contenant la chaîne de caractères.
    I : nombre de caractères ( 1 <= I <= 5).

Corps :
    I := 0
    POUR J =5, 1:
        SI DIV(N, 10 J-1) <>0 :
            I := I + 1
            C(I) := Car( DIV(N, 10 J-1))
            N:= N - (DIV (N, 10J-1) * 10 J-1
        FSI
    FINPOUR

Car désigne la fonction qui associe un caractère à un chiffre.
Les autres modules :

Mise_deC_dansV : Range la chaîne C courante dans le vecteur V à partir de la fin. La variable K est globale pour ce module et est initialisée à Max + 1 avant le premier appel à ce module.

    POUR J=I,1,-1
        K := K - 1
        V(K) := C(I)
    FINPOUR

Mise_a_jour_deV : Décalage vers le bas du vecteur de la chaîne de caractères représentant le nombre.

    L := Max - K + 1
    POUR J=1, L :
        V(J) := V(J+K-1)
    FINPOUR

Somme de 2 grands entiers positifs

Soient L1 et L2 les listes chaînées représentant les deux grands nombres à additionner, L3 la liste chaînée résultante.


    Pp := Suivant(L1) ; Qq := Suivant(L2)
    {Création du maillon d'en-tête}
    Allouer (L3, S) { S est le type du maillon }
    Aff_Val(L3, -1); Aff_Adr(L3, L3)
    P := L3
    Retenue := 0
    TANTQUE Valeur(Pp)<>-1 ET Valeur(Qq)<>-1 :
        Total := Valeur(Pp) + Valeur(Qq) + Retenue
        Nombre := Mod( Total, 105)
        Retenue := DIV(Total, 105)
        Allouer (R,S); Aff_Val(R, Nombre)
        Aff_Adr(P,R) ; Aff_Adr(R, L3)
        P:= R
        Pp := Suivant(Pp); Qq := Suivant(Qq)
    FINTANTQUE
    SI Valeur(Pp) <>-1 : Rr := Pp SINON Rr := Qq FSI
    TANTQUE Valeur(Rr) <> -1 :
        Total := Valeur(Rr) + Retenue
        Nombre := Mod( Total, 105)
        Retenue := DIV(Total, 105)
        Allouer (R, S) ; Aff_Val(R, Nombre)
        Aff_Adr(P,R) ; Aff_Adr(R, L3)
        P := R
    FINTANTQUE
    SI Retenue = 1
        Allouer (R, S); Aff_Val(R, 1)
        Aff_Adr(P,R) ; Aff_Adr(R, L3)
    FSI