Algorithmes et structures de données en C++ : guide pratique

Algorithmes et structures de données en C++ : de la théorie à la pratique

La maîtrise des algorithmes et des structures de données est une étape clé dans la formation d'un développeur professionnel. Sans une compréhension approfondie de la manière d'organiser et de traiter efficacement les données, il est impossible de créer des applications performantes et évolutives. C++ offre des possibilités uniques pour le travail de bas niveau avec la mémoire et des performances élevées, ce qui en fait un langage idéal pour étudier ce sujet.

Dans cet article, nous examinerons les algorithmes et structures de données fondamentaux en C++ avec des exemples de code pratiques que vous pourrez immédiatement appliquer dans vos projets. Nous ne nous plongerons pas dans des calculs mathématiques abstraits — notre objectif est la mise en œuvre réelle et la compréhension des principes de fonctionnement.

1. Tableaux dynamiques et gestion de la mémoire

Commençons par les bases — les tableaux dynamiques. Contrairement aux tableaux statiques, dont la taille est fixée au moment de la compilation, les tableaux dynamiques permettent de modifier la taille pendant l'exécution du programme. En C++, on utilise pour cela les opérateurs new[] et delete[].

#include <iostream>\n\nint main() {\n    int size = 5;\n    int* arr = new int[size]; // allocation mémoire\n    \n    // Initialisation\n    for(int i = 0; i < size; i++) {\n        arr[i] = i * 10;\n    }\n    \n    // Affichage\n    for(int i = 0; i < size; i++) {\n        std::cout << arr[i] << " ";\n    }\n    \n    delete[] arr; // libération mémoire\n    return 0;\n}

Il est important de se rappeler que lorsque vous travaillez avec la mémoire dynamique, vous êtes responsable de sa libération. Les fuites de mémoire sont l'un des problèmes les plus courants en C++. Il est recommandé d'utiliser des pointeurs intelligents (std::unique_ptr, std::shared_ptr) de la bibliothèque standard pour une gestion automatique de la mémoire.

2. Pile et file d'attente : structures de données classiques

La pile et la file d'attente sont deux structures de données fondamentales qui implémentent respectivement les principes LIFO (Last In, First Out) et FIFO (First In, First Out). Examinons leur implémentation en C++ à l'aide d'un tableau dynamique.

Implémentation de la pile

#include <iostream>\n#include <stdexcept>\n\nclass Stack {\nprivate:\n    int* data;\n    int capacity;\n    int top;\n    \npublic:\n    Stack(int size) : capacity(size), top(-1) {\n        data = new int[capacity];\n    }\n    \n    ~Stack() {\n        delete[] data;\n    }\n    \n    void push(int value) {\n        if(top >= capacity - 1) {\n            throw std::overflow_error("Stack overflow");\n        }\n        data[++top] = value;\n    }\n    \n    int pop() {\n        if(isEmpty()) {\n            throw std::underflow_error("Stack underflow");\n        }\n        return data[top--];\n    }\n    \n    bool isEmpty() const {\n        return top == -1;\n    }\n    \n    int peek() const {\n        if(isEmpty()) {\n            throw std::underflow_error("Stack is empty");\n        }\n        return data[top];\n    }\n};\n\nint main() {\n    Stack stack(5);\n    stack.push(10);\n    stack.push(20);\n    stack.push(30);\n    \n    std::cout << "Élément supérieur : " << stack.peek() << std::endl;\n    std::cout << "Dépilage : " << stack.pop() << std::endl;\n    std::cout << "Dépilage : " << stack.pop() << std::endl;\n    \n    return 0;\n}

Implémentation de la file d'attente

#include <iostream>\n\nclass Queue {\nprivate:\n    int* data;\n    int capacity;\n    int front;\n    int rear;\n    int count;\n    \npublic:\n    Queue(int size) : capacity(size), front(0), rear(-1), count(0) {\n        data = new int[capacity];\n    }\n    \n    ~Queue() {\n        delete[] data;\n    }\n    \n    void enqueue(int value) {\n        if(isFull()) {\n            throw std::overflow_error("Queue overflow");\n        }\n        rear = (rear + 1) %