Université des Sciences et Technologies de Lille
Licence Miage - Programmation 1 - TD


Les listes chaînées


Dans tous les exercices, on dispose d'un type Liste défini par

   type Cellule;
   type Liste is access Cellule;
   type Cellule is record
      Valeur:Element;
      Suivant:Liste;
   end record;
Element est un type quelconque.



Exercice 1   Écrire une procédure Inverser qui inverse une liste : les éléments de tête deviennent les éléments de queue.


Exercice 2   Soit R, un prédicat unaire sur le type Element: R est une fonction qui prend en argument un Element et retourne un booléen.

· Écrire une fonction Selection acceptant comme paramètre générique R: Selection prend en argument une liste et construit une nouvelle liste ne contenant que les éléments satisfaisant R.

·Écrire une procédure Selectionner, qui élimine d'une liste tous les éléments qui ne satisfont par R. Bien sûr, cette procédure doit s'exécuter avec un espace mémoire constant.


Exercice 3   On suppose que le type Element est muni d'une relation d'ordre < . Programmer le tri par insertion avec recherche séquentielle sur la structure de liste chaînée.


Exercice 4   Les matrices creuses sont des matrices d'entiers comprenant une majorité de 0 .
æ
ç
ç
ç
è
0 2 0 0 0
1 0 3 0 0
0 0 0 0 0
0 0 0 6 0
ö
÷
÷
÷
ø
Par souci d'économie, on peut représenter une matrice creuse par une liste chaînée, contenant uniquement les éléments non nuls, avec leurs indices.
[ (2,(1,2)); (1,(2,1)); (3,(2,3)); (6,(4,4)); (0, (4,5))]
Les éléments sont rangés par indice croissant (ligne, puis colonne). Pour connaitre la dimension de la matrice, l'élément d'indice maximal est précisé dans la liste chainée, meme si celui-ci est nul.

· On définit un type composé Indice , avec deux champs: ligne, colonne:Positive . Écrire une fonction < qui compare deux indices.

· Écrire un type matrice_creuse .

· Écrire une fonction qui fait la somme de deux matrices creuses.


Exercice 5   Lors du TP La laverie automatique, vous avez conçu un paquetage paq_file, avec les primitives Enfiler et Defiler. La procédure Defiler s'exécute en temps constant, mais la procédure Enfiler est en temps linéaire: il faut parcourir la liste pour atteindre le dernier élément. Comment pourrait-on améliorer la structure de données pour obtenir une opération d'enfilage en temps constant ? Réécrivez la procédure Enfiler.