Planche : 1


Objectifs

Planche : 2


Organisation du cours

Planche : 3


Quelques éléments de Java

Planche : 4


Les valeurs

Planche : 5


Déclaration: avec et sans initialisation
  int x = 1 ;

Ne pas confondre déclaration avec initialisation et affectation. Même si la syntaxe est très semblable.

int x = 1 ; // Création avec initialisation.
x = 2 ;     // Changer le contenu
int y ;     // Création tout court

Remarque : Quelle est la valeur initiale de la variable y ?
On ne peut pas le savoir !


Planche : 6


Variables locales

Les variables locales sont :

Le compilateur vérifie « l’initialisation » des variables locales.

class T {
  static int f(int x) {
    int y ;
    if (x != 0) y = 1 ;
    return x + y ;
  }
}
# javac T.java
T.java:5: variable y might not have been initialized

Planche : 7


Les variables sont « des cases »

Deux déclarations de variable.

int x=1, y ;

Une affectation.

y = x ;

On remarque que :


Planche : 8


Appel de méthode

Le principe est le suivant :

static int f(int x) {
   x = x + 2 ;
   return x ;
}

public static void main (String [] arg) {
  int x = 2 ;
  int r = f(x) ;
  System.out.println("f(" + x + ") = " + r) ;
}

Résultat : f(2) = 4


Planche : 9


Avec des boites
static int f(int x) {
   x = x + 2 ;
   return x ;
}

Au début de l’appel de méthode :

Juste avant le return :


Planche : 10


Portée

La portée d’une variable est la zone du code où on peut l’utiliser, autrement dit, la zone de visibilité.

Dans l’exemple précédent, les portées des deux variables x étaient clairement limitées aux corps des méthodes main et f.

La portée est structurée selon les blocs, en gros délimités par {}.

Quelques règles importantes :


Planche : 11


Exemple de portée I

Que penser de :

static int f() {
  for (int i = 0 ; i < 10 ; i++) { … }
  return i ;
}

Ce code est incorrect, car dans l’instruction return i, la variable i ne fait référence à aucune déclaration visible.

Note : On peu considérer que la boucle for est plus ou moins équivalente à :

  { int i = 0 ;  // NB. un bloc est ouvert
    while (i < 10) { …
      i++ ;
    }
  }

Planche : 12


Portée, II

Que se passe-t-il si on appelle f(4) ?

static int f(int x) {
  { int x = 2 ;
    System.out.print("x = " + x) ;
  }
  System.out.println(", x = " + x) ;
}

Ce programme est correct. Il affiche :

 x = 2, x = 4

Il y a en fait deux variables, x et x.

On peut très bien changer x (ou x) en y, sans rien changer au fond. Les variables (locales) sont un peu comme les variables muettes des mathématiques.


Planche : 13


Un tableau avec les boites

Un tableau de taille n est (plus ou moins) une grosse case composée de n cases « normales ».

   int [] t = new int[6] ;

Mais la valeur du tableau est une flèche (référence, pointeur, adresse) vers la grosse case.

Note : Les cases du tableau sont initialisés par défaut.


Planche : 14


Valeur par défaut

Les cases des tableaux ont une valeur par défaut.

Notons que null est un objet un peu spécial. Il appartient à toutes les classes, mais on ne peut rien faire avec, sauf :


Planche : 15


La deuxième dimension

Une matrice à 3 lignes et 2 colonnes.

   int [] [] t = new int [3][2] ;

Est en fait un tableau de trois tableaux de deux entiers.


Planche : 16


Et null dans tout ça ?

Logiquement, les tableaux sont initialisés par défaut à null.

   int [] t // = null ;

La valeur null remplace une flèche, mais ne pointe nulle part.

L’initialisation par défaut vaut aussi pour les cases de tableau.

   int [][] t = new int[3][] ; // tableau de tableaux

Soit : un tableau de trois null.


Planche : 17


Les tableaux sont alloués « dynamiquement »

