Cours sur les structures de données dynamiques
19 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Cours sur les structures de données dynamiques

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
19 pages
Français

Description

-1- -2-ObjectifsINF 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 ))Luc.Maranget@inria.frhttp://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´ee3∗CC +max(CC,HC−k)◮ Allocation dynamique→ lettre4⊲ Les tableaux.⊲ Les paires.⊲ Les listes.-5- -6-Les valeurs D´eclaration: avec et sans initialisationint x = 1 ;◮ Les scalaires.⊲ Les bool´eens : boolean (true et false).◮ ( int x )) est la d´eclaration : une variable (qui contient8⊲ Les entiers : byte (modulo 2 ), char et short (moduloun int) est cr´e´ee.16 32 642 ), int (modulo 2 ), long (modulo 2 ).◮ ( = 1 )) est l’initialisation : la valeur initiale de la variable⊲ Les flottants : float (simple pr´ecision), double ...

Sujets

Informations

Publié par
Nombre de lectures 56
Langue Français

Exrait

-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 ))
Luc.Maranget@inria.fr
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.
false
◮ L’´egalit´e structurelle est plus ( math´ematique )).
Un conseil donc, utiliser equals, mˆeme sur les chaˆınes.-25- -26-
Affichage Fabriquons nos propres structures de donn´ees
Nous savons afficher des scalaires et des chaˆınes. Par exemple une paire (de deux int):
System.out.println(1 + " " + true + ...) ;
class Pair {
int x, y ; // Variables d’instance ou champs
Mais savons nous afficher des (( objets ) ?
Pair (int x0, int y0) { // Constructeur
int [] t = {1, 2} ;
x = x0 ; y = y0 ;
System.out.println(t) ;
}
}
Affiche : [I@a16869, c’est la fl`eche (l’adresse) qui est affich´ee !
Pour afficher un tableau, il faut ´ecrire une boucle : La classe ci dessus est un patron pour cr´eer des objets, par :
static void print(PrintStream out, int [] t) { Pair p = new Pair (1, 2) ;
for (int i = 0 ; i < t.length ; i++) {
out.print(" " + t[i]) ;
Important : L’ecriture avec constructeur est meilleure que :
}
Pair p = new Pair () ; // Constructeur par d´efaut
} // Appel : print(System.err, new [] {1, 2}) ;
p.x = 1 ; p.y = 2 ;
-27- -28-
Les valeurs des objets sont des r´ef´erences Comment afficher les paires
Ou d´ebut de programmation objet.
Et tout ce qui s’appliquait au tableaux reste vrai.
Pair p = new Pair (1, 2) ;
◮ Si out est un PrintStream, et o un objet, le code
Pair q = p ;
out.print(o), revient a` afficher la chaˆıne renvoy´ee par l’appel
q.x = 0 ;
de m´ethode o.toString().
System.out.println(p.x) ; // Affiche ’0’
◮ Par d´efaut, o.toString() affiche la valeur de o (une fl`eche).
out.print(new Pair(1,2))⇒ Pair@6f0472
q q
◮ Mais on peut red´efinir la m´ethode toString (dans la classe

Pair).
1 2 0 2
p p
public String toString() { // pas de static
return "[x=" + x + ",y=" + y + "]" ;
}
D`es lors,
out.print(new Pair(1, 2))⇒ [x=1,y=2]-29- -30-
R´esum´e sur les classes Surcharge (Overloading)
Une classe C (( pour faire des objets o ) comprend : Il est possible de d´efinir plusieurs constructeurs, a` condition que
leurs arguments soient de types distincts.
◮ Un (ou des ou pas du tout) constructeur homonyme au nom de
class Pair {
la classe. On cr´ee un objet o par :
int x, y ;
new C(...)
Pair() { // Constructeur de l’origine
◮ Des (ou une ou pas du tout) variables x, que l’on r´ef`ere par :
x = 0 ; y = 0 ; // Autant insister (init. par de´faut)
}
o.x
◮ Des (ou une ou pas du tout) m´ethodes f, que l’on appelle par :
Pair (int x0, int y0) {
x = x0 ; y = y0 ;
o.f(...)
}
Plus compliqu´e :
}
◮ Pour le moment : static nulle part.
◮ Cela fonctionne aussi pour les m´ethodes.
◮ L’objet peut posseder des m´ethodes pr´e-existantes, qui peuvent
◮ Tout ce passe comme si le type des arguments faisait partie du
ˆetre red´efinies.
nom des constructeurs/m´ethodes.
-31- -32-
Visibilit´e des variables d’instance Visibilit´e des variables d’instance II
La r`egle des blocs semble rester valable : Mais en fait, c’est un peu diff´erent, la port´ee des variables
d’instance s’´etend sur l’ensemble de l’objet.
class Pair {
int x, y ; // De´claration
class Pair {
Pair (int x0, int y0) {
Pair (int x0, int y0) {
x = x0 ; y = y0 ;
x = x0 ; y = y0 ;
}
}
...
int x, y ; // D´eclaration
public String toString() {
}
return "(" + x + ", " + y + ")" ;
}
En outre, on a aussi droit a` p.x a` peu pr`es n’importe ou`... (a`
}
condition de ne pas sp´ecifier private int x)-33- -34-
Visibilit´e des variables d’instance III La liste
En fait la notation des variables d’instance comme des variables Le tableau mˆeme dynamique est encore un peu rigide.
normales est une commodit´e.
◮ Typiquement, il faut connaˆıtre la taille du tableau a` l’avance.
La r´ef´erence x dans le constructeur ou dans une m´ethode est une
Mais consid´erons une ( liste )) de courses :
abr´eviation pour this.x.
◮ Typiquement, nous ajoutons les articles a` acheter, un par un,
Ou` this est l’objet construit ou dont on a appel´e la m´ethode.
sans savoir combien il y en aura.
Cela permet le style :
Tant qu’il y a du papier...
class Pair {
◮ Lorsque nous faisons les courses, pour ne rien oublier, nous
int x, y ; // D´eclaration
pouvons acheter les articles dans l’ordre de la liste.
Pair (int x, int y) {
Une analogie plus exacte, est un ( carnet de courses ) : un article
this.x = x ; this.y = y ;
par page !
}
...
}
-35- -36-
Soyons plus pr´ecis La liste dans la m´emoire
Une liste est : Une valeur de type List est
◮ Soit vide, ◮ Une r´ef´erence vers une cellule de List (pointeur, addresse).
◮ Soit un premier article et le reste de la liste. ◮ Ou bien la r´ef´erence null qui ne pointe nulle part.
Le plus simple est de proc´eder ainsi : Une cellule de liste comporte :
◮ La liste vide est null. ◮ L’´el´ement en tˆete de liste (champ val).
◮ La cellule de liste est un objet de la classe : ◮ Et un le reste de la liste (champ next de type List).
class List {
List moi = new List("patates", new List("thon", null)) ;
String val ;
List next ;
moi
}
List moi = new List("patates", new List("thon", null)) ;
List elle = new List("laitue", new List("boulgour", null)) ;
"patates" "thon"-37- -38-
Interm`ede Afficher une liste
On veut afficher les listes : peut-on y arriver en red´efinissant Il faut employer une m´ethode statique.
toString ? static void print(List p) {
for (List q = p ; q != null ; q = q.next) {
Non ! Pourquoi ?
System.out.println(q.val) ;
Parce que null est une liste valide, et que null.toString() ne
}
}
fonctionne pas.
List pasFaim = null ;
Remarques Ce genre de boucle for est la fa¸con (( idiomatique )
System.out.println(pasFaim) ;
de parcourir une liste.
Affiche null, car la m´ethode println est du genre.
Ici, la variable q n’est pas utile :
void println(... p) {
static void print(List p) {
if (p == null) {
for ( ; p != null ; p = p.next) {
printString("null") ;
System.out.println(p.val) ;
} else {
}
printString(p.toString()) ;
}
}
}
(Car on modifie p, variable locale, pas la liste).
-39- -40-
Quoi de neuf ? Programmation naturellement r´ecursive
C’est comme la paire, sauf... Fabriquer une nouvelle liste de courses avec deux listes de courses.
List courses = List.append(moi, elle) ;
class List {
...
On peut exprimer append par des ´equations (r´ecursives), en notant
List next ;
}
∅ la liste vide et (a;L) une liste non-vide.
... que la liste est une structure de donn´ee r´ecursive. A(∅,M) = M
A((a;L),M) = a; A(L,M)
◮ Les listes de courses sont solution de l’´equation :
static List append(List p, List q) {
L = null⊎(String×L)
if (p == null) {
return q ;
◮ La programation sur les listes est ( naturellement ) r´ecursive.
} else {
return new List(p.val, append(p.next, q)) ;
}
}