Structures de données en Java 2100069373, 9782100069378 [PDF]

Zitiervorschau

lims Hubbard

22/06/06

12:33

Page 1

STRUCTURES DE DONNÉES EN JAVA J. R. HUBBARD Professeur de mathématiques et d’informatique à l’université de Richmond (Virginie, USA)

Traduit de l’américain par Virginie Maréchal

lims Hubbard

22/06/06

12:33

Page 2

Ce pictogramme mérite une explication. Son objet est d’alerter le lecteur sur la menace que représente pour l’avenir de l’écrit, particulièrement dans le domaine de l’édition technique et universitaire, le développement massif du photocopillage. Le Code de la propriété intellectuelle du 1er juillet 1992 interdit en effet expressément la photocopie à usage collectif sans autorisation des ayants droit. Or, cette pratique s’est généralisée dans les

établissements d’enseignement supérieur, provoquant une baisse brutale des achats de livres et de revues, au point que la possibilité même pour les auteurs de créer des œuvres nouvelles et de les faire éditer correctement est aujourd’hui menacée. Nous rappelons donc que toute reproduction, partielle ou totale, de la présente publication est interdite sans autorisation du Centre français d’exploitation du droit de copie (CFC, 20 rue des GrandsAugustins, 75006 Paris).

Original edition copyright © 2001 by The McGraw-Hill Companies, Inc. All rights reserved. L’édition originale de cet ouvrage est parue sous le titre : Schaum’s Outline of Data Structures with Java.

© Dunod, Paris, 2003, pour l’édition française. Tous droits réservés. ISBN : 2-10-0006937-3

Toute représentation ou reproduction intégrale ou partielle faite sans le consentement de l’auteur ou de ses ayants droit ou ayants cause est illicite selon le Code de la propriété intellectuelle (Art L 122-4) et constitue une contrefaçon réprimée par le Code pénal. • Seules sont autorisées (Art L 122-5) les copies ou reproductions strictement réservées à l’usage privé du copiste et non destinées à une utilisation collective, ainsi que les analyses et courtes citations justifiées par le caractère critique, pédagogique ou d’information de l’œuvre à laquelle elles sont incorporées, sous réserve, toutefois, du respect des dispositions des articles L 122-10 à L 122-12 du même Code, relatives à la reproduction par reprographie.

Sommaire

Avant-propos Chapitre 1

IX Caractéristiques de base du langage java 1.1 Programmation orientée objet 1.2 Langage de programmation Java 1.3 Variables et objets 1.4 Types primitifs 1.5 Contrôle du flux 1.6 Classes 1.7 Modificateurs 1.8 Classe String 1.9 Classe Math Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 2

Caractéristiques de base des tableaux 2.1 Propriétés des tableaux 2.2 Copier un tableau 2.3 Classe Arrays 2.4 Algorithme de recherche séquentielle 2.5 Algorithme de recherche binaire 2.6 Classe Vector Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 3

Java avancé 3.1 3.2 3.3 3.4 3.5

Héritage Polymorphisme Conversion des types Classe Object Classes abstraites

1 1 1 2 3 5 7 9 10 13 16 17 18 20 25 25 27 28 31 33 35 38 39 39 44 57 57 58 60 62 64

IV

Chapitre 4

Structures de données en Java

3.6 Interfaces 3.7 Paquetages 3.8 Gérer les exceptions Questions de révision Réponses Exercices d’entraînement Solutions

67 70 70 72 72 73 74

Récursivité

77 78 79 80 82 83 83 84 85 85 87 88 89 89 92

4.1 La base et la partie récursive de la récursivité 4.2 Tracer un appel récursif 4.3 Algorithme récursif de recherche binaire 4.4 Coefficients binomiaux 4.5 Algorithme d’Euclide 4.6 Preuve inductive de correction 4.7 Analyse de la complexité des algorithmes récursifs 4.8 Programmation dynamique 4.9 Les tours de Hanoi 4.10 Récursivité mutuelle Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 5

Collections 5.1 Framework de collections Java 5.2 Interface Collection 5.3 Classe AbstractCollection 5.4 Classe Bag 5.5 Interface Iterator Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 6

