Première partie

Objectifs d'apprentissage

  • Expliquer le concept d’itérateur dans vos propres mots.
  • Résoudre des problèmes exigeant l’utilisation d’itérateurs.

Itérateurs

Pour ce laboratoire, vous utiliserez une liste chaînée afin de sauvegarder un nombre illimité de bits : des zéros et des uns. Contrairement aux implémentations vues jusqu’ici, les valeurs à l’intérieur des noeuds sont des entiers (int).

La classe BitList possède une classe interne. Il s'agit en fait d'une seconde définition de classe dite privé se trouvant dans le même fichier de définition de la classe public BitList. Cette classe interne (inner en anglais) est BitListIterator.

BitListIterator réalise l'interface Iterator qui oblige l'implémentation de 3 méthodes, soit hasNext, next et add.

Prenez le temps de bien comprendre le comportement de chacune des méthodes et leur implémentation.

BitList

Puisque plusieurs opérations sur les bits nécessitent un traitement de droite à gauche, l’implémentation doit sauvegarder les bits dans l’ordre «droite à gauche», c.-à-d. le bit le plus à droite dans le mot binaire sera en en première position dans la liste (premier noeud).

Par exemple, les bits «11010» doivent être sauvegardés dans une liste telle que le premier noeud contienne 0, le second 1, suivi d’un 0, puis 1, et 1 :

  • -> 0 -> 1 -> 0 -> 1 -> 1

1. Complétez l’implémentation de la classe BitList.

public BitList( String s ) 

Ce constructueur doit créer une liste représentant la chaîne de 0s et 1s donnée en entrée.

La chaîne s doit contenir que des 0s et des 1s sinon il faudra lancer l'exception IllegalArgumentException.

Le constructeur initialise cette nouvelle liste de bits afin de représenter la valeur de la chaîne. Chaque caractère de la chaîne représente un bit de la liste.

Par exemple, étant donné la chaîne «1010111», le constructeur doit initialiser cette liste afin d’y inclure les bits suivants (portez attention à l'ordre des bits encore une fois!).

  • -> 1 -> 1 -> 1 -> 0 -> 1 -> 0 -> 1

Si la chaîne est vide, le constructeur doit créer une liste vide — la valeur null n’est pas valide.

Le constructeur ne doit pas retirer les zéros de la partie gauche. Par exemple, étant donné «0001» le constructeur doit initialiser cette liste comme suit.

  • -> 1 -> 0 -> 0 -> 0

Utilisez la classe BitListTest pour tester votre implémentation.

 

Deuxième partie

Iterative

Créez une classe nommée Iterative. Implémentez les méthodes ci-bas dans cette classe. Vos solutions doivent être itératives (c.-à-d. utilise des itérateurs).

2.1 static BitList complement(BitList in)

Créez une méthode «static» itérative retournant une nouvelle liste de bits (BitList) qui soit le complément de celle en entrée. Le complément de 0 est 1 ; et vice-versa. Le complément d’une liste de bits est une nouvelle liste, de même longueur que l’entrée, telle que chaque bit est le complément du bit à la même position dans la liste d’entrée. Voici 4 exemples.

1011  
0100  

0  
1  

01  
10  

0000111  
1111000

2.2 static BitList or(BitList a, BitList b)

Vous devez écrire une méthode de classe retournant le ou («or») des deux listes passées en paramètre. Cette liste a la même longueur que les listes en entrée et chacun des bits de cette liste est le ou («or») des bits à cette position dans les listes en entrée. La méthode lance une exception, IllegalArgumentException, si l’une ou l’autre des deux listes est vide ou si les listes sont de longueur différente.

Lorsque l’on compare deux bits avec le ou, le résultat est 1 si au moins l’un des bit est un 1, 0 si les deux bits sont des 0.

a = 10001  
b = 00011  
a or b = 10011

2.3 et et ou exclusif

Créer les méthodes static BitList and(BitList a, BitList b) et static BitList xor(BitList a, BitList b). Ces méthodes sont similaire à la méthode or mais il implémente respectivement le et binaire ainsi que le ou exclusif (xor).

Avec le et binaire, le résultat d’une comparaison est 1 si les deux bits sont 1, sinon le resultat est 0.

a = 10001  
b = 00011  
a and b = 00001

Avec le ou exclusif binaire, le résultat d’une comparaison est 1 si et seulement si l’un des deux bits est 1. Donc si les deux bits sont 0 ou 1, le résultat sera 0.

a = 10001  
b = 00011  
a xor b = 10010

 

Troisième partie

Objectifs d'apprentissage

  • Concevoir et écrire une méthode itérative pour un arbre binaire de recherche.

Pour cette partie du laboratoire, vous devez utiliser la classe BinarySearchTree. La classe L11 contient des exemples qui vous aideront à mieux comprendre les questions.

Fichiers

Vous devez implémenter les méthodes qui suivent.

1. E max()

Retourne la plus grande valeur de cet arbre. Lance l’exception NoSuchElementException si l’arbre est vide.

Par exemple, si vous déclarez BinarySearchTree t, et ajoute un animal "Lion" à l'arbre

BinarySearchTree t;
t = new BinarySearchTree();
t.add( "Lion" );

et appelez t.max(), cela devrait retourner "Lion".

2. E min()

Retourne la plus petite valeur de cet arbre. Lance l’exception NoSuchElementException si l’arbre est vide.

Par exemple, si vous appelez t.min() sur la base de l'exemple ci-dessus, cela devrait retourner "Lion".

3. int depth()

Retourne la profondeur de l’arbre, c’est-à-dire la profondeur du noeud le plus profond.

Par exemple, si vous appelez t.depth() sur la base de l'exemple ci-dessus, cela devrait retourner 0.

4. boolean isTwoTree()

Un arbre binaire est un two-tree s’il est vide ou si tous ses noeuds internes ont deux fils.

Par exemple, si vous appelez t.isTwoTree() sur la base de l'exemple ci-dessus, cela devrait retourner true.



Comme mentionné précédemment, pour plus d'exemples, référez-vous au bloc de commentaires du code dans L11.

 

Quatrième partie

Quiz (1 point)

Pour cette question, nous utilisons l’itérateur de Java ListIterator. Cet itérateur possède une méthode add. En conséquence, l’itérateur peut ajouter des éléments à une liste.

import java.util.ListIterator; 
import java.util.LinkedList; 
 
public class Test { 
 
    public static void main( String[] args ) { 
 
        LinkedList a, b; 
 
        a = new LinkedList(); 
        b = new LinkedList(); 
 
        a.add("alpha"); 
        a.add("bravo"); 
        a.add("tango"); 
        a.add("charlie"); 
 
        ListIterator i, j; 
 
        i = a.listIterator(); 
        j = b.listIterator(); 
 
        while (i.hasNext()) { 
            j.add(i.next()); 
        } 
 
        System.out.println(a); 
        System.out.println(b); 
 
    } 
}

Quel résultat obtient-on lorsqu’on exécute le programme Java ci-haut ?

  1. charlie, tango, bravo, alpha
    charlie, tango, bravo, alpha
  2. alpha, bravo, tango, charlie
    alpha, bravo, tango, charlie
  3. charlie, tango, bravo, alpha
    alpha, bravo, tango, charlie
  4. alpha, bravo, tango, charlie charlie, tango, bravo, alpha
  5. Runs into an infinite loop

Inscrivez votre réponse à la question ci-dessus dans le champ Soumission : de la page de soumission du devoir (voir ci-dessous) ;

Table of Contents