LISTES CHAÎNÉES
Mme Ahlem Ben Cherifa
GESTION DYNAMIQUE DE LA MÉMOIRE
déclaration des variables connaître le
nombre de données nécessaires au programme.
Tableaux : déclarer des tableaux d’une taille
maximale fixée
Nombre de données inconnu à priori ?
Solution : allouer dynamiquement et à la
demande, des emplacements en mémoire pour
stocker les données.
GESTION DYNAMIQUE DE LA MÉMOIRE
Type : Pointeur
^type_base
Exemple :
X : ^entier X
CH : ^chaine
E : ^etudiant CH
Constante : NIL E
GESTION DYNAMIQUE DE LA MÉMOIRE
Opérations :
Avant Créer( p )
p : ^type_base
P !
Réservation (allocation) :
Après Créer( p )
P @0 P^
Créer( p )
@0
Libération :
Après Libérer( p )
@0
P
Libérer( p )
@0
GESTION DYNAMIQUE DE LA MÉMOIRE
IMPORTANT:
➢libérer les zones mémoires dont on n’a plus
besoin
➢la mémoire libérée sera à nouveau disponible
pour des appels ultérieurs de Créer
➢Que se passe-t-il si on passe en argument à
Libérer une adresse non obtenue par Créer
LISTES CHAÎNÉES
Présentation:
Tableau : représenter en mémoire une collection de données de même
nature.
Tableau : manipulé sous forme linéaire : la donnée à l’indice i + 1 est
consécutive en mémoire à la donnée d’indice i.
! Cette contiguïté peut ne pas être satisfaisante :
ajouter ou supprimer une donnée à un endroit quelconque
décaler la fin du tableau .
Problème :
la notion d’élément suivant dans un tableau est une notion implicite.
Solution:
Expliciter la notion du suivant : utiliser l’adresse mémoire afin de désigner de
façon unique un élément.
LISTES CHAÎNÉES
Définition:
On appelle donc liste chaînée ou plus simplement liste une
structure de données constituée d’éléments contenant chacun:
✓ une donnée;
✓ une référence (adresse, ou pointeur) de l’élément suivant.
La liste est elle-même totalement déterminée par la référence
(l’adresse) de son premier élément.
Premier élément = tête de liste.
Le dernier élément de la liste n’a pas de successeur
son successeur est la constante NIL
LISTES CHAÎNÉES
Opérations sur les listes:
➢l’initialisation d’une liste (en général, liste vide) ;
➢ le test, permettant de déterminer si une liste est
vide ;
➢passage à l’élément suivant ;
➢ l’ajout d’un élément dans une liste ;
➢ la suppression d’un élément dans une liste ;
➢ le parcours de la liste ; etc…
LISTES CHAÎNÉES
LS1 = ^nœud
noeud = enreg
val : valeur
next : LS1
fenreg
Exemple : liste = ( 1 , 2 , 3 , 4) représentée par L
L 1 2 3 4 NIL
LISTES CHAÎNÉES
Insertion en tête: insérer x en tête de L
L ……. NIL
X
LISTES CHAÎNÉES
insère_tête( var L : LS1 ; x : valeur)
var p : LS1
Début
créer( p )
p^.val := x
p^.next := L
L := p
Fin
LISTES CHAÎNÉES
Insertion en queue: insérer x à la fin de L
L:
……. NIL
X NIL
LISTES CHAÎNÉES
insère_queue( var L : LS1 ; x : get_last( L : LS1 ) : LS1
valeur) var p : LS1
var p , last : LS1 Début
Début p := L
créer( p ) tant que p^.next ≠ NIL faire
p^.val := x p := p^.next
p^.next := NIL fait
Si ( L = NIL ) get_last := p
alors L := p Fin
sinon
last := get_last( L )
last^.next := p
fsi
Fin
LISTES CHAÎNÉES
Insertion après un élément: insérer x après y
L:
Y
……. NIL
X
LISTES CHAÎNÉES
insère_val(var L : LS1 ; get_élém( L : LS1 ; y : valeur ) : LS1
x,y:valeur) var p , pred : LS1
var p , pred : LS1 Début
Début p := L
pred := get_élém(L , y) pred := NIL
si pred ≠ NIL tant que p≠ NIL et p^.val ≠ y
alors créer( p ) faire
p^.val := x pred := p
p^.next := pred^.next p := p^.next
pred^.next := p fait
fsi si p = NIL
Fin alors get_élém := NIL
sinon get_élém := pred
fsi
Fin
LISTES CHAÎNÉES
Pré-condition : La liste est NON VIDE
Suppression en tête: Supprimer la tête de L
NIL
…….
LISTES CHAÎNÉES
Supprime_tête( var L : LS1 )
var p : LS1
Début
p := L
L := L^.next
Libérer( p )
Fin
LISTES CHAÎNÉES
Suppression en queue: Supprimer le dernier
élément de L
L NIL NIL
Cas Particulier : Liste avec 1 seul élément
L
NIL
L
NIL
LISTES CHAÎNÉES
Supprime_queue( var L : LS1 ) get_pred_last( L : LS1 ) : LS1
var pred , last : LS1 var p , pred : LS1
Début Début
pred := get_pred_last( L ) p := L
Si ( pred = NIL ) pred := NIL
alors last := L tant que p^.next ≠ NIL faire
L := NIL pred := p
sinon p := p^.next
last := pred^.next fait
pred^.next := NIL get_pred_last := pred
fsi Fin
Libérer( last )
Fin
LISTES CHAÎNÉES
Suppression d’un élément x donné:
L
NIL
…….
X
LISTES CHAÎNÉES
Supprime_val(var L:LS1; x:valeur ) get_val( L : LS1 ; x : valeur ) : LS1
var pred , p : LS1 var p , pred : LS1
Début Début
pred := get_val( L , x) p := L
Si ( pred = NIL ) % x 1er de L ou x ɇ L pred := NIL
alors Si (L^.val = x ) tant que p ≠ NIL et p^.val ≠ x faire
alors p := L pred := p
L := L^.next p := p^.next
sinon p := NIL fait
fsi Si (p = NIL)
sinon alors get_val := NIL %xɇL
p := pred^.next sinon get_val := pred
pred^.next := p^.next Fin
fsi
Si ( p ≠ NIL )
alors Libérer( p )
fsi
Fin
LISTES CHAÎNÉES
LS2 = enreg
first : ^nœud
last : ^nœud
fenreg
noeud = enreg
val : valeur
next : ^nœud
fenreg
Exemple : liste = ( 1 , 2 , 3 , 4) représentée par L
L 1 2 3
4 NIL
LISTES CHAÎNÉES
insère_tête( var L : LS2 ; x : valeur)
var p : ^noeud
Début
créer( p )
p^.val := x
p^.next := L.first
L.first := p
Si L.last = NIL
alors L.last := p
fsi
Fin
LISTES CHAÎNÉES
insère_queue( var L : LS2 ; x : valeur)
var p : ^noeud
Début
créer( p )
p^.val := x
p^.next := NIL
Si ( L.first = NIL )
alors L.first := p
sinon L.last^.next := p
fsi
L.last := p
Fin
LISTES CHAÎNÉES
insère_triée( var L : LS2 ;x :valeur) get_pred( L : LS2 ; x : valeur ) : ^noeud
var p , pred : ^noeud var p , pred : ^noeud
Début Début
créer( p ) p := L.first
p^.val := x pred := NIL
Si ( L.first = NIL ) tant que p ≠ NIL et p^.val < x faire
alors p^.next := NIL pred := p
L.first := p p := p^.next
L.last := p fait
sinon get_pred := pred
pred := get_pred(L , x) Fin
si pred = NIL
alors p^.next := L.first
L.first := p
sinon p^.next := pred^.next
pred^.next := p
fsi
fsi
Fin
LISTES CHAÎNÉES
Supprime_tête( var L : LS2 )
var p : ^noeud
Début
p := L.first
L.first := p^.next
if L.first = NIL
alors L.last := NIL
fsi
Libérer( p )
Fin
LISTES CHAÎNÉES
Supprime_queue( var L : LS2 ) get_pred_last( L : LS2 ): ^noeud
var pred , last : ^noeud var p , pred : ^noeud
Début Début
pred := get_pred_last( L ) p := L.first
last := L.last pred := NIL
Si ( pred = NIL ) tant que p^.next ≠ NIL faire
alors L.first := NIL pred := p
L.last := NIL p := p^.next
sinon fait
pred^.next := NIL get_pred_last := pred
L.last := pred Fin
fsi
Libérer( last )
Fin
LISTES CHAÎNÉES
Supprime_val(var L:LS2; x:valeur ) get_val( L : LS2 ; x : valeur ) : ^noeud
var pred , p : ^noeud var p , pred : ^noeud
Début Début
pred := get_val( L , x) p := L.first
Si ( pred = NIL ) % x 1er de L ou x ɇ L pred := NIL
alors Si (L.first^.val = x ) tant que p ≠ NIL et p^.val ≠ x faire
alors p := L.first pred := p
L.first := L.first^.next p := p^.next
Si L.first = NIL fait
alors L.last = NIL Si (p = NIL)
fsi alors get_val := NIL %xɇL
sinon p := NIL sinon get_val := pred
fsi Fin
sinon
p := pred^.next
pred^.next := p^.next
fsi
Si ( p ≠ NIL )
alors Libérer( p )
fsi
Fin
LISTES CHAÎNÉES
Liste chaînée double:
LD = enreg
first : ^nœud
last : ^nœud
fenreg
noeud = enreg
val : valeur
pred : ^nœud
next : ^nœud
fenreg
LISTES CHAÎNÉES
Exemple : liste = ( 1 , 2 , 3 , 4) représentée par L
L 1 NIL 2 3
4 NIL
LISTES CHAÎNÉES
insère_tête( var L : LD ; x : valeur)
var p : ^noeud
Début
créer( p )
p^.val := x
p^.next := L.first
p^.pred := NIL
Si L.first = NIL
alors L.last := p
sinon L.first^.pred := p
fsi
L.first := p
Fin
LISTES CHAÎNÉES
insère_queue( var L : LD ; x : valeur)
var p : ^noeud
Début
créer( p )
p^.val := x
p^.next := NIL
Si ( L.first = NIL )
alors L.first := p
p^.pred := NIL
sinon p^.pred := L.last
L.last^.next := p
fsi
L.last := p
Fin
LISTES CHAÎNÉES
insère_triée( var L : LD ;x :valeur)
var p , q : ^noeud
Début
créer( p )
p^.val := x
Si L.first = NIL
alors p^.next := NIL
p^.pred := NIL
L.first := p
L.last := p
sinon
q:= L.first
pred := NIL
tant que q ≠ NIL et q^.val < x faire
q := q^.next
fait
si q = L.first
alors p^.next := L.first
L.first^.pred := p
p^.pred := NIL
L.first := p
sinon p^.next := q
p^.pred:= q^.pred
q^.pred := p
fsi
fsi
Fin
LISTES CHAÎNÉES
Supprime_tête( var L : LD )
var p : ^noeud
Début
p := L.first
L.first := p^.next
if L.first = NIL
alors L.last := NIL
sinon L.first^.pred := NIL
fsi
Libérer( p )
Fin
LISTES CHAÎNÉES
Supprime_queue( var L : LD )
var last : ^noeud
Début
last := L.last
L.last := L.last^.pred
Si ( L.last = NIL )
alors L.first := NIL
sinon
L.last^.next := NIL
fsi
Libérer( last )
Fin
LISTES CHAÎNÉES
Supprime_val(var L:LD; x:valeur )
var p : ^noeud
Début
p := L.first
tant que p ≠ NIL et p^.val ≠ x faire
p := p^.next
fait
Si (p ≠ NIL)
alors Si ( p = L.first )
alors L.first := L.first^.next
Si L.first = NIL
alors L.last = NIL
sinon L.first^.pred := NIL
fsi
sinon p^.pred^.next := p^.next
p^.next^.pred := p^.pred
fsi
libérer(p)
fsi
Fin
