TD — Séance 1 — ADT et interfaces Java

Listes, piles, files et deques : un contrat, plusieurs réalisations

TD de la séance 1 de Structures de données et algorithmes avancés : listes, piles, files et deques : un contrat, plusieurs réalisations.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Appliquer à la main, sur des données nouvelles, les mécanismes de la séance : contrat et implémentation, liste sur tableau et liste chaînée, parenthésage et notation postfixe, file circulaire et deque, coût amorti du doublement. Chaque réponse se donne sous la forme demandée (tableau, chaîne, trace, valeur) et se justifie en une ou deux phrases.

Conventions. Les classes sont celles du cours. ListeTableau double sa capacité quand elle est pleine, en recopiant ses éléments (une copie par élément), et ajouter(i, x) décale d’une case les éléments des rangs \(i\) et suivants (un décalage par élément déplacé) ; supprimer(i) décale les éléments qui suivent le rang \(i\). ListeChainee garde tete et queue : en tête et en fin, aucun parcours ; ailleurs, atteindre le nœud de rang \(i-1\) suit \(i-1\) références, et get(i) en suit \(i\). FileCirculaire et ArrayDeque écrivent en fin dans la case \((\texttt{tete}+\texttt{taille}) \bmod m\), reculent la tête par \((\texttt{tete}-1+m) \bmod m\) et s’agrandissent dans l’ordre logique. Les numéros de ligne de estEquilibree sont ceux du cours : rejet ligne 7 (fermante sur une pile vide), ligne 9 (fermante qui ne correspond pas), ligne 12 (pile non vide à la fin). Dans un tableau, . note une case vide.

Exercice 1 : contrat ou implémentation, et choix de l’ADT

  1. Pour chaque affirmation, cocher la colonne qui convient, et justifier les cas 4 et 6 en une phrase.

    affirmation contrat implémentation
    1 push(x) suivi de pop() rend x.
    2 Le sommet d’une PileTableau est la case \(\texttt{taille}-1\).
    3 peek() sur une file vide lève NoSuchElementException.
    4 Une ListeChainee garde une référence vers son dernier nœud.
    5 Après enqueue(a) puis enqueue(b) sur une file vide, dequeue() rend a.
    6 Le tableau d’une FileCirculaire est agrandi dans l’ordre logique.
    7 get(i) lève IndexOutOfBoundsException si \(i\geq\texttt{taille()}\).
    8 removeFirst() d’un ArrayDeque ne déplace aucun élément.

  2. Nommer l’ADT (List, Stack, Queue ou Deque) qui convient à chaque besoin, et l’opération la plus fréquente.

    1. Le bouton « retour » d’une application mobile, qui revient à l’écran précédent.
    2. Les SMS d’un lot, envoyés dans l’ordre de leur dépôt.
    3. Le classement des étudiants d’une promotion, consulté par rang.
    4. Les dix dernières mesures d’une station météo de Guédiawaye : on ajoute la plus récente, on retire la plus ancienne, on lit les deux bouts.
    5. L’historique des opérations d’un traitement de texte, pour annuler la dernière.

  3. Pour le besoin 2, une liste sur tableau dont dequeue appelle supprimer(0) respecte-t-elle le contrat ? Combien de décalages coûte l’envoi d’un lot de \(n\) SMS ?

Exercice 2 : une liste sur tableau

Une ListeTableau<Integer> est créée avec une capacité de 3. Elle reçoit, dans cet ordre, les opérations du tableau.

  1. Compléter le tableau : les cases de donnees après chaque opération (laisser vides les cases qui n’existent pas encore), taille, et le nombre de décalages et de copies de l’opération.
  2. Donner les totaux, la capacité finale, la valeur rendue par chaque supprimer et celle de get(2) à la fin.
  3. On part d’une ListeTableau vide de capacité 3, et l’on fait 100 ajouts en fin. Combien d’agrandissements, combien de copies, quelle capacité finale ? Comparer les copies à \(2n\).
opération 0 1 2 3 4 5 6 7 taille décalages copies
ajouter(26)
ajouter(0, 73)
ajouter(1, 45)
ajouter(0, 19)
ajouter(4, 88)
ajouter(2, 61)
supprimer(1)
supprimer(3)

Exercice 3 : une liste chaînée

