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
Partie
7.
Listes linéaires chaînées
COURS 21. Les 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
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, [email protected] permet l'accès au champ valeur de ce maillon. [email protected] 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. |
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.