Chapitre 2
Structures de données
Une structure de données est une organisation logique des données permettant de simplifier ou d'accélérer leur traitement.
Rappels
En informatique on manipule essentiellement des données.
Lorsqu'elles sont simples comme des nombres, des chaînes de caractères ou des booléens, on peut les stocker dans des variables qui seront typées en fonction de la nature de la donnée.
Les classes
La programmation orientée objet (POO) permet de créer ses propres structures de données.
TP - Flappy fish
Création d'un flappy fish avec Processing
Les listes
La structure de liste est assez facile à imaginer comme une suite d'éléments ordonnés par leurs indices.
a0 , a1 , a2 , ... , an
Dans cette partie on s'intéresse aux listes d'un point de vue "structure de données" et pas aux listes Python qui sont une implémentation spécifique à Python de la notion de liste.
Les piles
En informatique, une pile (en anglais stack) est une structure de données fondée sur le principe«dernier arrivé, premier sorti» (ou LIFO pour Last In, First Out), ce qui veut dire que les derniers éléments ajoutés à la pile seront les premiers à être récupérés.
TP - Piles
Les files
En informatique, une file (queue en anglais ) est une structure de données basée sur le principe «Premier entré,premier sorti», en anglais FIFO (First In, First Out), ce qui veut dire que les premiers éléments ajoutés à la file seront les premiers à être récupérés.
Conclusion
Une structure de données permet de gérer un ensemble de données à partir d'un jeu réduit de méthodes qui sont les seuls moyens d'accéder à tel ou tel élément, de modifier l'ensemble des données, d'en créer un nouveau, etc.
La description de ce jeu réduit de méthodes ainsi que de leur sémantique s'appelle l'interface de la structure de données.
Pour une même interface, on peut proposer diverses implémentations de la structure de données, et il est recommandé de pouvoir donner le coût d'exécution de chaque méthode dans le cadre d'une implémentation particulière.
L'utilisateur d'une structure de données n'a besoin de connaître que son interface, et nullement les détails de son implémentation.
Les modules Python proposent en général des interfaces très riches, ce qui généralise leur utilisation au détriment de la clarté : ce sont souvent plusieurs structures de données auxquelles il est donné accès par le biais d'un même module.
Pour la suite...
Créer deux fichiers qui contiendront les classes Pile et File (et leurs méthodes...), pour pouvoir les utiliser dans la suite du cours
