Chapitre 1 : Les listes linéaires chaînées

[Notion d'allocations statique et dynamique

Représentation (allocation) statique

L'allocation de l'espace se fait tout à fait au début d'un traitement. En termes techniques, on dit que l'espace est connu à la compilation. C'est donc la notion de tableau.

Représentation dynamique

L'allocation de l'espace se fait au fur et à mesure de l'exécution du programme. Pour pouvoir faire ce type d'allocation, l'utilisateur doit disposer des deux opérations : allocation et libération de l'espace. Si le langage offre ces possibilités, on les utilise directement, sinon on sera dans l'obligation de les simuler, c'est à dire gérer l'espace soi-même dans un grand tableau.







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

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






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 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
On notera cet ensemble d'opérations MLlc. Cet ensemble est appelé modèle.






Exemple d'introduction

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 n' 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.

solution

On utilise les deux faits suivants :

un nombre n'est premier que s'il n'est pas divisible par les nombres premiers qui le précèdent
tous les nombres premiers sont de la forme 6m+1 ou 6m-1.
L'Algorithme

{ Création de maillons pour les nombres premiers 2 et 3 }

Allouer(T,P)
Aff_Val(P,2)
Tête := p
Allouer(T, Q)
Aff_Val(Q,3) ; Aff_Adr(Q, NIL)
Aff_Adr(P,Q)
P := Q
M := 1 ; Continue := VRAI ; Aig := VRAI
TANTQUE Continue :
Gen_nombre (M, Aig, Nombre)
Aig := NON Aig
SI Aig : M := M + 1 FSI
SI Nombre <= N :
SI Premier (Tête, Nombre) :
Allouer (T, Q)
Aff_Val(Q, Nombre) ; Aff_Adr( Q, NIL)
Aff_Adr(P, Q)
P := Q
FSI
SINON
Continue := FAUX
FSI
FINTANTQUE

Les modules précédents sont définis comme suit :

Module Gen_nombre( M, Aig, Nombre )
En entrée :
- M qui prend des valeurs dans {1, 2, 3, .. }
- Aig pour l'alternance du "+" et "-" dans la formule.
En sortie :
- Nombre : le prochain nombre candidat pour le module Premier.
C'est tout simplement :

SI Aig : Nombre := 6M - 1
SINON Nombre := 6M + 1 FSI



Module Premier (L, N)
en entrée
- L : une tête de LLC
- N : un nombre
en sortie
- la valeur VRAI si L ne contient pas de diviseurs de N, FAUX sinon.

P:= L ; Trouv := FAUX
TANTQUE P <> NIL ET NON Trouv :
SI Divisible ( Nombre, Valeur(P) ) :
Trouv := VRAI
SINON
P := Suivant(P)
FSI
FINTANTQUE
Premier := NON Trouv

Enfin, le module Divisible (A, B) peut s'écrire comme suit :
C'est un prédicat qui est égal à VRAI si B est un diviseur de A , FAUX sinon.
Q étant une variable de type ENTIER,

Q := A / B {Division entière}
SI Q.B = A : Divisible := VRAI
SINON Divisible := FAUX FSI

Soit T le type d'un maillon de la Llc, P et Q des variables de type POINTEUR.
En supposant que :

Gen_nombre est un module qui détermine le prochain nombre candidat pour le test ( premier ou pas)
Premier est un prédicat égal à VRAI si un nombre donné est premier, FAUX sinon





Algorithmes sur les listes

De même que sur les vecteurs, on peut classer les algorithmes sur les LLCs comme suit :

parcours :accès par valeur, accès par position

mise à jour : insertion, suppression

algorithmes sur plusieurs LLCs : fusion, interclassement, éclatement,...

tri sur les LLCs







Listes linéaires chaînées particulières

Liste bidirectionnelle

C'est une Llc que l'on peut parcourir dans les deux sens. Schématiquement, elle se présente comme suit :




MLlcb = MLlc - {Aff_Adr} + { Aff_Adrg, Aff_Adrd, Précédent }



Le type d'un maillon est défini comme suit :

TYPE Typedumaillon = STRUCTURE
Valeur : Typeqq
Adresse1 : POINTEUR (Typedumaillon)
Adresse2 : POINTEUR (Typedumaillon)
FIN
Le modèle des Llc est donc étendu par les opérations suivantes :

Précédent(P) accès au champ adresse gauche du maillon d'adresse P.
Aff_Adrg(P, Q) dans le champ Adresse1 (adresse gauche) du maillon d'adresse P, on range l'adresse Q.
Aff_Adrd(P, Q) dans le champ Adresse2 (adresse droite) du maillon d'adresse P, on range l'adresse Q


Exemple

Suppression d'un élément pointé par P dans une liste linéaire chaînée bidirectionnelle L.

SI P # NIL :
SI Précédent(P) # NIL :
Aff_Adrd( Précédent(P), Suivant(P) )
SINON
L := Suivant (P)
FSI
SI Suivant(P) # NIL :
Aff_Adrg( Suivant(P), Précédent(P) )
FSI
Libérer(P)
FSI

Liste circulaire ou anneau

C'est une Llc telle que le dernier élément pointe sur le premier. Elle est définie par l'adresse d'un élément quelconque.


MLlcc = MLlc



Liste bidirectionnelle circulaire

C'est une Llc à double sens et dont le dernier(premier) pointe sur le premier(dernier).


MLlcbc = MLlcb







Implémentation des listes linéaires chaînées avec la représentation contigue

On peut représenter les Llcs dans un même tableau où chaque élément renferme au moins 2 champs : l'information et le lien. Par exemple la liste suivante




peut être représentée dans un tableau comme suit :




Définition de la structure

TYPE T = STRUCTURE
Info : Typeqq
Lien : ENTIER
Vide : BOOLEEN { pour les positions vides du tableau }

FIN
VAR T : TABLEAU ( 1 : Max ) DE T



Initialement les champs Vide de tous les éléments sont à vrai ( pour indiquer des positions disponibles).

Une Llc est définie par l'indice de son premier élément dans le tableau T.

L'implémentation du modèle de Llcs au moyen de tableau revient à traduire les opérations du modèle au moyen de la seule opération d'indexation définie sur les tableaux.

La fonction Allouer ( P ) rend l'indice d'une position vide sinon la valeur -1( s'il n’y a pas de place ). Ceci revient à chercher une entrée libre P dans le tableau T. Une solution simple consiste à balayer le tableau linéairement du début vers la fin jusqu'à la rencontre d'une entrée libre.
l'Algorithme

I := 1 ; Trouv := FAUX
TANTQUE I <= Max ET NON Trouv :
SI T(I).Vide : Trouv := VRAI
SINON I := I + 1
FSI
FINTANTQUE
SI NON Trouv : Allouer := - 1
SINON
Allouer := i
T(I).Vide := FAUX
FSI

Les autres opérations en bref

Libérer(P) : T(P).Vide := VRAI
valeur(i) : valeur := t(i).info
Suivant(I) : Suivant := T(I).Lien
Aff_Adr(I,J) : T(I).Lien := J
aff_val(i, val): t(i).info := val






Les listes en Pascal

Le type d'un maillon est définit comme suit :

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


Les variables de type Pointeur sont définit 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)

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.







TRAVAUX DIRIGES

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

1. Construire une Llc à partir de n données lues.

2. Longueur d'une Llc.

3. Rechercher dans une Llc l'élément qui a le plus grand nombre d'occurrences.

4. Accès par valeur dans une Llc.

5. Accès par position dans une Llc.

6. Suppression par valeur dans une Llc.

7. Suppression par position dans une Llc.

8. Insertion par position dans une Llc.

9. Interclassement de deux listes ordonnées.

10. Eclater une liste en 2 Llcs selon un critère donné.

11. Trier une Llc par la méthode des bulles.

12. Implémenter le modèle de Llc en utilisant la représentation contigue.

13. Un polynôme peut être représenté par une Llc. Dire comment. Ecrire les algorithmes suivants :

- calcul du polynôme en un point x donné.

- dérivé d'un polynôme.

- somme de deux polynômes.

- produit de deux polynômes.

14. Etudier les algorithmes de recherche, insertion et suppression d'un élément dans un vecteur. Les comparer avec ceux correspondant sur les Llcs.

15. Construire une liste bidirectionnelle à partir de n données.

16. Insérer un élément dans une liste bidirectionnelle.

17. Supprimer un élément dans une liste bidirectionnelle.