Tableaux statiques et dynamiques en C++

• Le document porte sur les structures de données, notamment les tableaux en C++, avec un focus sur les tableaux statiques, pseudo-dynamiques et dynamiques, y compris ceux avec marge.

Objectifs

• Redécouvrir les tableaux statiques.
• Explorer les tableaux dynamiques et leurs performances.

Introduction

• Les tableaux seront étudiés sous un nouvel angle.
• Les tableaux usuels sont statiques.
• Création de tableaux dynamiques avec ou sans marge.
• Découverte de l'intérêt des tableaux et de leurs cas d'utilisation pertinents.

Tableaux statiques

• Un tableau est une collection d'éléments de même type accessibles par un indice entier.
• L'accès à un élément par son indice est direct et se fait en temps constant, noté O(1).
• Les données des tableaux sont rangées de manière contiguë en mémoire.
• L'organisation contiguë des données permet un accès direct (O(1)) mais rend la réorganisation coûteuse.
• L'insertion ou la suppression d'éléments se fait en temps linéaire O(n), où n est la taille du tableau.
• Un tableau statique a une taille fixe qui ne peut pas être modifiée après sa déclaration.

Tableaux pseudo dynamiques

• Les tableaux sont statiques en C++.
• Simulation d'un comportement dynamique en utilisant une structure de données.
• Un tableau pseudo-dynamique combine un tableau statique (surdimensionné) et un compteur du nombre d'éléments effectifs.
• La dimension du tableau est majorée par une constante, qui donne le nombre maximal d'éléments enregistrables et qui est la capacité.
• Une variable n donne le nombre effectif d'éléments enregistrés.
• L'ajout d'un élément supplémentaire à la fin d'un tableau est une opération fondamentale pour comparer les structures de données.
• L'ajout d'un élément consiste à le placer à la position n et incrémenter n, sous réserve que n reste inférieur à la capacité.
• Cette structure présente l'avantage de simuler un tableau dynamique, mais avec un gaspillage de mémoire et une capacité limitée.

Tableaux dynamiques

• Les tableaux dynamiques utilisent des pointeurs et l'allocation dynamique de mémoire.
• Un pointeur sur le type de données stockées et un entier représentant le nombre d'éléments.
• L'allocation de mémoire est gérée dynamiquement.
• L'ajout d'un élément à la fin nécessite la création d'un nouveau tableau temporaire plus grand, la copie des éléments de l'ancien tableau, la libération de la mémoire de l'ancien tableau, et l'ajout du nouvel élément.
• Cette opération d'ajout est inefficace, car elle se fait en temps linéaire.
• Pas de gaspillage de mémoire et capacité illimitée.
• L'ajout de valeurs est coûteux, car nécessite d’allouer de la place, de recopier les valeurs et libérer l'espace.

Tableaux dynamiques avec marge

• Combinaison des approches précédentes pour éviter ou limiter les inconvénients.
• Accès direct aux éléments, caractère dynamique, gaspillage de mémoire limité.
• L'ajout d'un élément se fait en temps constant amorti.
• Possède un tableau d'une certaine capacité et une dimension (inférieure ou égale à la capacité).
• Chaque élément ajouté incrémente la dimension. Lorsque la dimension atteint la capacité, celle-ci est augmentée, un nouveau tableau est alloué, et les anciennes valeurs sont recopiées.
• L'opération d'ajout est efficace et se fait en temps constant amorti.
• La capacité est illimitée et le gaspillage réduit car la capacité est doublé à chaque fois.

Une classe tableau dynamique avec marge

• Utilisation d'une classe C++ pour encapsuler la structure de données, permettant une manipulation plus sûre et abstraite.
• La partie publique (interface) de la classe contient les méthodes essentielles à son usage.
• La partie privée contient la structure de données.
• La classe TableauDynamiqueAvecMarge possède des méthodes pour créer, détruire, connaître la dimension, lire et écrire des valeurs, et ajouter un élément.
• La structure de données privée contient un pointeur pour la table, la dimension et la capacité.
• Le fichier d'en-têtes réunit les déclarations de la classe.
• Le constructeur initialise un tableau vide avec une capacité initiale.
• Le destructeur libère la mémoire allouée dynamiquement.
• La méthode ajouter ajoute un élément, en doublant la capacité si nécessaire.