cours sur les structures d'associations

Description

-1-INF 421 — 04 Luc [e-mail]://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-2-PlanA Table d’association/(Java : interface)B Table de hachage/(Java : biblioth`eque)C Bonus Java-3-Les tables d’associations◮ Qu’est-ce que c’est ? Des associations de n’importe quoi a`n’importe quoi.◮ Comment c¸a marche ? Trois impl´ementations.⊲ Avec des listes.⊲ Avec notre table de hachage.⊲ Avec les tables de hachage de la biblioth`eque.-4-La table d’associationSoit des ( informations ), munies d’une ( cl´e )).◮ La cl´e identifie d’information.⊲ Nom (et pr´enom)→ num´ero de t´el´ephone dans l’annuaire.⊲ Matricule→ soldat.⊲ Num´ero d’immatriculation→ v´ehicule, dans le fichier descartes grises.◮ On se place dans le cas ou` la cl´e identifie une informationunique (par ex. fichier des cartes grises).-5-La table d’associationEnsemble dynamique d’informations.Type abstrait de donn´ees, d´efini par les op´erations.◮ Trouver l’information associ´ee `a une cl´e donn´ee.◮ Ajouter une nouvelle association entre une cl´e et uneinformation.◮ Retirer une cl´e de la table (avec l’information associ´ee).Et plus pr´ecis´ement (unicit´e des cl´es)◮ S’il existe d´ej`a une information associ´ee `a la cl´e dans la table,alors la nouvelle information remplace l’ancienne.◮ Sinon, une nouvelle association est ajout´ee `a la table.-6-ApplicationOn veut produire une statistique des mots d’un texte.◮ Voici par ...

Sujets

• informatique

Informations

• Publié par: Astlio
• Nombre de lectures: 33
• Langue: Français

Extrait

-1-

INF

421

— 04

Luc

Associations

Maranget

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

-2-

A

B

C

Table

Table

Plan

d’association/(Java

de hachage/(Java

Bonus Java

:

:

interface)

biblioth`eque)

-3-

◮

◮

Les tables d’associations

Qu’est-cequec’est?Desassociationsden’importequoia` n’importe quoi.

Comment¸camarche?Troisimple´mentations.

⊲Avec des listes.

⊲Avec notre table de hachage.

⊲Avec lestables de hachageeqh`otli.uebabidle

-4-

La table d’association

Soit des✭informations✮, munies d’une✭cle✮. ´

◮tienid´eclLamrtaoi.nefi’dniof

⊲r´enom)Nom(etp→´tepe´l´mundoreanl’ainunehonsda e re.

⊲trMaeulic→soldat.

⊲uNi’dore´mricummatonlati→ucele´ihlsfied,naviechesrd cartes grises.

◮noitamrieedtnfiiueenniofanslecaso`ulacl´nOlpesdeca unique (par ex. fichier des cartes grises).

-5-

La table d’association

Ensembledynamiqueorma’infd.sitno

Typeabstraitdedonn´ees,d´efiniparlesope´rations.

◮rTuoevlri’nformationassoci`ee´enuae´lcnnode.´e

◮llaeuoevaiitsscotreuonen´eetneclenujoAerutenun information.

◮ruretiRede´eclnessan´icomrofoitaecavinl’talae(blee).

Etpluspr´ecis´ement(unicite´descle´s)

◮fnienua`je´detsiexilS’lstadenaca´l`elaci´eassotionormaelba, alors la nouvelle information remplace l’ancienne.

◮t´ouajsttala`aeeossaelleenoitaiclb.eSinon,unenouv

-6-

Application

On veut produire une statistique des mots d’un texte.

◮Voici par exemple un texte bien connu.

% cat marseillaise.txt Allons ! Enfants de la Patrie ! Lejourdegloireestarriv´e! etc.

◮tsiteuqifsedqe´rncuedeesotsmelsdStaedstmoe(islailsearaM taille≥jam,4.)´eesnlevleseuscu

% java Freq marseillaise.txt nous: 10 vous: 8 franc¸ais:7 etc.

-7-

En trois etapes. ´

Conception de

1.Lireletextemot-`a-mot.

2. Compter les occurrences des mots.

Freq

3.Produireunbelaffichage(parfre´quencesd´ecroissantes).

Pluspr´ecis´ement.

´ 1. Proceder selon le principe duReader.

2.Parunetabled’associationdesmotsauxcomptes.(cle´=un mot→information = un compte).

3.Paruntria`lafin.

-8-

Lecture des mots, tri

Onsupposedonne´s:

◮Une classe des objets✭lecteur de mots✮(WordReader). ⊲ConstructeurWordReader(String name)epuorcr´eerl lecteur des mots d’un fichier de nomname. ⊲etM´ohedString read(), renvoie le mot suivant (ounull quand c’est fini).

◮Un tri des paires, mot×ton(etpmsee´cow→c). Selon l’ordre total :

(w 1 →c 1 )<(w 2 →c 2 ) m

(c 1 > c 2 )∨(c 1 =c 2 ∧w 1 < w 2 )

-9-

D´efinitionpr´ecisedenotretable

Une table est un objetAssoc une table d’association des. C’est mots (String) auxint.

◮etM´dehointget(String w)ervniole,ssoci´e`aecompteaw.

⊲Ou bien 0 siwn’est pas dans la table.

◮eodMth´evoidput(String w,intc), associe le comptecau motw.

Spe´cificationenJava,paruneinterfacemmoc(ne´tee.)

interfaceAssoc{ /*Cr´eer/remplacerl’associationkey→val */ voidput(String key,intval) ; /*Trouverl’entierassoci´e`akey,ouze´ro.*/ intget(String key) ; }

-10-

Code de

main

classFreq{ . . . static voidcountFile(String name,Assoc t) { WordReader wr=newerWordRead(name) ; count(wr,t) ; wr.close() ;lp(erpsune’le´rtFe//errm)poer Sort.println(t) ;// Affichage tri´ e }

}

public static voidmain(String[]arg) { countFile(arg[0],. . .) }

-11-

Code decount static voidcount(WordReader in,Assoc t) { for(String word=in.read() ; word!=null; word=in.read()) { i f(word.length() >= 4) { word=word.LotrewoesaC() ; t.put(word,t.get(word)+1) ; } } }

Remarquer :Assocn’est pas une classe, mais on peut l’utiliser commeuntype,celuidudeuxi`emeargumentdecount.