Corrigé 47.  Enoncé
Soient
    Fdon Un Fichier De ( Entier , Vecteur ( 10 ) De Chaines , Vecteur ( 10 ) De Entiers , Vecteur ( 10 ) De Booleens ) Buffer  Bufdon ;
    Fx Un Fichier De ( Entier , Vecteur ( 10 ) De Chaines ) Buffer Bufx ;
    Taille_d , Taille_x : Entier ;
    Dernier_bloc_d : Entier ; { Utilisé par Alloc-bloc }
    Dernier_bloc_x : Entier ;
    Indice : Entier ; /* Utiliser par reorganiser */
    Arbre : Entier ; Init : Action ;
    Inserer , Inserer_n , Inserernoeud : Actions ;
    Recherche , Rech : Actions ; Lister , Afficher : Action ;
    Reorganiser , Ajouter , Parcours_d , Constr : Actions ;

Debut
    Appel Init ; Appel Inserer_n ; Ouvrir ( Fdon , 'fdon.pas' , 'A' ) ;
    Ecrire ( 'parcours ...' ) ; Appel Lister ( 1 , Bufdon ) ; Appel Afficher ;
Fin

/*-----------------------Initialisation---------------------------*/
Action Init ; Debut
    Ouvrir ( Fdon , 'fdon.pas' , 'N' ) ;
    Aff_struct ( Bufdon , 1 , 1 ) ;
    Aff_element ( Struct ( Bufdon , 3 ) [ 1 ] , - 1 ) ;
    Aff_element ( Struct ( Bufdon , 2 ) [ 1 ] , 'zzzz' ) ;
    Ecriredir ( Fdon , Bufdon , 1 ) ;
    Arbre := 1 ;
    Taille_d := 5 ; Taille_x := 5 ;
    Dernier_bloc := 1 ; Dernier_bloc_x := 0
Fin
Action Afficher ;
Soit I , J : Entier ;
Debut
    Pour J := 1 , Dernier_bloc
        Liredir ( Fdon , Bufdon , J ) ;
        Ecrire ( '***** Bloc ' , J ) ;
        Ecrire ( Struct ( Bufdon , 1 ) ) ;
        Pour I := 1 , Struct ( Bufdon , 1 )
            Ecrire ( Element ( Struct ( Bufdon , 2 ) [ I ] ) ) ;
        Fpour ;
        Pour I := 1 , Struct ( Bufdon , 1 )
            Ecrire ( Element ( Struct ( Bufdon , 3 ) [ I ] ) ) ;
        Fpour
    Finpour
Fin ;

/*-----------------------Insertion de n articles------------------*/
/* indice de la plus petite clé <= cle */
Action Rech ( Cle , I ) ;
Soit
    I : Entier ; Cle : Chaine ; Trouv : Booleen ;
Debut
    I := 1 ;
    Trouv := Faux ;
    Tq ( I <= Struct ( Bufdon , 1 ) ) Et ( Non Trouv )
        Si Element ( Struct ( Bufdon , 2 ) [ I ] ) >= Cle
            Trouv := Vrai
        Sinon
            I := I + 1
        Fsi
    Ftq
Fin

/*----------------------- Recherche d'un article------------------*/
Action Recherche ( Cle , Trouv , Q , I ) ;
Soit
    Cle : Chaine ; Trouv : Booleen ; P , Q , I : Entiers ;
Debut
    Q := - 1 ;
    P := 1 ;
    Trouv := Faux ;
    Tq ( P <> - 1 ) Et ( Non Trouv )
        Liredir ( Fdon , Bufdon , P ) ;
        Appel Rech ( Cle , I ) ;
        Q := P ;
        Si Cle = Element ( Struct ( Bufdon , 2 ) [ I ] )
            Trouv := Vrai
        Sinon
            P := Element ( Struct ( Bufdon , 3 ) [ I ] )
        Fsi ;
    Ftq
Fin

/*-----inserer le couple ( cle, -1) à. la position Pos-------*/
Action Inserernoeud ( Pos , Cle ) ;
Soit
    Pos : Entier ; Cle : Chaine ; I , Nt : Entier ;
Debut
    Nt := Struct ( Bufdon , 1 ) ;
    Aff_struct ( Bufdon , 1 , Nt + 1 ) ;
    Pour I := Nt , Pos , - 1
        Aff_element ( Struct ( Bufdon , 3 ) [ I + 1 ] , Element ( Struct ( Bufdon , 3 ) [ I ] ) ) ;
        Aff_element ( Struct ( Bufdon , 2 ) [ I + 1 ] , Element ( Struct ( Bufdon , 2 ) [ I ] ) ) ;
    Fpour ;
    Aff_element ( Struct ( Bufdon , 3 ) [ Pos ] , - 1 ) ;
    Aff_element ( Struct ( Bufdon , 2 ) [ Pos ] , Cle ) ;
Fin

/*----------------------- Insertion de n articles------------------*/
Action Inserer_n ;
Soit Cle : Chaine ; J , N Un Entier ;
Debut
    Lire ( N ) ;
    Pour J := 1 , N
        Cle := Aleachaine ( 4 ) ;
        Appel Inserer ( Cle )
    Fpour ;
    Fermer ( Fdon ) ;
Fin

