• Aucun article dans le panier.

Les listes doublements chaînées

Généralités

Encore appelée liste symétrique, une liste doublement chaînée est une liste dans laquelle chaque élément de la liste a deux pointeurs, l’un pointant sur son suivant et l’autre sur son précédent. La tête d’une liste doublement chaînée à son précédent qui pointe à nil, tandis que la queue à son suivant qui pointe à nil.

24

Déclaration d’une liste doublement chaînée

type pointeur double = ^liste double
liste double = enregistrement
info: type élément
suivant, précédent: pointeur double
fin enregstrement
type PtrD = ^listeD
listeD = enregistrement
info : entier
suiv, prec: PtrD
fin enregistrement


Création d’une liste doublement chaînée

Procédure creer_cellule(tete: PtrD)
var a: entier
début
nouveau(tete)
lire(a)
tete^.info ← a
tete^.prec ← nil
tete^.suiv ← nil
fin


Ajout d’un élément dans une liste doublement chaînée

Ajout en tete

25
procédure ajout_tete(tete: PtrD, val: entier)
var P: PtrD
début
nouveau(P)
P^.info ← val
P^.prec ← nil
P^.suiv ← tete
tete^.prec ← P
tete ← P
fin

Ajout avant P

26
procédure ajout_avant_P(tete: PtrD, val: entier)
debut
P1 ← tete
tant que P1≠P faire
P1 ← P1^.suiv
fin tnat que
nouveau(P2)
P2^.info ←- val
P2^.suiv ← P
P2^.prec ← P^.prec
P^.prec^.suiv ← P2
P^.prev ← P2
fin

Ajout en fin de liste

27
procédure ins_fin(tete: Ptr, val: entier)
var P: PtrD
début
P ← tete
tant que P^.suivant ≠ nil faire
P ← P^.suivant
fin tanty que
nouveau(P1)
P1^.info ← val
P1^.prec ← P
P1^.suivant ← nil
P^.suivant ←- P1
fin


Suppression d’un élément dans une liste symétrique

Suppression en tête

28
procédure sup_tete(tete: PtrD)
var P: PtrD
début
P ← tete
si tete#nil alors
tete ← tete^.suivant
tete^.prec ← nil
liberer(P)
fin si
fin

Suppression à la position P

29
Procédure Supp_P(tete: Ptr)
var P, P1: PtrD
début
P1 ← tete
tant que P1^.suivant≠P faire
P1 ← P1^.suivant
fin tant que
P1^.suivant ← P^.suivant
P^.suivant^.prec ← P1
librerer(P)
fin

Suppression en queue

30
procédure Sup_queue(tete: PtrD)
var P1: PtrD
début
P1 ← tete
tant que P1^.suivant ≠ nil faire
P1 ← P1^.suivant
fin tant que
P1^.prec^.suivant ← nil
liberer(P1)
fin

1 décembre 2021
© GoSukulu SARL. Tous droits réservés.
Ouvrir le chat
Besoin d'aide?
Salut👋,
Comment puis-je vous aider?