Cours les structures de données élémentaires, tutoriel & guide de travaux pratiques en pdf.

Types de collections

Séquentiels
– Dans cette catégorie de collections, l’accès est linéaire. C’est l’ordre qui compte. – Les éléments peuvent être stockés sous la forme : o Un tableau Dans ce cas, les éléments sont accessibles à partir d’un index. Ajouter ou enlever des éléments à partir de la fin du tableau est une opération très rapide à exécuter. Par contre, insérer un élément au début ou bien au milieu du tableau, il prend un certain temps car les éléments doivent être déplacés un par un pour créer une place au nouvel arrivant. o Une file C’est un tableau dynamique qui peut grossir dans les deux directions : une file bilatérale. L’insertion des éléments au début ou bien à la fin de la file est une opération rapide à exécuter. Par contre insérer un élément au milieu va prendre un certain temps car il faudra déplacer les éléments. o Une liste Les listes ne permettent pas un accès aléatoire c.-à-d. à un index donné comme le font les tableaux et les files. Pour accéder au Nième élément de la liste, il faut passer par les N-1 prédécesseurs. L’accès à un élément donné prend un temps linéaire nettement supérieur que, si cet élément était dans un tableau ou une file. L’avantage des listes est que l’insertion ou le retrait d’un élément se fait rapidement. Il suffit de modifier les adresses des pointeurs, des prédécesseurs et des successeurs.

Associatifs – Dans cette catégorie de collections, l’accès se fait par clés
– Les éléments sont rangés suivant un certain critère. Ce critère est une sorte de fonction qui compare suivant la valeur ou bien la clé associée à la valeur.
– Parmi ces collections nous citerons les dictionnaires (« map »).

Adaptateurs – Dans cette catégorie de collections, l’accès est réglementé
– Ces conteneurs adaptent les conteneurs séquentiels afin de remplir des missions précises.
– Parmi ces adaptateurs, nous citerons: pile (« stack »), file (« queues ») et les files prioritaires (« priority queues »).