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