Structure de données linéaires

Programme

Notions	Compétences	Remarques
Structures de données, interface et implémentation. Listes, piles, files : structures linéaires. Dictionnaires, index et clé.	Spécifier une structure de données par son interface. Distinguer interface et implémentation. Écrire plusieurs implémentations d'une même structure de données. Distinguer des structures par le jeu des méthodes qui caractérisent. Choisir une structure de données adaptée à la situation à modéliser. Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire.	L’abstraction des structures de données est introduite après plusieurs implémentations d’une structure simple comme la file (avec un tableau ou avec deux piles). On distingue les modes FIFO (first in first out) et LIFO (last in first out) des piles et des files.
Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.	Calculer la taille et la hauteur d’un arbre. Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d’abord). Rechercher une clé dans un arbre de recherche, insérer une clé.	Une structure de données récursive adaptée est utilisée. L’exemple des arbres permet d’illustrer la programmation par classe. La recherche dans un arbre de recherche équilibré est de coût logarithmique.

Une structure linéaire relie les données en séquences. C'est à dire qu'on peut numéroter les données, et que chaque élément a un rang.

Nous verrons dans ce chapitre l'exemple de la LISTE, dont la PILE et la FILE en sont des sous-exemple avec des opérations restreintes.