/*----------------------- Inserer un article-----------------------*/
Action Inserer ( Cle ) ;
Soit Q , I Un Entier ; Cle : Chaine ; Trouv : Booleen ;
Debut
    Appel Recherche ( Cle , Trouv , Q , I ) ;
    Ecrire ( 'cle=' , Cle ) ;
    Ecrire ( 'trouv=' , Trouv ) ;
    Ecrire ( 'Q=' , Q ) ;
    Ecrire ( 'i=' , I ) ;
    Si Non Trouv
        Si Struct ( Bufdon , 1 ) < Taille_d
            Appel Inserernoeud ( I , Cle ) ;
            Ecriredir ( Fdon , Bufdon , Q ) ;
        Sinon
            Dernier_bloc := Alloc_bloc ( Fdon ) ;
            Aff_element ( Struct ( Bufdon , 3 ) [ I ] , Dernier_bloc ) ;
            Ecriredir ( Fdon , Bufdon , Q ) ;
            Aff_struct ( Bufdon , 1 , 2 ) ;
            Aff_element ( Struct ( Bufdon , 2 ) [ 1 ] , Cle ) ;
            Aff_element ( Struct ( Bufdon , 3 ) [ 1 ] , - 1 ) ;
            Aff_element ( Struct ( Bufdon , 2 ) [ 2 ] , 'zzzz' ) ;
            Aff_element ( Struct ( Bufdon , 3 ) [ 2 ] , - 1 ) ;
            Ecriredir ( Fdon , Bufdon , Dernier_bloc ) ;
        Fsi
    Sinon
        Ecrire ( 'cl‚ existe' )
    Fsi
Fin

/*-------------- Lister le fichier en ordre croissant------------------*/
Action Lister ( A , Bufd ) ;
Soit
    Bufd : ( Entier , Vecteur ( 10 ) De Chaines , Vecteur ( 10 ) De Entiers , Vecteur ( 10 ) De Booleens ) ;
    A : Entier ; Nt , I : Entier ;
Debut
    Si A <> - 1
        Liredir ( Fdon , Bufd , A ) ;
        Nt := Struct ( Bufd , 1 ) ;
        Pour I := 1 , Nt - 1
            Appel Lister ( Element ( Struct ( Bufd , 3 ) [ I ] ) , Bufd ) ;
            Ecrire ( Element ( Struct ( Bufd , 2 ) [ I ] ) ) ;
        Fpour ;
        Appel Lister ( Element ( Struct ( Bufd , 3 ) [ Nt ] ) , Bufd ) ;
    Fsi
Fin

/*----------------------- Reorganisation---------------------------*/
Action Reorganiser Debut
    Indice := 0 ;
    Aff_struct ( Bufx , 1 , 0 ) ;
    Ouvrir ( Fdon , 'fdon.pas' , 'A' ) ;
    Ouvrir ( Fx , 'fx.pas' , 'N' ) ;
    Appel Constr ( Arbre , Bufdon ) ;
    {Ecriture dernier bloc}
    Si Indice <> 0
        Ecrireseq ( Fx , Bufx ) ;
        Dernier_bloc_x := Dernier_bloc_x + 1 ;
    Fsi ;
    Fermer ( Fx ) ;
    Ouvrir ( Fx , 'fx.pas' , 'A' ) ;
    Appel Parcours_d ( 1 , Dernier_bloc_x )
Fin

/*--------- Construction d'un fichier intermédiaire (TOF)-----------------*/
Action Constr ( A , Bufd ) ;
Soit
    Bufd : ( Entier , Vecteur ( 10 ) De Chaines , Vecteur ( 10 ) De Entiers , Vecteur ( 10 ) De Booleens ) ;
    A : Entier ; Nt , I : Entier ;
Debut
    Si A <> - 1
        Liredir ( Fdon , Bufd , A ) ;
        Nt := Struct ( Bufd , 1 ) ;
        Pour I := 1 , Nt - 1
            Appel Lister ( Element ( Struct ( Bufd , 3 ) [ I ] ) , Bufd ) ;
            Appel Ajouter ( Element ( Struct ( Bufd , 2 ) [ I ] ) ) ;
        Fpour ;
        Appel Lister ( Element ( Struct ( Bufd , 3 ) [ Nt ] ) , Bufd ) ;
    Fsi
Fin

/*------------Ajoute un article dans le fichier TOF--------------------*/
Action Ajouter ( Cle ) ;
Soit Cle Une Chaine ;
Debut
    /*ajouter*/
    Si Indice < Taille_x
        Indice := Indice + 1 ;
        Aff_element ( Struct ( Bufx , 2 ) [ Indice ] , Cle ) ;
        Aff_struct ( Bufx , 1 , Struct ( Bufx , 1 ) + 1 ) ;
    Sinon
        Ecrireseq ( Fx , Bufx ) ;
        Dernier_bloc_x := Dernier_bloc_x + 1 ;
        Indice := 0 ;
        Aff_struct ( Bufx , 1 , 0 ) ;
    Fsi
Fin

/*-------Parcours dichotomique du fichier TOF et Construction du nouvel arbre équilibré ! -------*/
Action Parcours_d ( Bi , Bs ) ;
Soit I , Bi , Bs , Mil : Entier ;
Debut
    Si Bi <= Bs
        Mil := ( Bi + Bs ) / 2 ;
        Ecrire ( '********** Bloc ' , Mil ) ;
        Liredir ( Fx , Bufx , Mil ) ;
        Pour I := 1 , Struct ( Bufx , 1 )
            Appel Inserer ( Element ( Struct ( Bufx , 2 ) [ I ] ) )
        Fpour ;
        Appel Parcours_d ( Bi , Mil - 1 ) ;
        Appel Parcours_d ( Mil + 1 , Bs ) ;
    Fsi
Fin