Corrigé 44.  Enoncé

SOIT
    Fdon UN FICHIER DE VECTEUR ( 50 ) DE CAR BUFFER Bufdon ;
    Pos : ENTIER ;
    Dernier_bloc : ENTIER ;
    Taille : ENTIER ;
    Seuil : ENTIER ;
    Findex UN FICHIER DE VECTEUR ( 5 ) DE CHAINES BUFFER Bufindex ;
    Ind UN ENTIER ;
    {chaine = cle(3) + numero de bloc(3) + depl(3) }
    A UN ARB DE ( CHAINE , ENTIER , ENTIER ) ;
    C UNE FONCTION ( CHAINE ) ;
    E UNE FONCTION ( ENTIER ) ;
    Inserer , Copier , Extraire DES ACTIONS ;
    Inser_fdon UNE ACTION ;
    Inordre UNE ACTION ;
    Lister_seq , Lister_ord DES ACTIONS ;
    Sauver_index , Inordr DES ACTIONS ;
    dicho_interne, dicho_externe des actions;

DEBUT
    A := NIL ;
    Pos := 1 ;
    Dernier_bloc := 1 ;
    Taille := 50 ;
    Seuil := 12 ;
    {1 + 3 + 4 + 4 + x; x >= 0 }
    APPEL Inserer ;
    APPEL Lister_seq ;
    APPEL Lister_ord ;
    APPEL Sauver_index ;
    ECRIRE('Dicho');
    appel dicho_externe(1, 4);
FIN

/* Insertion de n articles */
ACTION Inserer ;
SOIT
    I UN ENTIER ;
    Trouv : BOOLEEN ;
    P , Q DES ARB DE ( CHAINE , ENTIER , ENTIER ) ;
    Cle , Inf DES CHAINES ;
    S : ( CHAINE , ENTIER , ENTIER ) ;
    Numbloc , Depl DES ENTIERS ;

DEBUT
    OUVRIR ( Fdon , 'fdon.pas' , 'N' ) ;
    POUR I := 1 , 20
        P := A ;
        Cle := ALEACHAINE ( 4 ) ;
        Inf := ALEACHAINE ( ALEANOMBRE ( 10 ) + 4 ) ;
        Trouv := FAUX ;
        TQ ( P <> NIL ) ET NON Trouv
            Q := P ;
            SI STRUCT ( INFO ( P ) , 1 ) = Cle
                Trouv := VRAI
            SINON
                SI Cle < STRUCT ( INFO ( P ) , 1 )
                    P := FG ( P )
                SINON
                    P := FD ( P )
                FSI
            FSI
        FTQ ;
        SI NON Trouv
            APPEL Inser_fdon ( Cle + Inf , Numbloc , Depl ) ;
            INIT_STRUCT ( S , [ Cle , Numbloc , Depl ] ) ;
            SI A = NIL
                CREERNOEUD ( A ) ;
                AFF_INFO ( A , S )
            SINON
                CREERNOEUD ( P ) ;
                AFF_INFO ( P , S ) ;
                SI Cle < STRUCT ( INFO ( Q ) , 1 )
                    AFF_FG ( Q , P )
                SINON
                    AFF_FD ( Q , P )
                FSI
            FSI
        FSI
    FPOUR ;
    /* Ecriture dernier bloc */
    SI Pos <> 1
        ECRIRESEQ ( Fdon , Bufdon )
    FSI ;
    FERMER ( Fdon ) ;
FIN

/*-------------------------CONVERSION-------------------------------*/
/* Entier ---> Chaine */
FONCTION C ( N ) : CHAINE ;
SOIT
    N , Q , R DES ENTIERS ;
    Chain UNE CHAINE ;
