Rappel : Type de Données Abstrait (TDA)
Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par :
- Son nom ;
- Sa spécification, c’est à dire la liste des manipulations/opérations que l’on peut ou pas effectuer. La spécification indique généralement la complexité de chacune des opérations prévues par le TDA.
Un TDA peut être implémenté de plusieurs façons différentes.
Qu’est-ce qu’une file ?
Une file est une structure de données abstraite dans laquelle les données sont organisées comme le seraient des personnes dans une file d’attente (au guichet de la poste par exemple) :
[Lire]Listes Chaînées, présentation
... et implémentation à l'aide d'une classe
Tableaux
- Un tableau est une structure de données dans laquelle les éléments, tous de même type, occupent des positions contiguës en mémoire.
- Le nombre d’éléments qu’un tableau peut contenir est déterminé à la création d’un tableau.
| Type Python | Type | Opération | Exemple | Complexité |
|---|---|---|---|---|
| N’existe pas | Tableau | Accès à un élément | tab[i] |
$O(1)$ |
| Modification d’un élément | tab[i] = x |
$O(1)$ | ||
| Effacement d’un élément | retire(tab, i) |
$O(n)$ | ||
| Insertion d’un élément | insere(tab, x, i) |
$O(n)$ | ||
| Recherche d’un élément | est_dans(tab, x) |
$O(n)$ |
- La structure de données appelée « liste » dans le langage Python est implémentée à l’aide de tableaux dynamiques.
Remarque : Dans la suite de ce document, on va considérer que la liste Python tab, créé par l’instruction tab = [i for i in range(20)] est de longueur fixe. Elle se comporte alors comme un tableau.
Structures de données fournies avec le langage Python
Python possède dans la bibliothèque standard un grand nombre de structures de données, programmées de manière efficace.
Rappels : modules, fonctions
Pour chaque module, on distingue :
-
sa réalisation (ou implémentation) : c’est le code lui-même.
-
son interface (API) : c’est l’énumération des fonctions définies dans le module qui sont utilisées depuis d’autres modules/programmes, les clients.
-
L’interface doit présenter une documentation dans laquelle tout ce que doit savoir le client doit être indiqué.
[Lire]