TD 1 - 2

Théorie sur les listes chaînées.

    Rappels

    On rappelle le principe d'une liste chaînée, qui est constituée de deux structures. La première structure "cellule" possède deux champs, le premier étant un élément de la liste (une valeur, du type des éléments qu'on souhaite stocker), et le second est un pointeur vers la cellule suivante.

    Une deuxième structure "liste" possède un pointeur vers le premier élément de la liste et un entier qui stocke le nombre d'éléments de la liste. Ainsi, depuis une instance de la structure liste, on peut accéder au premier élément, puis naviguer de pointeur en pointeur pour parcourir la liste.

    Bases sur les listes chaînées

  1. Définir les deux structures décrites ci-dessus pour le cas de listes de réels.
  2. Donnez le code nécessaire pour déclarer et initialiser une instance d'une liste.
  3. Quels sont les deux cas à prévoir lorsqu'on ajoute un élément à une liste ? Proposez une fonction réalisant l'ajout d'un élément à une liste.
  4. Définissez la fonction "pop", qui renvoie le premier élément de la liste et le supprime. Attention à la gestion de la mémoire.
  5. Donnez une fonction booléenne permettant de savoir si une valeur se trouve dans la liste.
  6. Quels sont les cas à prévoir pour supprimer un élément d'une liste ? Donnez l'agorithme permettant de réaliser cela

    7. Algorithmes supplémentaires

  7. On considère le cas où la liste est déjà triée. Donnez l'algorithme d'insertion d'un élément à la bonne place dans ce cas.
  8. Quel serait le code d'une fonction vérifiant si une liste est triée ?
  9. Donnez un algorithme permettant de concaténer deux listes chaînées.
  10. Écrire une fonction permettant d'obtenir, pour un flottant donné, la position de cet élément dans une liste ainsi que la valeur de son prédécesseur et de son successeur.
  11. Donnez un algorithme permettant de supprimer complètement une liste.
  12. On considère une liste non-nécessairement triée. Donnez un algorithme permettant de connaître le nombre d'occurrence d'une valeur dans une liste.
  13. Dans les mêmes conditions, donnez une fonction déterminant le maximum et une autre déterminant le minimum des éléments d'une listes.

    14. Correction : td1-2.c.

    Liste doublement chaînées

  14. Donnez les structures permettant de définir des listes doublement chaînées.
  15. Adaptez les algorithmes d'ajout de suppression d'un élément, de recherche booléenne et la fonction "pop" pour les listes doublement chaînées.