:: Enseignements :: ESIPE :: E3INFO :: 2009-2010 :: Algorithmique ::

Listes (suite et fin)

Ce TD a pour objectif de se familiariser avec les pointeurs, les listes chaînées et leurs utilisations.

Exercice 1 - File

Une file est une structure de données basée sur le principe " Premier arrivé, premier servi ! " en anglais FIFO (First In, First Out), ce qui veut dire que les premiers éléments ajoutés à la file seront les premiers à être récupérés.

Proposer une implémentation d'une file à l'aide d'une liste chaînée, incluant les opérations d'insertion et de retrait d'un élément dans la file.

Exercice 2 - Liste circulaire

Une liste est dite circulaire si son dernier élément pointe sur le premier.

Écrire les fonctions permettant (1) de tester si une liste est circulaire, (2) d'insérer un élément dans une liste circulaire et (3) de supprimmer la première occurence d'un élément de la liste.
Expliquer comment peut-on représenter une file à l'aide d'une liste circulaire

Exercice 3 - Tri fusion

Écrire l'algorithme de tri fusion pour des données stockées dans des listes.