Embed Size (px)
Citation preview
TD3 – Liste Ordonnées - Généricité 1ère partie : paquetage de listes d’entiers ordonnées
On convient de modéliser une collection d’entiers par une liste ordonnée (par ordre croissant). On utilise la relation d’ordre "<=" (plusieurs occurrences d’un même entier peuvent exister).
On souhaite réaliser un paquetage exportant les éléments suivants :
Un type Liste limité privé, Une fonction Est_Vide(L) qui renvoie TRUE si la liste L est vide, FALSE sinon, Un sous-programme Init(L) permettant de créer une liste L vide (avant toute insertion)
ou bien de la vider totalement (si elle contient déjà des éléments au moment de l'appel), Une fonction Appartient(E,L) qui vérifie l’appartenance d’au moins une occurrence d’un
entier E donné dans une liste donnée L, Un sous-programme Insérer(E,L) permettant d'insérer un entier E dans une liste
d’entiers L ; l’insertion est effectuée même si plusieurs occurrences du même entier sont déjà présentes ; la liste L doit rester ordonnée après insertion,
Un sous-programme Supprimer(E,L) permettant de supprimer la 1ère occurrence d’un entier E donné de la liste L,
Un sous-programme permettant d’Afficher une liste.
TD3 Question 1 : Ecrire la spécification de ce paquetage. fichier
liste_ordonnee_entiers.ads !
Déclaration du type Liste en limité privé
Spécification des sous-programmes
Définition détaillée du type Liste
Où sont les commentaires
de la spécification ?
TD3 Question 2 : Ecrire l’algorithme et le corps des sous-programmes suivants :
Le sous-programme d’insertion (version itérative) Le sous-programme de suppression (version récursive)
Le sous-programme d’insertion (version itérative) :
On veut insérer l’entier E dans la liste L :
Si L est vide alors : On insère E en première position (actualisation de L)
Sinon si E est inférieur ou égal à la première valeur de L alors : On insère E en première position (actualisation de L)
Sinon : On initialise un pointeur père à la première cellule de L On initialise un pointeur fils avec le suivant du père Tant que le fils n’est pas nul et puis que E est supérieur à la valeur du fils :
Le père prend la position du fils On actualise le fils avec le suivant du père
Fin de la boucle tant que On insère E entre le père et le fils
Fin du si
TD3 Question 2 : Ecrire l’algorithme et le corps des sous-programmes suivants :
Le sous-programme d’insertion (version itérative) Le sous-programme de suppression (version récursive)
Le sous-programme d’insertion (version itérative) :
On veut insérer l’entier E dans la liste L :
Si L est vide alors : On insère E en première position (actualisation de L)
Sinon si E est inférieur ou égal à la première valeur de L alors : On insère E en première position (actualisation de L)
Sinon : On initialise un pointeur père à la première cellule de L On initialise un pointeur fils avec le suivant du père Tant que le fils n’est pas nul et puis que E est supérieur à la valeur du fils :
Le père prend la position du fils On actualise le fils avec le suivant du père
Fin de la boucle tant que On insère E entre le père et le fils
Fin du si
EN
RÉCURSIF
TD3 Question 2 : Ecrire l’algorithme et le corps des sous-programmes
suivants :
Le sous-programme d’insertion (version itérative) Le sous-programme de suppression (version récursive)
Le sous-programme de suppression (version récursive) :
On veut supprimer l’entier E de la liste L :
Si L est vide alors On ne fait rien
Sinon si E est égal à la première valeur de L alors : On supprime cette première valeur et on actualise L
Sinon si E est plus grand que la première valeur de L alors : On demande la suppression de E dans le reste de la liste après L
[ Sinon cela veut dire que E est plus petit que la première valeur de L et donc que E n’est pas dans la liste. On n’a donc rien de plus à faire. ]
Fin du si
TD3 Question 2 : Ecrire l’algorithme et le corps des sous-programmes
suivants :
Le sous-programme d’insertion (version itérative) Le sous-programme de suppression (version récursive)
Le sous-programme de suppression (version récursive) :
On veut supprimer l’entier E de la liste L :
Si L est vide alors On ne fait rien
Sinon si E est égal à la première valeur de L alors : On supprime cette première valeur et on actualise L
Sinon si E est plus grand que la première valeur de L alors : On demande la suppression de E dans le reste de la liste après L
[ Sinon cela veut dire que E est plus petit que la première valeur de L et donc que E n’est pas dans la liste. On n’a donc rien de plus à faire. ]
Fin du si
TD3 2ème partie : paquetage générique
On veut désormais manipuler des collections d’objets quelconques, dès lors qu'il est possible de les lier par une relation ‘≤’.
Question 3 : Donner la spécification d’un paquetage générique « Listes_Ordonnees_G », dont les paramètres de généricité sont les suivants :
le type des objets contenus dans les listes
la fonction de comparaison entre deux objets : ‘<=’
la fonction d’égalité entre deux objets : ‘=’
la fonction de conversion d’un objet en chaîne de caractères
Ce paquetage doit également inclure un sous-programme générique de construction de sous-liste d’objets. Le paramètre de généricité sera une fonction booléenne (un critère de sélection) utilisé pour décider si un élément doit être retenu ou pas dans la sous-liste.
Par exemple, si on veut construire la sous-liste des éléments de L qui sont pairs, le critère sera une fonction booléenne pair(E) retournant TRUE si E est pair et FALSE sinon.
TD3Paramètres génériques de paquetage
Paramètres génériques de procédure
TD3 Question 4 : Ecrire un programme client qui instancie le paquetage
précédent pour gérer une liste d'activités.
Une activité est caractérisée par :
Un numéro,
Un type de ressource (M1, M2, M3, ou M4),
Une durée positive,
Un nombre entier d’unités de ressources requises.
Utiliser l’instance du paquetage créé pour :
Créer une liste vide L1,
Y insérer 4 activités,
Créer la sous-liste L2 des activités utilisant M1 et l’afficher,
Créer la sous-liste L3 des activités de durée inférieure à 10 et l’afficher,
Supprimer une à une chaque activité de L1 et afficher la liste vide
résultante.
TD3
Fonction "<="
Instanciation du paquetage
Type Activite
Fonction "="
Fonction Activite_To_String
TD3
…suite…
TD3…suite et fin.
