Les listes chaînées

Parent Category: Informatique et réseaux Category: Algorithme
 

 


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