ASDC 20 21 Partie4

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 39

Les listes chaînées

Les listes chaînées


 Une liste chaînée permet de stocker un ensemble de
valeur du même type, comme un tableau.
 Contrairement au tableau, la taille de la liste chaînée peut
varier au cours du temps. En effet, contrairement au
tableau, la liste n'est pas allouée en une seule fois, mais
chaque élément est alloué indépendamment, sous la
forme d'un maillon.
 Notion de maillon
 L'élément de base d'une liste chaînée s'appelle le maillon. Il est
constitué : d’un ou des champs de données et d'un pointeur
vers un maillon.
Les listes chaînées
 Notion de liste chaînée
 Dans une liste chaînée, chaque élément pointe, à l'aide d’un
pointeur (suivant) vers l'élément suivant dans la liste ;
 le dernier élément, par définition, n'a pas de suivant, donc son
pointeur suivant vaut NIL.
Les listes chaînées
 Pour manipuler une liste chaînée, nous manipulons un
pointeur sur le premier élément; comme chaque
élément « connaît » l'élément suivant, on peut ainsi
accéder à tous les éléments de la liste.
 Si le pointeur premier vaut NIL, on considérera
naturellement que la liste est vide (elle ne contient aucun
élément).
 Le premier maillon de la liste est appelé tête, le dernier
maillon de la liste est appelé queue.
Les listes chaînées
 Implémentation du type liste chaînée
 Un maillon est composé de deux champs de types hétérogènes,
 il est implémenté donc en utilisant les enregistrements de la manière
suivante :
^maillon

 Déclaration du maillon
type
maillon = Enregistrement
valeur : type
suivant : ^maillon
Fin maillon
Les listes chaînées
 Autre modélisation du type liste chaînée
 Un maillon est composé de deux champs :
 Un champ de type enregistrement contenant les champs de données
 Un pointeur vers le maillon suivant
 Déclaration du maillon
type
data = Enregisterment
val1 : type
val2 : type

Fin data
maillon = Enregistrement
champ: data
suivant : ^maillon
Fin maillon
Les listes chaînées
 Définition du type liste
type
liste : maillon
 Déclaration d’une variable de type liste
 Une fois le type liste est défini on peut déclarer une variable de
type pointeur sur liste de la manière suivante
 p : ^liste
 Accès aux champs d’un maillon d’une liste
 Si p est un pointeur sur une variable de type liste, p^ est la
variable pointée par p. cette variable est un enregistrement, pour
accéder à ses champs on utilise l’opérateur ". "
p^. valeur
p^. suivant
Les listes chaînées
 Initialisation d’une liste à Nil
 Une liste est vide si le pointeur du premier maillon vaut Nil
 p ← Nil
 Insertion d’une valeur en tête d’une liste
 Ecrire la procédure InsertTete qui permet d’insérer une
valeur val en tête d’une liste chaînée donnée par
l’adresse de son premier élément (premier).
Notons qu’après l’insertion la valeur du premier
sera changée, donc le passage doit se faire par
adresse.
Les listes chaînées

 Principe
1. Créer un maillon d’adresse p1 contenant la valeur val
 p1 ← nouveau(^liste)
 p1^.valeur ← val
2. Créer un lien entre le nouveau maillon et la tête de la liste de telle sorte
que p soit le suivant de p1
 p1^.suivant ← premier
3. Le maillon p1 devient le premier maillon de liste p
 premier ← p1
Les listes chaînées
 Algorithmique
PROCEDURE InsertTete(var premier : ^liste, val : entier)
var
type
nouvElt: ^liste maillon = Enregistrement
valeur : entier
Début suivant : ^maillon
nouvElt ← nouveau(^liste) Fin maillon

nouvElt ^.valeur ← val liste : maillon


nouvElt ^.suivant ← premier
premier ← nouvElt
Fin
Complexité : O(1)
Les listes chaînées
 Récupérer l’adresse du dernier élément d’une liste
 Ecrire la fonction Dernier qui renvoie l’adresse du dernier
élément d’une liste donnée par l’adresse de son premier élément
(premier).

 Principe
 Le dernier élément de la liste s’il existe est un maillon qui ne
