Algo & Prog Structure de Données
Allocation dynamique
L’allocation dynamique permet de réserver de la mémoire pendant l’exécution du programme avec les opérateurs new et delete. Cela permet de créer des structures dont la taille peut varier pendant l'exécution (contrairement aux tableaux statiques).
int *p = new int[10]; //allocation
delete[] p; //liberation
Il est important de libérer la mémoire allouée pour éviter les fuites de mémoire. On utilise delete pour libérer la mémoire d'un objet ou d'un tableau.
Exemple d'allocation dynamique :
int *p = new int[10];
for (int i = 0; i < 10; i++) {
p[i] = i;
}
delete[] p;
Dans cet exemple, on alloue un tableau de 10 entiers, on le remplit avec des valeurs, puis on libère la mémoire.
Il est important de noter que si on oublie de libérer la mémoire, cela peut entraîner des fuites de mémoire, ce qui peut ralentir le programme ou même le faire planter.
Classe & Objet
Une classe est une structure de données qui regroupe des variables et des fonctions. Elle permet de créer des objets qui contiennent des données et des méthodes pour manipuler ces données.
Exemple de classe :
class Point {
public:
int x, y;
Point(int x, int y) { this->x = x; this->y = y; }
void afficher() { cout << "Point(" << x << ", " << y << ")" << endl; }
}
Dans cet exemple, on définit une classe Point avec deux attributs (x et y) et une méthode pour afficher le point.
On peut créer un objet de la classe Point comme ceci :
Point p(10, 20);
p.afficher();
On peut aussi créer des classes dérivées qui héritent des attributs et méthodes d'une classe de base. Cela permet de créer des hiérarchies de classes.
Exemple de classe dérivée :
class Point3D : public Point {
public:
int z;
Point3D(int x, int y, int z) : Point(x, y) { this->z = z; }
void afficher() { cout << "Point3D(" << x << ", " << y << ", " << z << ")" << endl; }
}
Dans cet exemple, on définit une classe Point3D qui hérite de la classe Point et ajoute un attribut z.
On peut créer un objet de la classe Point3D comme ceci :
Point3D p3d(10, 20, 30);
p3d.afficher();
Il est important de noter que les classes et objets permettent de structurer le code et de le rendre plus lisible et maintenable.
Algorithmes de tri
Les algorithmes de tri sont des méthodes pour organiser des données dans un certain ordre (croissant ou décroissant). Il existe plusieurs algorithmes de tri, chacun ayant ses propres avantages et inconvénients.
Voici quelques algorithmes de tri courants :
- Tri par insertion : construit progressivement un tableau trié en insérant chaque élément à sa place.
Le tri par insertion fonctionne en parcourant le tableau de gauche à droite et en insérant chaque élément à sa place dans la partie triée du tableau.
Exemple de tri par insertion :
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
Dans cet exemple, on parcourt le tableau à partir du deuxième élément et on insère chaque élément à sa place dans la partie triée du tableau. L'algorithme est donc de complexité O(n²) dans le pire des cas.
Le tri par sélection fonctionne en parcourant le tableau à la recherche de l'élément le plus petit, puis en l'échangeant avec le premier élément du tableau.
Exemple de tri par sélection :
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
Dans cet exemple, on parcourt le tableau à la recherche de l'élément le plus petit, puis on l'échange avec le premier élément du tableau. L'algorithme est donc de complexité O(n²) dans le pire des cas.
Le tri par fusion fonctionne en divisant le tableau en deux moitiés, en triant chaque moitié, puis en fusionnant les deux moitiés triées.
Exemple de tri par fusion :
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
>}
Dans cet exemple, on divise le tableau en deux moitiés, on trie chaque moitié, puis on fusionne les deux moitiés triées. L'algorithme est donc de complexité O(n log n) dans le pire des cas.
Programmation séparée
La programmation séparée consiste à séparer le code en plusieurs fichiers pour faciliter la gestion et la maintenance du code. Cela permet de diviser le code en modules, chacun ayant une responsabilité spécifique.
Pour organiser le code :
- Créer un fichier d'en-tête (.h) pour les déclarations de classes et de fonctions.
- Créer un fichier source (.cpp) pour les définitions de classes et de fonctions.
- Inclure le fichier d'en-tête dans le fichier source avec la directive
#include. - Utiliser des namespaces pour éviter les conflits de noms.
- Utiliser des commentaires pour expliquer le code.
Exemple de fichier d'en-tête :
class Point {
public:
int x, y;
Point(int x, int y);
void afficher();
}
Dans cet exemple, on définit une classe Point avec deux attributs (x et y) et deux méthodes (constructeur et afficher).
Exemple de fichier source :
#include "Point.h"
Point::Point(int x, int y) { this->x = x; this->y = y; }
void Point::afficher() { cout << "Point(" << x << ", " << y << ")" << endl; }
Dans cet exemple, on définit le constructeur et la méthode afficher de la classe Point.
Exemple de fichier principal :
// fichier main.cpp
#include "Point.h"
int main() {
Point p(10, 20);
p.afficher();
}
Dans cet exemple, on inclut un fichier d'en-tête Point.h qui contient la définition de la classe Point.
Il est important de noter que la programmation séparée permet de structurer le code et de le rendre plus lisible et maintenable.
Tableaux dynamiques
Un tableau dynamique est un tableau dont la taille peut varier pendant l'exécution du programme. On peut utiliser des pointeurs pour créer des tableaux dynamiques.
Exemple de tableau dynamique :
int *arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
delete[] arr;
Dans cet exemple, on crée un tableau dynamique de taille n, on le remplit avec des valeurs, puis on libère la mémoire.
Il est important de libérer la mémoire allouée pour éviter les fuites de mémoire. On utilise delete pour libérer la mémoire d'un tableau dynamique.
Il est aussi possible d'utiliser la bibliothèque vector de C++ pour créer des tableaux dynamiques. La bibliothèque vector gère automatiquement la mémoire et permet d'ajouter ou de supprimer des éléments facilement.
Exemple d'utilisation de vector :
#include <vector>
std::vector<int> arr;
arr.push_back(10);
arr.push_back(20);
arr.pop_back();
Dans cet exemple, on crée un tableau dynamique avec la bibliothèque vector, on ajoute des éléments avec push_back, puis on supprime le dernier élément avec pop_back.
Il est important de noter que les tableaux dynamiques permettent de gérer des données dont la taille peut varier pendant l'exécution du programme, ce qui est très utile dans de nombreux cas.
Listes
Une liste est une structure de données qui permet de stocker des éléments de manière dynamique. Contrairement aux tableaux, les listes peuvent contenir un nombre variable d'éléments et permettent d'insérer ou de supprimer des éléments facilement.
Il existe plusieurs types de listes, notamment :
- Liste chaînée : chaque élément (appelé nœud) contient une valeur et un pointeur vers le nœud suivant.
- Liste doublement chaînée : chaque nœud contient une valeur, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent.
- Liste circulaire : le dernier nœud pointe vers le premier nœud, formant ainsi une boucle.
Exemple de liste chaînée :
struct Node {
int data;
Node *next;
}
Node *head = nullptr;
Node *newNode = new Node();
newNode->data = 10;
newNode->next = head;
head = newNode;
Dans cet exemple, on crée une structure de nœud pour la liste chaînée, on alloue de la mémoire pour un nouveau nœud, on lui assigne une valeur et on l'ajoute au début de la liste.
Il est important de libérer la mémoire allouée pour éviter les fuites de mémoire. On utilise delete pour libérer la mémoire d'un nœud.
Exemple de libération de mémoire :
Node *temp = head;
while (temp != nullptr) {
Node *next = temp->next;
delete temp;
temp = next;
}
Dans cet exemple, on parcourt la liste chaînée et on libère la mémoire de chaque nœud.
Il est aussi possible d'utiliser la bibliothèque list de C++ pour créer des listes. La bibliothèque list gère automatiquement la mémoire et permet d'ajouter ou de supprimer des éléments facilement.
Exemple d'utilisation de list :
#include <list>
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
myList.pop_back();
Dans cet exemple, on crée une liste avec la bibliothèque list, on ajoute des éléments avec push_back, puis on supprime le dernier élément avec pop_back.
Il est important de noter que les listes permettent de gérer des données dont la taille peut varier pendant l'exécution du programme, ce qui est très utile dans de nombreux cas.
Arbres
Un arbre est une structure de données qui permet de stocker des éléments de manière hiérarchique. Chaque élément (appelé nœud) peut avoir plusieurs enfants, mais un seul parent. Le nœud racine est le nœud supérieur de l'arbre.
Il existe plusieurs types d'arbres, notamment :
- Arbre binaire : chaque nœud a au plus deux enfants (gauche et droite).
- Arbre binaire de recherche : un arbre binaire où chaque nœud respecte la propriété de recherche (les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud, et celles du sous-arbre droit sont supérieures).
- Arbre AVL : un arbre binaire de recherche équilibré, où la différence de hauteur entre les sous-arbres gauche et droit est au plus 1.
Exemple d'arbre binaire :
struct Node {
int data;
Node *left;
Node *right;
}
Node *root = nullptr;
Node *newNode = new Node();
newNode->data = 10;
newNode->left = nullptr;
newNode->right = nullptr;
root = newNode;
Dans cet exemple, on crée une structure de nœud pour l'arbre binaire, on alloue de la mémoire pour un nouveau nœud, on lui assigne une valeur et on le définit comme racine de l'arbre.
Il est important de libérer la mémoire allouée pour éviter les fuites de mémoire. On utilise delete pour libérer la mémoire d'un nœud.
Exemple de libération de mémoire :
void deleteTree(Node *node) {
if (node == nullptr) return;
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
deleteTree(root);
Dans cet exemple, on parcourt l'arbre et on libère la mémoire de chaque nœud.
Il est aussi possible d'utiliser la bibliothèque set de C++ pour créer des arbres. La bibliothèque set gère automatiquement la mémoire et permet d'ajouter ou de supprimer des éléments facilement.
Exemple d'utilisation de set :
#include <set>
std::set<int> mySet;
mySet.insert(10);
mySet.insert(20);
mySet.erase(10);
Dans cet exemple, on crée un ensemble avec la bibliothèque set, on ajoute des éléments avec insert, puis on supprime un élément avec erase.
Il est important de noter que les arbres permettent de gérer des données de manière hiérarchique, ce qui est très utile dans de nombreux cas.