Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité
Introduction et syntaxe de base
Pointeurs et fonctions
Programmation OO
Structures de données
La bibliothèque standard (STL)

Introduction aux structures de données

 

Introduction aux structures de données

Dans les applications réelles, les objets sont souvent des collections. Cela signifie que nous devons gérer une collection d'objets au lieu d'objets individuels. Les techniques que nous avons apprises jusqu'à présent peuvent être appliquées à chaque objet de la collection, mais nous devons également considérer la collection comme un objet d'objets. Nous avons appris à appliquer des opérations à des objets individuels, comme accéder ou modifier des attributs ; nous apprenons maintenant comment appliquer des opérations aux collections, insérer un objet, comment effacer un objet et comment accéder à un objet dans une collection.

Relation d'objets

Les opérations sur une collection, en tant qu'objet d'objets, dépendent de la relation entre les objets de la collection. Nous rencontrons normalement deux relations générales dans une collection : linéaire et non linéaire.

Relation linéaire

Une collection peut imposer une relation linéaire entre les objets d'une collection, ce qui signifie que chaque objet est en quelque sorte connecté à l'objet précédant et suivant. La figure ci-dessous présente le concept de base d'une collection linéaire.

Relation non linéaire

Dans une collection non linéaire, chaque objet peut être connecté à un groupe d'objets. Nous n'avons pas une collection d'objets qui se succèdent. Les objets peuvent être liés les uns aux autres dans une relation tabulaire, dans laquelle un objet est connecté à deux objets de la même ligne et à deux objets de la même colonne. Nous pouvons également avoir une collection dans laquelle les objets sont liés les uns aux autres de la même manière que les branches d'un arbre sont connectées. Nous pouvons avoir une racine et des branches, chacune avec un certain nombre d'objets, dans un arbre à l'envers. La figure ci-dessous présente ces deux types de relations dans une collection non linéaire.

Relation tabulaire

Relation hiérarchique (arbre)

Interface vs implémentation

Comme nous l'avons vu dans le cas des objets individuels, nous devons penser à deux aspects d'un objet en programmation orientée objet : l'interface et l'implémentation. Cette affirmation est également vraie pour une collection, qui est un objet d'objets.

Interface

Nous avons appris que l'interface d'un objet individuel donne simplement la liste des opérations que nous pouvons utiliser sans révéler comment l'objet est créé et son contenu. Cela est vrai pour les objets fondamentaux et définis par l'utilisateur. Puisqu'une collection est normalement implémentée en tant qu'entité modèle, nous pouvons définir le type des objets de la collection, mais la manière dont la collection est implémentée est cachée à l'utilisateur. Nous n'avons que l'interface, qui montre comment insérer, comment supprimer, comment accéder et comment réorganiser les objets. C'est le cas de la STL. La STL nous fournit un riche ensemble de collections et donne l'interface pour utiliser les opérations correspondantes des collections, mais l'implémentation est cachée.

Implémentation

Si nous voulons créer une collection personnelle avec certaines fonctionnalités qui ne sont pas définies dans la STL, nous pouvons écrire notre propre classe de collection et fournir les fonctions dont nous avons besoin. Une autre solution consiste à hériter de la classe STL et à personnaliser les opérations dont nous avons besoin.

Choix d’implémentation

Nous avons deux choix : utiliser un tableau ou utiliser une liste chaînée.

Utiliser un tableau

Nous pouvons utiliser un tableau à une dimension pour implémenter une collection linéaire ou un tableau à deux dimensions pour créer une collection non linéaire. Un tableau peut être implémenté dans la mémoire de la pile ou dans la mémoire du tas (Voir la représentation de la mémoire). Pendant l'exécution, si la taille du tableau doit être augmentée, nous pouvons créer un tableau plus grand, copier les valeurs du tableau précédent dans le nouveau tableau, puis détruire le tableau d'origine. Dans l'implémentation du tableau, la connexion entre les objets est établie via l'indice du tableau. Un objet d'un indice supérieur est situé après un objet d'un indice inférieur.

Utiliser une liste chainée

Dans une implémentation de liste chaînée, la connexion entre les objets de la collection est assurée par des pointeurs au lieu d'indices. Un objet peut avoir un ou plusieurs pointeurs vers d'autres objets de la collection. En d'autres termes, les objets sont liés par des pointeurs. Bien que l'implémentation de la liste chaînée demande plus d'efforts de la part du concepteur, elle présente deux avantages majeurs par rapport à l'implémentation du tableau : La taille de la collection ne doit pas être définie lors de la compilation et la taille peut être modifiée sans qu'il soit nécessaire de copier la collection entière dans une nouvelle collection.

Partager ce cours avec tes amis :
 
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.