Corrigé des exercices PDF Corrigé des exercices élément

1.5 PILEET FILE . Les exercices 1 à 1 6 20 à 2 5

SUJET + CORRIGE

16 déc. 2011 Exercice 1 (Files à l'aide de Piles (8 points)) ... la file est pleine si la pile de queue est pleine (c'est un choix).

Algorithmique et structures de données en langage C 2ème année

et fonctions pour manipuler des listes piles

Corrigé du TP sur les piles Langage C : Compilation séparée

typedef struct SPile *Pile;. Pile pileVide();. Pile pileAjouter(Pile p Element e);. Pile pileSupprimer(Pile p);. Element *pileSommet(Pile p);.

Exercice 1 : piles et files

séance n°9 - corrigé. Exercice 1 : piles et files. Un système muti-tâches peut exécuter n tâches en quasi parallélisme. Chaque tâche est munie d'une.

Algorithmique et Structures de données 1 Piles

type_File = File de objet; définis en cours. 1 Piles. Exercice 4.1. Evaluer `a l'aide des primitives du type abstrait Pile de objet la var C:car;.

Untitled

Exercice 6: Résolution d'un labyrinthe. Corrigé. Annexe. Correction du programme de parenthésage. Enoncé. Correction. PC - Lycée Thiers. TD 5: Les piles.

Corrigé de la série de TD N 03 de Structures de Données

Correction de l'exercice n. ?. 4. Soit P une pile d'entiers. Écrire les fonctions pour determiner: a/ Le nombre d'éléments. b/ La valeur maximale. c/ La

Corrigé des exercices

Corrigé des exercices élément de la file celui-ci est extrait de la pile b à moins que celle-ci ne soit vide

TD – Piles et files - Corrigé

TD – Piles et files. Corrigé. Piles. Exercice N°1 – Copie d'une pile Sans surprise ce tableau illustre clairement le fait que c'est la conservation de ...

Contrôlez l'ajout d'éléments avec les piles et les files

Exercice N°1 – Copie d’une pile Ecrire une fonction stack_copy(s) recevant une pile (s) comme argument et renvoyant une copie s2 de s Attention la pile s doit (bien sûr) être conservée ! Evaluer le coût en mémoire et le nombre d’opérations de la fonction

Chapitre 11 Piles et files - Nantes Université

DVD-MIAGE Piles et Files Algorithmique Chapitre 11 Page 1 / 6 Chapitre 11 Piles et files 1 Piles Une pile est une liste chaînée d'informations dans laquelle : Un élément ne peut être ajouté qu'au sommet de la pile Un élément ne peut être retiré que du sommet de la pile

Algorithmique et Structures de donn ees - LaBRI

fonction essai_file():File de car; var F: File de car; var C:car; debut creerFile(F); enfiler(F'A'); enfiler(F'B'); enfiler(F'C'); defiler(F); C=valeur(F); enfiler(F'a'); defiler(F); enfiler(F'b'); enfiler(FC); retourner(F); fin 4 6

Chapitre 1informatique commune

Corrigé des exercices

Exercice 1Lorsqu"on définit une pile à l"aide d"un tableau statique, on maintient un pointeur vers le première

case disponible du tableau, qui représente le sommet de la pile :123456 q classPile: définition d "unepile à l "aided "untableau """ def__init__(self, n): self.lst = [None]*n self.size = n self.q = 0 defempty(self): returnself.q == 0 deffull(self): returnself.q == self.size defpush(self, x): ifself.full(): raiseValueError("pilepleine ") self.lst[self.q] = x self.q += 1 defpop(self): ifself.empty(): raiseValueError("pilevide ") self.q= 1 returnself.lst[self.q]

Exercice 2

La première pile (la pilea) reçoit les éléments qu"on ajoute à la file. Lorsqu"on veut supprimer un

élément de la file, celui-ci est extrait de la pilebà moins que celle-ci ne soit vide, auquel cas les éléments de la

pileasont tout d"abord transférés dans la pileb.classFile:

Définition

d "unefile à l "aidede deux piles """ def__init__(self): self.a = Pile() self.b = Pile() defempty(self): returnself.a.empty()andself.b.empty() defadd(self, x): self.a.push(x) deftake(self): ifself.empty(): raiseValueError("filevide ")Jean-Pierre Becirspahic

1.2informatique communeifself.b.empty():

while not self.a.empty(): self.b.push(self.a.pop())

returnself.b.pop()Puisque la méthodeaddrevient à appliquer la méthodepushà la pilea, sont coût est unO(1). En revanche, le

coût de la méthodetakedépend de l"état de la pileb: si celle-ci n"est pas vide le coût est unO(1), si elle est

vide le coût est unO(n)(coût du transfert de la pileavers la pileb). Cependant on peut observer que le coût

amortide la méthodetakeest unO(1), car chaque élément de la file ne subit que trois opérations, toutes de

coût constant : ajout dans la pilea, transfert vers la pileb, suppression de la pileb.

Exercice 3

On empile les éléments dans celle des deux files qui est non vide (ou n"importe laquelle si les

deux sont vides); appelons-laa. Lorsqu"on veut dépiler un élément, on transfère les éléments de la fileavers la

fileb, à l"exception du dernier élément, qui est renvoyé.classPile: définition d "unepile à l "aidede deux files """ def__init__(self): self.a = File() self.b = File() defempty(self): returnself.a.empty()andself.b.empty() defpush(self, x): ifself.b.empty(): self.a.add(x) else: self.b.add(x) defpop(self): ifself.empty(): raiseValueError("listevide ") ifself.b.empty(): x = self.a.take() while not self.a.empty(): self.b.add(x) x = self.a.take() else: x = self.b.take() while not self.b.empty(): self.a.add(x) x = self.b.take() returnx

Le coût de la méthodepushest à l"évidence unO(1): on se contente d"insérer l"élément dans une des deux files.

En revanche, le coût de la méthodepopest systématiquement un(n), correspondant au transfert d"une file

vers l"autre. Exercice 4Commençons par définir le notion de cellule :classCell: définition d "unecellule avec deux pointeurs """ def__init__(self, x): self.val = x self.next = None self.pred = None

Les opérations d"ajout et de suppression dans une file doivent tenir compte du cas particulier de la file vide

(pour l"ajout) et de la file à un seul élément (pour la suppression).

Corrigé des exercices1.3classFile:

définition d "unefile par liste doublement chaînée """ def__init__(self): self.queue = None self.tete = None defempty(self): returnself.teteisNone defadd(self, x): c = Cell(x) ifself.empty(): self.tete = c else: c.next = self.queue self.queue.pred = c self.queue = c deftake(self): ifself.empty(): raiseValueError("filevide ") c = self.tete ifc.predisNone: self.tete = None self.queue = None else: self.tete = c.pred

returnc.valPour ajouter un élément, on crée une nouvelle cellule puis on modifie les pointeurs nécessaires pour préserver

la structure de liste doublement chaînée.

Pour supprimer un élément, on récupère la cellule en tête de liste puis là encore on modifie les pointeurs

nécessaires pour préserver la structure de liste doublement chaînée. Exercice 5Nous allons avoir besoin de la classeCelldéjà définie en cours :classCell: définitionquotesdbs_dbs2.pdfusesText_3

[PDF] Corrigé des exercices Corrigé des exercices élément

Langage C : énoncé et corrigé des exercices IUP GéniE

SUJET + CORRIGE

Algorithmique et structures de données en langage C 2ème année

Corrigé du TP sur les piles Langage C : Compilation séparée

Exercice 1 : piles et files

Algorithmique et Structures de données 1 Piles

Untitled

Corrigé de la série de TD N 03 de Structures de Données

Corrigé des exercices

TD – Piles et files - Corrigé

Contrôlez l'ajout d'éléments avec les piles et les files

Chapitre 11 Piles et files - Nantes Université

Algorithmique et Structures de donn ees - LaBRI

Chapitre 1informatique commune

Corrigé des exercices

Exercice 2

Définition

1.2informatique communeifself.b.empty():

Exercice 3

Corrigé des exercices1.3classFile: