Structures Fondamentales - Fiche de Révision

Introduction

Les structures fondamentales sont les bases de l'organisation des données et des programmes en informatique et en mathématiques. Comprendre ces structures permet d'optimiser le traitement, le stockage et la manipulation des informations. Cette fiche détaillée aborde les principales structures fondamentales, leurs caractéristiques, leurs utilisations ainsi que des exemples concrets pour un niveau intermediate.

1. Les Types de Structures Fondamentales

1.1. Les Structures Linéaires

Les structures linéaires organisent les éléments de manière séquentielle, c'est-à-dire qu'il y a un seul chemin possible à travers tous les éléments.

• Tableaux (Arrays) : collection d'éléments du même type, stockés contigus en mémoire.
• Listes chaînées (Linked Lists) : collection d'éléments où chaque élément pointe vers le suivant.
• Piles (Stacks) : structure LIFO (Last In, First Out).
• Files (Queues) : structure FIFO (First In, First Out).

Une structure linéaire est une collection où les données sont organisées séquentiellement.

Exemple concret : Tableaux vs Listes chaînées

2. Les Piles (Stacks)

Définition

La pile est une structure où le dernier élément ajouté est le premier à être retiré (LIFO).

Opérations principales

• push(x) : ajoute l’élément x au sommet de la pile.
• pop() : retire et renvoie l’élément du sommet.
• peek() : renvoie l’élément au sommet sans le retirer.
• isEmpty() : teste si la pile est vide.

Exemple d’utilisation : annulation dans un éditeur de texte

Chaque action est empilée. Lorsqu’on annule, on dépile la dernière action.

[Diagramme]

3. Les Files (Queues)

Définition

La file est une structure où le premier élément ajouté est le premier à être retiré (FIFO).

Opérations principales

• enqueue(x) : ajoute l’élément x à la fin de la file.
• dequeue() : retire et renvoie l’élément en tête.
• front() : renvoie l’élément en tête sans le retirer.
• isEmpty() : teste si la file est vide.

Exemple d’utilisation : gestion d’une file d’attente

Les clients arrivent dans l’ordre et sont servis dans cet ordre.

[Diagramme]

4. Les Listes Chaînées (Linked Lists)

Définition

Une liste chaînée est une collection d’éléments appelés nœuds, où chaque nœud contient une donnée et un pointeur vers le nœud suivant.

Types de listes chaînées

• Liste simplement chaînée : chaque nœud pointe vers le suivant.
• Liste doublement chaînée : chaque nœud pointe vers le précédent et le suivant.
• Liste circulaire : le dernier nœud pointe vers le premier, formant un cercle.

Exemple concret de liste simplement chaînée

[Diagramme]

Opérations importantes

• Insertion : O(1) si en tête, O(n) sinon.
• Suppression : O(1) en tête, O(n) sinon.
• Recherche : O(n).

5. Les Tableaux Associatifs (Dictionnaires)

Définition

Un tableau associatif (ou dictionnaire) est une structure permettant de stocker des paires clé-valeur.

Caractéristiques

• Accès rapide aux valeurs via leurs clés.
• Généralement implémenté par des tables de hachage.

Exemple en pseudo-code

dictionnaire = {}
dictionnaire["nom"] = "Alice"
dictionnaire["âge"] = 25
print(dictionnaire["nom"]) # Affiche "Alice"

6. Les Arbres

Définition

Un arbre est une structure hiérarchique composée de nœuds, où chaque nœud a un parent (sauf la racine) et zéro ou plusieurs enfants.

Types importants

• Arbre binaire : chaque nœud a au plus deux enfants.
• Arbre binaire de recherche (BST) : arbre binaire avec les valeurs ordonnées (gauche < racine < droite).
• Arbre équilibré (ex: AVL, rouge-noir) : garantit une hauteur minimale pour optimiser les opérations.

Exemple d’arbre binaire

[Diagramme]

Parcours classiques

• Pré-ordre : racine -> gauche -> droite
• In-ordre : gauche -> racine -> droite (ordre croissant pour BST)
• Post-ordre : gauche -> droite -> racine

7. Les Graphes

Définition

Un graphe est un ensemble de nœuds (sommets) reliés par des arêtes (liens), pouvant être orientés ou non.

Types de graphes

• Non orienté : arêtes bidirectionnelles.
• Orienté : les arêtes ont une direction.
• Pondéré : les arêtes ont un poids.

Représentations

• Matrice d’adjacence
• Liste d’adjacence

Exemple simple d’un graphe orienté

[Diagramme]

Liens entre les structures

• Les listes chaînées peuvent implémenter piles et files.
• Les arbres sont une généralisation des listes avec une hiérarchie et plusieurs branches.
• Les graphes généralisent les arbres avec cycles et connexions multiples.
• Les tableaux associatifs optimisent la recherche via des clés par rapport à des listes.

Synthèse

Conclusion

Les structures fondamentales sont essentielles pour organiser et manipuler les données efficacement. Maîtriser leurs caractéristiques, avantages et inconvénients aide à choisir la structure adaptée à chaque problème, garantissant ainsi des performances optimales. La compréhension des interactions entre ces structures, comme comment les piles et files s’appuient souvent sur les listes chaînées, ouvre la voie vers des architectures plus complexes.

N’hésitez pas à revoir ces concepts et à les mettre en pratique pour consolider votre compréhension !