Salut;
Comment declare-t-on une pile et une file sous python
comment empiler et depiler ? enfiler et defiler ?
merci d'avance
Salut;
Comment declare-t-on une pile et une file sous python
comment empiler et depiler ? enfiler et defiler ?
merci d'avance
Il n'y a pas de type pile ou file à proprement parler, mais il est facile d'utiliser une liste pour cela.
Par exemple:
pile = [1,2,3]
Empiler x => pile.append(x)
Dépiler => pile.pop()
file = [1,2,3]
Enfiler x => file.append(x)
Défiler => file.pop(0)
Mais il y a d'autres façons de faire.
Il existe bien une classe Queue dans le module du même nom, mais elle sert plutôt à communiquer entre threads...
Bonjour,
Simulation d'une pile avec une liste:
Déclaration:
Empilage de 'toto':
Code : Sélectionner tout - Visualiser dans une fenêtre à part pile=[]
Dépilage:
Code : Sélectionner tout - Visualiser dans une fenêtre à part pile.append('toto')
Ça, c'était une pile lifo, pour une pile fifo, il suffit de retirer le 1er élément (indice 0):
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 x=pile[-1] del pile[-1]
Je ne sais pas ce que tu entends par "file": tu pourrais préciser?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 x=pile[0] del pile[0]
Tyrtamos
[edit]: encore grillé... mais c'est lui qui a raison: pop est mieux
Un expert est une personne qui a fait toutes les erreurs qui peuvent être faites, dans un domaine étroit... (Niels Bohr)
Mes recettes python: http://www.jpvweb.com
merci de ta reponse dividee
dans ton exemple , il n'y a pas de difference entre une pile et une file ?
et aussi comment faire pour respecter les priorités ?
merci
Edit: je pense avoir compris :
c'est dans le depilage :
l.pop() pour une pile
et l.pop(0) pour une file
peut on utiliser des listes chainnées ?
j'ai defini la classe suivante :
avec ca on peut peut etre creer des files et des piles ?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 class Noeud: def __init__(self,valeur,suivant): self.val=valeur self.suiv=suivant def __repr__(self): return "Noeud de Valeur "+str(self.val)
Une idée de solution à adapter:
Dans une liste python, chaque élément peut être n'importe quoi, et pourquoi pas une liste.
Si l'élement est une liste, elle peut contenir l'indice de l'élément suivant en plus d'une valeur. On doit donc pouvoir chainer ces sous-listes dans un ordre différent de la liste de base.
Exemple:
Dans cet exemple simpliste, le 1er élément est L[1] (il faut le mémoriser dans une autre variable), qui renvoie à L[0], puis à L[3], puis enfin à L[2] qui est le dernier élément à qui on a attribué un suivant "None" qui peut être testé.
Code : Sélectionner tout - Visualiser dans une fenêtre à part L=[[3,'titi'],[0,'toto'],[None,'tutu'],[2,'tata']]
Mais, bon, gérer une pile avec cette liste chainée ne sera pas facile à coder...
Tyrtamos
Un expert est une personne qui a fait toutes les erreurs qui peuvent être faites, dans un domaine étroit... (Niels Bohr)
Mes recettes python: http://www.jpvweb.com
on peut aussi definir les deux classes:
et pour les arbres binaires :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 class noeudPile: def __init__(self,arbre,suivant=None) self.arbre=arbre self.suiv=suivant
maintenant le plus dur est de definir les operations sur ces nouveaux objets
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8 class noeudArbre: def __init__(self,valeur,gauche,droite): self.val=valeur self.filsgauche=gauche self.filsdroit=droite def __repr__(self): return "Noeud de valeur "+str(self.val)
a suivre ...
Salut;
j'ai finalement pu implementer ces structures sous python , neanmoins j'ai un petit probleme .
voila ce que j'ai fait (en m'inspirant de quelques algo d'un excellent livre !)
les fonctions empiler , depiler et affiche sont des fonctions definies sur les piles
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 from Piles import * #Soit E un ensemble dynamique.On souhaite representer une file f sur E #et implementer les operations Enfiler et Defiler a partir de 2 piles #p et q sur E et des operations d'empilement et de depilement.La file f #est representee par la paire de piles {p,q}. #pour enfiler un element e dans f , on l'empile dans p. #pour defiler f , on considere 2 cas : #1)si q n'est pas vide , alors on depile q. #2)sinon , on "vide" p dans q en depilant un a un les elements de p et en #les empilant au fur et a mesure dans q . Le dernier element depilé n'est #cependant pas empilé dans q car il s'agit de l'element a supprimer dans f. class File:#"file" avec f minuscule est un mot reservé ! def __init__(self,pile1,pile2): self.p=pile1 self.q=pile2 def afficheFile(f): affiche(f.p) affiche(f.q) def enfiler(f,x): return File(empiler(f.p,x),f.q) def defiler(f): if f.q!=None: return depiler(f.q) else: while f.p!=None: z=sommet(f.p) f.p=depiler(f.p) if f.p!=None: f.q=empiler(f.q,z)
Mon probleme est le suivant :
je souhaite que la fonction defiler(f) me retourne une file !
si je fais :
j'obtiens le message d'erreur suivant :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11 def defiler(f): if f.q!=None: return depiler(f.q) else: while f.p!=None: z=sommet(f.p) f.p=depiler(f.p) if f.p!=None: f.q=empiler(f.q,z) return File(f.p,f.q)
pouvez-vous me debloquer svp ?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 Traceback (most recent call last): File "/.../Files.py", line 50, in -toplevel- afficheFile(s) File "/.../Files.py", line 20, in afficheFile affiche(f.p) AttributeError: Noeud instance has no attribute 'p'
merci par avance
Bonjour,
C'est difficile de t'aider, parce qu'on a pas tout ton code.
Mais, a priori, le message d'erreur: "AttributeError: Noeud instance has no attribute 'p'" suggère que f n'est pas reconnu comme un objet ayant un attribut p.
Peut-être suffit-il de créer cet objet comme une classe:
A partir de là, si
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 class Truc(): p = None q = None
alors, f.p et f.q seront reconnus comme pouvant porter des valeurs. Par exemple:
Code : Sélectionner tout - Visualiser dans une fenêtre à part f = Truc()
Tyrtamos
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 f.p='toto' print f.p # affiche toto
Un expert est une personne qui a fait toutes les erreurs qui peuvent être faites, dans un domaine étroit... (Niels Bohr)
Mes recettes python: http://www.jpvweb.com
merci de ta reponse tyrtamos
voici le code complet :
contenu du fichier ListesChainees
celui du fichier Piles
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165 class Noeud: def __init__(self,valeur,suivant): self.val=valeur self.suiv=suivant def __repr__(self): return "Noeud de Valeur "+str(self.val) def copieRec(l): if l==None: return None else: res=copieRec(l.suiv) return Noeud(l.val,res) def affiche(l):#ou parcours if l!=None: print l.val affiche(l.suiv) def afficheBis(l): if l!=None: afficheBis(l.suiv) print l.val def parcoursIteratif(l): #cour est une variable qui effectue le parcours cour=copieRec(l) while cour!=None: print cour.val cour=cour.suiv def parcoursIter2(l): #on veut parcourir l jusqu'a l'avant dernier noeud #donc l ne doit pas etre vide ni reduite a un seul noeud #on a une variable de parcours des noeuds cour et une variable #de test d'arret test_courant if l==None or l.suiv==None: return "Erreur : l doit avoir au moins deux noeuds non vides !" else: cour=copieRec(l) test_courant=cour.suiv while test_courant!=None: print cour.val cour=cour.suiv test_courant=test_courant.suiv def somme(l): #somme des elements d'une liste simplement chainee if l==None: return 0 else: return l.val+somme(l.suiv) def produit(l): #produit des elements d'une liste simplement chainee if l==None: return 1 else: return l.val*produit(l.suiv) def recherche(l,x): #on renvoie l'adresse du premier noeud de la liste l #qui contient la valeur x s'il y en a , et None sinon if l==None: return None elif l.val==x: return l else: return recherche(l.suiv,x) def inserFin(l,x): if l==None: return Noeud(x,None) else: l.suiv=inserFin(l.suiv,x) return l def inserRec(l,x): #insertion de x dans l croissante de facon recursive if l==None: return Noeud(x,None) elif x<l.val: #insertion en tete return Noeud(x,l) else: l.suiv=inserRec(l.suiv,x) return l #l=la variable du parcours recursif def inserIter(l,x): if l==None: return Noeud(x,None) elif x<l.val: #insertion en tete return Noeud(x,l) else: #mise en place d'une variable de parcours insere_apres #apres laquelle on inserera #mise en place d'une varaible de test ref_test insere_apres=l ref_test=l.suiv fini=(ref_test==None) while not fini: if x>ref_test.val: #on avance insere_apres=insere_apres.suiv ref_test=ref_test.suiv if ref_test==None: fini=True else: #on vient de depasser l'endroit ou inserer fini=True #on fait l'insertion insere_apres.suiv=Noeud(x,ref_test) return l def fusionIter(l,m): #fusion de 2 listes croissantes sans valeur commune vl=l vm=m res=None #aucune liste epuisee while vl!=None and vm!=None: if vl.val<vm.val: res=Noeud(vl.val,res) #on avance dans l vl=vl.suiv else: res=Noeud(vm.val,res) #on avance dans m vm=vm.suiv #une au moins des 2 listes est epuisee while vm!=None or vl!=None: if vl!=None: res=Noeud(vl.val,res) #on avance vl=vl.suiv else: res=Noeud(vm.val,res) #on avance vm=vm.suiv return res def fusionRec(l,m): #on parcours les 2 istes de facon recursive #les tests d'arret d'abord if l==None and m==None: return None elif l!=None and m==None: return Noeud(l.val,fusionRec(l.suiv,m)) elif l==None and m!=None: return Noeud(m.val,fusionRec(l,m.suiv)) else:#les 2 listes sont non vides if l.val>m.val: return Noeud(m.val,fusionRec(l,m.suiv)) else: return Noeud(l.val,fusionRec(l.suiv,m))
voila pour ce qui est du code
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 from ListesChainees import * def acces(l,k):#acces au k-ieme elt de la liste chainee l if k==0: return l else: return acces(l.suiv,k-1) def sommet(p): return p.val def empiler(p,x): return Noeud(x,p) def depiler(p): if p==None: return None else: return p.suiv #l=Noeud(1,None) #for i in range(1,10): # inserRec(l,2**i) #m=Noeud(3,None) #for i in range(2,9): # inserRec(m,3**i) #d=fusionRec(l,m) #affiche(l)
sinon, j'ai pas reussi a surmenter le pb
toute suggestion sera la bienvenue
merci .
Curieusement, je ne trouve pas d'erreur à l'exécution!
J'ai pris le code de ton dernier message, j'ai tout mis dans la même page (en neutralisant "from ListesChainees import *", et j'ai dé-commenté les dernières lignes. Cela donne:
Etait-ce le résultat attendu?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 1 2 4 8 16 32 64 128 256 512
Tyrtamos
Un expert est une personne qui a fait toutes les erreurs qui peuvent être faites, dans un domaine étroit... (Niels Bohr)
Mes recettes python: http://www.jpvweb.com
Bonjour,
Tu peux aussi regarder du côté des deques.
"Etre conscient de la difficulté permet de l'éviter.."
Lao-Tseu.
Ca ne devrait pas plutôt être quelque chose comme ça :
?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 def defiler(f): if f.q!=None: return File(f.p,depiler(f.q)) else: while f.p!=None: z=sommet(f.p) f.p=depiler(f.p) if f.p!=None: f.q=empiler(f.q,z) return File(f.p,f.q)
Sinon une remarque plus générale: ton implémentation ressemble à une file persistante (tu crées une nouvelle file à chaque modification) mais n'en est pas une (tu modifies malgré tout les objets File). De deux choses l'une: soit tu ne cherches pas à implémenter une file persistante, et dans ce cas ta structure de données est inutilement compliquée, soit tu cherches à la faire, mais dans ce cas tu ne devrais jamais modifier l'état de tes objets...
Par "inutilement compliquée", je voulais dire qu'il est beaucoup plus simple d'utiliser une liste comme on te l'avait suggéré dans les premières réponses:
En style OO, sans doute préférable en Python:
Ou, si tu y tiens vraiment, en style "type de donnée abstrait":
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12 class File: def __init__(self): self._file = [] def empiler(self, x): self._file.append(x) def tete(self): return self._file[0] def depiler(self): self._file.pop(0)
Remarque qu'ici enfiler et defiler ne renvoient pas de nouvelle file, mais modifie la file existante.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8 File = list # c'est pas très propre car les méthodes de list seront visibles, # mais c'est l'idée. def enfiler(f,x): f.append(x) def defiler(f): f.pop(0) def tete(f): return f[0]
L'intérêt de renvoyer une nouvelle file à chaque fois, comme tu le fais, serait de pouvoir continuer à utiliser les anciennes sans qu'elles soient modifiées par les opérations suivantes. Cela peut être utile dans certains cas, par exemple cela permet de partir de la même file dans plusieurs thread différents sans avoir à craindre qu'un thread modifie une file utilisée par un autre thread (vu qu'une file n'est jamais modifiée, on en retourne toujours une nouvelle).
Le problème, c'est que ça ne fonctionne pas avec ton implémentation:
Une autre remarque, au passage: ton constructeur de File expose son implémentation; pourquoi devoir créer un file en lui passant deux piles ? Le programmeur qui utilise ta file ne devrait pas avoir à se préoccuper cela.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 >>> f1 = File(None, None) >>> f2 = enfiler(f1,1) >>> f2.p,f2.q (Noeud de Valeur 1, None) >>> f3 = defiler(f2) >>> f3.p, f3.q (None, None) >>> f2.p, f2.q (None, None) <-- le problème est ici; f2 est modifié
Il suffit de faire en sorte que defiler ne modifier pas son argument pour obtenir une file persistante:
Maintenant:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12 def defiler(f): if f.q!=None: return File(f.p,depiler(f.q)) else: fp = f.p fq = None while fp != None: z=sommet(fp) fp=depiler(fp) if fp!=None: fq=empiler(fq,z) return File(fp,fq)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 >>> f1 = File(None, None) >>> f2 = enfiler(f1,1) >>> f2.p,f2.q (Noeud de Valeur 1, None) >>> f3 = defiler(f2) >>> f3.p, f3.q (None, None) >>> f2.p, f2.q (Noeud de Valeur 1, None) <-- ok
merci dividee
merci également a tous ceux qui ont participé
à +
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager