Les listes

Représentation logique d’une liste

Définition

Une liste est une généralisation des structures précédentes.Elle doit permettre de représenter un ensemble de données ORDONNE tel que tout élément puisse être atteint sans qu’il soit nécessaire de retirer certains autres.

Cette structure sera utilisée chaque fois qu’il est nécessaire de représenter un ensemble ORDONNE ou les opérations d’insertion,recherche,destruction doivent se faire à des endroits quelconques.

Opérations possibles

Initialiser la liste
Placer un nouvel élément dans la liste
Tester si la liste est vide
Enlever un élément de la liste
Tester si la liste est pleine
Rechercher un élément ordonné (ou son prédécesseur)

Représentation physique d’une liste

Représentation contiguë à l’aide d’un tableau
Représentation dynamique ou chaînée par l’utilisation de pointeur
Représentation chaînée par l’utilisation d’indices

La représentation contiguë

Cette représentation implique un décalage vers la droite en cas d’insertion.

La représentation à l’aide d’indices

Cette représentation utilise un tableau de données et un tableau d’indices des éléments suivants.

La représentation dynamique

Les déclarations :

CONSTANTES maxelt = 5

Définition du type liste

TYPES liste = ^ bloc

bloc = ENREGISTREMENT

chaine elt

liste eltsuivant

FIN

Affectation du type liste à des variables

VARIABLES liste tete

Les opérations :

INITIALISER LA LISTE

PROCEDURE initliste (variables Liste p )

DEBUT

Allouer(p)

P^.elt <- ""

P^.eltsuivant<-nul

FIN

Nous créons au début de la liste un élément vide pour que les procédures prédecesseur qui seront déclarées ensuite soit plus facile à écrire.

TESTER SI LA LISTE EST VIDE

FONCTION listevide (variables Liste p ) : BOOLEEN

DEBUT

Retourne ( p^.eltsuivant = NUL)

FIN

AFFICHER LA LISTE

PROCEDURE afficheliste (variables Liste p )

VARIABLES liste ptr

DEBUT

Ptr <-p^.eltsuivant

TANT QUE ptr <> NUL FAIRE

ECRIRE( ptr^.elt)

ptr <-ptr^.eltsuivant

FIN TANT QUE

FIN

TROUVER LE PREDECESSEUR

FONCTION predecesseur (Entier valeur,variables Liste p ): liste

VARIABLES ptr,predecesseur liste

DEBUT

Predecesseur <- p

Ptr <-p^.eltsuivant

TANT QUE ptr<>NUL ET ptr^.elt<valeur FAIRE

Predecesseur <-ptr

Ptr <-ptr^.eltsuivant

FIN TANT QUE

Retourne(predecesseur)

FIN

ENLEVER UN ELEMENT DE LA LISTE

PROCÉDURE retraitliste (variables Liste p , Entier valeur)

VARIABLES ptr,precedent :liste

DEBUT

SI NON listevide(p) ALORS

1 Precedent <-predecesseur(valeur,p)

SI precedent^.eltsuivant=NUL OU precedent^.eltsuivant^.elt<>valeur

ALORS ECRIRE ("cet élément n’est pas dans la liste")

SINON

2 ptr <-precedent^.eltuivant

3 precedent^.eltsuivant <-ptr^.eltsuivant

4 LIBERER(ptr)

FIN SI

SINON

ECRIRE ("la liste est vide")

valeur<-0

FIN SI

FIN

AJOUTER UN ELEMENT DANS LA LISTE

PROCEDURE ajoutliste (variables Liste p ,Entier valeur )

VARIABLES ptr,precedent:liste

DEBUT

1 Precedent <-predecesseur(valeur,p)

2 ALLOUER(ptr)

3 Ptr^.elt <-valeur

4 Ptr^.eltsuivant <-precedent^.eltsuivant

5 Precedent^.eltsuivant <-ptr

FIN

Conclusion sur les listes simples :

Deux inconvénients :

- le parcours de la liste est toujours dans le même sens.certaines applications nécessitent un parcours en sens inverse.

- La recherche de l’élément précédent est fastidieux

Les liste doublement chaînées évitent ces inconvénients.

Les listes doublement chaînées

Les déclarations :

CONSTANTES maxelt = 100

Définition du type liste2c

TYPES liste2c= ^ bloc

bloc = ENREGISTREMENT

liste2c pred

entier elt

liste2c succ

FIN

Affectation du type liste à des variables

VARIABLES liste2c tete,queue

Les opérations :

ENLEVER UN ELEMENT DE LA LISTE

ALGORITHME PROCEDURE retraitliste2c

Ptr^.pred^.succ <-ptr^.succ

Ptr^.succ^.pred <-ptr^.pred

LIBERER(ptr)

AJOUTER UN ELEMENT DANS LA LISTE

ALGORITHME PROCEDURE ajoutliste2c

ALLOUER(ptr)

Ptr^.elt <-"Q"

Ptr^.succ <-precedent^.succ

Ptr^.pred <-precedent

Precedent^.succ <-ptr

Ptr^.succ^.pred <-ptr