Structures de données de base Flashcards
L’objectif de ce module est de vous présenter les structures de données de base couramment utilisées en informatique (tels que les vecteurs, listes, files, piles) et qui servent également de support à d’autres structures de données plus complexes que nous verrons plus loin dans le cours (tels que les arbres, graphes, tables de dispersions).
1
Q
Spécifications d’un Vecteur
A
● Accès kieme élément en O(1)
● Insertion et suppression du kième élément en O(n)
2
Q
Déf : Vecteur
A
Un vecteur est une séquence ordonnée d’éléments d’un certain type. (ordonné par leur position 1er, 2ieme etc.)
3
Q
Un Iterator permet ..
A
d’accéder séquentiellement (par itération) aux éléments
peu importe leurs types
4
Q
Déf : Liste
A
Une liste est une séquence ordonnée d’éléments d’un certain type.
Qui gère une “position courante”
(Ordre = position)
5
Q
Spécifications Liste
A
● Insertion ou suppression à la courante en O(1)
● Accéder à l’élément suivant en O(1)
● Accéder à l’élément précédent en O(1) (si doublement chainée)
● Temps d’accès au kième élément en O(n)
