Procédure ajout_fin(ES : pNouveau, pPrec :pointeurs sur element)
Début
pPrec→pSuiv ← pNouveau
pNouveau→pSuiv ← NIL
FinProc
Au final, aucun ajout n’aura été bien compliqué, puisque là encore vous disposez de tout le nécessaire. Pour rajouter
un élément entre deux autres éléments d’une liste, vous devez connaître l’adresse de l’élément précédent, et
l’adresse de l’élément courant, sachant que le nouvel élément sera inséré entre les deux. La procédure ajout_milieu()
reçoit donc trois arguments : le nouvel élément pNouveau, l’élément précédent pPrec et l’élément actuel pEncours.
Procédure ajout_milieu(ES :pNouveau, pPrec, pEncours) :pointeurs
sur element)
Début
pPrec←pSuiv → pNouveau
pNouveau←pSuiv → pEncours
FinProc
Le but est de généraliser les ajouts en un grand sousprogramme unifié. Pour ça, il faut savoir où placer l’élément à
rajouter. L’algorithme de recherche d’un élément retourne deux pointeurs : celui de l’élément trouvé et de l’élément
précédent. Supposez que vous souhaitez insérer votre nouvel élément juste avant l’élément recherché, ça devient
plutôt simple. Quatre cas de figure se présentent :
q pPrec contient NIL (pas d’élément avant) et pEncours contient NIL : il n’y a aucun élément dans la liste, le
nouveau sera le premier et seul élément.
q pPrec contient NIL (pas d’élément avant) et pEncours pointe sur l’élément trouvé qui est le premier : le
nouveau se place avant, en premier.
q pPrec pointe sur un élément précédent et pEncours pointe sur l’élément trouvé, le nouveau se place au milieu
des deux.
q pPrec pointe sur un élément précédent et pEncours contient NIL (la recherche est arrivée au bout, élément
trouvé ou non), le nouveau se place en dernier.
Quatre cas de figures qui correspondent aux quatre sousprogrammes déjà créés cidessus ! L’algorithme devient
simple : il suffit d’appeler la bonne procédure selon les valeurs de pPrec et de pEncours. La procédure ajout_element
prend trois valeurs : la valeur recherchée, la valeur à insérer avant et le pointeur de tête de la liste.
Procédure ajout_element(E:vrech,vnouveau :entiers, ES :pTete
:pointeur sur element)
Var
pPrec, pEncours, pNouveau : pointeurs sur element
Début
pNouveau←nouveau element ;
pNouveau→valeur ← vnouveau
recherche_liste(vrech,pTete,pPrec,pEncours)
Si pPrec=NIL Alors
Si pEncours=NIL Alors
ajout_unique(pNouveau, pTete)
Sinon
ajout_début(pNouveau, pTete)
FinSI
Sinon
Si pEncours=NIL Alors
ajout_fin(pNouveau, pPrec)
Sinon
ajout_milieu(pNouveau, pPrec, pEncours)
FinSi
FinSi
FinProc
Ajout en milieu de liste
Généralisation
- 6 -
© ENI Editions - All rigths reserved - Jonifar lina
179
Début
pPrec→pSuiv ← pNouveau
pNouveau→pSuiv ← NIL
FinProc
Au final, aucun ajout n’aura été bien compliqué, puisque là encore vous disposez de tout le nécessaire. Pour rajouter
un élément entre deux autres éléments d’une liste, vous devez connaître l’adresse de l’élément précédent, et
l’adresse de l’élément courant, sachant que le nouvel élément sera inséré entre les deux. La procédure ajout_milieu()
reçoit donc trois arguments : le nouvel élément pNouveau, l’élément précédent pPrec et l’élément actuel pEncours.
Procédure ajout_milieu(ES :pNouveau, pPrec, pEncours) :pointeurs
sur element)
Début
pPrec←pSuiv → pNouveau
pNouveau←pSuiv → pEncours
FinProc
Le but est de généraliser les ajouts en un grand sousprogramme unifié. Pour ça, il faut savoir où placer l’élément à
rajouter. L’algorithme de recherche d’un élément retourne deux pointeurs : celui de l’élément trouvé et de l’élément
précédent. Supposez que vous souhaitez insérer votre nouvel élément juste avant l’élément recherché, ça devient
plutôt simple. Quatre cas de figure se présentent :
q pPrec contient NIL (pas d’élément avant) et pEncours contient NIL : il n’y a aucun élément dans la liste, le
nouveau sera le premier et seul élément.
q pPrec contient NIL (pas d’élément avant) et pEncours pointe sur l’élément trouvé qui est le premier : le
nouveau se place avant, en premier.
q pPrec pointe sur un élément précédent et pEncours pointe sur l’élément trouvé, le nouveau se place au milieu
des deux.
q pPrec pointe sur un élément précédent et pEncours contient NIL (la recherche est arrivée au bout, élément
trouvé ou non), le nouveau se place en dernier.
Quatre cas de figures qui correspondent aux quatre sousprogrammes déjà créés cidessus ! L’algorithme devient
simple : il suffit d’appeler la bonne procédure selon les valeurs de pPrec et de pEncours. La procédure ajout_element
prend trois valeurs : la valeur recherchée, la valeur à insérer avant et le pointeur de tête de la liste.
Procédure ajout_element(E:vrech,vnouveau :entiers, ES :pTete
:pointeur sur element)
Var
pPrec, pEncours, pNouveau : pointeurs sur element
Début
pNouveau←nouveau element ;
pNouveau→valeur ← vnouveau
recherche_liste(vrech,pTete,pPrec,pEncours)
Si pPrec=NIL Alors
Si pEncours=NIL Alors
ajout_unique(pNouveau, pTete)
Sinon
ajout_début(pNouveau, pTete)
FinSI
Sinon
Si pEncours=NIL Alors
ajout_fin(pNouveau, pPrec)
Sinon
ajout_milieu(pNouveau, pPrec, pEncours)
FinSi
FinSi
FinProc
Ajout en milieu de liste
Généralisation
- 6 -
© ENI Editions - All rigths reserved - Jonifar lina
179