Piles 6.1 Classe Java Stack 6.2 Applications des piles 6.3 Supprimer la récursivité Questions de révision Réponses Exercices d’entraînement Solutions

99 99 100 101 102 109 109 110 110 111 115 115 118 121 122 122 123 125

V

Sommaire

Chapitre 7

Files 7.1 Framework des files 7.2 Implémentation contiguë 7.3 Implémentation chaînée 7.4 Applications utilisant les files Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 8

Listes 8.1 Interface java.util.List 8.2 Implémenter l’interface java.util.List 8.3 Classes AbstractList et AbstractSequentialList 8.4 Itérateurs de listes 8.5 Classe ArrayList 8.6 Classe LinkedList 8.7 Itérateurs de listes indépendants Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 9

Arbres 9.1 Terminologie des arbres 9.2 Arbres décisionnels et diagrammes de transition 9.3 Arbres ordonnés 9.4 Algorithmes de parcours des arbres ordonnés Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 10

Arbres binaires 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 10.9

Terminologie Compter les arbres binaires Arbres binaires complets Identité, égalité et isomorphisme Arbres binaires parfaits Algorithmes de parcours des arbres binaires Arbres d’expression Classe BinaryTree Implémenter les algorithmes de parcours

129 129 132 134 136 142 142 142 144 149 149 151 151 153 154 155 164 165 165 166 167 171 172 174 177 178 180 181 183 183 187 187 188 189 190 192 194 196 198 203

VI

Chapitre 11

Structures de données en Java

10.10 Forêts Questions de révision Réponses Exercices d’entraînement Solutions

205 206 207 208 210

Arbres de recherche

217 217 219 222

11.1 11.2 11.3 11.4

Arbres de recherche multidirectionnels Arbres équilibrés ou arbres-B Arbres binaires de recherche Caractéristiques des arbres binaires de recherche en matière de performances 223 11.4 Arbres AVL 11.6 Classe AVLTree Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 12

Tas et files de priorité 12.1 Tas 12.2 Mappage naturel 12.3 Insérer des éléments dans un tas 12.4 Supprimer un élément d’un tas 12.5 Classe PriorityQueue 12.6 Interface Java Comparator 12.7 Implémentation directe Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 13

Algorithmes de tri 13.1 13.2 13.3 13.4 13.5 13.6 13.7 13.8 13.9 13.10 13.11

Méthode Java Arrays.sort() Tri par permutation Tri par sélection Tri par insertion Tri Shell Tri par fusion Tri par segmentation Tri vertical Rapidité des algorithmes de tri par comparaison Tri digital Tri panier

224 225 227 228 228 229

233 233 233 234 235 236 237 239 243 243 244 245 251 252 252 254 255 256 258 260 263 268 268 270

VII

Sommaire

Chapitre 14

Questions de révision Réponses Exercices d’entraînement Solutions

272 274 275 277

Tables

287 287 288 289 290 292 293 295 296 298 300 300 301 302

14.1 Interface Java Map 14.2 Classe HashMap 14.3 Codes de hachage Java 14.4 Tables de hachage 14.5 Performances des tables de hachage 14.6 Algorithmes de résolution des collisions 14.7 Chaînage séparé 14.8 Applications 14.9 Classe TreeMap Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 15

Ensembles 15.1 Ensembles mathématiques 15.2 Interface Java Set 15.3 Classe Java AbstractSet 15.4 Classe Java HashSet 15.5 Classe Java TreeSet Questions de révision Réponses Exercices d’entraînement Solutions

Chapitre 16

Graphes 16.1 16.2 16.3 16.4 16.5 16.6 16.7 16.8 16.9 16.10 16.11 16.12

Graphes simples Terminologie des graphes Chemins et cycles Graphes isomorphes Matrice d’adjacence d’un graphe Matrice d’incidence d’un graphe Liste d’adjacences d’un graphe Digraphes Chemins d’un digraphe Digraphes pondérés et graphes Chemins et cycles eulériens et hamiltoniens Algorithme de Dijkstra

305 305 306 306 307 309 311 311 311 312 313 313 313 314 316 318 319 319 320 321 322 323 324

VIII

Annexes

Index

Structures de données en Java

