Les listes chaînées

Parent Category: Informatique et réseaux Category: Algorithme
Une liste chaînée est une suite d'objet de même type accessible un à un du premier au dernier élément.

La liste chaînée est une structure de données dynamiques, c'est-à-dire qu'elle permet de faire des allocations de mémoire selon la demande. La taille des données ou de la liste n'est pas fixée à l'avance, c'est le cas avec les tableaux (qui sont les structures de données statiques).

 

Les listes chaînées simples

 

C'est une structure de données telle que chaque élément forme un couple constitué:

  • Des informations caractéristiques de l'application, exemple: les caractères d'une personne.
  • Une adresse ou pointeur vers un autre élément (le suivant) ou une marque de fin s'il y'a pas d'élément successeur.

12

Remarque 1:

  • L'information peut être simple ou structurée (composée).
  • Le couple information/adresse est appelé cellule.
    Exemple:
13

Remarque 2:

  • C'est l'adresse de la première cellule qui détermine la liste.
  • Si le premier élément de la liste (tête) égale à nil (tête=nil), la liste est vide.
  • Il y'a autant de cellule que d'élément.
  • Le champ suivant d'une cellule contient l'adresse de la cellule suivante.
  • Le champ suivant de la dernière cellule contient nil.

Déclaration d'une liste chaînée

 

Type pointeur = ^liste chaînée
listechainee=Enregistrement
info: type
suivant: pointeur
fin enregistrement
var P: pointeur

Exemple:

Déclaration des patients chez un médecin
type Ptr = ^liste patient
liste patient=enregistrement
nom: chaîne
numéro: entier
suivant: Ptr
fin enregistrement
var P: Ptr

 
 

14

Affectation

 
 

15

Création d'une liste chaînée

Nous utilisons la fonction Nouveau pour l'allocation d'une nouvelle cellule.

 
 

16
procédure creer_liste(tete: Ptr)
var val: entier
début
Nouveau(tete)
lire(val)
tete^.info ← val
tete^.suivant ← nil
fin

Activité:

  1. Créer une liste chaînée à partir des éléments d'un vecteur.
  2. Créer une liste chaînée à partir des éléments d'un fichier.

procédure transfert_T_L(P: Ptr, V: vecteur, n: entier)
var i: entier
Pt: Pt
début
P ← nil
pour i=1 à n faire
nouveau(Pt)
Pt^.info ← V[i]
Pt^.suivant ← P
P ← Pt
fin pour
fin

procédure creation1(V: vecteur, tete: Ptr, N: entier)
va i: entier
P: Ptr
début
tete ← nil
pour i=1 à N faire
nouveau(P)
P^.info ← V[i]
P^.suivant ← tete
tete ← P
fin pour
fin

 
 

17
procédure creation2(F: fichier, tete: Ptr)
var P: Ptr
val: enregistrement
début
tete ← nil
ouvrirL(F)
lire(F)
tant que non(Fin(F)) faire
nouveau(P)
P^.info ← val
P^.suivant ← tete
tete ← P
lire(F, val)
fin tant que
fermer(F)
fin

 
 

18
procédure creation1_dans_l'ordre_normal(V: vecteur, tete: Ptr, n:entier)
var i: entier
P1, P: Ptr
début
nouveau(tete)
tete^.info ← V[i]
P ← tete
pour i=2 à n faire
nouveau(P1)
P1^.info ←V[i]
P^.suivant ← P1
P ← P1
fin pour
P1^.suivant ← nil
fin

 
 

19
Activité

  1. Ecrire une procédure qui affiche les éléments d'une liste chaînée.
  2. Ecrire une fonction qui prend en paramètre une liste chaînée et renvoie sa taille

procédure affiche(tete: Ptr)
var P1: Ptr
début
P1 ← tete
tant que P1≠nil faire
écrire(P1^.info)
P1 ← P1^.suivant
fin tant que
fin

procédure affiche(P: Ptr)
var Pt: Ptr
début
Pt ← P
tant que Pt≠nil faire
écrire(Pt^.info)
Pt ← Pt^.suivant
fin tant que
fin

fonction taille(L: Ptr):entier
var S: entier
P: Ptr
début
P ← L
S ← 0
tant que P≠nil faire
S ← S+1
P ← P^.suivant
fin tant que
taille ← S
fin


 

 


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

 

Ajout en tête

 

Pour ajouter un élément au début de la liste on a les étapes suivantes:

  • Créer une nouvelle cellule.
  • Remplir la nouvelle valeur dans la partie information.
  • Effectuer le chaînage.

La procédure correspondante est la suivante:

 
 

20
procédure (Pt: Ptr, val: info)
var P: Ptr
début
nouveau(P)
P^.info ← val
P^.suivant ← Pt
Pt ← P
fin

 

Ajout après P

 

Pour ajouter un nouvel élément après une cellule, on a les étapes suivantes:

  • Rechercher la cellule pointée par P
  • Créer une nouvelle cellule.
  • Introduire la nouvelle valeur de cette cellule.
  • Effectuer le chaînage c'est-à-dire pointer le suivant de la nouvelle cellule au suivant de la cellule P. Ensuite pointer le suivant de P à la nouvelle cellule. La procédure correspondante est la suivante
 