possède pas de suivant.
 On fait le parcours de liste du premier élément jusqu’à trouver
un maillon dont le suivant vaut Nil.
 L’adresse de ce maillon est renvoyée par la fonction.
Les listes chaînées
 Algorithmique
Fonction Dernier( premier : ^liste) : ^liste
Debut
Tantque(premier <>Nil et premier ^.suivant<>Nil) faire
premier ← premier ^.suivant
FinTantque
Retourner premier
Fin

Complexité : O(N), N : nombre d’élément dans la liste


Les listes chaînées
 Insertion d’une valeur en queue d’une liste
 Ecrire la procédure InsertQueue qui permet d’insérer une valeur
val dans une liste chaînée donnée par l’adresse de son premier
élément (premier).
 Après l’insertion la valeur du premier peut changer (dans le cas
où la liste est vide) donc le passage doit se faire par adresse.
Les listes chaînées
 Principe : Deux cas
Si la liste est vide l’insertion en queue est une insertion en tête.
si(premier =Nil) alors
InsertTete(premier,val)
Sinon
 Créer un maillon d’adresse nouvElt contenant la valeur val et dont l’élément
suivant est Nil
nouvElt ← nouveau(^liste)
nouvElt ^.valeur ← val
nouvElt ^.suivant ← Nil
 Récupérer l’adresse du dernier maillon (Der) et nouvElt devient le suivant de Der
Der ← Dernier(premier)
Der^.suivant ← nouvElt
Finsi
Les listes chaînées
 Algorithmique
PROCEDURE InsertQueue(var premier : ^liste, val : entier)
var
nouvElt, Der: ^liste
Début
si(premier=Nil) alors
InsertTete(premier,val)
Sinon
nouvElt ← nouveau(^liste)
nouvElt ^.valeur ← val
nouvElt ^.suivant ← Nil // il sera le dernier
Der ← Dernier(premier)
Der^.suivant ← nouvElt
Finsi
Fin
Les listes chaînées
 Longueur d’une liste
 Écrire la fonction LongListe qui permet de renvoyer le
nombre d’éléments d’une liste chaînée donnée par l’adresse
de son premier élément (premier).
 La fonction renvoie 0 si la liste est vide.
 Principe
 On fait le parcours de la liste du premier élément jusqu’au
dernier en incrémentant un compteur de 1 à chaque passage d’un
maillon à son suivant.
 La valeur de ce compteur au départ vaut 0
Les listes chaînées
Algorithmique
FONCTION LongListe(premier : ^liste) : entier
var
L : entier
Début
L←0
Tantque(premier <>Nil) faire
L ← L+1;
premier ← premier ^.suivant;
FinTantque
Retourner L;
Fin
Les listes chaînées
 Exercices
 Ecrire une fonction récursive Longueur qui retourne le
nombre d’éléments d’une liste chaînée donnée en
paramètre.
 Ecrire une fonction récursive qui retourne le membre à la
ième position dans une liste chaînée, la liste et la position
sont données en paramètre.
Les listes chaînées
 Insertion d’une valeur à une position k dans une liste
 Écrire la procédure Insertk qui permet d’insérer une valeur val à
une position k dans une liste chaînée donnée par l’adresse de son
premier élément (premier).
 La valeur val aura le rang k+1 dans la liste après l’insertion.
Les listes chaînées
 Principe
Si (k =0) alors //Si k=0 l’insertion se fait en tête de la liste.
InsertTete(premier,val)
Sinon
Si (k>LongListe(premier)) alors
écrire("la position k=" ,k, " n'existe pas car la liste est de taille",LongListe(premier))
Sinon
Pour i de 1 à k-1 faire // Récupérer l’adresse du maillon qui se trouve à la position k (pk) .
pk ← pk^.suivant;
Finpour
// Créer un maillon d’adresse nouvElt contenant la valeur val et dont l’élément suivant est le
suivant de pk
nouvElt ← nouveau(^liste)
nouvElt ^.valeur ← val
nouvElt^.suivant ← pk^.suivant // Le suivant de nouvElt est le suivant de pk.
pk^.suivant ← nouvElt // Le suivant de pk devient nouvElt.
Finsi
Finsi
Les listes chaînées
PROCEDURE Insertk(var premier : ^liste , k: entier,val: entier)
var
nouvElt,pk : ^liste
i: entier
Début
Si (k =0) alors
InsertTete(premier,val)
Sinon
Si (k>LongListe(premier)) alors
écrire("la position k=" ,k, " n'existe pas car la liste est de taille",LongListe(premier))
Sinon
pk ← premier
Pour i de 1 à k-1 faire
pk ← pk^.suivant
Finpour
nouvElt ← nouveau(^liste)
nouvElt^.valeur ← val
nouvElt^.suivant ← pk^.suivant
pk^.suivant ← nouvElt
Finsi
Finsi
Fin
Les listes chaînées
 Suppression du premier maillon d’une liste
 Écrire la procédure SuppTete qui permet de supprimer le premier