16.13 Algorithmes de parcours des graphes Questions de révision Réponses Exercices d’entraînement Solutions

328 332 332 333 338

A. Mathématiques de base

345

B. De C++ à Java

366

C. Environnements de développement Java

368 371

Avant-propos

Comme tous les livres de notions fondamentales proposés dans la série Schaum’s, celui-ci est en premier lieu destiné aux personnes qui souhaitent étudier seules, de préférence en complément d’un cours sur les structures de données. Il constitue également une excellente référence pour les programmeurs Java plus expérimentés. Cet ouvrage comprend plus de 260 exemples et exercices d’entraînement. L’auteur est convaincu que les principes des structures de données peuvent être acquis plus aisément grâce à un large éventail d’exemples bien structurés et accompagnés d’explications précises. Ce livre est conçu de façon à apporter cette aide au lecteur. Le code source des exemples et les exercices peuvent être téléchargés depuis le site web de l’auteur http://www.mathcs.richmond.edu/~hubbard/Books.html. Toutes les corrections et les addenda sont également disponibles sur ce site. Je souhaiterais remercier tous mes amis, collègues, étudiants dont les critiques constructives m’ont été d’une aide précieuse. Je tiens tout particulièrement à remercier ma femme, Anita Hubbard, pour ses conseils, ses encouragements et les exemples créatifs qu’elle a apportés à ce livre. La plupart des idées originales que vous y trouverez sont d’elle. JOHN R. HUBBARD Richmond, Virginie [email protected]

Chapitre 1

Caractéristiques de base du langage java Ce chapitre est consacré aux fonctionnalités de base du langage de programmation Java nécessaires à la conception et l’implémentation des structures de données.

1.1 PROGRAMMATION ORIENTÉE OBJET Java est un langage de programmation orienté objet parce qu’il présente les caractéristiques suivantes : • • • •

Chaque élément de donnée est encapsulé dans un objet. Chaque instruction exécutable est effectuée par un objet donné. Chaque objet est l’instanciation d’une classe ou est un tableau. Chaque classe est définie dans le cadre d’une hiérarchie d’héritage unique. La hiérarchie d’héritage unique de Java est une structure arborescente dont la racine est la classe

Object (reportez-vous à la section 3.4). Même si cette structure peut vous faire penser que Java est un

langage simple, ne vous fiez pas aux apparences car elle comprend les bibliothèques de classes Java 1.3 qui sont composées de 2 130 classes et de 23 901 membres. Ce sont ces caractéristiques orientées objet qui font de Java un langage particulièrement adapté à la conception et à l’implémentation des structures de données. L’architecture de ses collections (reportezvous au chapitre 4) offre une plate-forme idéale de construction des structures de données.

1.2 LANGAGE DE PROGRAMMATION JAVA Un programme Java est une collection d’un ou de plusieurs fichiers texte. Au moins l’un de ces fichiers contient une classe publique unique avec une méthode unique dont la signature est la suivante : public static void main(String[] args)

Chaque fichier du programme doit comprendre une classe ou bien une interface publique et est appelé X.java, X correspondant au nom de la classe ou de l’interface publique unique. Chaque fichier X.java est compilé dans un fichier classe appelé X.class. Le programme est ensuite lancé en exécutant le fichier X.class qui contient la méthode main(String[]) comprenant les instructions à exécuter.

2

Caractéristiques de base du langage java

Cette programmation peut être effectuée à partir de la ligne de commande ou bien d’un environnement IDE (reportez-vous à l’annexe C).

1.3 VARIABLES ET OBJETS Dans le cadre de tous les langages de programmation, l’accès aux données est effectué via les variables. Avec Java, une variable est soit une référence à un objet, soit l’un des huit types primitifs, comme illustré dans le diagramme. S’il s’agit d’une référence, sa valeur est null ou bien elle contient l’adresse d’un objet instancié. Chaque objet appartient à une classe unique qui définit les propriétés et les opérations de ses objets de la même manière qu’un type primitif définit les propriétés et les opérations de ses variables. Une variable est créée par une déclaration spécifiant son type et sa valeur initiale facultative. Un objet est créé par l’opérateur new qui appelle son constructeur de classe.

Types Java Types primitifs

