Différentes implémentations☘

Un même type abstrait de données peut être implémenté de différentes manières :

programmation itérative ;
programmation orientée objet ;
autre...

Pour l’utilisateur d’une telle structure, l’implémentation importe peu. Seule l’interface lui est nécessaire, ainsi que le respect des performances induites par la structure utilisée.

Les tableaux☘

Une interface minimale pour le TAD « tableau » est :

Méthode/Opérations	Description
`tab = Tableau(n)`	Initialisation d'un tableau vide de `n` éléments
`est_vide(tab)`	Renvoie `True` si le tableau est vide, `False` sinon.
`lg = longueur(tab)`	Renvoie le nombre d’éléments du tableau.
`elt = valeur(tab, i)`	Renvoie la valeur de l'élément d’indice `i`
`modifie(tab, i, elt)`	Modifie la valeur de l'élément d’indice `i`

Les piles☘

Une interface minimale pour le TAD « pile » est :

Méthode/Opérations	Description
`P = Pile()`	Initialisation d'une pile vide.
`est_vide(P)`	Renvoie `True` si la pile est vide, `False` sinon.
`P = empiler(P, elt)`	Empile un nouvel élément au sommet de la pile.
`elt = depiler(P)`	Lorsque la pile n'est pas vide, supprime le sommet de la pile et renvoie la valeur de ce sommet.

Les files☘

Une interface minimale pour le TAD « file » est :

Méthode/Opérations	Description
`F = File()`	Initialisation d'une file vide.
`est_vide(F)`	Renvoie `True` si la file est vide, `False` sinon.
`F = enfiler(F, elt)`	Enfile un nouvel élément en queue de la file.
`elt = defiler(F)`	Lorsque la file n'est pas vide, supprime le premier élément de la file et renvoie la valeur de cet élément.

Les listes☘

Une interface minimale pour le TAD « liste » est :

Méthode/Opérations	Description
`L = Liste()`	Initialisation d'une liste vide
`est_vide(L)`	Renvoie `True` si la liste est vide, `False` sinon.
`L = inserer_en_tete(L, elt)`	Ajoute un nouvel élément en tête de la liste. La liste `L` devient le couple `(elt, L)`
`elt = tete(L)`	Renvoie la valeur du premier élément
`lst = queue(L)`	Renvoie la liste située en queue

Les tableaux associatifs☘

Une interface minimale pour le TAD « tableau associatif » est :

Méthode/Opérations	Description
`d = Dico()`	Initialisation d'un tableau associatif vide
`est_vide(d)`	Renvoie `True` si le tableau associatif est vide, `False` sinon.
`d = ajout(d, cle, valeur)`	Associe `valeur` à une nouvelle clef `cle`
`modif(d, cle, valeur)`	Modifie la valeur associée à la clef `cle`
`elt = valeur(d, cle)`	Renvoie la valeur associée à la clef `cle`
`supprime(d, cle)`	Supprime la clef `cle` (et donc la valeur associée)