Par transformation des fonctions du document 1 dans ce chapitre en méthodes, écrire le code de la classe Liste
qui définit le type abstrait « Liste chaînée ».
Réponse
|
|
Par transformation des fonctions du document 1 dans ce chapitre en méthodes, écrire le code de la classe Liste
qui définit le type abstrait « Liste chaînée ».
|
|
Reprendre toutes les fonctions des sections 2 et 3 du document 1 de ce chapitre, en implémentant cette fois le type abstrait « Liste chaînée » à l’aide de tuples (à la place de la classe).
|
|
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 :
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]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 :
Une pile est une structure de données abstraite dans laquelle les données sont organisées comme le seraient des assiettes dans une pile d’assiettes contenue dans une boite de profondeur quelconque mais étroite (ce qui empêche de manipuler les assiettes par le côté).
On peut donc seulement :
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)$ |
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.