boolean Types numériques Types entiers

byte short int long char Types à virgule flottante

float double Types de références type Tableau type Classe type Interface

Exemple 1.1 Créer des variables et des objets public class Ex0101 { public static void main(String[] args) { boolean flag=true; char ch=’B’; short m; int n=22; float x=3.14159F; double y; String str; String nada=null; String pays = new String("France"); System.out.println("flag = " + flag); System.out.println("ch = " + ch); System.out.println("n = " + n); System.out.println("x = " + x); System.out.println("nada = " + nada); System.out.println("pays = " + pays); } } flag = true ch = B n = 22 x = 3,14159 nada = null pays = France

Ce programme déclare neuf variables, puis il imprime les six qui ont été initialisées. Les six premières variables sont de type primitif et les trois dernières sont des références aux objets String. Il contient un seul objet qui est de type String et s’appelle pays (techniquement, pays est le nom de la variable faisant référence à l’objet String).

3

Types primitifs

La figure présentée contient les neuf variables et le seul objet. Chacune de ces variables a un nom et un type. Si le type est une classe, la variable est une référence à une instance (c’est-à-dire à un objet) de cette classe. Les variables non initialisées sont vides, tandis que les autres contiennent une valeur. Une variable de référence ne peut contenir qu’une seule valeur, c’est-à-dire la référence dessinée sous forme d’un point noir. Si cette référence n’est pas null, le point est composé d’une flèche pointant vers l’objet auquel il fait référence. En Java, un objet ne peut pas exister si une variable de référence ne pointe pas vers lui.

flag

true

ch

"B"

boolean

m

char

n

22

short

x

3.14159

int

y

float

str String

pays

double

nada String

"France"

String

1.4 TYPES PRIMITIFS Le langage Java définit les huit types primitifs suivants : • • • • • • • •

boolean false ou true

caractère Unicode 6 bits char, soit ’B’ ou ’π’ entier 8 bits byte : –128 à 127 entier 16 bits short : –32768 à 32767 entier 32 bits int : –2147483648 à 2147483647 entier 64 bits long : –9223372036854775808 à 9223372036854775807 nombre décimal à virgule flottante 32 bits float : (plus ou moins) 1.4E-45F à 3.4E38F nombre décimal à virgule flottante 64 bits double : (plus ou moins) 4.9E-324 à 1.8E308

Remarquez que les littéraux de type float doivent être précédés du suffixe F qui les différencie des valeurs de type double. Chaque littéral Unicode peut être exprimé sous la forme '\uxxxx', x correspondant à un chiffre hexadécimal. Par exemple, 'B' correspond à '\u0042' et 'π' à '\u03C0'. Outre leur valeur numérique, les variables à virgule flottante peuvent également contenir l’une des trois valeurs spéciales suivantes : NEGATIVE_INFINITY, POSITIVE_INFINITY et NaN (Not a Number, c’est-à-dire « n’est pas un nombre »). Ces valeurs spéciales sont obtenues à la suite de mauvaises opérations arithmétiques.

