coursAlgo_V4

7/30/2019 coursAlgo_V4

1/53

iUT ORSAY

U niversit Paris XI

I.U.T. d'OrsayDpartement InformatiqueAnne scolaire 2003-2004

Algorithmique : Volume 4 Listes chanes Piles et files

Ccile Balkanski, Nelly Bensimon, Grard Ligozat


2/53

Algorithmique 4 : Listes chanes 1

Retour au type tableau

Avantages

- Accs direct un lment quelconque du tableau par unindice

- Souplesse dans lcriture des algorithmes

- Algorithmes de recherche trs performants quand leslments sont ordonns


3/53


Retour au type tableau (suite)

Inconvnients- Ncessit de dfinir la dimension maximale alloue ds la

dclaration, c'est dire de faon statique

- Lourdeur dans la gestion optimale de l'espace occup parles donnes

- Ncessit d'effectuer des contrles de dbordement chaque tape du traitement


4/53


Cahier des charges d'une

reprsentation moins contrainte Permettre l'allocation de mmoire en fonction des besoins,

de faon dynamique

Faciliter la gestion de la mmoire occupe en casd'insertion ou de suppression de nouvelles donnes

Simulation de phnomnes du monde physique malreprsents par la structure en tableaux

Exemples de situations : File d'attente un guichet Urgences d'un hpital

Distribution de cartes une table de joueurs

Gestion des dossiers empils sur un bureau


5/53


La notion de liste chane

donne

donne donne

donne donne

cellule

li e n


6/53


Insertion/suppression d'une donne

donne

donne donne

donne donne

nouvelledonne

nouvelledonne

nouvelledonne

Cellule insrer en milieu de chane

Cellule insrer

en fin de chane

Cellule insrer en dbut de chane

cellule retirer


7/53


Reprage des cellules

d'une liste chane

donne

donne donne

donnedonne

Premire("tte")

PrcdenteCourante

Suivante

Dernire("queue")


8/53


Exemples de traitements oprssur les listes (1)

Traitements relatifs la composition structurellede la liste :- Positionnement sur la premire cellule de la structure

- Positionnement sur la dernire cellule de la structure

- Calcul de la longueur d'une liste (nombre de cellules)

- Reconnaissance d'une liste vide

- Dplacement du positionnement courant sur la cellule

suivante


9/53


Exemples de traitements oprssur les listes (2)

Traitements relatifs l'information enregistredans une liste :- Enregistrement de donnes jusqu' puisement du flot de

donnes

- Visualisation de l'information enregistre dans une cellule,quelle que soit sa place dans la liste

- Visualisation de l'ensemble des informations enregistresdans la liste

- Suppression d'une cellule; ajout dune cellule


10/53


Cahier des charges

pour une classe Liste Les attributs de la classe Liste doivent

permettre: le positionnement sur les diffrentes cellules de la liste

la dfinition du type d'information enregistre dans lacellule

Les mthodes de la classe doivent permettretous les traitements dcrits prcdemment(et plus...)


11/53


Dfinition de la classe Liste

classe ListeAttributs :

tte : rfrence {rfrence la cellule tte de liste}curseur : rfrence {rfrence la cellule courante}

rfrence : type dont le domaine de dfinition est l'ensemble des adressesmmoire.

- Valeur de lattribut tte (attribut curseur ) : adresse de la case mmoire oest stocke la cellule de tte de liste (cellule courante)

- Reprsentation graphique : une flche

cellule tte

curseur

listeAcellule


12/53


Dfinition d'une cellule

type Cellule = agrgatval : Info {information stocke dans une cellule}suivant : rfrence {rfrence une autre cellule}fin

Info : le type de l'information stocke; peut-tre un type de base (par

exemple, un entier) ou bien un type complexe (un agrgat)

Reprsentation graphique des cellules :

tte

curseur

val1 val2

val4

val3

listeA


13/53


Mthodes de la classe ListeMProcdure suivant(){place le curseur sur la cellule qui suit la cellule courante.Si le curseur tait sur la dernire cellule, il devient hors liste. Erreur si la liste

est vide ou si le curseur est dj hors liste.}paramtre (D/R) cible : Liste

exemple :

liste initiale L1 aprs L1.suivant()


14/53


Mthodes (suite)MProcdure premier(){place le curseur sur la premire cellule de la liste.Si la liste est vide, le curseur reste hors liste.}paramtre (D/R) cible : Liste

MProcdure dernier(){place le curseur sur la dernire cellule de la liste.Si la liste est vide, le curseur reste hors liste.}paramtre (D/R) cible : Liste

