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