Eniso Sousse
Algorithmique et Structures de données
Série
Les listes chaînées
Exercice 1
Soit une liste simplement chaînée qu’on suppose déjà crée ayant la définition suivante :
Type
Enreg = enregistrement
Val : entier
Suiv : pointeur sur Enreg
Fin enregistrement
Liste : pointeur sur Enreg
Var
L : liste
1. Ecrire une fonction Inverser permettant d’inverser les éléments de la liste. (Utiliser la
fonction Ajout_tete à deux paramètres L et x.
2. Ecrire un programme principal permettant d’afficher les éléments de la liste avant et
après inversion.
Exercice 2
Soit une liste simplement chaînée qu’on suppose déjà crée. On vous demande d’écrire les
fonctions suivantes :
1. Une fonction Ajout_ele permettant d’ajouter un entier en queue de la liste.
2. Un programme principal permettant de :
- Charger une liste L1,
- Eclater la liste L1 en deux listes L2 et L3 (L2 contient les éléments pairs de L1 et L3
les éléments impairs.
- Afficher les éléments de L1, L2 et L3.
Exercice 3
Soit la définition suivante :
Type
Enreg = enregistrement
Val : entier
Suiv : pointeur sur Enreg
Fin enregistrement
Liste : pointeur sur Enreg
Var
L : liste
X : entier
Eniso Sousse
Algorithmique et Structures de données
On suppose que la liste est déjà crée. On vous demande d’écrire les procédures/fonctions
suivantes :
1. Une procédure Affiche permettant d’afficher les éléments de la liste.
Procédure Affiche (L : liste)
2. Une fonction Nb_occ permettant de déterminer le nombre d’occurrence de l’entier x dans
la liste L.
Fonction Nb_occ (L : liste ; x : entier) : entier
3. Une fonction Supp_Ele permettant de supprimer un élément de la liste.
Fonction Supp_Ele (L : liste ; x : entier) : liste
4. Une fonction Determine permettant de retourner le nombre d’éléments distincts de la
liste
Fonction Determine (L : liste) : entier
5. Une fonction Elimine_Ele permettant d’éliminer toutes les occurrences de l’élément x de
la liste. (Utiliser les deux fonctions suivantes : Nb_occ et Supp_Ele).
Fonction Elimine_Ele (L : liste ; x : entier) : liste
6. Ecrire un programme principal qui permet de :
- Saisir un entier x,
- Afficher le nombre d’éléments distincts de la liste L,
- Afficher les éléments de la liste avant et après suppression de l ‘entier x.
Exercice 4
Soit une liste simplement chaînée qu’on suppose déjà crée. On vous demande d’écrire les
fonctions suivantes :
1. Une fonction Fusion à deux paramètres L1 et L2 permettant de construire une liste L3
trié par ordre croissant avec les éléments des deux listes L1 et L2. (Utiliser la fonction
Ajout_ele de l’exercice 2).
2. Un programme principal permettant d’afficher les éléments de L1, L2 et L3.
Exercice 5
Soit la définition suivante :
Type
Enreg = enregistrement
Val : entier
Suiv : pointeur sur Enreg
Fin enregistrement
Liste : pointeur sur Enreg
Val peut avoir la valeur 0 ou 1. On vous demande d’écrire les fonctions suivantes :
Eniso Sousse
Algorithmique et Structures de données
1. Une fonction Ajout_queue permettant de charger et retourner une liste L contenant des 0
et des 1,
2. Une fonction Affiche permettant d’afficher les éléments de la liste L,
3. Une fonction Taille permettant de retourner la taille de la liste L
4. Une fonction Conversion permettant de retourner un entier décimal résultat de la
conversion d’un nombre binaire. Ce nombre binaire étant représenté par la liste L.
(Utiliser la fonction Taille).
5. Le programme principal permettant de :
- Charger la liste par des 1 et des 0 et d’afficher le nombre en binaire.
- Convertir le nombre binaire en décimal et afficher le résultat.
Exemple :
1 β 0 λ 1 µ 1 α 0 NULL
Le nombre binaire est : 10110
Sa conversion = 22.
Exercice 6
Un étudiant peut être représenté par une liste simplement chaînée dont la définition est la
suivante :
Etudiant = enregistrement
CIN : entier
Nom : chaîne [20]
Pre : chaîne [20]
Note : tableau [1..8] de réel
Suiv : pointeur sur Etudiant
Fin enregistrement
Liste : pointeur sur Etudiant
1. Ecrire une fonction Test qui permet de retourner :
- 1 : si l’étudiant ayant le numéro NCIN existe dans la liste,
- 0 sinon
Fonction Test (LE : liste, NCIN : entier) : entier
2. Ecrire une fonction Ajout_queue qui permet de créer une liste chaînée d’étudiants.
Fonction Ajout_queue (LE : liste) : liste
Remarques
- Le nombre d’étudiants est inconnu au départ (L’ajout s’arrête lorsque le CIN = 0),
- La fonction doit vérifier que l’identifiant est unique (c.à.d. qu’il n’y a pas deux
étudiants qui ont le même CIN). Utiliser la fonction Test.
3. Ecrire une procédure Affiche_E qui permet d’afficher la liste des étudiants (Afficher
seulement les champs : CIN, Nom et Pre)
Procédure Affiche_E (LE : liste) : réel
4. Ecrire une fonction Moyenne permettant de retourner la moyenne d’un étudiant donné de
la liste sachant que les notes ont les mêmes coefficients.
Fonction Moyenne (LE : liste) : réel
Eniso Sousse
Algorithmique et Structures de données
5. Ecrire une procédure Admis qui permet de chercher et d’afficher les étudiants qui ont
une moyenne supérieure ou égale à 10. (Utiliser la fonction Moyenne).
Procédure Admis (LE : liste)
6. Ecrire un programme principal qui permet de :
- Charger la liste,
- Afficher la liste,
- Afficher les étudiants admis.