21
La procédure correspondante est la suivante:
procédure ajout_apres(tete, P: pointeur)
var P1, P2: pointeur
val: entier
début
P1 tete
tant que P1≠P faire
P1 P1^.suivant
fin tant que
lire(val)
nouveau(P2)
P2^.info val
P2^.suivant P^.suivant
P^.suivant P2
fin

 

Ajout avant P

 
 

22
procédure ajout_avant(tete, P: Ptr)
var P2, t: Ptr
val: info
début
t ← tete
tant que t^.suivant≠P faire
t ← t^.suivant
fin tant que
lire(val)
nouveau(P2)
P2^.info ← val
t^.suivant ← P2
P2^.suivant ← P
fin

 

Ajout en fin de liste

 
 

23
procédure ajout_fin(tete: Ptr)
var P1, P2: Ptr
val: info
début
P1 ← tete
tant que P1^.suivant
fin tant que
lire(val)
nouveau(P2)
P2^.info ← val
P2^.suivant ← nil
P1^.suivant ← P2
fin

procédure insertion(tete, Ptr, val: entier)
var P, P1, P2: Ptr
début
P ← tete
si val<P^.info alors
nouveau(P1)
P1^.info ← val
P1^.suivant ← P1
tete ← P1
sinon
tant que (P^.info<val) et (P^.suivant≠nil) faire
P ← P^.suivant
fin tant que
si P^.info >= val alors
P1 ← tete
tant que P1^.suivant≠P faire
P1 ← P1^.suivant
fin tant que
nouveau(P2)
P2^.info ← val
P1^.suivant ← P2
P2^.suivant ← P
sinon
si P^.suivant = nil
nouveau(P2)
P2^.info ← val
P2^.suivant ← nil
P^.suivant ← P2
fin si
fin si
fin si
fin

Exercice 2:

fonction compte(tête: Ptr, val: entier): entier
var P: Ptr
i: entier
début
P ← tete
t ← 0
tant que P≠nil faire
si P^.info=val alors
t ← t+1
fin si
P ← P^.suivant
fin tant
compte ← t
fin

Exercice 3:

Créer un polynôme (donner dans l'ordre croissant)
Déclaration
type polynôme = ^liste chaînée
liste chaîne = enregistrement
coef: réel
deg: entier
suivant = polynôme
fin enregistrement

procédure creer_polynome(tete: polynome)
début
tete ← nil

nouveau(P)
lire(val)
lire(val1)
P^.coef ← val
P^.deg ← val1
P^.suivant ← nul
tete ← P
repéter
lire(val)
lire(val1)
si val≠0 alors
si val1<tete^degré alors
nouveau(P1)
P1^.coef ← val
P1^.deg ← val1
P1^.suivant ← tete
tete ← P1
sinon
P ← tete
tant que (P^.deg<val1) et (P^.suivant≠nil) faire
P ← P^.suivant
fin tant que
si P^.deg>val1 alors
P1 ← tete
tant que P1^.suivant≠P faire
P1 ← P1^.suivant
fin tant que
nouveau(P2)
P2^.coef ← val
P2^.degre ← val1
P2^.suivant ← P
P1^.suivant ← P2
sinon
si P^.suivant=nil alors
nouveau(P2)
P2^.coef ← val
P2^.deg ← val1
P2^.suivant ← nil
P^.suivant ← P2
fin si
fin si
fin si
fin si
jusqu'à val=0
fin


 

 


Suppression d'un élément dans une liste chaînée

 

Utilisons la fonction libérer (en Pascal = dispose) pour libérer un emplacement occupé en mémoire.

Remarque:

  • La fonction "libérer" ne libère pas un emplacement nil et il libère une seule cellule à la fois.
  • La fonction "libérer" ne libère qu'une seule cellule de la liste et non de la liste tout entière.

Suppression en tête de liste

 

Il s'agit de retirer l'élément en tête de la liste si la liste est vide, on ne retire aucun élément et on envoye un message correspondant

procédure supp_tete(tete: Ptr)
var P: Ptr
P ← tete
si tete=nil alors
écrire('pas de suppression')
sinon
tete ← tete^.suivant
liberer(P)
fin si
fin

 

Suppression d'un élément P de la liste

 

Pour supprimer un élément P de la liste, parcourir la liste chaînée du début de la liste jusqu'au précédent de la cellule P, ensuite pointer le suivant du précédent de P ou suivant de P. Enfin libérer la cellule P. La procédure correspondante est:

procédure supp_p(tête, P: Ptr)
var P1: Ptr
début
si tete≠nil alors
P1 ← tete
tant que P1^.suivant#P faire
P1 ← P1^.suivant
fin tant que
P1^.suivant ← P^.suivant
liberer(P)
fin si
fin

 

Suppression en fin de liste

 

Pour supprimer un élément en fin de liste, il faut maintenir un pointeur à l'avant dernière cellule, ensuite libérer la dernière cellule et enfin mettre le suivant de l'avant dernière cellule à nil. La procédure correspondante est la suivante.

Procédure Supp_fin(tete: Ptr)
var P, P1: Ptr
début
P1 ← tete
P ← P1^.suivant
tant que P^.suivant≠nil faire
P1 ← P1^.suvant
P ← P^.suivant
fin tant que
P^.suivant ← nil
liberer(P)
fin