Les listes chaînées

 Insertion d’une valeur à une position k dans une liste

 Écrire la procédure Insertk qui permet d’insérer une valeur val à
une position k dans une liste chaînée donnée par l’adresse de son
premier élément (premier).
 La valeur val aura le rang k+1 dans la liste après l’insertion.
Les listes chaînées
 Principe
Si (k =0) alors //Si k=0 l’insertion se fait en tête de la liste.
InsertTete(premier,val)
Sinon
Si (k>LongListe(premier)) alors
écrire("la position k=" ,k, " n'existe pas car la liste est de taille",LongListe(premier))
Sinon
Pour i de 1 à k-1 faire // Récupérer l’adresse du maillon qui se trouve à la position k (pk) .
pk ← pk^.suivant;
Finpour
// Créer un maillon d’adresse nouvElt contenant la valeur val et dont l’élément suivant est le
suivant de pk
nouvElt ← nouveau(^liste)
nouvElt ^.valeur ← val
nouvElt^.suivant ← pk^.suivant // Le suivant de nouvElt est le suivant de pk.
pk^.suivant ← nouvElt // Le suivant de pk devient nouvElt.
Finsi
Finsi
Les listes chaînées
PROCEDURE Insertk(var premier : ^liste , k: entier,val: entier)
var
nouvElt,pk : ^liste
i: entier
Début
Si (k =0) alors
InsertTete(premier,val)
Sinon
Si (k>LongListe(premier)) alors
écrire("la position k=" ,k, " n'existe pas car la liste est de taille",LongListe(premier))
Sinon
pk ← premier
Pour i de 1 à k-1 faire
pk ← pk^.suivant
Finpour
nouvElt ← nouveau(^liste)
nouvElt^.valeur ← val
nouvElt^.suivant ← pk^.suivant
pk^.suivant ← nouvElt
Finsi
Finsi
Fin
Les listes chaînées
 Suppression du premier maillon d’une liste
 Écrire la procédure SuppTete qui permet de supprimer le premier
maillon d’une liste chaînée donnée par l’adresse de son premier
élément (premier).
Les listes chaînées
 Principe
//Si la liste est non vide : on sauvegarde premier dans une variable p.
Si (premier ≠ Nil) alors
p ← premier
// La valeur de premier prend la valeur de son suivant.
premier ← premier^.suivant
// On libère la zone mémoire d’adresse p.
liberer(p)
Finsi
Les listes chaînées
 Algorithmique
PROCEDURE SuppTete(var premier : ^liste)
var
p : ^Liste
Début
Si (premier <> Nil) alors
p ← premier
premier ← premier ^.suivant
liberer(p)
Finsi
Fin
Les listes chaînées
 Suppression du dernier maillon d’une liste
 Écrire la procédure SuppQueue qui permet de supprimer le
dernier maillon d’une liste chaînée donnée par l’adresse de son
premier élément (premier).
 Notons qu’après la suppression la valeur du premier peut changer
Les listes chaînées
 Principe
Si (premier ≠ Nil) alors //Si la liste est non vide
//Si la liste contient un seul élément, la suppression se fait en tête de la liste
Si (LongListe(premier)=1) alors
SuppTete(premier)
Sinon // Sinon, On récupère l’adresse de l’avant dernier élément (AvDer)
AvDer ← premier
Tantque(AvDer ^.suivant^.suivant<>Nil) faire
AvDer ← AvDer ^.suivant
FinTantque
// On sauvegarde l’adresse du dernier élément dans une variable p.
p ← AvDer ^.suivant
AvDer^.suivant ← Nil // L’élément d’adresse AvDer devient le dernier élément.
liberer(p) // on libère la zone mémoire d’adresse p.
Finsi
Finsi
Les listes chaînées
 Algorithmique
PROCEDURE SuppFin( var premier : ^liste)
var
AvDer,p : ^liste
Début
Si (premier <> Nil) alors
Si (LongListe(premier)=1)
SuppTete(premier)
Sinon
AvDer ← premier
Tantque(AvDer ^.suivant^.suivant<>Nil) faire
AvDer ← AvDer ^.suivant
Fintantque
p ← AvDer ^.suivant
AvDer ^.suivant ← Nil
liberer(p)
Finsi
Finsi
Fin
Les listes chaînées
 Suppression de tous les maillons d’une liste
 Écrire la procédure SuppListe qui permet de supprimer tous les
éléments d’une liste chaînée donnée par l’adresse de son premier
élément (premier).
 Après la suppression la valeur du premier vaudra Nil.
 Algorithmique
PROCEDURE SuppListe(var premier: ^liste)
Début
Tantque(premier<>Nil)faire
SuppTete(premier)
fintantque
fin
Les listes chaînées
 Exercice 1 :
