Fichiers

Partie 7.

Listes linéaires chaînées

 

COURS 21.  Les listes linéaires chaînées

COURS 22. Algorithmes sur les listes et programmation en PASCAL

TRAVAUX DIRIGES

 



                                                   Partie 7.
   

                                Listes linéaires chaînées

 

 

COURS 21.  Les listes linéaires chaînées  Menu Listes linéaires chaînées

Objectifs : introduire le concept d'allocation dynamique afin de présenter une structure de données évolutive : liste linéaire chaînée.

21.1 Notion d'allocation dynamique

L'utilisation des tableaux tels que nous les avons définis dans le chapitre précédent implique que l'allocation de l'espace se fait tout à fait au début d'un traitement, c'est à dire que l'espace est connu à la compilation.

Pour certains problèmes, on ne connaît pas à l'avance l'espace utilisé par le programme. on est donc contraint à utiliser une autre forme d'allocation. L'allocation de l'espace se fait alors au fur et à mesure de l'exécution du programme.

Afin de pratiquer ce type d'allocation, deux opérations sont nécessaires : allocation et libération de l'espace.

21.2 Exemple

Supposons que l'on veuille résoudre le problème suivant : " Trouver tous les nombres premiers de 1 a n et les stocker en mémoire."

Le problème réside dans le choix de la structure d'accueil. Si on utilise un tableau, il n'est pas possible de définir la taille de ce vecteur avec précision même si nous connaissons la valeur de n (par exemple 10000).  Ne connaissant pas la valeur de n,  on a aucune idée sur le choix de sa taille. On est donc, ici, en face d'un problème où la réservation de l'espace doit être dynamique.

21.3 Définition d'une liste linéaire chaînée

Une liste linéaire chaînée (Llc) est un ensemble de maillons (alloués dynamiquement)chaînés entre eux.

Schématiquement, on peut la représenter comme suit :

Un élément d'une Llc est toujours une structure ( objet composé) avec deux champs : un champ Valeur contenant l'information et un champ Adresse donnant l'adresse du prochain maillon. A chaque maillon est associée une adresse. On introduit ainsi une nouvelle classe d'objet: le type POINTEUR en langage algorithmique.  Une Llc est caractérisée par l'adresse de son premier élément. NIL constitue l'adresse qui ne pointe aucun maillon.

Dans le langage algorithmique, on définira le type d'un maillon comme suit :

   TYPE Typedumaillon = STRUCTURE
        Valeur     : Typeqq { désigne un type quelconque }
        Adresse     : POINTEUR(Typedumaillon)
    FIN

21.4 Modèle sur les listes linéaires chaînées

Afin de développer des algorithmes sur les Llcs, on construit une machine abstraite avec les opérations suivantes :

Allouer, Libérer, Aff_Adr, Aff_Val, Suivant, Valeur

définies comme suit :

Allouer(T, P)    : allocation d'un espace de taille spécifiée par le type T. L'adresse de              cet espace est rendue dans la variable POINTEUR P.
Libérer(P)     : libération de l'espace pointé par P.
Valeur(P)     : consultation du champ Valeur du maillon d'adresse P.
Suivant(P)     : consultation du champ Adresse du maillon d'adresse P.
Aff_Adr(P, Q)    : dans le champ Adresse du maillon d'adresse P, on range l'adresse Q.
Aff_Val(P,Val)    : dans le champ Valeur du maillon d'adresse P, on range la valeur Val.

Cet ensemble est appelé modèle.

COURS 22. Algorithmes sur les listes et programmation en PASCAL  Menu Listes linéaires chaînées

Objectifs : présenter les algorithmes classiques sur les listes en détaillant quelques uns incluant leur utilisation en PASCAL.

22. 1  Algorithmes sur les listes

De même que sur les vecteurs, on peut classer les algorithmes sur les LLCs comme suit :
a) parcours : accès par valeur, accès par position,
b) mise à jour : insertion, suppression,
c) algorithmes sur plusieurs LLCs : fusion, interclassement, éclatement,...
d) tri sur les LLCs.

Donnons quelques algorithmes :

1. Création d'une liste et listage de ses éléments

L'algorithme qui suit crée une liste linéaire chaînée à partir d'une suite de valeurs données, puis imprime la liste ainsi créée.

    ALGORITHME Creer
    VAR
        P, Q, Liste : POINTEUR( Typedumaillon)
        I, Nombre : ENTIER
        Val : Typeqq
    DEBUT
        Liste := NIL
        P := NIL
        LIRE(Nombre)
        POUR I:= 1, Nombre :
            LIRE ( Val )
            Allouer ( Q )
            Aff_val(Q, val)
            Aff_adr(Q, NIL)
            SI Liste # NIL :
                Aff_adr(P, Q)
            SINON
                Liste := Q
            FSI
            P := Q
        FINPOUR
       
        { Listage }
        P := Liste
        TANTQUE P # NIL :
            ECRIRE( Valeur( P) )
            P := Suivant(P)
        FINTANTQUE
    FIN

2. Recherche d'un élément