Une ListeChainee<String> vide reçoit, dans cet ordre, les opérations du tableau.

  1. Compléter le tableau : la chaîne de la tête à la queue après chaque opération, le nombre de références suivies et la valeur rendue.
  2. Dessiner la chaîne après ajouter(2, "Binta"), avec tete, queue, les références et null, et entourer les deux références écrites par cette insertion.
  3. Pour une liste de \(n\) éléments, combien de références suit supprimer(n - 1) ? Pourquoi queue ne permet-elle pas de l’éviter ?
  4. Dans ajouter(i, x), un étudiant écrit prec.suivant = new Noeud<>(x, null);. Décrire la chaîne après ajouter(2, "Binta") avec cette erreur, à partir de l’état de la quatrième ligne, et ce que vaut alors taille.
opération chaîne (tête \(\rightarrow\) queue) références rend
ajouter("Fama")
ajouter(0, "Nafi")
ajouter(1, "Bamba")
ajouter("Coura")
ajouter(2, "Binta")
supprimer(3)
supprimer(0)
get(2)

Exercice 4 : parenthésage et notation postfixe

  1. Dérouler estEquilibree sur [3*(4+2)]-{5} puis sur {(8-[2*3)]} : pour chaque symbole ouvrant ou fermant, son indice dans la chaîne (à partir de 0), l’action et la pile après (de la base au sommet). Arrêter la trace au rejet.
  2. Compléter le tableau des verdicts pour les quatre expressions.
[3*(4+2)]-{5}
indice caractère action pile après
{(8-[2*3)]}
indice caractère action pile après
expression verdict ligne du rejet hauteur maximale
[3*(4+2)]-{5}
{(8-[2*3)]}
(7+(2*4)
4*2)+(1

Dans une boutique de Pikine, un client achète 3 sachets de lait à 800 FCFA et la moitié d’un pack de jus à 1 500 FCFA, et présente un bon de réduction de 250 FCFA : 800 3 * 1500 2 / + 250 -.

  1. Compléter la pile après chaque jeton (le sommet en haut), puis donner le résultat et la hauteur maximale de la pile.
  2. Quel résultat donne l’évaluateur dont les deux dépilements sont échangés ? Quels opérateurs de l’expression rendent l’erreur visible ?
  3. Écrire en notation postfixe \((1\,200-300)\times(4+2)\), puis l’évaluer.
  4. Que fait la méthode evaluer du cours sur 500 2 3 +, puis sur 500 + ? Indiquer le test qui échoue.
jeton 800 3 * 1500 2 / + 250 -
pile

Exercice 5 : deque, file circulaire et modulo

  1. Un ArrayDeque<Integer> de capacité 8, vide (tete \(=0\)), reçoit les opérations du tableau. Compléter la case écrite ou libérée, tete, taille et la valeur rendue. Donner l’état final des huit cases.
  2. Une FileCirculaire<Integer> de capacité 5 est pleine : tete \(=3\), et les tickets 71 à 75 sont entrés dans cet ordre. Donner ses cinq cases. Après enqueue(76), donner les cases, tete, taille et le nombre de copies, puis le ticket rendu par le dequeue() suivant.
  3. Donner la valeur de chaque expression Java du second tableau.
opération case tete taille rend
addFirst(5)
addFirst(6)
addLast(7)
removeFirst()
addLast(8)
addFirst(9)
removeLast()
removeLast()
expression valeur
(2 - 1) % 5
(0 - 1) % 5
(0 - 1 + 5) % 5
(4 + 1) % 5
-6 % 5
Math.floorMod(-6, 5)

Exercice 6 : le coût amorti, en détail

  1. Un tableau de capacité initiale 1 double quand il est plein. Calculer les copies faites par \(n\) ajouts en fin pour \(n=9\), 65 et 513. Montrer que, pour tout \(n\geq2\), les copies valent au plus \(2n-3\), avec égalité quand \(n-1\) est une puissance de 2.
  2. Un tableau qui rétrécit rend la mémoire inutile. Première règle : il double quand il est plein, et se réduit de moitié dès qu’il est à moitié plein après un supprimer (copie des éléments restants). Partant de 8 éléments dans 8 cases, il reçoit ajouter, supprimer, ajouter, supprimer, ajouter, supprimer. Donner après chaque opération le nombre d’éléments, la capacité et le total des copies. Refaire avec la seconde règle : réduction de moitié quand le tableau n’est plus rempli qu’au quart. Laquelle garde un coût amorti constant ? Pourquoi ?
opération ajouter supprimer ajouter supprimer ajouter supprimer
moitié : éléments / capacité / copies
quart : éléments / capacité / copies
  1. Avec un facteur 3 au lieu de 2 (capacité initiale 1), calculer les copies pour \(n=100\) et \(n=1\,000\), et majorer les copies par ajout. Quel est l’inconvénient d’un facteur plus grand ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet