-1-INF 421 — Luc MarangetProgrammer avec leslistesComplexit´e des trisLuc.Maranget@inria.frhttp://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-2-Programmer avec les listes´◮ Echauffement◮ Tri des listes⊲ par insertion,⊲ par fusion.◮ Programmation objet⊲ ensembles persistents,⊲ ensembles mutables.-3-Notre amie, la classe des (cellules de) listes◮ D´eclarationclass List {int val ;List next ;List (int val, List next) {this.val = val ;this.next = next ;}}◮ Usage : fabriquer la liste [1;2;3].new List (1, new List (2, new List (3, null)))-4-Op´erations ´el´ementairesIl y en a trois.◮ La liste est elle vide ? p == null.◮ Prendre la tˆete, p.val.◮ Prendre la queue, p.next.Boucle idiomatiqueTraiter les ´el´ements un par un, dans l’ordre.for (List p = ... ; p != null ; p = p.next) {... // p.val est l’e´le´ment courant.}-5-Pr´esentation th´eorique des listes◮ Les listes (de E) sont les solutions de l’´equation:LhEi ={∅}∪(E×LhEi)Ce qui veut simplement dire, une liste est soit la liste vide, soitune paire compos´ee d’un ´el´ement et d’uen autre liste.◮ Nous notons donc:⊲ La liste vide ∅,⊲ La liste non-vide (e;E).-6-Lecture au clavierUne liste d’entiers lus au clavier (ou dans un fichier), termin´ee parCtrl-d (fin de fichier).class IntReader { // Lecteur des intint read() { ... }boolean hasNext() { ... }}class List {...static List lireInts(IntReader in) {List r = null ;while (in.hasNext()) {r = new ...
Ce qui veut simplement dire, une liste est soit la liste vide, soit unepairecompose´ed’un´el´ementetd’uenautreliste.
Nous notons donc:
⊲La liste vide∅,
⊲La liste non-vide (e;E).
-6-
Lecture au clavier Unelisted’entierslusauclavier(oudansunfichier),termine´epar Ctrl-d(fin de fichier). classIntReader{// Lecteur des int intread() {. . .} booleanhasNext() {. . .} }
◮L’utilisateur entre les valeursi1 . . ,, .ineer´tne’lemrefte( standard).
◮La boucle construit la liste : . . . r=newList(i1,r)// r est null initialement
. r=newList(in,r) . . .
(Et renvoier.)
◮onclDterealise´eevnyots[:in;. . .;i1].
-9-
Retourner une liste
Ilya(aumoins)deuxfac¸onsd’aborderlaquestion.
◮tnate´sreitesenre.Lecturlalpeuoocmmdereor´cpnOptue cettefoisextraitsdelaliste`aretourner. staticList rev(List p) { List r=null; while(p!=null) {// Tant qu’il y a des entiers... r=newList(p.val,r) ; p=p.next;// Les consommer } returnr; }