Il s'agit bien entendu de la recherche séquentielle d'une valeur donnée.

    ALGORITHME Rechercher
    VAR
        P, Liste : POINTEUR( Typedumaillon)
        Trouv : BOOLEEN
        Val : Typeqq
    DEBUT
        LIRE(Val)
        P := Liste
        Trouv := FAUX
        TANTQUE P # NIL ET NON Trouv :
            SI Valeur(P) = Val :
                Trouv := VRAI
            SINON
                P :=Suivant(P)
            FSI
        FINTANTQUE
        SI Trouv :
            ECRIRE ( " L'élément existe " )
        SINON
            ECRIRE ( " L'élément n'existe pas ")
        FSI
    FIN

3. Interclassement de deux listes triées

L'algorithme qui suit construit une liste linéaire chaînée ordonnée à partir de deux listes linéaires chaînées aussi ordonnées.

    ALGORITHME Interclasser
    VAR
        Q, P, P1, P2, Liste : POINTEUR( Typedumaillon)
    DEBUT
        P1 := Liste1
        P2 := Liste2
        P := NIL
        Liste := NIL
        TANTQUE P1 # NIL ET P2 # NIL :
            Allouer(Q)
            Aff_adr(Q, NIL)
            SI Valeur(P1) < Valeur(P2) :
                Aff_val( Q, Valeur(P1) )
                P1 := Suivant(P1)
            SINON
                Aff_val(Q, Valeur(P2))
                P2 := Suivant(P2)
            FSI
            SI P # NIL :
                Aff_adr(P, Q)
            SINON
                Liste := Q
            FSI
            P := Q
        FINTANTQUE
   
        TANTQUE P1 # NIL :
            Allouer (Q)
            Aff_val(Q, valeur(P1)
            Aff_adr(Q, NIL)
            SI P # NIL :
                Aff_adr(P, Q)
            SINON
                Liste := Q
            FSI
            P := Q
            P1 := Suivant(P1)
        FINTANTQUE

        TANTQUE P2 # NIL :
            Allouer (Q)
            Aff_val(Q, valeur(P2)
            Aff_adr(Q, NIL)
            SI P # NIL :
                Aff_adr(P, Q)
            SINON
                Liste := Q
            FSI
            P := Q
            P2 := Suivant(P2)
        FINTANTQUE

22. 2 Utilisation en PASCAL

On définit le type d'un maillon comme suit :

    TYPE Pointeur = @ T
    TYPE T = RECORD
        Val : Typeqq ;
        Adr : Pointeur
    End

et les variables de type Pointeur de la façon suivante :

VAR P, Q, R, ..   : @ T

Le langage est doté des deux opérations suivantes permettant de faire l'allocation dynamique :

NEW(P) et DISPOSE(P)

L'accès à un champ d'un maillon se fait comme suit :

Si P est l'adresse d'un maillon, P@.Val permet l'accès au champ valeur de ce maillon. P@.Adr permet l'accès au champ adresse.

Exemple : traduction de l'algorithme de création

    PROGRAM Creer;
    TYPE
        Typeqq = INTEGER;
        Pointeur = @Typedumaillon ;
        Typedumaillon = RECORD
            Val : Typeqq ;
            Adr : Pointeur
        END;

    PROCEDURE Allouer( VAR P : Pointeur ) ;
        BEGIN NEW(P) END ;

    PROCEDURE Aff_val( VAR P : Pointeur; Val :INTEGER ) ;
        BEGIN P^.Val := Val END ;

    PROCEDURE Aff_adr( VAR P : Pointeur; Q : Pointeur ) ;
        BEGIN P^.Adr := Q END ;

    FUNCTION Suivant( P : Pointeur ) : Pointeur ;
        BEGIN Suivant := P^.Adr END ;

    FUNCTION Valeur( P : Pointeur ) : INTEGER ;
        BEGIN Valeur := P^.Val END ;


    VAR
        P, Q, Liste : Pointeur;
        I, Nombre : INTEGER;
        Val : Typeqq
    BEGIN
        Liste := NIL;
        P := NIL;
        READ(Nombre) ;
        FOR I:= 1 TO Nombre DO
            BEGIN
                READ ( Val ) ;
                Allouer(Q ) ;
                Aff_val(Q, val);
                Aff_adr(Q, NIL);
                IF Liste # NIL
                THEN Aff_adr(P, Q)
                ELSE Liste := Q
                P := Q
            END;
        WRITE(Fs, '+ {')
        P := Liste ;
        WHILE (P <> NIL) DO
            BEGIN
                WRITELN( Valeur(P), ',' ) ;
                L := Suivant(P)
            END ;
        WRITELN(Fs, '}')
    END.

TRAVAUX DIRIGÉS   Menu Listes linéaires chaînées

Développer les algorithmes suivants sur les listes linéaires chaînées :

1. Longueur d'une liste.
2. Rechercher l'élément qui a le plus grand nombre d'occurrences.
3. Accès par valeur.
4. Accès par position.
5. Suppression par valeur.
6. Suppression par position.
7. Insertion par position.
8. Tri par la méthode  "sélection et permutation".
9. Tri par la méthode des bulles.