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
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:
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
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
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
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
Probatoire A-ABI 2021 Epreuve de littérature ou de culture générale