Programme officiel
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Listes, piles, files : structures linéaires. Dictionnaires, index et clé. | Distinguer des structures par le jeu des méthodes qui les caractérisent. Choisir une structure de données adaptée à la situation à modéliser. Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire. |
On distingue les modes FIFO(first in first out) et LIFO (last in first out) des piles et des files. |
Information
Une pile est fondée sur le principe: Last In First Out
- creer_pile() -> Pile: crée une pile vide
- est_vide(p: Pile) -> bool: renvoie True si la pile est vide, False sinon.
- empiler(p: Pile, e: T) -> None: ajoute un élément e au sommet de la pile.
- depiler(p: Pile) -> T: retire et renvoie l’élément du sommet de la pile.
class Element:
def __init__(self, d: int, s: object):
self.donnees = d
self.successeur = s
class Pile:
def __init__(self):
self.sommet=None
def est_vide(self)->bool:
return self.sommet is None
def empiler(self, e:int)->None:
self.sommet=Element(e,self.sommet)
def depiler(self)->int:
if not self.est_vide():
retour=self.sommet.donnees
self.sommet=self.sommet.successeur
return retour
def __str__(self) -> str:
affiche=""
last = self.sommet
while last is not None:
# affichage vertical: \n = saut de ligne
affiche += str(last.donnees) + "\n\u2193\n"
last = last.successeur
return affiche + "fin"
p = Pile()
p.empiler(3)
p.empiler(9)
p.empiler(4)
print(p)
print("dépile:", p.depiler())
print(p)
Information
Une file est fondée sur le principe: First In First Out
- creer_file() () -> File: crée une file vide
- est_vide(f: File) -> bool: renvoie True si la file est vide, False sinon.
- enfiler(f: File, e: T) -> None: ajoute un élément e à la fin de la File.
- defiler(f: File) -> T: etire et renvoie l’élément du début de la file.
class Element:
def __init__(self, d: int, s: object):
self.donnees = d
self.successeur = s
class File:
def __init__(self):
self.premier = None
self.dernier = None
def est_vide(self) -> bool:
return self.premier == None
def enfiler(self, e: int) -> None:
nouveau = Element(e, None)
if self.est_vide():
# 1 seul élément: le premier est le dernier
self.premier = nouveau
else:
# le dernier devient avant-dernier
self.dernier.successeur = nouveau
# le nouveau devient dernier
self.dernier = nouveau
def defiler(self) -> int:
if not self.est_vide():
res = self.premier.donnees
self.premier = self.premier.successeur
return res
def __str__(self):
c = self.premier
s = ""
while not c is None:
s = s + str(c.donnees)+"|"
c = c.successeur
return "\u2BA4|" + s + "\u2BA0"
from random import randint
maFile = File()
for i in range(6):
maFile.enfiler(randint(1, 20))
print(maFile)
for i in range(6):
maFile.defiler()
print(maFile)
La programmation orientée objet est un choix d’implémentation possible. Il n’est pas unique.
class Maillon:
"""
Crée un maillon de la liste chaînée
"""
def __init__(self, val: int, suiv: object):
self.valeur = val
self.suivant = suiv
class Liste:
"""
Crée une liste chaînée
"""
def __init__(self):
# selt.tete référence un Maillon
self.tete = None
Les méthodes ajoutées à l’objet Liste implémenteront l’interface proposée.
class Liste:
"""
Crée une liste chaînée
"""
def __init__(self):
# selt.tete référence un Maillon
self.tete = None
def est_vide(self) -> bool:
return self.tete is None
def ajouter(self, val: int) -> None:
self.tete = Maillon(val, self.tete)