Prgrammer avec les listes : Complexité

Description

INF 421 Luc MarangetProgrammer avec leslistesComplexit´e des [e-mail]://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/1Programmer avec les listes´◮ Echauffement◮ Tri des listes⊲ par insertion,⊲ par fusion.◮ Programmation objet⊲ ensembles persistents,⊲ ensembles mutables.2Notre 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)))3Op´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´l´ement courant.}4Pr´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).5Lecture 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 List (in.read(), ...

Sujets

• informatique

Informations

• Publié par: Miphing
• Nombre de lectures: 52
• Langue: Français

Extrait

INF 421

Luc Maranget

Programmer avec les

listes

Complexite´destris

[e-mail] http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/

1

◮

◮

◮

Programmer

´ Echauffement

Tri des listes

⊲par insertion,

⊲par fusion.

Programmation objet

⊲ensembles persistents,

⊲ensembles mutables.

avec

2

les

listes

Notre amie, la classe des (cellules de) listes

◮ioatarcl´eDn classList{ intval; List next;

List(intval,List next) { this.val=val; this.next=next; } }

◮ 2; 3]. la liste [1; fabriquerUsage :

newList(1,newList(2,newList(3,null)))

3

Il y en a trois.

Ope´ration´l´ntaires s e eme

◮La liste est elle vide ?p==null.

◮nerPlerdatˆete, p.val.

◮nerPlerdatˆete,

◮Prendre la queue,

p.next.

Boucle idiomatique

Traiterlese´le´mentsunparun,dans l’ordre.

for(List p=. . .;p!=null;p=p.next) . . .rant.ementcouts’le´´l//.pavel }

4

{

◮

◮

Pr´esentationth´eoriquedeslistes

Les listes (deEsont)tulossel’ledsnoiioatqu´en:

LhEi={ ∅ } ∪(E×LhEi)

Ce qui veut simplement dire, une liste est soit la liste vide, soit unepairecompose´ed’une´le´mentetd’uenautreliste.

Nous notons donc:

⊲La liste vide∅,

⊲La liste non-vide (e;E).

5

Lecture au clavier

Unelisted’entierslusauclavier(oudansunfichier),teri´eepar m n Ctrl-d(fin de fichier). classIntReader{// Lecteur des int intread() {. . .} booleanhasNext() {. . .} }

classList{ . . . staticList lireInts(IntReader in) { List r=null; while(in.hasNext()) { r=newList(in.read(),r) ; } returnr; } }

6

Initialement,

r

L’utilisateur entre 1,

r

puis 2,

r

puis 3,

r

etc.

1

2

3

Fonctionnement

1

2

7

1

Enr´esume´

◮L’utilisateur entre les valeursi 1  . . ,, .i n etr´el’enermee(ft standard).

◮La boucle construit la liste : . . . r=newList(i 1 ,r)// r est null initialement

. r=newList(i n ,r) . . .

(Et renvoier.)

◮ncDoretsilalee´yovne[est:i n ;. . .;i 1 ].

8

Retourner une liste

Ilya(aumoins)deuxfa¸consd’aborderlaquestion.

◮tne´ateisrestnruopelalrutceL.eprut´eocrcdemeomnOep cettefoisextraitsdelalistea`retourner. 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; }

Mieux :Boucle idiomatique. for(;p!=null;p=p.next) { r=newList(p.val,r) ; }

9

p

1

r

2

10

3

4

p

1

1

r

2

11

3

4