Programmer avec les listes : complexité des tries

Description

-1-INF 421 — Luc MarangetProgrammer avec leslistesComplexit´e des [e-mail]://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 ...

Sujets

• informatique

Informations

• Publié par: Thuwyug
• Nombre de lectures: 54
• Langue: Français

Extrait

-1-

INF 421 —

Luc Maranget

Programmer avec les

listes

Complexite´destris

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

-2-

◮

◮

◮

Programmer

´ Echauffement

Tri des listes

⊲par insertion,

⊲par fusion.

Programmation objet

⊲ensembles persistents,

⊲ensembles mutables.

avec

les

listes

-3-

Notre amie, la classe des (cellules de) listes

◮D´noaritceal classList{ intval; List next;

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

◮ 2; 3]. la liste [1;Usage : fabriquer

newList(1,newList(2,new

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

-4-

Il y en a trois.

Ope´rations´el´ementaires

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

◮rPnerdleta,eteˆp.val.

◮Prendre la queue,p.next.

◮Prendre la queue,

Boucle idiomatique

Traiterlesele´mentsunparun,dans l’ordre. ´

for(List p=. . .;p!=null;p=p.next) { . . .l’´el´/e/mp.valesttn.nectuoar }

-5-

◮

◮

Pre´sentationthe´oriquedeslistes

Les listes (deE:uaeqontisdon’´eltlon)stilusoes

LhEi={ ∅ } ∪(E×LhEi)

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() {. . .} }

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

r;

-7-

Initialement,

r

L’utilisateur entre 1,

r

puis 2,

r

puis 3,

r

etc.

1

2

3

Fonctionnement

1

2

1

-8-

Enr´esume ´

◮L’utilisateur entre les valeursi 1  . . ,, .i n eer´tne’lemrefte( standard).

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

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

(Et renvoier.)

◮onclDterealise´eevnyots[:i n ;. . .;i 1 ].

-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; }

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

-10-

Approcher´ecursive

G´en´eralisonsleprobl`eme(commesouvent).

La methoderevAppend(p 1 ;. . .;p n ,q 1 ;. . .;q m )doit renvoyer la listep n ;. . .;p 1 ;q 1 ;. . . q m .

Parinductionsurlapremi`ereliste,lafonctionRsuivante convient.

R(∅ Q) =Q

R((a;P) Q) =R(P(a;Q))

En notantPla listePaptepyhr`htodese´eerrrcuceen:e´,euonrrte

Avec

R(P(a;Q)) =P;a;Q

a;P=P;ainfie´draerudnoitmeneurto).nt(disonsp

-11-

Lese´quations:

Programmation deR

R(∅ Q) =Q

R((a;P) Q) =R(P(a;Q))

Le code : staticList revAppend(List p,List q) { i f(p==null) { returnq; }else{ returnrevAppend(p.next,newList(p.val,q)) ; } }

staticList rev(List p) { returnrevAppend(p,null) ; }