1. Structures de Données

1.1. Tableau Dynamique

Caractéristiques d'un Tableau

• Stockage : Éléments contigus en mémoire.
• Avantages : Accès rapide aux éléments par index, recherches efficaces (si l'index est connu).
• Inconvénients : L'insertion ou la suppression d'éléments est coûteuse, car elle nécessite le décalage des éléments suivants.

Stratégies de Mise en Œuvre

• Allocation Initiale : Utilisation de fonctions comme malloc() pour réserver un bloc de mémoire.
• Redimensionnement : En cas de capacité insuffisante, realloc() est employé pour ajuster la taille du bloc mémoire, potentiellement en déplaçant le tableau.
• Insertion d'Éléments : Pour insérer un élément à une position donnée, tous les éléments subséquents doivent être décalés d'une position vers la droite.
• Suppression d'Éléments : Pour suprimer un élément, les éléments situés après la position de suppression doivent être décalés d'une position vers la gauche.

1.2. Liste Chaînée

Types de Listes Chaînées

• Liste simplement chaînée
• Liste doublement chaînée
• Liste simplement chaînée circulaire
• Liste doublement chaînée circulaire

Particularités des Listes Chaînées

• Stockage : Éléments dispersés en mémoire. Chaque nœud contient des données et un ou plusieurs pointeurs vers d'autres nœuds.
• Avantages : L'ajout et la suppression de nœuds sont très efficaces, et la taille de la liste peut être étendue facilement sans redimensionnement global.
• Inconvénients : La recherche d'un élément est lente (nécessite une traversée séquentielle). Chaque nœud entraîne un surcoût mémoire pour le stockage des adresses des nœuds adjacents.

Méthodes d'Implémentation

• Chaque nœud est une entité mémoire distincte, contenant la valeur et l'adresse du (ou des) nœud(s) suivant(s).
• Recherche d'un Nœud : Commence par le nœud de tête et parcourt chaque nœud séquentiellement.
• Ajout d'un Nouveau Nœud : Implique la modification des pointeurs du nœud précédent et du nouveau nœud pour l'intégrer dans la séquence.
• Spupression d'un Nœud : Consiste à reconfigurer les pointeurs du nœud précédent pour qu'il pointe directement vers le nœud suivant celui qui est suppprimé.
• Libération de Mémoire : Nécessite de parcourir la liste et de libérer la mémoire de chaque nœud individuellement.

Comparaison entre Tableau Dynamique et Liste Chaînée

• Avantages de la liste chaînée sur le tableau : Efficacité des opérations d'ajout et de suppression de nœuds.
• Inconvénients de la liste chaînée sur le tableau : Faible efficacité de recherche et occupation de mémoire supplémentaire pour les pointeurs.

1.3. Pile (Stack)

Principe Fondamental

• Fonctionne sur le principe LIFO (Last-In, First-Out) : le dernier élément ajouté est le premier à être retiré.

Terminologie Spécifique

• Sommet de Pile (Stack Top) : L'extrémité où les insertions et suppressions sont autorisées.
• Base de Pile (Stack Bottom) : L'extrémité où aucune opération n'est permise.
• Pile Vide : Une pile ne contenant aucun élément.
• Empiler (Push) : L'opération d'ajout d'un nouvel élément au sommet de la pile.
• Dépiler (Pop) : L'opération de suppression de l'élément situé au sommet de la pile.

1.4. File d'Attente (Queue)

Principe Fondamental

• Fonctionne sur le principe FIFO (First-In, First-Out) : le premier élément ajouté est le premier à être retiré.

Terminologie Spécifique

• Tête de File (Front) : L'extrémité d'où les éléments sont retirés.
• Queue de File (Rear) : L'extrémité où les nouveaux éléments sont ajoutés.
• File Vide : Une file ne contenant aucun élément.
• Enfiler (Enqueue) : L'opération d'ajout d'un élément à la queue de la file.
• Défiler (Dequeue) : L'opération de suppression d'un élément de la tête de la file.

2. Algorithmes

2.1. Critères d'Évaluation des Algorithmes

Complexité Temporelle

Décrit l'efficacité d'exécution d'un programme en fonction de la taille des données d'entrée (souvent notée 'n').

n           O(n) Exécutions     O(log n) Exécutions
1           1                   0
2           2                   1
4           4                   2
8           8                   3
...

Ordre de croissance des complexités temporelles (du plus efficace au moins efficace) :

O(1) < O(log n) < O(n) < O(n log n) < O(n^2)

Complexité Spatiale

Décrit la quantité de mémoire utilisée par un programme en fonction de la taille des données d'entrée.

2.2. Algorithmes de Recherche

• Recherche Séquentielle (ou Linéaire) :
  • Parcourt chaque élément un par un.
  • Complexité temporelle : O(n).
• Recherche Binaire :
  • Nécessite impérativement que le tableau soit trié.
  • Divise le tableau en deux à chaque étape pour réduire l'espace de recherche.
  • Complexité temporelle : O(log n), ce qui est très efficace pour de grands ensembles de données.

2.3. Algorithmes de Tri

• **Tri à Bulles (Bubble Sort) :**Parcourt le tableau à plusieurs reprises, compare les éléments adjacents et les échange s'ils sont dans le désordre. Les éléments les plus grands "remontent" progressivement vers la fin du tableau à chaque passe.

  Le processus se répète n-1 fois pour un tableau de n éléments.

• **Tri Rapide (Quick Sort) :**Sélectionne un élément "pivot" et réorganise les autres éléments de manière à ce que tous les éléments plus petits que le pivot le précèdent et tous les éléments plus grands le suivent. Les sous-tableaux sont ensuite triés récursivement.