Cela veut dire que leur place est calculée/allouée lors de l’exécution.

  static int [] f(int nint x0) {
    int [] r = new int [n] ;
    for (int i = 0 ; i < n ; i++) { r[i] = x0 ; }
    return r ;
  }

En outre, l’allocation est effectuée dans le « tas ».


Planche : 18


Les valeurs des tableaux sont des flèches
  int [] t = {1, 2, 3, 4, 5, 6} ; // Initialisation explicite
  int [] r = t ;

Dans r = t c’est la flèche qui est copiée.

De sorte que ici t[2] et r[2] désignent la même case (la troisième).

   t[2] = 0 ; // ranger 0 dans la case désignée
   System.out.println(r[2]) ; // Affiche '0'

Planche : 19


À comparer avec

La copie du contenu de variables de type scalaire.

   int x = 3, y = x ;
   x = 0 ; System.out.println(y) ; // Affiche '3'

Car ici x et y sont deux cases différentes.


Planche : 20


Appel de méthode

Les valeurs sont bien copiées, mais ce sont des flèches.

static void f(int [] r) { r[0] = 0 ; }
  int [] t = { 1, 2 } ;
  System.out.println(t[0]) ; // Affiche '1'
  f(t) ;
  System.out.println(t[0]) ; // Affiche '0'

Planche : 21


Égalité « physique »

L’égalité == est l’égalité des valeurs.


Planche : 22


Égalité « structurelle »

Pour savoir si deux tableaux sont identiques (et non plus exactement le même). On utilise o1.equals(o2).

int [] t = {1, 2, 3} ;
boolean b = t.equals(new int [] {1, 2, 3}) // tableau « anonyme »
System.out.println(b) ;

Affiche true.



Résumé :


Planche : 23


Les chaînes sont des objets…

Mais des objets un peu particuliers.

class Coucou {
  public static void main(String [] arg) {
    System.out.println("coucou" == "coucou") ;
    System.out.println(arg[0] == arg[1]) ;
  }
}

La commande « java Coucou coucou coucou » affichera :

true
false

Un conseil donc, utiliser equals, même sur les chaînes.


Planche : 24


Affichage

Nous savons afficher des scalaires et des chaînes.

System.out.println(1 + " " + true + …) ;

Mais savons nous afficher des « objets » ?

int [] t = {1, 2} ;
System.out.println(t) ;