Utilisez les fonctions et procédures vues précédemment dans
le cours pour écrire une procédure qui prend en entrée une
liste chaînée d'entiers et qui ressort deux listes chaînées :
 une pour les nombres pairs
 et une autre pour les nombres impairs.
 la liste initiale est détruite.
Les listes chaînées
 Exercice 2 :
Un polynôme est composé d’un ensemble de monômes.
Chaque monôme est caractérisé par un degré et un coefficient.
 Proposez les structures nécessaires pour modéliser un monôme et un
polynôme.
 Ecrire une fonction qui prend en argument un tableau tab de n
éléments et construit un polynôme tel que pour tout indice i, tab[i]
est le coefficient du monôme xi .
 Ecrire une fonction qui supprime le monôme de degré i d’un
polynôme p.
 Ecrire une fonction qui retourne la dérivée d’un polynôme p donné
en paramètre.
 Ecrire une fonction qui retourne la somme de deux polynômes p et q
donnés en paramètre.
Les listes chaînées
 Les listes doublement chaînées
 Dans une liste doublement chaînée un maillon est composé de trois
champs:
 Un champ de données ;
 Un pointeur vers un le maillon suivant.
 Un pointeur vers un le maillon précédent.

 Suivant : Ce champ pointe vers le maillon suivant de la liste.

S'il n'y a pas de maillon suivant, le pointeur vaut NIL.
 Précédent : Ce champ pointe vers le maillon précédent de la
liste. S'il n'y a pas de maillon précédent, le pointeur vaut NIL.
Les listes chaînées
 Le type liste doublement chaînée
type
maillon = Enregistrement
Valeur : entier
suivant : ^maillon
précédent : ^maillon
Fin maillon
// Définition du type listedc
listedc =maillon
Les listes chaînées
 Insertion d’une valeur en tête d’une liste doublement
chainée.
 Écrire la procédure InserTete qui permet d’insérer une valeur v
en tête d’une liste doublement chaînée donnée par l’adresse de
son premier élément (premier).
 Après l’insertion la valeur du premier sera changée donc le
passage doit se faire par adresse.
Les listes chaînées
 Principe
// Créer un maillon d’adresse nouvElt contenant la valeur v et dont le pointeur
précédent est nil (il sera le premier).
nouvElt ← nouveau(^listedc)
nouvElt ^.valeur ← v
nouvElt ^.précédent ← Nil
// Créer un lien entre le nouveau maillon et la tête de la liste de telle sorte que
premier soit le suivant de nouvElt
nouvElt ^.suivant ← premier
// Créer un lien entre la tête de la liste (si elle existe) et le nouveau maillon de telle
sorte que nouvElt soit le précédent de premier.
Si (premier<>nil) alors
premier^.précèdent ← nouvElt
Finsi
//Le maillon nouvElt devient le premier maillon de liste premier
premier ← nouvElt
Les listes chaînées
 Algorithmique
PROCEDURE InsertTete(var premier : ^listedc, v : entier)
var
nouvElt : ^listedc
Debut
nouvElt ← nouveau(^listedc)
nouvElt ^.valeur ← v
nouvElt ^.précédent ← Nil
nouvElt ^.suivant ← premier
si(premier <>Nil) alors
premier ^.précédent ← nouvElt
Finsi
premier ← nouvElt
Fin
Les listes chaînées
 Suppression du premier maillon d’une liste
doublement chaînée
 Écrire la procédure SuppTete qui permet de supprimer le premier
maillon d’une liste doublement chaînée donnée par l’adresse de
son premier élément (premier).
 Après la suppression, la valeur du premier maillon doit changer,
donc le passage doit se faire par adresse.
Les listes chaînées
 Principe
// Si la liste est non vide : on sauvegarde premier dans une variable P1
Si(premier ≠ Nil) alors
P1 ← premier
// La valeur de premier prend la valeur de son suivant.
premier ← premier^.suivant
// La valeur du précédent prend la valeur Nil
premier^.précédent ← Nil
// On libère la zone mémoire d’adresse P1.
libérer(P1)
Finsi
Finsi
Les listes chaînées
 Algorithme
PROCEDURE SuppTete (var p : ^listedc)
var
P1: ^listedc
Début
P1 ← p ;
si (p<>Nil) alors
p ← p^.suivant
p^. précédent ← Nil
libérer(P1)
fin si
fin
Les listes chaînées
 Les listes circulaires
 Une liste où le pointeur Nil du dernier élément est remplacé par
l’adresse du premier élément est appelée liste circulaire.
 Dans une liste circulaire tous les maillons sont accessibles à partir de
n’importe quel autre maillon.
 Une liste circulaire n’a pas de premier et de dernier maillon. Par
convention, on peut prendre le pointeur externe de la liste vers le
dernier élément et le suivant serait le premier élément de la liste.