Cours sur les structures de données dynamiques

Sujets

• informatique

Informations

• Publié par: Vowyong
• Nombre de lectures: 56
• Langue: Français

Extrait

-1- -2-
Objectifs
INF 421 Luc Maranget
◮ Structures de donn´ees ( dynamiques ).
⊲ Listes, tables de hachage, arbres...
⊲ Et leurs algorithmes traditionnels, (recherches par exemple).
R´evisions : valeurs,
◮ Perfectionnement en programmation.
⊲ Programmer c’est comprendre (vraiment).
variables, ..., Listes
⊲ Programmation des structures de donn´ees r´ecursives.
⊲ Choix des structures de donn´ees, (exemples ( realistes ))
[e-mail]
http://www.enseignement.polytechnique.fr/profs/
informatique/Luc.Maranget/421/
-3- -4-
Organisation du cours Quelques ´el´ements de Java
◮ 9 blocs, soit 9 vendredis. ◮ Qu’est-ce au juste qu’une valeur ?
⊲ Le matin, amphi, de 10h30 a` 12h00. ⊲ Scalaires
⊲ L’apr`es-midi, TP. ⊲ Objets
´
◮ Evaluation. ◮ Qu’est-ce au juste qu’une variable ?
⊲ TP not´e, — le cinqui`eme, 9 Dec, non le 7 Dec. ⊲ Cr´eation et initialisation.
⊲ Controlˆ e classant, a` la fin, 25 Jan. ⊲ Appel de m´ethode
⊲ Note de module : ⊲ Port´ee
3∗CC +max(CC,HC−k)
◮ Allocation dynamique
→ lettre
4
⊲ Les tableaux.
⊲ Les paires.
⊲ Les listes.-5- -6-
Les valeurs D´eclaration: avec et sans initialisation
int x = 1 ;
◮ Les scalaires.
⊲ Les bool´eens : boolean (true et false).
◮ ( int x )) est la d´eclaration : une variable (qui contient
8
⊲ Les entiers : byte (modulo 2 ), char et short (modulo
un int) est cr´e´ee.
16 32 64
2 ), int (modulo 2 ), long (modulo 2 ).
◮ ( = 1 )) est l’initialisation : la valeur initiale de la variable
⊲ Les flottants : float (simple pr´ecision), double (double
est 1.
pr´ecision).
Ne pas confondre d´eclaration avec initialisation et affectation.
◮ Les objets : tout le reste ! Les objets appartiennent a` des
Mˆeme si la syntaxe est tr`es semblable.
classes qui sont plus ou moins leur type.
int x = 1 ; // Cr´eation avec initialisation.
⊲ Les un peu sp´eciaux : String, les tableaux...
x = 2 ; // Changer le contenu
⊲ Les objets de classses de la librairie : par ex. System.out
int y ; // Cre´ation tout court
de la classe PrintStreamWriter.
Remarque : Quelle est la valeur initiale de la variable y ?
⊲ Ceux que l’on fait soi-mˆeme (en d´efinissant leur classe et
On ne peut pas le savoir !
par new).
-7- -8-
Variables locales Les variables sont ( des cases )
Les variables locales sont : Deux d´eclarations de variable.
int x=1, y ;
◮ D´eclar´ees dans le corps des m´ethodes,
1 ?
x y
◮ Ou bien ce sont les param`etres des m´ethodes.
Une affectation.
Le compilateur v´erifie ( l’initialisation ) des variables locales.
y = x ;
class T {
1 1
x y
static int f(int x) {
int y ;
On remarque que :
if (x != 0) y = 1 ;
return x + y ;
`
◮ A gauche du =, une variable→ une case.
}
`
} ◮ A droite du =, une variable→ le contenu d’une case.
# javac T.java
T.java:5: variable y might not have been initialized-9- -10-
Appel de m´ethode Avec des boites
static int f(int x) {
Le principe est le suivant :
x = x + 2 ;
◮ Chaque appel de methode cr´ee ses propres variables.
return x ;
}
◮ Les variables sont initialis´es par l’appel.
static int f(int x) { Au d´ebut de l’appel de m´ethode :
x = x + 2 ;
return x ; 2 2
x(de m) x(de f)
}
Juste avant le return :
public static void main (String [] arg) {
int x = 2 ;
2 4
x(de m) x(de f)
int r = f(x) ;
System.out.println("f(" + x + ") = " + r) ;
}
R´esultat : f(2) = 4
-11- -12-
Port´ee Exemple de port´ee I
La port´ee d’une variable est la zone du code ou` on peut l’utiliser, Que penser de :
autrement dit, la zone de visibilit´e.
static int f() {
for (int i = 0 ; i < 10 ; i++) { ... }
Dans l’exemple pr´ec´edent, les port´ees des deux variables x ´etaient
return i ;
clairement limit´ees aux corps des m´ethodes main et f.
}
La port´ee est structur´ee selon les blocs, en gros d´elimit´es par {...}.
Ce code est incorrect, car dans l’instruction return i, la variable i
Quelques r`egles importantes :
ne fait r´ef´erence a` aucune d´eclaration visible.
◮ La port´ee s’´etend de la d´eclaration de la variable a` la fin du
Note : On peu consid´erer que la boucle for est plus ou moins
bloc de d´eclaration.
´equivalente a` :
◮ Dans un mˆeme bloc, il ne peut pas y avoir deux variables de { int i = 0 ; // NB. un bloc est ouvert
while (i < 10) { ...
mˆeme nom.
i++ ;
◮ L’usage d’une variable fait r´ef´erence a` la d´eclaration la plus
}
}
proche vers le haut du programme (liaison lexicale).-13- -14-
Port´ee, II Un tableau avec les boites
Que se passe-t-il si on appelle f(4) ? Un tableau de taille n est (plus ou moins) une grosse case compos´ee
de n cases (( normales ).
static int f(int x) {
{ int xx = 2 ;
int [] t = new int[6] ;
System.out.print("x = " + x) ;
}
Mais la valeur du tableau est une fl`eche (r´ef´erence, pointeur,
System.out.println(", x = " + x) ;
adresse) vers la grosse case.
}
t
Ce programme est correct. Il affiche :
x = 2, xx = 4
0 0 0 0 0 0
Il y a en fait deux variables, x et x.
On peut tr`es bien changer x (ou x) en y, sans rien changer au fond.
Note : Les cases du tableau sont initialis´es par d´efaut.
Les variables (locales) sont un peu comme les variables muettes des
math´ematiques.
-15- -16-
Valeur par d´efaut La deuxi`eme dimension
Les cases des tableaux ont une valeur par d´efaut. Une matrice a` 3 lignes et 2 colonnes.
int [] [] t = new int [3][2] ;
◮ Scalaires : une esp`ece de z´ero.
⊲ boolean : c’est... false.
Est en fait un tableau de trois tableaux de deux entiers.
⊲ Autres scalaires : c’est bien z´ero.
t
◮ Objets : null.
Notons que null est un objet un peu sp´ecial. Il appartient a` toutes
les classes, mais on ne peut rien faire avec, sauf :
◮ L’affecter, par ex. String s = null
0 0 0
◮ Le comparer, par ex. if (s != null)...
0 0 0-17- -18-
Et null dans tout c¸a ? Les tableaux sont allou´es ( dynamiquement )
Logiquement, les tableaux sont initialis´es par d´efaut a` null. Cela veut dire que leur place est calcul´ee/allou´ee lors de l’ex´ecution.
int [] t // = null ;
static int [] f(int n, int x0) {
int [] r = new int [n] ;
La valeur null remplace une fl`eche, mais ne pointe nulle part. for (int i = 0 ; i < n ; i++) { r[i] = x0 ; }
return r ;
t
}
L’initialisation par d´efaut vaut aussi pour les cases de tableau.
En outre, l’allocation est effectu´ee dans le ( tas )).
int [][] t = new int[3][] ; // tableau de tableaux
◮ Le tableau existe encore apr`es le retour de la m´ethode f
Soit : un tableau de trois null.
(contrairement a` la variable r).
◮ Il n’y a pas lieu de lib´erer explicitement la place occup´ee
t
lorsque le tableau devient inutile (GC).
-19- -20-
Les valeurs des tableaux sont des fl`eches `
A comparer avec
int [] t = {1, 2, 3, 4, 5, 6} ; // Initialisation explicite
La copie du contenu de variables de type scalaire.
int [] r = t ;
int x = 3, y = x ;
Dans r = t c’est la fl`eche qui est copi´ee.
3 3
x y
t
x = 0 ; System.out.println(y) ; // Affiche ’3’
1 2 3 4 5 6
r
0 3
x y
De sorte que ici t[2] et r[2] d´esignent la mˆeme case (la troisi`eme).
Car ici x et y sont deux cases diff´erentes.
t[2] = 0 ; // ranger 0 dans la case d´esigne´e
System.out.println(r[2]) ; // Affiche ’0’-21- -22-
Appel de m´ethode ´
Egalit´e (( physique ))
Les valeurs sont bien copi´ees, mais ce sont des fl`eches.
L’´egalit´e == est l’´egalit´e des valeurs.
static void f(int [] r) { r[0] = 0 ; }
◮ Pour les scalaires aucun probl`eme !
◮ Pour les objets, attention ! Les valeurs sont les fl`eches.
1 2
t
int [] t = {1, 2, 3} , r = {1, 2, 3} ; // Deux variables.
int [] u = t ;
int [] t = { 1, 2 } ;
System.out.println((t == r) + ", " + (t == u)) ;
System.out.println(t[0]) ; // Affiche ’1’
f(t) ;
Le r´esultat est false, true, car
System.out.println(t[0]) ; // Affiche ’0’
1 2 3
t u
0 2
t r
1 2 3
r
-23- -24-
´ Les chaˆınes sont des objets...
Egalit´e (( structurelle ))
Mais des objets un peu particuliers.
Pour savoir si deux tableaux sont identiques (et non plus
exactement le mˆeme). On utilise o .equals(o ). class Coucou {
1 2
public static void main(String [] arg) {
int [] t = {1, 2, 3} ;
System.out.println("coucou" == "coucou") ;
boolean b = t.equals(new int [] {1, 2, 3}) // tableau ( anonyme )
System.out.println(arg[0] == arg[1]) ;
System.out.println(b) ;
}
}
Affiche true.
La commande ( java Coucou coucou coucou )) affichera :
R´esum´e :
true
◮ L’´egalit´e physique == expose l’impl´ementation.