TD 5

Nous avons vu les bases pour créer et utiliser des listes. On les a même mis en pratique sur des données "un peu complexe" (des chaînes de caractères). Maintenant on va voir quelques fonctionnalités, un peu plus complexe...

Pour cela, nous allons d'abord revenir sur les listes qui stockent des entiers. (n'abordons pas deux difficultés a la fois ). Bien sûr ces fonctionnalités pourront être intégrées, une fois qu'elles seront testées, dans un programme qui gère des données plus complexes.

Vous analyserez la complexité algorithmique ainsi que la complexité mémoire pour chaque fonction.

1. Une fonction qui recherche et remplace un élément par un autres. Exemple, chercher la valeur 3 et la remplacer par la valeur 6, partout dans la liste.
2. Une fonction qui affiche, le n ième élément d'une liste.
3. Une fonction qui supprimer le 1er élément de la liste.
4. Une fonction qui supprime un élément de la liste en fonction de sa valeur. Exemple, rechercher la cellule contenant l'élément de valeur 12, et le supprimer de la liste. Bien sur le reste des données de la liste ne doit pas être affecté. La cellule supprimée doit être désallouée.
5. Une fonction qui insère tous les éléments d'une liste (L2) dans une autre liste (L1). L2 ne doit pas être modifié.
6. Une fonction qui transforme une liste classique en liste circulaire : faire pointer la dernière cellule vers la première.
7. ...La fonction précédente vous demandera de modifier votre fonction d'affichage pour qu'elle se termine!
8. ...Vous constatez maintenant que la fonction de désallocation nécessite elle aussi d'être adaptée pour le cas où la liste est circulaire!

Si vous avez fini toutes ces fonctions, vous pouvez les intégrer à votre code qui gère des liste stockant des chaînes de caractère. Revenez sur le problème de reconstruction de document détruit en implémentant une solution utilisant les listes.