Pour ranger ses affaires, on choisit le bon contenant : une pile d'assiettes, une file d'attente, un agenda.
En informatique, c'est pareil : selon ce que l'on veut faire des données, une organisation sera bien plus commode qu'une autre.
À faire dans le cahier.
L'éditeur contient une classe Truc et quelques lignes qui l'utilisent.
Tu n'as pas besoin de comprendre le code de la classe : on va seulement observer comment se comporte un objet Truc quand on l'utilise.
t. Dans la console sous l'éditeur, tape ensuite plusieurs fois t.enleve(). Quel prénom sort à chaque appel ? Ajoute d'autres prénoms avec t.ajout(…), enlève-en encore, puis énonce la règle.Truc. Où rencontre-t-on ce fonctionnement dans la vie courante ?Truc.
En informatique, que cela soit pour les ordinateurs personnels, les smartphones, les serveurs ou tout autre matériel numérique, nos programmes manipulent un ordre considérable de données
Les programmes actuels structurent leurs données dans les algorithmes.
Il y a plusieurs façons de structurer les données au niveau logiciel.
Avant de ranger des données, il faut se poser une question : leur nombre peut-il changer en cours de route ?
None en Python.Pense au parking du lycée : il a 5 places, ni plus ni moins, qu'elles soient libres ou occupées : c'est une structure statique. Une file d'attente à la cantine, elle, s'allonge et se raccourcit sans cesse : c'est une structure dynamique.
Pourquoi ne pas tout faire en dynamique ? Parce que la souplesse a un prix : une structure statique réserve sa place en mémoire une fois pour toutes, c'est simple et rapide. Une structure dynamique oblige la machine à trouver de la place à chaque fois qu'elle grandit (on le verra avec les tableaux).
Dans l'animation, le tableau statique t naît avec 4 cases vides (None), la liste
l naît vide. On range les mêmes valeurs dans les deux, puis on en retire : observe leur taille.
Pour savoir si une structure est linéaire, place-toi sur un élément et demande-toi : quel est l'élément juste avant ? Et celui juste après ?
Dans l'animation, cinq structures se présentent l'une après l'autre. Pour chacune, on observe un élément à la fois (en jaune), avec son prédécesseur (en vert) et ses successeurs (en bleu), puis on la range dans la bonne colonne.
Ici, la question est : pour atteindre un élément précis, faut-il passer par les autres ?
l[4] donne tout de suite l'élément d'indice 4 d'une liste, même si elle en contient un million.La classe Truc de l'activité est non indexée : on ne peut obtenir que le premier prénom
entré. Pour atteindre le 4e, il faut d'abord passer par les trois premiers.
Dans l'animation, une structure indexée et une structure non indexée contiennent les mêmes valeurs. On leur demande le même élément : compte les étapes de chacune.
Un tableau est une suite finie d'éléments, repérés par un indice entier allant de 0 à n − 1, auxquels on accède directement grâce à cet indice. C'est donc une structure linéaire (les indices ordonnent les éléments) et indexée (accès immédiat).
Il faut faire attention au contexte pour savoir si c'est une structure statique ou dynamique :
TableauStatique de l'exercice suivant) ;list est un tableau dynamique : on peut lui ajouter des éléments
avec append ou en retirer avec pop.Dans l'animation, on demande plusieurs éléments du tableau t par leur indice : observe
comment chacun est trouvé, puis ce qui se passe quand l'indice dépasse n − 1.
Le parking du lycée compte exactement 5 places numérotées de 0 à 4. Ce nombre ne changera jamais : on ne peut ni ajouter ni retirer de place. Pour chaque place, on veut savoir quelle voiture l’occupe (sa plaque d’immatriculation) ou si elle est libre (None). On accède directement à une place par son numéro, sans parcourir les autres.
Une liste Python, qui peut grandir avec append, ne convient donc pas tout à fait : il nous faut un tableau statique, dont la taille est fixée une fois pour toutes à sa création.
On souhaite créer une classe TableauStatique qui permet de créer un objet de type statique, indexé et linéaire.
Le squelette de la classe est déjà écrit : complète chaque ... dans l’éditeur.
Le tableau doit avoir les caractéristiques suivantes :
__init__(self, taille).None (attribut privé).__tab est une liste qui contiendra les données du tableau.__taille est privé et correspond à la taille du tableautaille_tableau(self) retourne la taille du tableau.est_vide(self) renvoie True si le tableau est composé uniquement de None, False sinon.change(self, i, data) change l’élément d’indice i en data.effacer(self, i) remplace l’élément d’indice i par None.connaitre(self, i) renvoie le contenu de l’élément à l’indice i.affiche_tout(self) affiche le contenu complet du tableau.
Une file est une structure de données linéaire, non indexée, qui peut être dynamique et où l'élément que l'on peut sortir est le premier à être rentré (FIFO : First In, First Out).
C'est le principe d'une file d'attente à une caisse : le premier client arrivé est le premier servi. Observe l'animation ci-dessous : les éléments entrent par l'arrière (à gauche) et sortent par l'avant (à droite).
Regarde bien : le premier entré est toujours le premier sorti.
Une pile est une structure de données linéaire, non indexée, qui peut être dynamique et où l'élément que l'on peut sortir est le dernier à être rentré (LIFO : Last In, First Out).
C'est le principe d'une pile d'assiettes : on pose une assiette au sommet, et on reprend toujours celle du sommet. Observe l'animation ci-dessous : les éléments entrent et sortent par le haut.
Ce sont exactement les mêmes valeurs que dans la file plus haut, qui entrent au même moment : compare ce qui sort de chaque structure !
Regarde bien : le dernier entré est toujours le premier sorti.
Par exemple, les piles et les files ne sont pas présentes dans Python.
On peut toutefois créer cet objet avec par exemple la classe Pile ci-dessous :
class Pile:
def __init__(self):
self.tablo = []
def empiler(self, data):
self.tablo.append(data)
def depiler(self):
return self.tablo.pop()
def est_vide(self):
return self.tablo == []
p = Pile()
p.empiler(2)
print(p.depiler()) # 2
print(p.est_vide()) # True
Ci-dessous :
caracteres_dans_pile qui prend comme paramètre un string et renvoie une pile contenant les caractères (un par un) de ce string.Créer une fonction nb_espaces qui prend comme paramètre une pile contenant des caractères et renvoie le nombre de fois où le caractère espace apparait sous la forme d'un integer.
La pile peut être détruite dans le processus.
L’éditeur contient la classe Truc de l’activité 1, renommée cette fois File avec le vocabulaire habituel des files (lis sa documentation) : enfiler(objet) ajoute un élément à la fin, defiler() retire et renvoie le premier élément entré et est_vide() teste si la file est vide.
En utilisant cette classe File :
extraire(un_texte) qui prend un string et met chaque caractère dans une file.Créer une fonction voyelle(une_file) qui prend une file qui contient des caractères et renvoie un integer correspondant au nombre de voyelles présentes dans la file.
La file pourra être détruite dans le processus.
plus_grande(une_file) qui prend une file composée uniquement d’entiers et renvoie le plus grand nombre de la file.
On considère des chaînes composées uniquement de parenthèses ouvrantes '(' et fermantes ')'.
Un parenthésage est correct si :
Cette fonction utilise une pile et suit le principe suivant : en parcourant la chaîne de gauche à droite, si on trouve une parenthèse ouvrante, on l’empile au sommet de la pile et si on trouve une parenthèse fermante, on dépile (si possible) la parenthèse ouvrante stockée au sommet de la pile.
La chaîne est alors bien parenthésée si, à la fin du parcours, la pile est vide.
Elle est, par contre, mal parenthésée :
Compléter la fonction bon_parenthesage(ch) ci-dessous :
>>> bon_parenthesage("((()())(()))")
True
>>> bon_parenthesage("())(()")
False
>>> bon_parenthesage("(())(()")
False
Cet exercice utilise des piles qui seront représentées par des listes Python.
Si pile est une pile, alors pile == [] indique si la pile est vide, pile.pop() retire et renvoie le sommet de la pile et pile.append(v) ajoute la valeur v au sommet de la pile.
Si on considère qu’une fonction manipule une pile, elle ne peut pas utiliser d’autres opérations que celles décrites ci-dessus.
On cherche à écrire une fonction positifs qui prend une pile de nombres entiers en paramètre et qui renvoie une nouvelle pile contenant les entiers positifs de la pile initiale, dans le même ordre, quitte à modifier la pile initiale.
Pour cela, on va également écrire une fonction renverse qui prend une pile en paramètre et qui renvoie une nouvelle pile contenant les mêmes éléments que la pile initiale, mais dans l’ordre inverse. Cette fonction sera également amenée à modifier la pile passée en paramètre.
Compléter le code Python des fonctions renverse et positifs ci-après.
Exemples :
>>> renverse([1, 2, 3, 4, 5])
[5, 4, 3, 2, 1]
>>> positifs([-1, 0, 5, -3, 4, -6, 10, 9, -8])
[0, 5, 4, 10, 9]
>>> positifs([-2])
[]