Td corrigé 2 Les piles - BigBozoid pdf

2 Les piles - BigBozoid

Structure séquentielle : listes (cas particulier des piles et des files). Structures ... Structures associatives à tableaux associatifs, tableaux de hachage. .... Donc, par exemple, la liste (1, 3, 2, 5) est notée en notation formelle : (1, (3, (2, (5, ( ))))).




part of the document



booléen
Calcul
Fonction DuréeEnJour (E d1, d2 : date) : entier
Service
Fonction Lendemain (E d : date) : date
Remarque : Un type abstrait de données ressemble donc fortement à une classe (voir cours de C/C++). C’est d’ailleurs par des classes qu’il faudra de préférence définir et manipuler les types abstraits de données.
Historique
Historiquement, les types abstraits de données désignent plutôt des structures abstraites de données :
Structure linéaire à accès direct : tableaux
Structure séquentielle : listes (cas particulier des piles et des files)
Structures arborescente : arbres binaires, arbres quelconques
Structures relationnelles : graphe
Structures associatives à tableaux associatifs, tableaux de hachage.
Nous allons essayer de voir tous ces types abstraits de données. Les tableaux ont déjà été abordés, voyons tout d’abord ce que sont les piles et les files.
Les piles
Une pile est une suite ordonnée d’éléments dans laquelle l’ajout ou la suppression d’éléments se fait toujours du même côté.
Pour tous les exercices suivants, on se définit les actions et fonctions de bases sur les piles définies sur la fiche III : Types Abstraits de Données.
Exercice 1
a) Ecrire une fonction qui prend en entrée une pile et retourne le nombre d’éléments de cette pile.
b) Ecrire une fonction qui prend en entrée une pile et qui sort une autre pile, identique à la pile d’entrée.
c) Faire des variantes de b) en écrivant une action qui prend en entrée sortie une pile et qui sort une pile en prenant un élément sur deux

a)
Fonction NombreElement (E p : Tpile ) : entier
Var : n : entier
Début
N=0
Tant que ( !Pilevide (p)) faire
N( N+1
Dépiler(p)
Retourner N
Fin

b)
Action clone (ES p1 : Tpile, p3 : Tpile)
Var : p2 ; p3 : Tpile
Début
CréerPile(p2)
CréerPile(p3)
Tant que ( !PileVide(p1))
Empiler (p2, ValeurSommet(p1))
Dépiler(p1)
Tant que ( !PileVide(p2))
Empiler(p3, ValeurSommet(p2))
Empiler(p1, ValeurSommet(p2)) // car p1 est en ES et on veut la récupérer dans le même état.
Dépiler (p2)
Fin

c)
Action UnSurDeux (ES p1 : Tpile, p3 : Tpile)
Var : p2, p3 : Tpile cpt : entier
Début
Cpt=0 ;
CréerPile(p2) ;
CréerPile(p3) ;
Tant que ( !PileVide(p1))
Si cpt%2=0 alors Empiler (p2, ValeurSommet(i1))
Dépiler(p1)
Cpt++
Tant que ( !PileVide(p2))
Empiler(p3, ValeurSommet(p2))
Dépiler(p2) ;
Fin
Evaluation d’expressions arithmétiques avec les piles