Exemple 1.2 Valeurs spéciales des types à virgule flottante public class Ex0102 { public static void main(String[] args) { double x=1E200; // x=10000...0 (1 suivi de 200 zéros) System.out.println("x = " + x); System.out.println("x*x = " + x*x); System.out.println("(x*x)/x = " + (x*x)/x); System.out.println("(x*x)/(x*x) = " + (x*x)/(x*x)); } } x = 1.0E200 x*x = Infinity (x*x)/x = Infinity (x*x)/(x*x) = NaN

4

Caractéristiques de base du langage java

La valeur de x*x est Infinity parce que (10200)(10200) == 10400, soit une valeur supérieure au maximum de 1.3(10308) pour le type double. D’un point de vue algébrique, (xx)/x = x, sauf lorsque x est fini. En effet, Infinity divisé par une valeur finie non négative sera toujours Infinity. En dernier lieu, la valeur Infinity divisée par Infinity ne produit pas de valeur finie, mais une valeur indéterminée sur le plan algébrique, d’où la valeur Java NaN. Pour chacun des huit types primitifs, Java définit une classe enveloppe qui fournit les services orientés objets nécessaires à la manipulation des types primitifs. Par exemple, la classe enveloppe du type double est Double, et celle du type int est Integer.

Exemple 1.3 Utiliser une classe enveloppe public class Ex0103 { public static void main(String[] args) { String s = "2.7182818284590"; System.out.println("s = " + s); Double x = new Double(s); System.out.println("x = " + x); double y = x.doubleValue(); System.out.println("y = " + y); s += 45; System.out.println("s = " + s); y += 45; System.out.println("y = " + y); int n = x.intValue(); System.out.println("n = " + n); n = Integer.parseInt("3A9",16); System.out.println("n = " + n); } } s x y s y n n

= = = = = = =

2.7182818284590 2.718281828459 2.718281828459 2.718281828459045 47.718281828459 2 937

Le constructeur Double(s) crée l’objet x de type Double à partir de l’objet s de type String et il stocke la valeur numérique 2.7182818284590 dans l’objet x. La deuxième instruction println() appelle implicitement la méthode Double.toString() qui reconvertit cette valeur numérique en chaîne à imprimer. L’appel x.doubleValue() renvoie la valeur numérique stockée affectée à y. L’opérateur += est ensuite appliqué à l’objet s de type String et à la variable y de type double, créant ainsi des résultats complètement différents. Dans le cas des chaînes, += signifie « insérer » alors qu’il signifie « additionner » lorsqu’il s’agit de numéros. Puis, la méthode Double.intValue() tronque la valeur numérique stockée de l’entier 2 et l’utilise pour initialiser n. En dernier lieu, Integer.parseInt("3A9",16) renvoie la valeur int (au format décimal) pour l’entier dont la représentation hexadécimale est 3A9, soit 3(162) + 10(16) + 9 = 937. Remarquez que l’opérateur + convertit automatiquement le nombre y en son équivalent de type chaîne lorsqu’il est combiné à une chaîne, comme c’est le cas pour l’appel System.out .println("y = " + y).

Contrôle du flux

5

1.5 CONTRÔLE DU FLUX Le langage Java supporte les instructions if, if..else et switch, ainsi que l’opérateur d’expression conditionnelle ?..:.

Exemple 1.4 Utiliser les instructions conditionnelles Le programme suivant génère des entiers aléatoires dans un intervalle de 0 à 99, puis il utilise les instructions conditionnelles afin de les classer : public class Ex0104 { public static void main(String[] args) { int n = (int)Math.round(100*Math.random()); System.out.println("n = " + n); if (n>25 && n0 ? " est impair" : " est pair")); } } n = 19 19 n’est pas compris entre 25 et 75 19 < 20 19 < 40 19 < 60 19 est impair

Remarquez que l’absence d’instruction break entre case 0 et case 1 permet au contrôle de traverser chacun de ces cas jusqu’à la case 2 et d’exécuter les trois instructions println(). L’expression (n%2>0 ? " est impair" : " est pair") est évaluée à la chaîne " est impair" si la condition n%2>0 est vraie (c’est-à-dire si n n’est pas divisible par 2). Dans le cas contraire, elle est évaluée à la chaîne " est pair" (lorsque n est divisible par 2). Java supporte les instructions while, do..while et for.

Exemple 1.5 Utiliser les boucles Le programme teste empiriquement le théorème des nombres premiers de Gauss : si p(n) est le nombre de nombres premiers inférieurs à n, le rapport p(n)(ln n)/n se rapproche de 1.0 lorsque n devient illimité. Il compte le nombre p(n) de nombres premiers pour chaque n impair situé dans l’intervalle 3 à 1 000 000. Au fur et à mesure de l’augmentation de p(n), chaque fois qu’un multiple de 5 000 est passé, le programme imprime les valeurs de n, p(n), lnn (le logarithme naturel) et le rapport p(n)(ln n)/n, soit un nombre proche de 1.0. public class Ex0105 { public static void main(String[] args) { System.out.println("n\tp(n)\tln(n)\t\t\tp(n)*ln(n)/n"); final String DASHES18="\t------------------"; System.out.println("------\t-----" + DASHES18 + DASHES18);

6

Caractéristiques de base du langage java

int p=1; // p = nombre de nombres premiers qui sont