DEBUT
    Chain := '123456789' ;
    Q := N ;
    C := '' ;
    TQ Q <> 0
        R := MOD ( Q , 10 ) ;
        SI R = 0
            C := '0' + C
        SINON
            C := CARACT ( Chain , R ) + C
        FSI ;
        Q := Q / 10 ;
    FTQ ;
    SI LONGCHAINE ( C ) = 1
        C := '00' + C
    SINON
        SI LONGCHAINE ( C ) = 2
            C := '0' + C
        FSI
    FSI
FIN
/* Chaine --> Entier */
FONCTION E ( C ) : ENTIER ;
SOIT
    C UNE CHAINE ;
    Chain UNE CHAINE ;
    I , K , R DES ENTIERS ;
    Trouv : BOOLEEN ;

DEBUT
    Chain := '123456789' ;
    E := 0 ;
    POUR I := 1 , LONGCHAINE ( C )
        K := 1 ;
        Trouv := FAUX ;
        R := 0 ;
        TQ ( K <= 9 ) ET NON Trouv
            SI CARACT ( Chain , K ) = CARACT ( C , I )
                R := K ;
                Trouv := VRAI
            SINON
                K := K + 1
            FSI
        FTQ ;
        E := E + R * EXP ( 10 , ( LONGCHAINE ( C ) - I ) ) ;
    POUR ;
    SI E = 0
        ECRIRE ( 'erreur' ) ;
        I := I / 0
    FSI ;
FIN

/*-------------------------TRANSFERT DE CHAINES---------------------*/
/* Copier C de longueur L ... partir de la position Deb dans le buffer */
ACTION Copier ( C , L , Deb )
SOIT
    C UNE CHAINE ;
    Deb UN ENTIER ;
    I , L DES ENTIERS ;

DEBUT
    POUR I := 1 , L
        AFF_ELEMENT ( Bufdon [ Deb + I - 1 ] , CARACT ( C , I ) )
    FINPOUR
FIN
/* Extraire dans Ch la chaine dans le buffer commen‡cant en Deb de longueur L*/
ACTION Extraire ( Deb , L , Ch )
SOIT
    Ch UNE CHAINE ;
    Deb UN ENTIER ;
    I , L DES ENTIERS ;

DEBUT
    Ch := '' ;
    POUR I := Deb , Deb + L - 1
        Ch := Ch + ELEMENT ( Bufdon [ I ] )
    FINPOUR
FIN

ACTION Inser_fdon ( Article , Nb , D )
SOIT
    Article UNE CHAINE ;
    Nb , D DES ENTIERS ;
    I UN ENTIER ;

DEBUT
    SI ( Taille - Pos - 4 ) + 1 >= LONGCHAINE ( Article )
        D := Pos ;
        APPEL Copier ( 'N' + C ( LONGCHAINE ( Article ) ) + Article , LONGCHAINE ( Article ) + 4 , Pos ) ;
    SINON
        D : = 1 ;
        Dernier_bloc := Dernier_bloc + 1 ;
        SI Taille - Pos + 1 >= Seuil
            APPEL Copier ( 'T' + C ( Taille - Pos - 3 ) , 4 , Pos )
        SINON
            POUR I := Pos , Taille
                AFF_ELEMENT ( Bufdon [ I ] , 'T' )
            FPOUR
        FSI ;
        ECRIRESEQ ( Fdon , Bufdon ) ;
        APPEL Copier ( 'N' + C ( LONGCHAINE ( Article ) ) + Article , LONGCHAINE ( Article ) + 4 , 1 ) ;
        Pos := 1 ;
    FSI ;
    Pos := Pos + LONGCHAINE ( Article ) + 4 ;
    Nb := Dernier_bloc
FIN

1. Lister le fichier en ordre séquentiel.

ACTION Lister_seq ;
SOIT
    Clong : CHAINE ;
    Arret : BOOLEEN ;
    I : ENTIER ;
    Etat : CAR ;
    Article : CHAINE ;

