(+212) 616 374 790 contact@developpement-informatique.com
| Connexion
Langage C Langage c++ Langage java Langage Python

Introduction aux structures de données

19 Nov 2021 19 Nov 2021 7533 vues ESSADDOUKI Mostafa 4 min de lecture
Introduction et syntaxe de base
1 Introduction au langage C++ 2 Entrée-sortie en C++ - cin et cout 3 Inférence de type avec le mot-clé auto en C++ 4 Classe std::string et les chaînes de caractères en C++ 5 Les structures conditionnelles (if et switch) en C++ (C++17 et C++20) 6 Les boucles en C++ (C++17 et C++20) 7 La gestion des fichiers en C++
Pointeurs et fonctions
8 Introduction aux pointeurs en C++ - Déclaration et interêts 9 Les références en C++ - déclaration et interêts 10 Les tableaux en C++ - Déclaration et interêts 11 Introduction aux fonctions en C++ 12 Passer des arguments à une fonction en C++ 13 Déclarer un paramètre const en C++ 14 Les fonctions Lambda en C++ 15 Fonctions utiles (Mathématiques et caractères) en C++
Programmation OO
16 Classes et objets en C++ 17 Spécificateurs d'accès en C++ 18 Constructeurs et destructeur d'une classe en C++ 19 Fonctions membres en C++ 20 Membres statiques d'une classe en C++ 21 Fonctions en ligne en C++ - inline 22 Fonctions et classes amies en C++ - friend 23 Surcharge des fonctions en C++ 24 Surcharge des opérateurs en C++ 25 Héritage en C++ 26 La gestion d'exceptions en C++ : déclaration, utilisation et personnalisation 27 fonctions et classes templates en C++ 28 Les nouveautés C++20 pour améliorer les templates en C++
Structures de données
29 Introduction aux structures de données 30 Les structures en C++ et la différence avec les structures en C 31 Les listes chaînées en C++ 32 Les piles en C++ 33 File d'attente en C++ 34 Arbre binaire de recherche : définition et mise en oeuvre en C++
La bibliothèque standard (STL)
35 Introduction à la bibliothèque de Template Standard STL 36 Les itérateurs en C++ - définition, déclaration et exemples 37 La classe array en C++ (bibliothèque STL) <array> 38 La classe vector de la bibliothèque STL <vector> 39 La classe deque en C++ ( Bibliothèque STL) 40 La classe list en C++ (bibliothèque STL) <list> 41 La classe stack (Pile) en C++ (bibliothèque STL) <stack> 42 La classe queue (File d'attente) en C++ (bibliothèque STL) <queue> 43 La file d'attente prioritaire (classe priority_queue) - Bibliothèque STL 44 Les ensembles en C++ (Classe set <set> - Bibliothèque STL) 45 Les dictionnaires en C++ : Classe map (Bibliothèque STL) 46 Introduction aux algorithmes de la bibliothèque STL (programmation compétitive) 47 Tri et méthodes associées en C++ - Bibliothèque STL 48 Recherche dichotomique et méthodes associées en C++ - Bibliothèque STL 49 Appliquer un prédicat ou une fonction aux éléments d'une séquence en C++ - Bibliothèque STL 50 Recherche dans une séquence et méthodes associées en C++ - Bibliothèque STL

Collections d'objets

Dans les applications réelles, les objets sont souvent regroupés en collections. Il faut alors gérer la collection en tant qu'entité à part entière, et non seulement les objets individuels. Les opérations typiques sur une collection sont : insérer, supprimer et accéder à un objet.

Relation entre objets d'une collection

Les opérations applicables à une collection dépendent de la relation entre ses objets. On distingue deux grandes familles : les relations linéaires et les relations non linéaires.

Relation linéaire

Dans une collection linéaire, chaque objet est connecté à l'objet précédent et à l'objet suivant. Les objets se succèdent dans un ordre défini.

Collection linéaire

Relation non linéaire

Dans une collection non linéaire, un objet peut être connecté à plusieurs autres objets. On distingue deux sous-types courants :

Relation tabulaire

Un objet est connecté à deux objets de la même ligne et à deux objets de la même colonne, formant une structure en grille.

Relation tabulaire

Relation hiérarchique (arbre)

Les objets sont organisés comme les branches d'un arbre inversé : une racine relie des branches, chacune portant un ensemble d'objets enfants.

Relation hiérarchique — arbre

Interface vs Implémentation

Comme pour tout objet en programmation orientée objet, une collection possède deux aspects distincts qu'il faut dissocier : l'interface et l'implémentation.

Interface

L'interface d'une collection expose les opérations disponibles — insérer, supprimer, accéder, réorganiser — sans révéler comment la collection est construite en mémoire. C'est le principe de la STL (Standard Template Library) : elle fournit un riche ensemble de collections avec leurs interfaces, mais l'implémentation interne reste cachée à l'utilisateur.

Implémentation

Si la STL ne répond pas à un besoin spécifique, deux approches sont possibles :

  • Écrire sa propre classe de collection avec les fonctions nécessaires.
  • Hériter d'une classe STL existante et personnaliser uniquement les opérations requises.

Choix d'implémentation

Pour implémenter une collection, deux structures de données fondamentales s'offrent à nous : le tableau et la liste chaînée.

Utiliser un tableau

Un tableau à une dimension convient aux collections linéaires ; un tableau à deux dimensions aux collections non linéaires. La connexion entre les objets est établie via l'indice : un objet d'indice supérieur suit celui d'indice inférieur.

Redimensionnement coûteux Si la taille du tableau doit augmenter pendant l'exécution, il faut créer un nouveau tableau plus grand, y copier tous les éléments du tableau original, puis détruire ce dernier. Cette opération est coûteuse en temps et en mémoire.

Utiliser une liste chaînée

Dans une liste chaînée, les objets sont reliés par des pointeurs plutôt que par des indices. Un objet peut pointer vers un ou plusieurs autres objets de la collection.

Avantages de la liste chaînée
  • La taille n'a pas besoin d'être connue à la compilation.
  • Le redimensionnement ne nécessite pas de copier toute la collection — on ajuste simplement les pointeurs.
CritèreTableauListe chaînée
Connexion entre objetsPar indicePar pointeur
Taille fixée à la compilationOui (tableau statique)Non
RedimensionnementCopie complète nécessaireAjustement des pointeurs uniquement
Complexité d'implémentationSimplePlus élevée
Accès aléatoireDirect (O(1))Séquentiel (O(n))
Structures de données
Suivant Les listes chaînées en C++

Discussion (0)

Soyez le premier à laisser un commentaire !

Laisser un commentaire

Votre commentaire sera visible après modération.