Expressions infixées
Dans l’expression infixées, l’opérateur (+ - * / ) est placé entre ses 2 opérateurs. Le problème de l’expression infixée, c’est qu’en lisant au fur et à mesure, on n’a pas une vision des priorité sur les opérations.
Exemple : 5*3+2 ( 5+3*2
Pour simplifier, dans un premier temps, on peut utiliser les expressions complètement parenthésées (ECP) : Un nombre, ou une variable est une ECP. Si ( est un opérateur et x et y sont des ECP alors (x*y) est un ECP.
Dans une ECP, on n’a donc plus besoin d’introduire les priorités entre opérateurs car les parenthèses définissent ces priorités.
Voir et faire tourner la fonction donnée évalECP (feuille ci jointe) sur ((((A+B)*C)/D)-(E-F)) avec l’environnement a=5 ; B=3 ; C=6 ; D=2 ; E=5 ; F=3.
Expressions postfixées
Une expression postfixée (EP) : Une variable, ou un nombre est une EP. Si (est un opérateur et x et y deux EP alors xy( est une EP.
Exemple : 2+3 ( 2.3*
Le but est de mettre au point un algorithme permettant d’évaluer une EP (comme évalECP du 2.2.1)
Remarque : Dans l’expression postfixée, l’ordre des opérateurs donne l’ordre dans lequel on doit faire les calculs (dès que l’on a un opérateur, on sait qu’il faut faire un calcul et qu’il est dans l’ordre)
Idée de l’algorithme d’évaluation :
Tant que l’on tombe sur une opérande, on empile sa valeur. Dès que l’on tombe sur un opérateur, on dépile les deux dernières opérandes, on effectue le calcul et on place le résultat dans la pile. A la fin, la seule valeur présente dans la pile est le résultat de l’expression qu’il fallait évaluer.
Exercice : faire l’algorithme de evalEP
Fonction evalEP ( E : EP : tableau[MAX] de caractères) : réel
Var : i entier ; vald, valg, résultat : réels ; p : Tpile)
Début
CréerPile(p)
I(0
tant que EP[i] ‘%’ faire
si variable(EP[i]) alors empiler(p, ValeurSommet(eP[i])
sinon
vald(ValeurSommet(p)
dépiler(p)
valg(ValeurSommet(p)
dépiler(p)
empiler(p, oper(valg, EP[i], vald)
i++
fin tant que
résultat(ValeurSommet(p)
dépiler(p)
retourner(résultat)
fin
Passage d’une écriture infixée à une écriture postfixée
Par exemple, on veut passer de l’expression : a*b + c/(d*e) à son expression postfixée ab*cde*/+. Les opérandes apparaissent dans le même ordre dans les deux expressions, donc il n’est pas besoin de les stocker dans un temporaire. En revanche, on va stocker les opérateurs dans une pile en faisant attention de les sortir au bon moment.
Entrée EISortie EPPileLit aEcrit avideLit *aEcrit *Lit bEcrit b : ab*Lit +ab*Compare + et * : * (qui est dans la pile) est plus fort, on le sort de la pile et on l’écrit dans EP, puis on met + dans la pileLit cécrit c : ab*c+Lit /ab*cCompare + et / : + (qui est dans la pile) est plus faible, on ajoute alors / à la pileLit (ab*cOn ajoute ( à la pile.Lit décrit d : ab*cd+ / (Lit *ab*cdLes deux opérandes sont identiques : on empile : + / ( *Lit eécrit e : ab*cde + / ( *Lit )écrit * : ab*cde*On sort tous les opérateurs de la pile qui sont après ( : donc ici on enlève * et on le met dans EPab*cde*puis on écrit tous les opérateurs de la pile en ne mettant pas (ab*cde*/+c’est le résultat final. La pile est vide. 
Exercice : Faire l’algorithme de changement d’écriture (d’une expression infixée à une expression postfixée) en vous aidant du tableau explicatif de fonctionnement si dessus.
Les files
La notion de file en algorithme correspond à la notion de file d’attente. Une file est donc un ensemble d’éléments ordonnés. Toute insertion se fait à la fin de la file, et toute suppression se fait en début de file. Seule la valeur en début de file est accessible.
Une file est donc une structure First In – First Out (FIFO)
Les primitives
Voir la fiche ASD III : « les types abstraits de données »
Un exemple
Ecriture d’une action qui retourne la file inverse d’une file passée en entrée sortie.
Action FileInverse (ES F : Tfile)
Var : p : Tpile
Début
CréerPile (p)
Tant que ( !PileVide (p))
Empiler (p, valeurPremier(F))
Défiler (F)
Tant que ( !PileVide(p))
Enfiler (F, valeurSommet(p))
Dépiler (p)
Fin
Les listes
Généralités
Une liste est une suite d’éléments placés dans un certain ordre. (exemple : (1, 3, 2, 5) (3, 1, 2, 5) (1, 2, 3, 5) sont 3 listes différentes. On peut ajouter ou supprimer un élément en n’importe quelle position dans la liste avec conservation des positions respectives des autres éléments.
On se donne un moyen de parcourir la liste : pour savoir quel est le premier élément, ou bien, étant donné un élément, savoir aller au suivant.
Définitions formelles
Une liste est soit la liste vide (notée ‘( )’), soit un couple composé d’une valeur et d’une liste (notée ‘(valeur, liste)’). Donc, par exemple, la liste (1, 3, 2, 5) est notée en notation formelle : (1, (3, (2, (5, ( ))))).
Une liste est composé d’un premier élément et d’une sous liste qui est la liste des suivant (elle même composée d’un premier élément et d’une sous liste, et ainsi de suite).
Primitives
Voir la feuille ASD III sur les types abstraits de données.
En quoi les primitives peuvent être utiles ?
Pour savoir si une liste (ou une sous liste) est vide
Etant donné une liste, on peut obtenir la valeur du premier élément, ou bien obtenir la liste des suivants
L’insertion en-tête d’un élément se fait par création d’une nouvelle liste à partir d’un couple.
L’insertion en milieu de liste se fait par remplacement de la liste des suivants
Primitives de manipulation de listes
Pour cela, on se donne des primitives de manipulation de liste. Voir fiche ASD III types abstraits de données.
Exemple
Affichage des éléments d’une liste :
Action Affichage (E L : Tliste)
Var : Adr : Tadresse
Début
Adr ( AdressePremier(L)
Tant que Adr != NULL faire
Ecrire (ValeurElement(L, Adr))
Adr(AdresseSuivant(L, Adr)
Fin
Exercices sur les listes
Exercice 1
On suppose qu’on a en entrée une liste de TEtudiants, dont un champ s’appelle note. Calculer la moyenne de la classe (on suppose que la liste est non vide).
Fonction Moyenne (E L : Tliste) : réel
Var : Adr : Tadresse
Som, cpt : réel
Etd : TEtudiants
Début
Adr(AdressePremier(L)
Som(0
Cpt(0
Tant que Adr != NULL faire
Etd(ValeurElement(L, Adr)
Som(Som+Etd.note
Cpt++
Retourner (Som/Cpt)
Fin
Exercice 2
On suppose qu’on a en entrée une liste triée par ordre croissant d’entiers. Ecrivez l’action qui rajoute un entier donné en paramètre à cette liste de façon à ce qu’elle soit encore triée après insertion.
Action InsertTrié (ES L : Tliste, E Nb : entier)
Var : Adr, Adrpr : Tadresse
Début
Adr(AdressePremier(L)
Si (Adr==NULL ou ValeurElement(L, Adr)(n)
InsérerEnTete(L, Nb)
Sinon
Tant que (AdresseSuivant(L, Adr) ( NULL et n > ValeurElement(L, AdresseSuivant(L, Adr)) )
Adr(AdresseSuivant(L, Adr)
InsérerAprès(L, Nb, Adr)
Fin
Quelques astuces pour des algorithmes simples avec les listes
Pour retourner l’adresse de l’élément au milieu de la liste, on déplace deux adresses, d’adresse en adresse, avec une adresse qui se déplace une fois sur deux… Ainsi, quand l’une des adresses arrive à la fin de la liste, l’autre adresse est au milieu. On a alors l’adresse de l’élément au milieu.
Si la liste est triée (des réels par exemple) on obtient donc (en un seul passage de liste et sans avoir à connaître la longueur de la liste) la médiane de la liste.
Pour l’exercice 2 : dans ce type d’exercice, on est obligé de vérifier une condition, suivant que l’on est en début de liste ou non. Pour éviter cela, on peut insérer en début de liste un élément fictif, puis effectuer les opérations à partir du deuxième élément. En fin de calcul, on supprime cet élément fictif.
Exercice 3
Proposer un algorithme qui fait la concaténation de deux listes (en entrée) retournant une liste (en sortie). Par exemple, si l’on a les listes (3, 7, 2) et (5, 4) on obtient la liste (3, 7, 2, 5, 4).
Proposer ensuite un algorithme séparant une liste en deux. Etant donné une liste en entrée, un élément sur deux va dans la première liste et un élément sur deux va dans la deuxième liste.
Faire une action de fusion de listes supposées triées par ordre croissant en une troisième liste triée.
Faire, en utilisant au choix les trois actions précédentes une action de tri fusion qui étant donné deux listes en entrée (pas forcément triées) retourne une liste triée.
Action concaténation (E L1 : Tliste, E L2 : Tliste, S L : Tliste)
Var : Adr, AdrS : Tadresse
Début
CréerListe (L)
InsérerEnTete (L,  % )
AdrS ( AdressePremier(L)
Adr( AdressePremier(L1)
Tant que Adr `"NULL faire
InsérerAprès (L, ValeurElement(L1, Adr), AdrS)
Adr( AdresseSuivant (L1, Adr)
AdrS( AdresseSuivant (L, AdrS)
Adr(AdressePremier(L2)
Tant que Adr `"NULL faire
InsérerAprès (L, ValeurElement(L2, Adr), AdrS)
Adr(AdresseSuivant(L2, Adr)
AdrS(AdresseSuivant(L, AdrS)
SupprimerEnTete(L)
Fin

Action Séparer (E L : Tliste, S L1 : Tliste, S L2 : Tliste)
Var : Adr, Adr1, Adr2 : Tadresse ; B : booléen
Début
CréerListe(L1)
CréerListe (L2)
B(true
InsérerEnTete(L1, E)
InsérerEnTete(L2, E)
Adr1(AdressePremier(L1)
Adr2(AdressePremier(L2)
Adr(AdressePremier(L)
Tant que Adr`"NULL faire
Si B alors
InsérerAprès(L1, ValeurElement(L, Adr), Adr1)
Adr1(AdresseSuivant(L1, Adr1)
Sinon
InsérerAprès(L2, ValeurElement(L, Adr), Adr2)
Adr2(AdresseSuivant(L2, Adr2)
B( !B
Adr(AdresseSuivant(Adr)
SupprimerEnTete(L1)
SupprimerEnTete(L2)
Fin

Action Fusion (E L1 : Tliste, E L2 : Tliste, S L : Tliste)
Var : Adr1, Adr2, Adr : Tadresse
Début
CréerListe(L)
InsérerEnTete(L, E)
Adr(AdressePremier(L)
Adr1(AdressePremier(L1)
Adr2(AdressePremier(L2)
Tant que (Adr1`"NULL et Adr`"NULL)
Si ValeurElement(L1, Adr1) v alors Adr ( AdresseFilsGauche(A, Adr)
Sinon Adr ( AdresseFilsDroit(A, Adr)
Retourne Adr
Fin
Efficacité des requêtes classiques :
Si l’arbre n’est pas équilibré, les recherches peuvent prendre jusqu’à N opérations
Dans un arbre équilibré, la longueur des branches est de [log2 N]+1
Donc, comment réaliser un arbre de recherche équilibré ? En utilisant le théorème suivant : A tout ensemble d’actions, il existe un arbre équilibré. Comment ? On fait des rééquilibrages progressifs, par rotation de racines.
PAGE 


PAGE 10



Les types abstraits de données


 :