maillon d’une liste chaînée donnée par l’adresse de son premier
élément (premier).
Les listes chaînées
 Principe
//Si la liste est non vide : on sauvegarde premier dans une variable p.
Si (premier ≠ Nil) alors
p ← premier
// La valeur de premier prend la valeur de son suivant.
premier ← premier^.suivant
// On libère la zone mémoire d’adresse p.
liberer(p)
Finsi
Les listes chaînées
 Algorithmique
PROCEDURE SuppTete(var premier : ^liste)
var
p : ^Liste
Début
Si (premier <> Nil) alors
p ← premier
premier ← premier ^.suivant
liberer(p)
Finsi
Fin
Les listes chaînées
 Suppression du dernier maillon d’une liste
 Écrire la procédure SuppQueue qui permet de supprimer le
dernier maillon d’une liste chaînée donnée par l’adresse de son
premier élément (premier).
 Notons qu’après la suppression la valeur du premier peut changer
Les listes chaînées
 Principe
Si (premier ≠ Nil) alors //Si la liste est non vide
//Si la liste contient un seul élément, la suppression se fait en tête de la liste
Si (LongListe(premier)=1) alors
SuppTete(premier)
Sinon // Sinon, On récupère l’adresse de l’avant dernier élément (AvDer)
AvDer ← premier
Tantque(AvDer ^.suivant^.suivant<>Nil) faire
AvDer ← AvDer ^.suivant
FinTantque
// On sauvegarde l’adresse du dernier élément dans une variable p.
p ← AvDer ^.suivant
AvDer^.suivant ← Nil // L’élément d’adresse AvDer devient le dernier élément.
liberer(p) // on libère la zone mémoire d’adresse p.
Finsi
Finsi
Les listes chaînées
 Algorithmique
PROCEDURE SuppFin( var premier : ^liste)
var
AvDer,p : ^liste
Début
Si (premier <> Nil) alors
Si (LongListe(premier)=1)
SuppTete(p)
Sinon
AvDer ← premier
Tantque(AvDer ^.suivant^.suivant<>Nil) faire
AvDer ← AvDer ^.suivant
Fintantque
p ← AvDer ^.suivant
AvDer ^.suivant ← Nil
liberer(p)
Finsi
Finsi
Fin
Les listes chaînées
 Suppression de tous les maillons d’une liste
 Écrire la procédure SuppListe qui permet de supprimer tous les
éléments d’une liste chaînée donnée par l’adresse de son premier
élément (premier).
 Après la suppression la valeur du premier vaudra Nil.
 Algorithmique
PROCEDURE SuppListe(var premier: ^liste)
Début
Tantque(premier<>Nil)faire
SuppTete(premier)
fintantque
fin
Les listes chaînées
 Exercice 1 :
Utilisez les fonctions et procédures vues précédemment dans
le cours pour écrire une procédure qui prend en entrée une
liste chaînée d'entiers et qui ressort deux listes chaînées :
 une pour les nombres pairs
 et une autre pour les nombres impairs.
 la liste initiale est détruite.
Les listes chaînées
 Exercice 2 :
Un polynôme est composé d’un ensemble de monômes.
Chaque monôme est caractérisé par un degré et un coefficient.
 Proposez les structures nécessaires pour modéliser un monôme et un
polynôme.
 Ecrire une fonction qui prend en argument un tableau tab de n