MFonction vide() retourne boolen{retourne vrai si la liste est vide, faux sinon}paramtre (D) cible : Liste


15/53


Mthodes (suite)MFonction horsListe() retourne boolen{retourne vrai si le curseur est plac hors liste ou si la liste est vide, faux sinon.}

paramtre (D) cible : ListeMFonction info() retourne Info{retourne la valeur enregistre dans la cellule courante.

Erreur si la liste est vide ou si le curseur est hors liste.}paramtre (D) cible : Liste

MProcdure affecter(val)

{affecte la valeur val la cellule courante.Erreur si la liste est vide ou si le curseur est hors liste.}paramtres (D/R) cible : Liste

(D) val : Info


16/53


Mthodes (suite)MProcdure insrerAvant(val){cre une nouvelle cellule, y affecte la valeur val, et l'insre avant la cellule courante. Le curseur est alors plac sur cette nouvelle cellule qui devient ainsi la nouvelle cellule courante. Si le curseur tait plac sur la tte, la nouvelle cellule devient la nouvelle tte.Si la liste tait vide, elle contient maintenant l'unique cellule qui

vient d'tre cre.Erreur si la liste tait non vide et le curseur hors liste.}paramtres (D/R) cible : Liste

(D) val : Info

Remarque :premier() suivi de insrerAvant(val) ajouter en tte


17/53


Insertion dune cellule : insrerAvant

cellule couranteinsrerAvant :en milieu de liste

1e donne 2e donne nouvelle

donne3e donne 4 e donne

nouvelle cellule

nouvelledonne

1e donne 2 e donne

cellule courante

nouvelle cellule couranteinsrerAvant :en dbut de liste

nouvelle cellule


18/53


Mthodes (suite)

MProcdure insrerAprs(val){cre une nouvelle cellule, y affecte la valeur val, et l'insre aprs

la cellule courante. Le curseur est alors plac sur cette nouvelle cellule qui devient ainsi la nouvelle cellule courante. Si liste tait vide, elle contient maintenant l'unique cellule qui vient d'tre cre. Erreur si la liste tait non vide et le curseur hors liste.}paramtres (D/R) cible : Liste

(D) val : Info

Remarque :dernier() suivi de insrerAprs(val) ajouter en queue


19/53


Insertion dune cellule : insrerAprsinsrerAprs :en milieu de liste

cellule courante

1e donne 2 e donne 3 e donne nouvelledonne 4e donne

nouvelle cellule

nouvelledonne

nouvelle cellule

1e donne 2 e donne 3 e donne

cellule courante

nouvelle cellule couranteinsrerAprs :en fin de liste


20/53


Mthodes (suite)MProcdure supprimer(){supprime la cellule courante. Le curseur est alors plac sur la cellule suivante qui devient ainsi la nouvelle cellule courante.

Si la cellule supprimer est la dernire cellule, le curseur devient hors liste. Si la cellule supprimer est la tte, la cellule suivante devient alors la nouvelle tte. Si la liste ne contenait qu'une seule cellule, la liste devient vide. Erreur si la liste est vide ou si le curseur est hors liste.}paramtre (D/R) cible : Liste

Remarquepremier() suivi de supprimer() supprimer en ttedernier() suivi de supprimer() supprimer en queue


21/53


Suppression dune cellulecellule courante, supprimer

1e donne 2 e donne 3 e donne 4 e donne 5 e donne

4e

donne1e donne 2 e donne 3 e donne

nouvelle cellule courante

cellule courante, supprimer

supprimer :en milieu de liste

supprimer :en fin de liste

Mth d ( i fi )


22/53


Mthodes (suite et fin)

MProcdure saisirListe(){Saisit des valeurs (de type Info), jusqu' une valeur d'arrt, et cre au fur et mesure autant de cellules que ncessaire, en y affectant les valeurs saisies. Le curseur est ensuite replac en tte de liste.}paramtre (R) cible : Liste

MProcdure afficherListe(){Affiche toutes les valeurs contenues dans la liste cible.}paramtre (D) cible : Liste

MProcdure supprimerTout(){supprime toutes les cellules de la liste (qui peut tre vide); la liste devient vide et le curseur devient hors liste.}paramtre (D/R) cible : Liste


23/53


Remarques importantes

Mthodes de deux types :- mthodes de base: leur dfinition ncessite de modifier les attributs

privs de la classe (sera fait en C++).- saisirListe() , afficherListe(), supprimerTout() : mthodes rajoutes

la classe pour rendre son utilisation plus commode; leur dfinitionpeut se faire laide des mthodes de base.

Rappel : les 3 acteurs de la programmationobjet :- programmeur concepteur de la classe- programmeur utilisateur de la classe- utilisateur de lapplication

Saisie d'une liste


24/53


Saisie d une liste

MProcdure saisirListe(){Saisit des valeurs (de type Info), jusqu' une valeur d'arrt (constante dfinie dans l'algorithme appelant), et cre au fur et mesure autant de cellules que ncessaire, en y affectant les valeurs saisies. Le curseur est ensuite replac en

tte de liste.}paramtre (R) cible : Listevariables uneVal : Info

cpt : entier

dbut saisir (uneVal) ; cpt 0tant que uneVal valStop faire

cpt cpt + 1

cible.insrerAprs(uneVal)saisir(uneVal)ftqcible.premier() {replace le curseur en tte}afficher(La nouvelle liste contient , cpt, cellules.)fin


25/53


Saisie d'une liste : simulation

Affi h d' li t


26/53


Affichage d'une liste

MProcdure afficherListe(){Affiche toutes les valeurs contenues dans la liste cible.}paramtre (D) cible : Listevariable copieCible : Listedbut

copieCible cible {copie de la cible,pour permettre modification du curseur}

copieCible.premier() {place le curseur en tte}tant que non copieCible.horsListe() faire

{arrt quand curseur hors liste}afficher( copieCible.info()) {rcupre la valeur de la cellule

courante et l'affiche}copieCible.suivant() {place le curseur sur la cellule

suivante}ftq

fin


27/53


Exemple dalgorithme (1)

Algorithme ManipListes1{Saisie et affichage dune liste.}constante (VALSTOP : entier) 0variable listeA : Listedbut

listeA.saisirListe()

afficher("Liste saisie : ")listeA.afficher()fin


28/53


Exemple de fonction utilisant la

classe liste (1)Fonction valMin(uneListe) retourne rel{retourne la plus petite valeur contenue dans une liste de rels suppose non

vide}paramtre (D) uneListe : ListeRel

l d f l l


29/53



classe liste (2)Fonction inverse(uneListe) retourne Liste{cre une nouvelle liste, en y affectant les valeurs de la liste uneListe mais dans

l'ordre inverse. La liste uneListe est suppose non vide}paramtre (D) uneListe : Liste

E l d f i ili l


30/53



classe liste (3)Procdure supprimerGlobal(uneVal, uneListe){supprime toutes les cellules de la liste uneListe qui contiennent la valeur uneVal. Replace le curseur en tte.}paramtre (D/R) uneListe : Liste

(D) uneVal : Info

E l d l i h (2)


31/53


Exemple dalgorithme (2)Algorithme ManipListes2{Exemple dalgorithme manipulant les listes.}constante (VALSTOP : entier) 0variables listeA, listeB, listeC : Liste

dbut listeA.saisir()afficher("listeA: ")listeA.afficher()

si non listeA.vide()alors listeB inverse(listeA)afficher("listeB contient les lments de la listeA en ordre

inverse : ")

listeB.afficher()supprimerGlobal(0, listeA)afficher("ListeA sans zros: ")listeA.afficher()

afficher("Plus petite valeur de listeA :" , valMin(listeA) )fsifin

Files et Piles


32/53

Algorithmique 4 : Files et Piles 31

Files et Piles

Retour sur la motivation:pourquoi des listes chanes? Possibilit de crotre ou de diminuer selon les besoins Facilit de rordonnancement des lments

Exemples :- placer le dernier lment en tte : changer trois rfrences

(tableau : tout dcaler)- insertion d'un nouvel lment : changer deux rfrences,

indpendamment de la longueur de la liste- effacement d'un lment

Mais : mal adaptes d'autres oprations- trouver le k-ime lment : parcours squentiel de k rfrences

(tableau : accs direct lindice k)

- trouver l'lment qui prcde un lment donn


33/53


Files et PilesDans beaucoup d'applications, on peut se contenter demodes d'accs trs restreints la structure de donnes

Avantages :

le programme n'a pas se proccuper de dtails de gestion(des rfrences, par exemple)

traitements plus simples et moins rigides(moins d'oprations)

Reprsentation d'une file


34/53


Reprsentation d une file

par une liste chaneAlice Julie Anna Pierre Daniel

cible.ajouterEnFin ("Daniel")

cible. supprimerEnTte()tte queue

- les ajouts se font en fin de file, les suppressions en tte de file

- seule linformation de la tte est accessible et traitable file dattente un guichet "premier rentr, premier sorti"

(FIFO : first in first out, queue)

Reprsentation d'une pile


35/53


Reprsentation d une pile

par une liste chaneAlice Julie Anna Pierre Daniel

cible.empiler("Alice")

cible.dpiler( )tte

- les ajouts comme les suppressions se font en tte de pile

- seule linformation de la tte est accessible et traitable pile dassiettes "dernier rentr, premier sorti"

(LIFO : last in first out, stack)

l l Fil


36/53


la classe File :les besoins

Attributs :- la tte et la queue, mais pas de curseur

Mthodes :

- infoTte() : retourne la valeur de linformation en tte de file

- vide() : indique si la file est vide

- ajouterEnFin(val) : ajoute une information en fin de file

- supprimerEnTte() : supprime (et retourne) linformation en tte de file- saisirFile()- afficherFile()

Dfinition de la classe File


37/53

36

Attributs :

tte : rfrence {rfrence la tte de file}queue : rfrence {rfrence la queue de file}Mthodes

MFonction infoTte() retourne Info{retourne la valeur enregistre dans la cellule de tte. Erreur si la file est vide}paramtre (D) cible : File

Mfonction vide() retourne boolen{retourne vrai si la file est vide, faux sinon}paramtre (D) cible : File

Mprocdure ajouterEnFin(val){Cre une nouvelle cellule, y affecte la valeur val, et l'insre aprs la dernire cellule .

Si file tait vide, elle contient maintenant lunique cellule qui vient d'tre cre.}paramtre (D/R) cible : File ; (D) val : Info

Mfonction supprimerEnTte() retourne Info{Supprime la premire cellule de la file et retourne la valeur quelle contient. Si la

file ne contenant qu'une seule cellule, la file devient vide. Erreur si la file est vide.}paramtre (D/R) cible : File


38/53


Mthodes (suite)MProcdure saisirFile (){Saisit des valeurs (de type Info), jusqu' une valeur d'arrt (constante dfinie dans l'algorithme appelant), et cre au fur et mesure autant de cellules que

ncessaire, en y affectant les valeurs saisies . }paramtre (R) cible : Filevariables uneVal : Info, cpt : entierdbut

saisir (uneVal) ; cpt 0tant que uneVal VALSTOP fairecpt cpt + 1cible.ajouterEnFin(uneVal)

saisir(uneVal)ftqafficher(La nouvelle file contient , cpt, cellules.)

fin


39/53


Mthodes (suite)

MProcdure afficherFile(){Affiche toutes les valeurs contenues dans la file cible.}

paramtre (D) cible : Filevariables uneVal : InfocopieCible : File

dbutcopieCible cibletant que non copieCible.vide() faire

uneVal copieCible. supprimerEnTte()afficher(uneVal)

ftqfin

la classe Pile :


40/53


la classe Pile :les besoinsAttributs :

- la tte mais pas de curseur

Mthodes :

- infoTte() : retourne la valeur de linformation en tte de pile

- vide() : indique si la pile est vide

- empiler(val) : ajoute une information en tte de pile

- dpiler() : supprime (et retourne) linformation en tte de pile- saisirPile()

- afficherPile()

Dfinition de la classe Pile


41/53

40

t o de a c asse eAttributs :

tte : rfrence {rfrence la tte de pile}Mthodes

MFonction infoTte() retourne Info{retourne la valeur enregistre dans la cellule de tte. Erreur si la pile est vide}paramtre (D) cible : Pile

Mfonction vide() retourne boolen

{retourne vrai si la pile est vide, faux sinon}paramtre (D) cible : Pile

Mprocdure empiler(val){Cre une nouvelle cellule, y affecte la valeur val, et l'insre en tte de pile. Si pile tait vide,

elle contient maintenant l'unique cellule qui vient d'tre cre.}paramtre (D/R) cible : Pile ; (D) val : Info

Mfonction dpiler() retourne Info{Supprime la premire cellule de la pile et retourne la valeur quelle contient. Si la pile ne contenant qu'une seule cellule, la pile devient vide. Erreur si la pile est vide.}paramtre (D/R) cible : Pile

Mthodes (suite)


42/53


Mthodes (suite)MProcdure saisirPile(){Saisit des valeurs (de type Info), jusqu' une valeur d'arrt (constante dfinie dans l'algorithme appelant), et cre au fur et mesure autant de cellules que ncessaire,en y affectant les valeurs saisies}paramtre (R) cible : Pilevariables uneVal : Info

cpt : entierdbut

saisir (uneVal) ; cpt 0tant que uneVal VALSTOP faire

cpt cpt + 1cible.empiler(uneVal)saisir(uneVal)

ftqafficher("La nouvelle pile contient", cpt, "cellules.")

fin

Mthodes (suite)


43/53


Mthodes (suite)

MProcdure afficherPile(){Affiche toutes les valeurs contenues dans la pile cible.}

paramtre (D) cible : Pilevariables uneVal : InfocopieCible : Pile

dbutcopieCible cibletant que non copieCible.vide() faire

uneVal copieCible. dpiler()afficher(uneVal)

ftqfin

Exemple 1 : Parenthsage


44/53


p gFonction bienForm(tab, nbr) retourne boolen{tab est un tableau de nbr parenthses. Retourne vrai si le parenthsage est cohrent}paramtres (D) tab: tableau [1, MAX] de caractres ; nbr : entiervariables cpt, marque, val : entier ; bienform : boolen

unePile : Pile {unePile est vide au dpart}dbut

cpt 1; marque 0 {jeton} ; bienform vraitant que bienform et cpt nbr faire

si tab[cpt] = '('alors unePile.empiler(marque)sinon si unePile.vide() alors bienform faux

sinon val unePile.dpiler() {on a alors ') }fsi

fsicpt cpt +1

ftqretourne (bienform et unePile.vide() )

fin

Parenthsage : simulation


45/53


Parenthsage : simulation

Exemple 2: valuation d'une


46/53


pexpression arithmtique

5 * (((9 + 8) * (4 * 6)) + 7)OBJECTIF:1. empiler (5)2. empiler (9)3. empiler (8)4. empiler( dpiler () + dpiler())

5. empiler (4)6. empiler (6)7. empiler (dpiler () * dpiler())8. empiler (dpiler () * dpiler())

9. empiler (7)10. empiler (dpiler () + dpiler())11. empiler (dpiler () * dpiler())12. afficher( dpiler())

valuation : simulation


47/53


valuation : simulation

Dabord : conversion infix postfix


48/53


Procdure infixVersPostfix(tab, nbr, tab_res, nbr_res)paramtres (D) tab : tableau [1, MAX] de caractres

(D) nbr : entier(R) tabRes: tableau [1, MAX] de caractres(R) nbrRes : entier

variables i, j : entier ; unePile : Piledbuti 0 ; j 0tant que ( i < nbr)

i

i + 1si oprateur(tab[i])alors unePile.empiler (tab[i])sinon si tab[i] = ')

alors j j + 1; tabRes[j] unePile .dpiler() ;sinon si nombre(tab[i]) alors j j+1 ; tabRes[j] tab[i]

fsifsi

ftqnbrRes jfin

Conversion : simulation


49/53


Conversion : simulation

Ensuite : calculer postfix


50/53


pFonction calculerPostfix (tab, nbr) retourne (entier)paramtres (D) tab: tableau [1, MAX] de caractres

(D) nbr : entiervariables i, res : entiers

unePile : Piledbuti 1; res 0tant que ( i nbr) faire

si tab[i] = '+' alors res unePile.dpiler() + unePile.dpiler()sinon si tab[i] = -' alors res unePile.dpiler() - unePile.dpiler()sinon si tab[i] = '*' alors res unePile.dpiler() * unePile.dpiler()sinon si nombre(tab[i]) alors res tab[i]

fsiunePile.empiler (res)i i+1

ftqretourne(unePile .dpiler())

fin

Calculer postfix : simulation


51/53


Calculer postfix : simulation

Retour lvaluation d'une


52/53


expression arithmtiqueAlgorithme valuation{affiche l'valuation dune expression arithmtique}

variables expInfix : tableau [1, MAX] de caractres {expression en criture infixe}expPostfix : tableau [1, MAX] de caractres {expression en criture postfixe}

nbrEltsInfix : entier {nombre dlments de lexpression infixe}nbrEltsPostfix : entier {nombre dlments de lexpression postfixe}

valeur : entier {rsultat de lvaluation}dbutsaisirExpInfix(expInfix, nbrEltsInfix )infixVersPostfix(expInfix, nbrEltsInfix , expPostfix , nbrEltsPostfix )valeur calculerPostfix(expPostfix , nbrEltsPostfix )afficher( Lvaluation de votre expression est , valeur)

fin


53/53


Fin Volume 4

Documents

coursAlgo_V4