Scribd
Importer
30 vues15 pages

Les Listes Doublement Chaînées: - Une Liste Bilatère (Doublement Chainée) Comporte Trois Parties

Le document décrit les listes doublement chaînées en détaillant leur structure, déclaration et opérations de base comme l'initialisation, l'ajout et la suppression d'éléments.

Transféré par

Tasnim Mehrabi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
30 vues15 pages

Les Listes Doublement Chaînées: - Une Liste Bilatère (Doublement Chainée) Comporte Trois Parties

Le document décrit les listes doublement chaînées en détaillant leur structure, déclaration et opérations de base comme l'initialisation, l'ajout et la suppression d'éléments.

Transféré par

Tasnim Mehrabi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

©Amen BHA

Les listes doublement chaînées


• Une liste bilatère (doublement chainée)
comporte trois parties :
– deux zones de chainage ( pointeurs qu’on appelle
« avant » et « après ») et
– une zone de donnée (valeur).
• Cette structure permet de parcourir la
liste dans les 2 sens et d’accélérer la
recherche d’un élément.
59
©Amen BHA

Les listes doublement chaînées


Représentation

60
©Amen BHA

Les listes doublement chaînées


Déclaration : Syntaxe Remarque
Si L.Tête = [Link] = NIL ⇒ La liste est vide
TYPE Si L.Tête = [Link] ≠ NIL ⇒ La liste à un seul élément
<typeElem> = <Type>
<Cellule> = Enregistrement
<avant> : pointeur sur Cellule
<valeur> : typeElem
<après> : pointeur sur Cellule
Fin enregistrement
LISTE = pointeur sur Cellule

LD = Enregistrement
Tête = LISTE
Queue = LISTE
Fin enregistrement
Var
L : LD

61
©Amen BHA

Les listes doublement chaînées


Opérations de base
1- initialisation d’une liste double
Procédure Init (VAR L : LD)
DEBUT
L.Tête ← NIL
[Link] ← NIL
FIN

62
©Amen BHA

Les listes doublement chaînées


Opérations de base
2- vérifier si la liste double est vide
Fonction Vide (L : LD) :boolean
DEBUT
Si (L.Tête = [Link] ) et (L.Tête=NIL)
alors
Vide vrai
Sinon
Vide faux
FIN
63
©Amen BHA

Les listes doublement chaînées


Opérations de base
3. Ajouter un nouvel élément au début de la liste double

Procédure AjoutTete (x : Type_Elem, var L : LD)


var Nouveau : LISTE
Début Nouveau
Allouer (Nouveau)
(*Nouveau).valeur x
(*Nouveau).avantNIL
Si vide(L) Alors
}
(*Nouveau).apres NIL
[Link] Nouveau X
[Link] Nouveau
Sinon 1
*([Link]).avant  Nouveau //1
(*Nouveau).apres [Link] //2
[Link] Nouveau //3
Fin si
} 3
2

Fin
64
©Amen BHA

Les listes doublement chaînées


Opérations de base
4- Ajouter un nouvel élément en queue de la liste double
Procédure AjoutQueue (val: Type_Elem, var L : LD)
var
Nouveau : LISTE
Début Nouveau

}
Allouer(Nouveau)
Nouveau^.valeur  val
Nouveau^.apres  NIL
Si vide (L) Alors
Nouveau ^.avant  NIL X
[Link] Nouveau
[Link] Nouveau
Sinon 1

[Link] Nouveau //3


Fin Si
}
[Link]^.apres  Nouveau //1
Nouveau^.avant  [Link] //2 2
Queue
3

Fin

65
©Amen BHA

Les listes doublement chaînées


Opérations de base
4- Ajouter un nouvel élément après une position donnée (on suppose que la liste est non
vide et P le pointeur de la position après lequel l’ajout sera fait)
Procédure AjoutApresPosition (X: Type_Elem, P: LISTE, var L : LD)
var P1,Nouveau : LISTE
Début
Si (P=[Link]) alors
AjoutQueue(X,L)
sinon

}
p1P^.apres P
Allouer(Nouveau)
Nouveau^.valeur  x
Nouveau^.apres  P1 //1
P1^.avantNouveau //2
3 2
P^.apresNouveau //3 1
4
Nouveau^.avantP //4
Fin Si
FIN

66
©Amen BHA

Les listes doublement chaînées


Opérations de base
5- Rechercher un élément
Fonction Recherche (x : Type_Elem, L : LD ) :
LISTE
Var
p :LISTE
Début
p  [Link]
Tantque p != NIL ET p^.valeur != x Faire
p  p^.apres
FinTantque
Recherchep
Fin

67
©Amen BHA

Les listes doublement chaînées


Opérations de base
6- Supprimer un élément
Procédure supprimer (x : Type_Elem, var L:LD)
Var P,P1,P2 : LISTE Si (P = [Link]) Alors // suppression en tete
Début [Link]  [Link]^.apres
P  Recherche (x,L) [Link]^.avant  NIL
Si (P≠ NIL) Alors Liberer(P)
Si (P = [Link] et P=[Link]) AlorsSinon Si (P=[Link]) Alors //suppression en queue
(P^.avant)^.apres  NIL
// liste à un seul élément L. Queue ← P → avant
Liberer (P) Liberer (p)
[Link] NIL Sinon
[Link] NIL P1 P^.avant
P2 P^.apres
Sinon P1^.apres  P2
P2^.avant P1
Liberer (p)
FinSi
FinSi FinSi FinSi Fin 68
©Amen BHA

Exemples
Exemple 1 : Créer une liste simplement chaînée composée de 2
éléments de type entier
Déclarations des types pour la liste :
Type
Element = Enregistrement
Info : entier
Suivant : pointeur sur Element
Fin Enregitrement
Liste = pointeur sur Element

69
©Amen BHA

Exemple
Algorithme CréationListe2Elements
Var
Tete, P : Liste
NombreElt : entier
DEBUT
1 Tete  Nil /* pour l'instant la liste est vide*/
2 Allouer(P) /* réserve un espace mémoire pour le premier élément */
3 Lire(P^.Info) /* stocke dans l'Info de l'élément pointé par P la valeur saisie */
4 P^.Suivant  Nil /* il n'y a pas d'élément suivant */
5 Tete  P /* le pointeur Tete pointe maintenant sur P */
/* Il faut maintenant ajouter le 2e élément, ce qui revient à insérer un élément en tête de liste */
6 Allouer(P) /* réserve un espace mémoire pour le second élément */
7 Lire(P^.Info) /* stocke dans l'Info de l'élément pointé par P la valeur saisie */
8 P^.Suivant  Tete /* élément inséré en tête de liste */
9 Tete  P
FIN

70
©Amen BHA

Exemple

10

71
©Amen BHA

Exemple

10

10

10

72
©Amen BHA

Exemple

10 45

10 45

10 45

73

Vous aimerez peut-être aussi