éléments et construit un polynôme tel que pour tout indice i, tab[i]
est le coefficient du monôme xi .
 Ecrire une fonction qui supprime le monôme de degré i d’un
polynôme p.
 Ecrire une fonction qui retourne la dérivée d’un polynôme p donné
en paramètre.
 Ecrire une fonction qui retourne la somme de deux polynômes p et q
donnés en paramètre.
Les listes chaînées
 Les listes doublement chaînées
 Dans une liste doublement chaînée un maillon est composé de trois
champs:
 Un champ de données ;
 Un pointeur vers un le maillon suivant.
 Un pointeur vers un le maillon précédent.

 Suivant : Ce champ pointe vers le maillon suivant de la liste.


S'il n'y a pas de maillon suivant, le pointeur vaut NIL.
 Précédent : Ce champ pointe vers le maillon précédent de la
liste. S'il n'y a pas de maillon précédent, le pointeur vaut NIL.
Les listes chaînées
 Le type liste doublement chaînée
type
maillon = Enregistrement
Valeur : entier
suivant : ^maillon
précédent : ^maillon
Fin maillon
// Définition du type listedc
listedc =maillon
Les listes chaînées
 Insertion d’une valeur en tête d’une liste doublement
chainée.
 Écrire la procédure InserTete qui permet d’insérer une valeur v
en tête d’une liste doublement chaînée donnée par l’adresse de
son premier élément (premier).
 Après l’insertion la valeur du premier sera changée donc le
passage doit se faire par adresse.
Les listes chaînées
 Principe
// Créer un maillon d’adresse nouvElt contenant la valeur v et dont le pointeur
précédent est nil (il sera le premier).
nouvElt ← nouveau(^listedc)
nouvElt ^.valeur ← v
nouvElt ^.précédent ← Nil
// Créer un lien entre le nouveau maillon et la tête de la liste de telle sorte que
premier soit le suivant de nouvElt
nouvElt ^.suivant ← premier
// Créer un lien entre la tête de la liste (si elle existe) et le nouveau maillon de telle
sorte que nouvElt soit le précédent de premier.
Si (premier<>nil) alors
premier^.précèdent ← nouvElt
Finsi
//Le maillon nouvElt devient le premier maillon de liste premier
premier ← nouvElt
Les listes chaînées
 Algorithmique
PROCEDURE InsertTete(var premier : ^listedc, v : entier)
var
nouvElt : ^listedc
Debut
nouvElt ← nouveau(^listedc)
nouvElt ^.valeur ← v
nouvElt ^.précédent ← Nil
nouvElt ^.suivant ← premier
si(premier <>Nil) alors
premier ^.précédent ← nouvElt
Finsi
premier ← nouvElt
Fin
Les listes chaînées
 Suppression du premier maillon d’une liste
doublement chaînée
 Écrire la procédure SuppTete qui permet de supprimer le premier
maillon d’une liste doublement chaînée donnée par l’adresse de
son premier élément (premier).
 Après la suppression, la valeur du premier maillon doit changer,
donc le passage doit se faire par adresse.
Les listes chaînées
 Principe
// Si la liste est non vide : on sauvegarde premier dans une variable P1
Si(premier ≠ Nil) alors
P1 ← premier
// La valeur de premier prend la valeur de son suivant.
premier ← premier^.suivant
// La valeur du précédent prend la valeur Nil
premier^.précédent ← Nil
// On libère la zone mémoire d’adresse P1.
libérer(P1)
Finsi
Finsi
Les listes chaînées
 Algorithme
PROCEDURE SuppTete (var p : ^listedc)
var
P1: ^listedc
Début
P1 ← p ;
si (p<>Nil) alors
p ← p^.suivant
p^. précédent ← Nil
libérer(P1)
fin si
fin
Les listes chaînées
 Les listes circulaires
 Une liste où le pointeur Nil du dernier élément est remplacé par
l’adresse du premier élément est appelée liste circulaire.
 Dans une liste circulaire tous les maillons sont accessibles à partir de
n’importe quel autre maillon.
 Une liste circulaire n’a pas de premier et de dernier maillon. Par
convention, on peut prendre le pointeur externe de la liste vers le
dernier élément et le suivant serait le premier élément de la liste.

Vous aimerez peut-être aussi