Affiche : [I@a16869, c’est la flèche (l’adresse) qui est affichée !

Pour afficher un tableau, il faut écrire une boucle :

static void print(PrintStream outint [] t) {
  for (int i = 0 ; i < t.length ; i++) {
    out.print(" " + t[i]) ;
  }
// Appel : print(System.err, new [] {1, 2}) ;

Planche : 25


Fabriquons nos propres structures de données

Par exemple une paire (de deux int):

class Pair {
  int xy ; // Variables d'instance ou champs

  Pair (int x0int y0) { // Constructeur
    x = x0 ; y = y0 ;
  }
}

La classe ci dessus est un patron pour créer des objets, par :

  Pair p = new Pair (1, 2) ;

Important : L’ecriture avec constructeur est meilleure que :

  Pair p = new Pair () ; // Constructeur par défaut
  p.x = 1 ; p.y = 2 ;

Planche : 26


Les valeurs des objets sont des références

Et tout ce qui s’appliquait au tableaux reste vrai.

Pair p = new Pair (1, 2) ;
Pair q = p ;
q.x = 0 ;
System.out.println(p.x) ; // Affiche '0'

Planche : 27


Comment afficher les paires

Ou début de programmation objet.


Planche : 28


Résumé sur les classes

Une classe C « pour faire des objets o » comprend :

Plus compliqué :


Planche : 29


Surcharge (Overloading)

Il est possible de définir plusieurs constructeurs, à condition que leurs arguments soient de types distincts.

class Pair {
  int xy ;

  Pair() { // Constructeur de l'origine
    x = 0 ; y = 0 ; // Autant insister (init. par défaut)
  }

  Pair (int x0int y0) {
    x = x0 ; y = y0 ;
  }
}

Planche : 30


Visibilité des variables d’instance

La règle des blocs semble rester valable :

class Pair {
  int xy ; // Déclaration

  Pair (int x0int y0) {
    x = x0 ;  y = y0 ;
  }

  public String toString() {
    return "(" + x + ", " + y + ")" ;
  }
}

Planche : 31


Visibilité des variables d’instance II

Mais en fait, c’est un peu différent, la portée des variables d’instance s’étend sur l’ensemble de l’objet.

class Pair {
  Pair (int x0int y0) {
    x = x0 ;  y = y0 ;
  }
  …
  int xy ; // Déclaration
}

En outre, on a aussi droit à p.x à peu près n’importe où… (à condition de ne pas spécifier private int x)


Planche : 32


Visibilité des variables d’instance III

En fait la notation des variables d’instance comme des variables normales est une commodité.

La référence x dans le constructeur ou dans une méthode est une abréviation pour this.x.

this est l’objet construit ou dont on a appelé la méthode.

Cela permet le style :

class Pair {
  int xy ; // Déclaration

  Pair (int xint y) {
    this.x = x ;  this.y = y ;
  }
  …
}

Planche : 33


La liste

Le tableau même dynamique est encore un peu rigide.

Mais considérons une « liste » de courses :

Une analogie plus exacte, est un « carnet de courses » : un article par page !


Planche : 34


Soyons plus précis

Une liste est :

Le plus simple est de procéder ainsi :

List moi =  new List("patates"new List("thon"null)) ;
List elle = new List("laitue"new List("boulgour"null)) ;

Planche : 35


La liste dans la mémoire

Une valeur de type List est

Une cellule de liste comporte :

List moi = new List("patates"new List("thon"null)) ;

Planche : 36


Intermède

On veut afficher les listes : peut-on y arriver en redéfinissant toString ?

Non ! Pourquoi ?

Parce que null est une liste valide, et que null.toString() ne fonctionne pas.

  List pasFaim = null ;
  System.out.println(pasFaim) ;

Affiche null, car la méthode println est du genre.

  void println(… p) {
    if (p == null) {
      printString("null") ;
    } else {
      printString(p.toString()) ;
    }
  }

Planche : 37


Afficher une liste

Il faut employer une méthode statique.

  static void print(List p) {
    for (List q = p ; q != null ; q = q.next) {
      System.out.println(q.val) ;
    }
  }

Remarques Ce genre de boucle for est la façon « idiomatique » de parcourir une liste.

Ici, la variable q n’est pas utile :

  static void print(List p) {
    for ( ; p != null ; p = p.next) {
      System.out.println(p.val) ;
    }
  }

(Car on modifie p, variable locale, pas la liste).


Planche : 38


Quoi de neuf ?

C’est comme la paire, sauf…

class List {
  …
  List next ;
}

… que la liste est une structure de donnée récursive.


Planche : 39


Programmation naturellement récursive

Fabriquer une nouvelle liste de courses avec deux listes de courses.

  List courses = List.append(moielle) ;

On peut exprimer append par des équations (récursives), en notant ∅ la liste vide et (a; L) une liste non-vide.

A(∅,M)= M 
A((aL), M)= aA(LM
static List append(List pList q) {
  if (p == null) {
    return q ;
  } else {
    return new List(p.valappend(p.nextq)) ;
  }
}

Planche : 40


Premier appel


Planche : 41


Deuxième appel


Planche : 42


Troisième appel


Planche : 43


Retour du troisième appel


Planche : 44


Retour du deuxième appel


Planche : 45


Retour du premier appel


Planche : 46


Situation finale
  List courses = List.append(ellemoi) ;

La liste courses est"laitue"; "blougour"; "patates"; "thon"

Important : La liste elle n’a pas changé. Structure persistante.

Moins important : Les cellules de elle sont copiées.


Planche : 47


Et si je change d’avis
  moi.val = "carottes" ;

Situation :

Conclusion : moi devient "carotte"; "thon" et courses devient "laitue"; "boulgour"; "carotte"; "thon".


Planche : 48


Et si elle change d’avis ?
  elle.val = "scarole" ;

Situation :

Conclusion : courses ne change pas.

Conclusion

La mutation est incompatible avec les structure persistantes.


Planche : 49


J’aime les chose délicates

Planche : 50


Concaténer en place

La fonction nappend concatène les listes « en place »

Elle s’écrit facilement, en remplaçant les allocations de cellules de append par des mutations du champ next.

static List nappend(List xsList ys) {
  if (xs == null) {
    return ys ;
  } else {
    xs.next = nappend(xs.nextys) ;
    return xs ;
  }
}

Planche : 51


Premier appel


Planche : 52


Deuxième appel


Planche : 53


Troisième appel


Planche : 54


Retour du troisième appel


Planche : 55


Retour du deuxième appel


Planche : 56


Retour du premier appel


Planche : 57


Résultat (des courses en place)

Danger principal La liste pointée par moi a « changé ». Car une de ses cellules a été « mutée ».


Planche : 58


Un second problème

Écrivons

List courses = List.nappend(moimoi) ;

Planche : 59


Programation itérative

Deux façons d’aborder la programmation.

En gros, programmation récursive vs. programmation avec des boucles.


Planche : 60


Programmation itérative

Comment nappend fonctionne-elle ?

static List nappend2(List xsList ys) {
  if (xs == null) return ys ;
  List zs = xs ;
  for ( ; zs.next != null ; zs = zs.next) ;
  zs.next = ys ;
  return xs ;
}

Planche : 61


Et sans modifier la liste d’origine ?

Comment obtenir une concaténation itérative et non-destructive simplement :

static List append2(List xsList ys) {
   List zs = copy(xs) ; // Copier xs qui va être modifiée
   return nappend2(zsyz) ;
}

(En pratique, on ne devrait presque jamais écrire un truc pareil. Si le besoin s’en fait sentir, penser aux listes persistentes.)


Planche : 62


En trichant

Il est facile d’écrire un copy récursif.

List copy(List xs) {
  if (xs == null) {
    return null ;
  } else {
    return new List (xs.valcopy(xs.next)) ;
  }
}

Ne pas tricher c’est écrire copy en style itératif.

Qu’est-ce que ça fait ?


Planche : 63


Premier essai
static List copy2(List xs) {
  List r = null ;
  for ( ; xs != null ; xs = xs.next) {
    r = new List (xs.val, r) ;
  }
  return r ;
}

Planche : 64


Première itération

Planche : 65


Exécution du corps

Planche : 66


Deuxième itération (fin)

Planche : 67


Troisième itération (fin)

Planche : 68


Et c’est fini

Planche : 69


Copier dans l’ordre

Planche : 70


Copier dans l’ordre

Planche : 71


Programmation itérative de copy
static List copy2(List xs) {
  if (xs == null) return ys ;
  List r = new List (xs.val,null) ;
  List lst = r ;
  for ( xs = xs.next ; xs != null ; xs = xs.next) {
    lst.next = new List (xs.val, null) ;
    lst = lst.next ;
  }
  return r ;
}

Planche : 72


Programmation itérative de append

Comment append fonctionne-elle ?

static List append2(List xsList ys) {
  if (xs == null) return ys ;
  List r = new List (xs.val,null) ;
  List lst = r ;
  for ( xs = xs.next ; xs.next != null ; xs = xs.next) {
    lst.next = new List (xs.val, null) ;
    lst = lst.next ;
  }
  lst.next = ys ;
  return r ;
}

Planche : 73


Les structures de données dynamiques

Nature des structures de données :

Le choix persistant/mutable est un choix de fonctionalité. Il doit être conscient et influence l’ensemble du programme.

Style de programmation :

Le choix récursif/itératif est un choix d’efficacité, compromis facilité d’écriture/efficacité du programme.


Planche : 74


Résumé

On peut définir quatre catégories. Selon la nature des structures de données et le style de programmation.

 PersistantMutable
Récursifapppendnappend
Itératifappend2append2

Ce document a été traduit de LATEX par HEVEA