DEBUT
    ECRIRE ( '___________________Ordre sequentiel' ) ;
    OUVRIR ( Fdon , 'fdon.pas' , 'A' ) ;
    TQ NON FINFICH ( Fdon )
        LIRESEQ ( Fdon , Bufdon ) ;
        Arret := FAUX ;
        I := 1 ;
        TQ NON Arret
            APPEL Extraire ( I , 1 , Etat ) ;
            APPEL Extraire ( I + 1 , 3 , Clong ) ;
            APPEL Extraire ( I + 4 , E ( Clong ) , Article ) ;
            SI Etat = 'N'
                ECRIRE ( Article )
            FSI ;
            I := I + E ( Clong ) + 4 ;
            SI Taille - I < Seuil
                Arret := VRAI
            FSI
        FTQ
    FTQ ;
    FERMER ( Fdon )
FIN

2. Lister le fichier en ordre croissant.

ACTION Lister_ord ; DEBUT
    ECRIRE ( '___________________Ordre croissant' ) ;
    OUVRIR ( Fdon , 'fdon.pas' , 'A' ) ;
    APPEL Inordre ( A ) ;
    FERMER ( Fdon )
FIN
ACTION Inordre ( A )
SOIT
    A UN ARB DE ( CHAINE , ENTIER , ENTIER ) ;
    Article UNE CHAINE ;
    D UN ENTIER ;
    Clong UNE CHAINE ;

DEBUT
    SI A <> NIL
        APPEL Inordre ( FG ( A ) ) ;
        LIREDIR ( Fdon , Bufdon , STRUCT ( INFO ( A ) , 2 ) ) ;
        D := STRUCT ( INFO ( A ) , 3 ) ;
        APPEL Extraire ( D + 1 , 3 , Clong ) ;
        APPEL Extraire ( D + 4 , E ( Clong ) , Article ) ;
        ECRIRE ( Article ) ;
        APPEL Inordre ( FD ( A ) )
    FSI
FIN

3. Sauvegarder l'index.

ACTION Sauver_index ; DEBUT
    Ind := 0 ;
    OUVRIR ( Findex , 'findex.pas' , 'N' ) ;
    APPEL Inordr ( A ) ;
    FERMER ( Findex ) ;
FIN
ACTION Inordr ( A )
SOIT
    A UN ARB DE ( CHAINE , ENTIER , ENTIER ) ;
    Article UNE CHAINE ;
DEBUT
    SI A <> NIL
        APPEL Inordr ( FG ( A ) ) ;
        Article := STRUCT ( INFO ( A ) , 1 ) + C ( STRUCT ( INFO ( A ) , 2 ) ) + C ( STRUCT ( INFO ( A ) , 3 ) ) ;
        Ind := Ind + 1 ;
        SI Ind < 5
            AFF_ELEMENT ( Bufindex [ Ind ] , Article )
        SINON
            ECRIRESEQ ( Findex , Bufindex ) ;
            AFF_ELEMENT ( Bufindex [ 1 ] , Article );
            Ind := 1 ;
        FSI ;
        APPEL Inordr ( FD ( A ) )
    FSI
FIN

4. Charger l'index en mémoire.

ACTION Dicho_interne ( Bi , Bs )
SOIT
    Bi , Bs , M DES ENTIERS ;
DEBUT
    SI Bi <= Bs
        M := ( Bi + Bs ) / 2 ;
        ECRIRE ( ELEMENT ( bufindex [ M ] ) ) ;
        APPEL Dicho_interne ( Bi , M - 1 ) ;
        APPEL Dicho_interne ( M + 1 , Bs )
    FSI ;
FIN
ACTION Dicho_externe ( Bi , Bs )
SOIT
    Bi , Bs , M DES ENTIERS ;
DEBUT
    SI Bi <= Bs
        M := ( Bi + Bs ) / 2 ;
        LIREDIR(findex, bufindex, m);
        APPEL dicho_interne ( 1, 5 ) ;
        APPEL Dicho_externe ( Bi , M - 1 ) ;
        APPEL Dicho_externe ( M + 1 , Bs )
    FSI ;
FIN