Cours de programmation sur les listes

Sujets

• informatique

Informations

• Publié par: Shiem
• Nombre de lectures: 73
• Langue: Français

Extrait

-1- -2-
INF 421 — Luc Maranget
Programmer avec les listes
´
◮ Echauffement
Programmer avec les
◮ Tri des listes
listes ⊲ par insertion,
⊲ par fusion.
◮ Programmation objet
Complexit´e des tris
⊲ ensembles persistents,
⊲ ensembles mutables.
[e-mail]
http://www.enseignement.polytechnique.fr/profs/
informatique/Luc.Maranget/421/
-3- -4-
Op´erations ´el´ementaires
Notre amie, la classe des (cellules de) listes
Il y en a trois.
◮ D´eclaration
class List {
◮ La liste est elle vide ? p == null.
int val ;
◮ Prendre la tˆete, p.val.
List next ;
◮ Prendre la queue, p.next.
List (int val, List next) {
this.val = val ;
Boucle idiomatique
this.next = next ;
}
Traiter les ´el´ements un par un, dans l’ordre.
}
for (List p = ... ; p != null ; p = p.next) {
... // p.val est l’´el´ement courant.
◮ Usage : fabriquer la liste [1;2;3].
}
new List (1, new List (2, new List (3, null)))-5- -6-
Pr´esentation th´eorique des listes Lecture au clavier
Une liste d’entiers lus au clavier (ou dans un fichier), termin´ee par
◮ Les listes (de E) sont les solutions de l’´equation:
Ctrl-d (fin de fichier).
LhEi ={∅}∪(E×LhEi)
class IntReader { // Lecteur des int
int read() { ... }
Ce qui veut simplement dire, une liste est soit la liste vide, soit
boolean hasNext() { ... }
une paire compos´ee d’un ´el´ement et d’uen autre liste.
}
◮ Nous notons donc:
class List {
⊲ La liste vide ∅, ...
static List lireInts(IntReader in) {
⊲ La liste non-vide (e;E).
List r = null ;
while (in.hasNext()) {
r = new List (in.read(), r) ;
}
return r ;
}
}
-7- -8-
Fonctionnement En r´esum´e
Initialement,
◮ L’utilisateur entre les valeurs i , ..., i (et ferme l’entr´ee
1 n
standard).
r
◮ La boucle construit la liste :
L’utilisateur entre 1,
...
r = new List(i , r) // r est null initialement
1
1
r
.
.
.
r = new List(i , r)
puis 2,
n
...
2 1
r
(Et renvoie r.)
puis 3,
◮ Donc la liste renvoy´ee est : [i ;...;i ].
n 1
3 2 1
r
etc.-9- -10-
Retourner une liste Approche r´ecursive
Il y a (au moins) deux fa¸cons d’aborder la question.
G´en´eralisons le probl`eme (comme souvent).
◮ On peut proc´eder comme pour la lecture. Les entiers ´etant
La methode revAppend(p ;...;p , q ;...;q ) doit
1 n 1 m
cette fois extraits de la liste a` retourner.
renvoyer la liste p ;...;p ;q ;...q .
n 1 1 m
static List rev(List p) {
Par induction sur la premi`ere liste, la fonction R suivante convient.
List r = null ;
while (p != null) { // Tant qu’il y a des entiers...
R(∅,Q) = Q
r = new List(p.val, r) ;
p = p.next ; // Les consommer
R((a;P),Q) = R(P,(a;Q))
}
return r ;
En notant P la liste P retourn´ee, et par hypoth`ese de r´ecurrence :
}
R(P,(a;Q)) =P;a;Q
Mieux : Boucle idiomatique.
for (; p != null ; p = p.next) { Avec a;P =P;a (disons par d´efinition du retournement).
r = new List(p.val, r) ;
}
-11- -12-
Programmation de R ´
Elimination de la r´ecursion (terminale)
Les ´equations :
La boucle,
x = x ; r = r ;
0 0
R(∅,Q) = Q
while (P(x)) {
R((a;P),Q) = R(P,(a;Q))
r = f(x,r) ; x = g(x) ;
}
Le code :
static List revAppend(List p, List q) { ´
Equivaut a` la r´ecursion
if (p == null) {
static ... recLoop(... x, ... r) {
return q ;
if (P(x)) {
} else {
return recLoop(g(x), f(x,r)) ;
return revAppend(p.next, new List(p.val, q)) ;
} else {
}
return r ;
}
}
}
static List rev(List p) {
... r = recLoop(x , r ) ...
0 0
return revAppend(p, null) ;
}
Remarquer C’est un compl´ement : aller voir le poly.-13- -14-
Un autre exemple : l’affichage Encore un exemple : n-i`eme ´element
C’est plus simple, car il n’y a pas de r´esultat (accumulateur r).
R´ecursif
static int nth(int i, List p) {
◮ R´ecursif
if (p == null) { throw new Error() ; }
private static void doPrint(List p) {
if (i == 0) {
if (p != null) {
return p.val ;
System.out.println(p.val) ;
} else {
doPrint(p.next) ;
return nth(i-1, p.next) ;
}
}
}
static print(List p) { doPrint(p) ; } ;
It´eratif: allons nous pouvoir utiliser la boucle idiomatique ? Oui
static int nth(int i, List p) {
(afficher a;P c’est afficher a, puis afficher P.)
for ( ; p != null ; p = p.next) {
◮ It´eratif
if (i == 0) return p.val ;
static void print(List p) { i-- ;
for ( ; p != null ; p = p.next) { }
System.out.println(p.val) ;
throw new Error() ;
}}
}
-15- -16-
` Que retenir ?
A propos
La programmation r´ecursive est la plus puissante (et de loin).
On ne doit pas ´ecrire :
for (int i = 0 ; i < length(p) ; i++) {
Par exemple, afficher a` l’envers.
int x = nth(i, p) ;
static void revPrint(List p) {
...
if (p != null) {
}
revPrint(p.next) ;
System.out.println(p.val) ;
Mais plutotˆ .
}
for (List q = p ; q != null ; q = q.next) {
}
int x = q.val ;
...
(afficher a;P a` l’envers, c’est afficher P a` l’envers, puis afficher a.)
}
Pas de version it´erative... simple.
Pourquoi
◮ Efficacit´e (quadratique/lin´eaire).
◮ Mais surtout harmonie, le premier code convient aux tableau
(acc`es dit al´eatoire) le second aux listes (acc`es dit s´equentiel).-17- -18-
Pourquoi trier ? Trier une liste simplement
Trions une main a` la belote (ou au bridge).
◮ On a parfois tout simplement besoin de trier.
⊲ Le professeur trie les lignes d’une feuille de calcul (genre
◮ je prend les cartes dans la main gauche,
Excel), selon les noms des ´el`eves, ou selon les notes obtenues
◮ je prend une carte et la met dans ma main droite,
a` un examen, selon qu’il veut controlˆ er qu’aucun ´el`eve ne
◮ je prend une carte et la range a` sa place dans ma main droite,
manque, ou classer les ´el`eves.
◮ je prend une carte et la range a` sa place dans ma main droite,
◮ Op´erer sur des donn´ees tri´ees, est parfois, plus simple, plus
.
efficace, ou mˆeme plus simple et plus efficace.
.
.
⊲ Par exemple, enlever les doublons d’une liste.
◮ ma main gauche est vide.
⋆ Sur une liste tri´ee, il suffit d’un parcours, car les doublons
se suivent. L’insertion semble plus simple dans une liste que dans un tableau.
⋆ Sur une liste non-tri´ee, il faut multiplier les parcours.
-19- -20-
Insertion, ´equations Programmation du tri des listes
Trouver la place ou` ranger la nouvelle valeur x dans une liste tri´ee D’abord le tri en supposant insert ´ecrite.
static boolean ici(int x, List p) { static List sort(List p) {
return (p == null || x <= p.val) ; List r = null ;
for ( ; p != null ; p = p.next) {
}
r = insert(p.val, r) ;
Noter : ici(x,P) faux entraˆıne P non-vide. }
return r ;
}
I(x,P) = x;P , si ici(x,P)
I(x,(a;P)) = a;I(x,P), sinon
Et l’insertion.
static List insert(int x, List p) {
Correction :
if (ici(x,p)) {
◮ Base : Si ici(x,P) et P tri´ee, alors (x;P) est tri´ee.
return new List (x, p) ;
} else { // (p != null) && (x > p.val)
◮ Induction : Sinon (liste a;P avec a<x)
return new List (p.val, insert(x, p.next)) ;
⊲ a minore P et x, et donc I(x,P).
}
}
⊲ I(x,P) est tri´e (induction).-21- -22-
Combien ¸ca couˆte Combien c¸a couˆte ? II
On peut (plus simplement) compter les comparaisons.
Pour une liste de taille (longeur) n.
n(n−1)
◮ La m´ethode sort appelle n fois insert,
n−1≤I(n)≤
2
◮ En outre, elle est responsable de moins de k ×n+k autres
1 0
Ici, I(n) est le nombre de comparaisons d’´el´ements effectu´ees pour
op´erations (´el´ementaires, i.e. de couˆt constant).
trier une liste de taille n.
◮ Chacun de ces n appels de insert(x,p) (p de longeur ℓ) se
Ce r´esultat donne une indication sens´ee du temps d’ex´ecution.
′ ′
solde par moins de k ×ℓ+k op´erations.
1 0
◮ La comparaison est souvent l’op´eration la plus couˆteuse (tri de
grandes chaˆınes).
◮ ℓ vaut 0, 1, ...n−1.
◮ On peut affecter un nombre constant d’op´erations a` chaque
◮ Au final le tri s’effectue en moins de
comparaison (la borne asymptotique est inchang´ee).
′ ′
k ×n+k +n×(k ×n+k )
1 0
1 0
On peut aussi compter le nombre de cellules de listes allou´ees.
2
Soit un couˆt en O(n ).
n(n+1)
n≤I(n)≤
2 2
La borne O(n ) est bien serr´ee (listes tri´ees de tailles croissante).
-23- -24-
Couˆt en moyenne Insertion ( en place ))
Les arguments du tri sont pris dans un espace de probabilit´e (S). La m´ethode insert pr´ecedente n’est pas conforme a` l’intuition
On calcule l’esp´erance de la variable al´eatoire (( couˆt ) (X). d’insertion dans un jeu de cartes.
X
Revenons aux equa