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.
Remarque 1:
- L'information peut être simple ou structurée (composée).
- Le couple information/adresse est appelé cellule.
Exemple:
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
Affectation
Création d'une liste chaînée
Nous utilisons la fonction Nouveau pour l'allocation d'une nouvelle cellule.
procédure creer_liste(tete: Ptr)
var val: entier
début
Nouveau(tete)
lire(val)
tete^.info ← val
tete^.suivant ← nil
fin
Activité:
- Créer une liste chaînée à partir des éléments d'un vecteur.
- 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
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
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
Activité
- Ecrire une procédure qui affiche les éléments d'une liste chaînée.
- 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
Probatoire A-ABI 2021 Epreuve de littérature ou de culture générale