TP11 .pdf


Nom original: TP11.pdf

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.12, et a été envoyé sur fichier-pdf.fr le 03/05/2013 à 18:20, depuis l'adresse IP 91.176.x.x. La présente page de téléchargement du fichier a été vue 944 fois.
Taille du document: 175 Ko (3 pages).
Confidentialité: fichier public


Aperçu du document


Programmation & Algorithmique 2
TP - Séance 11
er
1 mars 2013

Matière visée : Accès aléatoire, JList, JUnit, clonage d'objets et structures de données.

1

Somme de carrés parfaits

1.1 A chage des éléments
Reprennez votre chier binaire contenant les 1000 premiers carrés parfaits (TP - séance 8).
Pour cet exercice, nous vous demandons d'utiliser le composant JList pour a cher tous les
éléments du chier. Etant donné qu'il y a un grand nombre d'éléments à a cher, veuillez utiliser
JScrollPane.
La source des données n'étant ni un vecteur, ni un tableau d'Object, nous vous demandons de créer
votre propre modèle (implémentant ListModel) qui lira les données directement dans votre chier en
accès aléatoire (RandomAccessFile).

1.2 Somme des éléments sélectionnés
Complétez votre programme en ajoutant un bouton SUM. Losque ce bouton est pressé, la somme
des éléments séléctionnés dans la JList doit être a chée.

1.3 Analyse des interactions JList-Model
Ajoutez des instructions aux méthodes de votre modèle a n qu'il vous informe quand les méthodes
sont appelée lorsque vous manipulez le JList de votre interface graphique (impression en console su t).
Tentez de tirer des conclusions conernant la manière dont JList utilise votre modèle pour a cher les
informations.

2

Arbres binaires de recherche

2.1 Dé nitions
Un arbre binaire T peut être dé ni récursivement comme suit :
Cas de base : une feuille (Les références vers le ls droite et vers le ls gauche sont null)
Cas généraux :

Avec Tlef t et Tright deux arbres binaires.
1

Exemple d'arbre binaire (d'entiers) :

Un arbre binaire de recherche est un arbre binaire tel que pour tout n÷ud T de l'arbre :
tous les n÷uds du sous-arbre gauche (Tlef t ) ont une valeur < Tdata ; et
tous les n÷uds du sous-arbre droit (Tright ) ont une valeur > Tdata .
Exemple d'arbre binaire de recherche (d'entiers) :

2.2 Classe ABRNode
Ecrivez une classe ABRNode. Un objet de cette classe représente un n÷ud d'un arbre binaire d'entiers. Implémentez-y les di érents accesseurs. Un arbre binaire de recherche sera en fait un pointeur
vers sa racine (qui est l'ABRNode au sommet de l'arbre).

2.3 Clonage d'arbres
Surchargez la méthode Object clone() de la classe Object a n de pouvoir cloner les arbres.
N'oubliez pas le clonage en profondeur !

2.4 Egalité
Récursivement, deux arbres binaires de recherche sont égaux si et seulement si les données des
deux racines sont égales et les deux sous-arbres respectifs sont égaux.
Ajoutez dans votre classe ABRNode une méthode récursive boolean estEgal(ABRNode abr) qui
permet de tester l'égalité de deux arbres binaires de recherche.
Utilisez JUnit pour tester votre méthode. Construisez "à la main" l'arbre donné en exemple et
clonez-le. Créez également "à la main" un deuxième arbre di érent du premier. Votre test consistera
en l'égalité du premier arbre et de son clone (doit retourner true) et en l'égalité du premier et du
second arbre (doit retourner false).

2.5 Insertion d'une donnée
Ajoutez dans votre classe ABRNode une méthode récursive void insere(int data) qui permet
d'insérer un n÷ud contenant la valeur data dans l'arbre.

2

Si une variable myTree référence l'arbre binaire de recherche donné en exemple, myTree.insere(6)
doit modi er l'arbre a n d'obtenir :

Avant d'implémenter, ré échissez à la manière dont l'algorithme va procéder. Notez que le nouvel
arbre doit toujours respecter la propriété d'arbre binaire de recherche.
Utilisez JUnit pour tester votre méthode. Reproduisez l'arbre donné en exemple en utilisant votre
méthode insere (attention que l'ordre dans lequel vous insérez les éléments a de l'importance, vous
voyez pourquoi ?). Le test consitera à tester l'égalité de cet arbre avec le premier arbre créé au point
précédent.

2.6 Recherche d'une donnée
Ajoutez dans votre classe ABRNode une méthode récursive boolean recherche(int data) qui retourne true si l'entier data est contenu dans l'arbre, false sinon.
Utilisez JUnit pour tester votre méthode. Vos tests consisteront à véri er la présence (et l'absence)
des éléments de votre choix dans l'un des arbres créés précédemment.

2.7 A chage des données
Ajoutez dans votre classe ABRNode une méthode récursive void affichage() qui a che en console
les valeurs contenues dans l'arbre par ordre croissant.
Testez votre méthode sur l'arbre créé au point précédent.

2.8 A chage des données d'un intervalle donné
Ajoutez dans votre classe ABRNode une méthode récursive void affichage(int bi, int bs) qui
a che en console les valeurs contenues dans l'arbre et dans l'interalle [bi, bs] par ordre croissant. Il
vous est demandé de ne pas parcourir des n÷ud "inutiles".
Testez votre méthode sur l'arbre créé précédement.

3


Aperçu du document TP11.pdf - page 1/3

Aperçu du document TP11.pdf - page 2/3

Aperçu du document TP11.pdf - page 3/3




Télécharger le fichier (PDF)


TP11.pdf (PDF, 175 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


tp11
c
0ydl2ey
tm3
poly algo
cours2