Corrigé 45.  Enoncé

1. File d'attente avec priorité

Chaque de la liste est le couple (valeur, priorité).
Nous supposons dans cette solution que la valeur est de type chaîne et priorité une valeur entière quelconque. C'est exactement comme une file d'attente ordinaire, sauf qu'il n'ya pas de queue puisque l'enfilement d'un élément ne se fait pas à la fin.
Soit
    L Une Liste De ( Chaine , Entier ) ;
    Enfiler_p , Defiler_p , Creerfile_p Des Actions ;
    Filevide_p Une Fonction ( Booleen ) ;
    I Un Entier ;
    V Une Chaine ;
Debut
    { Test ou vérification des opérations du modèle }
    Appel Creerfile_p ( L ) ;
    Pour I := 1 , 8
        Appel Enfiler_p ( L , Aleachaine ( 5 ) , Aleanombre ( 20 ) ) ;
    Fpour ;

    Tq Non Filevide_p ( L )
        Appel Defiler_p ( L , V ) ;
        Ecrire ( V )
    Ftq
Fin

Action Creerfile_p ( L )
Soit
    L Une Liste De ( Chaine , Entier ) ;
Debut
    L := Nil
Fin

Action Defiler_p ( L , V )
Soit
    L Une Liste De ( Chaine , Entier ) ;
    V Une Chaine ;
    Sauv Un Pointeur Vers Une Liste De ( Chaine , Entier ) ;
Debut
    Si L <> Nil
        V := Struct ( Valeur ( L ) , 1 ) ;
        Sauv := L ;
        L := Suivant ( L ) ;
        Liberer ( Sauv )
    Sinon
        Ecrire ( 'Underflow' )
    Fsi
Fin

Action Enfiler_p ( L , V , Pr )
Soit
    Q , P , L , Prec Des Listes De ( Chaine , Entier ) ;
    V Une Chaine ;
    Pr Un Entier ;
    Trouv Un Booleen ;
    S Une Structure ( Chaine , Entier ) ;
Debut
    Prec := Nil ;
    P := L ;
    Trouv := Faux ;
    Tq ( P <> Nil ) Et Non Trouv
        Si Pr < Struct ( Valeur ( P ) , 2 )
            Trouv := Vrai
        Sinon
            Prec := P ;
            P := Suivant ( P )
        Fsi
    Ftq ;
    Allouer ( Q ) ;
    Init_struct ( S , [ V , Pr ] ) ;
    Aff_val ( Q , S ) ;
    Aff_adr ( Q , Nil ) ;
    Si L <> Nil
        Si Prec = Nil
            Aff_adr ( Q , L ) ;
            L := Q
        Sinon
            Aff_adr ( Q , Suivant ( Prec ) ) ;
            Aff_adr ( Prec , Q ) ;
        Fsi
    Sinon
        L := Q
    Fsi
Fin

Fonction Filevide_p ( L ) : Booleen
Soit
    L Une Liste De ( Chaine , Entier ) ;
Debut
    Filevide_p := ( L = Nil )
Fin


2. Parcours parallèle dans une liste bilatérale.

Donnons 2 solutions, l'une sous forme d'action et l'autre sous forme d'une fonction.
Soit
    L Une Listebi ;
    Rechercher1 Une Action ;
    Rechercher2 Une Fonction(Booleen);
    Dernier : Listebi ;
    V Un Entier ;
    Trouv Un Booleen ;

Debut
    Creer_listebi(L,[23,65,32,76,88,12,55, 665 ]);
    Dernier := L ;
    Tq Suivant ( Dernier ) <> Nil
        Dernier := Suivant ( Dernier )
    Ftq ;
    Lire ( V ) ;
    Appel Rechercher1 (V , L, Dernier , Trouv ) ;
    Ecrire ( Trouv );
    Ecrire( Rechercher2(V, L, Dernier)
Fin
Action Rechercher1 (V ,L, Dernier ,Trouv ) ;
Soit
    V Un Entier ;
    L , Dernier Des Listebi ;
    Trouv Un Booleen ;

Debut
    Si L <> Nil
        Si ( Valeur ( L ) = V ) Ou ( Valeur ( Dernier ) = V )
            Trouv := Vrai
        Sinon
            Si ( L <> Dernier ) Ou ( Suivant ( L ) <> Dernier )
                Appel Rechercher1 ( V , Suivant ( L ) , Precedent ( Dernier ) , Trouv )
            Sinon
                Trouv := Faux
            Fsi
        Fsi
    Sinon
        Trouv := Faux
    Fsi
Fin

Fonction Rechercher2 ( V , L , Dernier ) : Booleen
Soit
    V Un Entier ;
    L , Dernier Des Listebi ;
Debut
    Si L <> Nil
        Si ( L = Dernier ) Ou ( Suivant ( L ) = Dernier )
            Rechercher2 := ( Valeur ( L ) = V ) Ou ( Valeur ( Dernier ) = V )
        Sinon
            Rechercher2 := Rechercher2 (V, Suivant ( L ) , Precedent ( Dernier ) )
        Fsi
    Sinon
        Rechercher2 := Faux
    Fsi
Fin

3. Version itérative du "préordre" dans un arbre binaire.

Remarquer qu'il y a un seul point de retour ( Après le Finsi) dans le module à dérécursifier.
Nous donnons deux solutions :

Une solution automatique serait :
La zone de données (zdd) contient deux champs Adr ( Adresse de retour) et a (le paramètre).
Trois points d'appel ( 2 dans le module récursif et l'autre dans le module principal qui fait appel la première fois à ce module ).

On obtient l'algorithme suivant

Création d'un arbre de racine r.
        zdd.a := r
        zdd.adr := 1
        creerpile(p)
        Empiler(p, zdd)
10 :  Si zdd.a <> nil
        Ecrire(info(zdd.a))
        {premier appel}
        empiler (p, zdd)
        zdd.a := fg(zdd.a)
        zdd.adr := 2
        Allera 10
2 :
        {deuxième appel}
        empiler (p, zdd)
        zdd.a := fd(zdd.a)
        zdd.adr := 3
        Allera 10
3:
        Fsi
        {retour}
        i := zdd.adr
        depiler(P, zdd)
        Allera i
1 :
Ensuite, il faut essayer d'éliminer les Allera.

Une autre solution, plus simple consiste à remarquer d'abord qu'il y a un appel en fin de procédure qui se traduit tout simplement par
a := fd(a)
Allera au début du module

On se ramène par conséquent à un seul appel dans le module. On peut donc éliminer l'adresse de retour de la zone de données qui se trouve ainsi réduite à l'unique paramètre a. De plus, l'opération dépiler(P, zone de données ) sera remplacée par dépiler(P, zone de données, Possible ) avec
Possible : vrai retourner dans le module récursif
Possible : faux retourner dans le module principal
On obtient une première traduction :

Une première traduction nous donne :
Construction de l'arbre de racine r.
        Creerpile (p)
        a := R;
10 :  Si a <> nil
            Ecrire(Info(a));
            Empiler (p, a) ;
            a := Fg(a) ;
            Allera 10;
2 :         a := Fd(a);
            Allera 10
        Fsi;
        Depiler(P, a, Possible);
        Si Possible Allera 2;

On remarque une boucle, introduisons un premier Tq

Construction de l'arbre de racine r.
        Creerpile(P)
        A := R;
10:   Tq A <> Nil
            Ecrire(Info(A));
            Empiler (p, A) ;