Exercice n°1
Coder la fonction afficherListe.
Vous devrez parcourir la liste jusqu'au bout et afficher toutes les valeurs
qu'elle contient. Voici son prototype :
1 |
void afficherListe(llist liste); |
Exercice n°2
Un deuxième exercice utilisant trois fonctions que nous avons vues jusqu'à
présent : *ajouterEnTete * ajouterEnFin * afficherListe
Vous
devez écrire le main permettant de remplir
et afficher la liste chaînée ci-dessous. Vous ne devrez utiliser qu'une seule
boucle for.
|
|
10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 |
Exercice n°3
Écrivez une fonction qui renvoie 1 si la liste est vide, et 0 si elle
contient au moins un élément. Son prototype est le suivant :
1 |
int estVide(llist liste); |
Il
s'agit là de supprimer le premier élément de la liste. Pour ce faire, il nous
faudra utiliser la fonction free . Si la liste
n'est pas vide, on stocke l'adresse du premier élément de la liste après
suppression (i.e. l'adresse du 2ème élément de la liste originale), on supprime
le premier élément, et on renvoie la nouvelle liste. Attention quand même à ne
pas libérer le premier élément avant d'avoir stocké l'adresse du second, sans
quoi il sera impossible de la récupérer.
Exercice n°5 : Supprimer un élément en fin de liste
Exercice n°6 : Rechercher un élément dans une liste
Le
but du jeu cette fois est de renvoyer l'adresse du premier élément trouvé ayant
une certaine valeur. Si aucun élément n'est trouvé, on renverra NULL. L'intérêt est de pouvoir, une fois le premier
élément trouvé, chercher la prochaine occurrence en recherchant à partir de elementTrouve->nxt. On parcourt donc la
liste jusqu'au bout, et dès qu'on trouve un élément qui correspond à ce que
l'on recherche, on renvoie son adresse.
Exercice n°7 : Compter le nombre d'occurrences d'une valeur
Pour
ce faire, nous allons utiliser la fonction précédente permettant de rechercher
un élément. On cherche une première occurrence : si on la trouve, alors on
continue la recherche à partir de l'élément suivant, et ce tant qu'il reste des
occurrences de la valeur recherchée. Il est aussi possible d'écrire cette
fonction sans utiliser la précédente bien entendu, en parcourant l'ensemble de
la liste avec un compteur que l'on incrémente à chaque fois que l'on passe sur
un élément ayant la valeur recherchée. Cette fonction n'est pas beaucoup plus
compliquée, mais il est intéressant d'un point de vue algorithmique de
réutiliser des fonctions pour simplifier nos codes.
Exercice n°8 :Recherche du i-ème élément
Il
suffit de se déplacer i fois à l'aide du pointeur tmp le long de la liste chaînée
et de renvoyer l'élément à l'indice i. Si la liste
contient moins de i élément(s), alors nous
renverrons NULL.
Exercice n°9 : Récupérer la valeur d'un
élément
C'est
une fonction du même style que la fonction estVide. Elle sert à "masquer" le
fonctionnement interne à l'utilisateur. Il suffit simplement de renvoyer à
l'utilisateur la valeur d'un élément. Il faudra renvoyer un code d'erreur
entier si l'élément n'existe pas (la liste est vide), c'est donc à vous de
définir une macro selon l'utilisation que vous voulez faire des listes
chaînées. Dans ce code, je considère qu'on ne travaille qu'avec des nombres
entiers positifs, on renverra donc -1 pour une
erreur. Vous pouvez mettre ici n'importe quelle valeur que vous êtes sûrs de ne
pas utiliser dans votre liste. Une autre solution consiste à renvoyer un
pointeur sur int au lieu
d'un int, vous laissant
donc la possibilité de renvoyer NULL.
Exercice n°10 : Compter le nombre
d'éléments d'une liste chaîné
Vous
parcourez la liste de bout en bout et incrémentez d'un pour chaque nouvel
élément que vous trouvez. Cet algorithme n'ayant aucun intérêt au point où nous
en sommes, Par contre transformez le en un algorithme récursif
Exercice n°11 : Effacer tous les
éléments ayant une certaine valeur
Pour
cette dernière fonction, nous allons encore une fois utiliser un algorithme
récursif. Même si la récursivité vous semble être une notion complexe (et ça
l'est sûrement), elle simplifie grandement les algorithmes dans certains cas,
et dans celui-ci tout particulièrement.
Exercice n°12
coder de manière itérative la fonction nombreElements
dont je vous rappelle le prototype :
1 |
int nombreElements(llist liste); |
Exercice n°13
Nous allons maintenant écrire une fonction permettant d'effacer complètement
une liste chaînée de la mémoire. Je vous propose d'écrire avec un algorithme
itératif dans un premier temps, puis une seconde fois grâce à un algorithme
récursif. Dans le premier cas, vous devez parcourir la liste, stocker l'élément
suivant, effacer l'élément courant et avancer d'une case. A la fin la liste est
vide, nous retournerons NULL.
DEVOIR LIBRE
Ecrire un programme qui contient 7 opérations : ajouter
une liste en tete , ajouter en fin , inserer une liste , afficher tous , rechercher par reference et afficher , la suppression d’une liste ,
modifier une liste :
Concernant la gestion d’un produit (reference
, nom , prix de vente , prix d’achat)
M Naji