Structure de données classiques (INFO410_INFO)

Ce cours utilise les notions de typage vues dans le module Programmation impérative 1 pour créer et manipuler des structures de données classiques, utilisant une allocation statique ou dynamique. Les aspects d’allocation dynamique dans les langages impératifs (notion de pointeurs) sont abordés en gardant à l’esprit un objectif de programmation propre. Les notions de files, de piles sont traitées dans ce cours. Les notions de modules (packages) et de généricité seront également introduites. Ce cours est illustré avec le langage de programmation ADA.

• Allocation statique et dynamique. Pointeurs.

• Structure dynamique : listes chainées, piles, files d’attente

• Création de ces structures. Manipulation classiques : insertion, destruction d’éléments, parcours préfixés, infixés et postfixés dans les arbres.

• Notion de généricité.

• Généricité dans les tris.

Les Tps réalisés varient d’une année sur l’autre. Il est fréquent de coder certaines applications de jeux qui mettent bien en évidence les besoins de structuration des traitements et des données.