.. _structures-donnees: ********************* Structures de données ********************* Les structures de données sont des moyens d'organiser et de stocker des données de manière efficace pour permettre un accès et une manipulation faciles. Elles sont fondamentales en informatique, car elles permettent de modéliser des concepts du monde réel et de résoudre des problèmes complexes. On distinguera : - les structures de données abstraites (Abstract Data Type, ADT) ; - l'organisation utilisée pour les mettre en oeuvre ; - leur implémentation dans un langage de programmation. Voici quelques structures de données abstraites courantes, leur représentation et leurs implémentations en Python et C : .. table:: Python +----------------------+----------------------+-----------------------+ | Structure abstraite | Représentation | Implémentation | +======================+======================+=======================+ | Séquence | Tableau dynamique | list | +----------------------+----------------------+-----------------------+ | Séquence | Tableau immuable | tuple | +----------------------+----------------------+-----------------------+ | Pile | Tableau dynamique | list | +----------------------+----------------------+-----------------------+ | File | deque | collections.deque | +----------------------+----------------------+-----------------------+ | Ensemble | Table de hachage | set | +----------------------+----------------------+-----------------------+ | Dictionnaire | Table de hachage | dict | +----------------------+----------------------+-----------------------+ .. table:: C +----------------------+----------------------+-------------------------------------------------------+ | Structure abstraite | Représentation | Implémentation | +======================+======================+=======================================================+ | Séquence | Tableau dynamique | ``struct {int *data; size_t size; size_t capacity;}`` | +----------------------+----------------------+-------------------------------------------------------+ | Séquence | Tableau immuable | ``int t[n]`` | +----------------------+----------------------+-------------------------------------------------------+ | Séquence | Liste chaînée | ``struct {int data; struct Node *next;}`` | +----------------------+----------------------+-------------------------------------------------------+ | Pile | Tableau dynamique | tableau + sommet | +----------------------+----------------------+-------------------------------------------------------+ | Pile | Liste chaînée | liste chainée + tête | +----------------------+----------------------+-------------------------------------------------------+ | File | Tableau circulaire | tableau + indice tête + indice queue | +----------------------+----------------------+-------------------------------------------------------+ | File | Liste chaînée | liste chainée + tête + queue | +----------------------+----------------------+-------------------------------------------------------+ | Ensemble | Table de hachage | à programmer | +----------------------+----------------------+-------------------------------------------------------+ | Ensemble | Arbre de recherche | à programmer | +----------------------+----------------------+-------------------------------------------------------+ | Dictionnaire | Table de hachage | à programmer | +----------------------+----------------------+-------------------------------------------------------+ | Dictionnaire | Arbre de recherche | à programmer | +----------------------+----------------------+-------------------------------------------------------+ .. quiz:: quiz-introduction-structures :title: Introduction aux structures de données - :quiz:`{"type":"TF","answer":"T"}` Une structure de données abstraite (ADT) spécifie les opérations sans préciser l'implémentation. - :quiz:`{"type":"TF","answer":"F"}` Une séquence ne peut être implémentée que par un tableau dynamique. - La :quiz:`{"type":"FB","answer":"représentation","flags":"fuzzy"}` d'une structure de données décrit comment elle est organisée en mémoire. - Une :quiz:`{"type":"FB","answer":"implémentation","flags":"fuzzy"}` est la réalisation concrète dans un langage de programmation. - :quiz:`{"type":"SC","values":"tableau statique,liste chaînée,table de hachage,toutes","answer":"toutes"}` Quelles représentations peuvent implémenter une séquence ? Les représentations =================== La représentation d'une structure de données est la manière dont les données sont organisées en mémoire pour permettre l'accès et la manipulation efficaces. Par exemple, une séquence peut être représentée par un tableau dynamique, une liste chaînée, ou un arbre binaire. Chaque représentation a ses avantages et ses inconvénients en termes de complexité temporelle et spatiale (mémoire) des opérations. .. quiz:: quiz-representations-intro :title: Concept de représentation - :quiz:`{"type":"TF","answer":"T"}` Chaque représentation a des avantages et inconvénients différents. - :quiz:`{"type":"TF","answer":"T"}` La même structure abstraite peut avoir plusieurs représentations différentes. - Le choix de la représentation affecte la :quiz:`{"type":"FB","answer":"complexité","flags":"fuzzy"}` des opérations. - Une représentation doit permettre l'accès et la :quiz:`{"type":"FB","answer":"manipulation","flags":"fuzzy"}` efficaces des données. - :quiz:`{"type":"SC","values":"mémoire,vitesse,complexité,tous","answer":"tous"}` Quel critère faut-il considérer pour choisir une représentation ? Tableau statique ---------------- Un tableau statique est une structure de données qui utilise un tableau alloué statiquement pour stocker les éléments, avec une taille maximale définie à la compilation. Il permet un accès rapide aux éléments par index, mais a une taille fixe et ne peut pas croître dynamiquement. Les éléments peuvent être modifiés, mais il n'est pas possible d'ajouter de nouveaux éléments au-delà de la taille maximale. .. figure:: images/prog-e3-05-structures-donnees-tableau-statique.drawio.png :align: center :width: 60% .. quiz:: quiz-tableau-statique :title: Tableau statique - :quiz:`{"type":"TF","answer":"T"}` La taille d'un tableau statique est définie à la compilation. - :quiz:`{"type":"TF","answer":"F"}` Un tableau statique peut redimensionner automatiquement sa taille. - :quiz:`{"type":"TF","answer":"T"}` Un tableau statique permet un accès rapide aux éléments par index. - Un tableau statique a une taille :quiz:`{"type":"FB","answer":"fixe","flags":"fuzzy"}` et ne peut pas croître. - Le principal inconvénient d'un tableau statique est la :quiz:`{"type":"SC","values":"flexibilité,performance,mémoire,simplicité","answer":"flexibilité"}` Tableau dynamique ----------------- Un tableau dynamique est une structure de données qui utilise un tableau pour stocker les éléments, mais qui peut redimensionner ce tableau lorsque sa capacité est dépassée. Il permet un accès rapide aux éléments par index, mais peut être coûteux en termes de temps de redimensionnement. .. figure:: images/prog-e3-05-structures-donnees-tableau-dynamique.drawio.png :align: center :width: 80% .. quiz:: quiz-tableau-dynamique :title: Tableau dynamique - :quiz:`{"type":"TF","answer":"T"}` Un tableau dynamique peut redimensionner sa capacité automatiquement. - :quiz:`{"type":"TF","answer":"T"}` Un tableau dynamique permet un accès par index aussi rapide que pour un tableau statique. - :quiz:`{"type":"TF","answer":"F"}` Toutes les opérations sur un tableau dynamique sont aussi rapides que les opérations d'accès - Le redimensionnement d'un tableau dynamique peut être :quiz:`{"type":"FB","answer":"coûteux","flags":"fuzzy"}` en termes de temps. - La complexité du redimensionnement d'un tableau dynamique est en temps :quiz:`{"type":"SC","values":"constant,linéaire,logarithmique,quadratique","answer":"linéaire"}` Tableau immuable ---------------- Un tableau immuable est une structure de données qui utilise un tableau pour stocker les éléments, mais qui ne peut pas être modifié après sa création. Il permet un accès rapide aux éléments par index, mais ne permet pas de modifier les éléments ou d'ajouter de nouveaux éléments. .. quiz:: quiz-tableau-immuable :title: Tableau immuable - :quiz:`{"type":"TF","answer":"T"}` Un tableau immuable ne peut pas être modifié après sa création. - :quiz:`{"type":"TF","answer":"T"}` Un tableau immuable permet un accès rapide aux éléments par index. - :quiz:`{"type":"TF","answer":"F"}` On peut ajouter des éléments à un tableau immuable après sa création. - En Python, un tableau immuable est implémenté par le type :quiz:`{"type":"FB","answer":"tuple","size":5}` - Le principal avantage d'un tableau immuable est la :quiz:`{"type":"SC","values":"sécurité,performance,flexibilité,mémoire","answer":"sécurité"}` Tableau circulaire ------------------ Un tableau circulaire est une structure de données qui utilise un tableau pour stocker les éléments, mais qui traite le tableau comme s'il était circulaire en utilisant un index modulo la taille du tableau. Il permet une utilisation efficace de l'espace pour les files, mais peut être plus complexe à implémenter que d'autres représentations. .. figure:: images/prog-e3-05-structures-donnees-tableau-circulaire.drawio.png :align: center :width: 60% .. quiz:: quiz-tableau-circulaire :title: Tableau circulaire - :quiz:`{"type":"TF","answer":"T"}` Un tableau circulaire peut écraser des données. - :quiz:`{"type":"TF","answer":"T"}` Un tableau circulaire est utile pour implémenter une file (FIFO). - L'opération :quiz:`{"type":"FB","answer":"modulo","flags":"fuzzy"}` est utilisée pour implémenter la circularité dans le tableau. - Un tableau circulaire est plus :quiz:`{"type":"FB","answer":"complexe","flags":"fuzzy"}` à implémenter que d'autres représentations. - La structure :quiz:`{"type":"SC","values":"séquence,pile,file,ensemble","answer":"file"}` est implémentée de façon particulièrement approprié avec un tableau circulaire. Liste chaînée ------------- Une liste chaînée est une structure de données qui utilise des noeuds pour stocker les éléments, où chaque noeud contient une référence au noeud suivant. Elle permet une insertion et une suppression efficaces, mais peut être moins efficace pour l'accès aux éléments par index. .. figure:: images/prog-e3-05-structures-donnees-liste-chainee-simple.drawio.png :align: center :width: 40% Les listes chainées peuvent également être doublement chaînées, où chaque noeud contient une référence au noeud précédent et au noeud suivant. Cela permet une navigation bidirectionnelle dans la liste, mais augmente la complexité de l'implémentation et l'utilisation de la mémoire. .. figure:: images/prog-e3-05-structures-donnees-liste-chainee-double.drawio.png :align: center :width: 40% Les listes chainées peuvent également être circulaires, où le dernier noeud pointe vers le premier noeud. Cela permet une navigation circulaire dans la liste, mais peut être plus complexe à implémenter et à gérer. .. quiz:: quiz-liste-chainee :title: Liste chaînée - :quiz:`{"type":"TF","answer":"T"}` Une liste chaînée permet une insertion et suppression efficaces. - :quiz:`{"type":"TF","answer":"F"}` Une liste chaînée est plus rapide qu'un tableau pour accéder aux éléments par index. - :quiz:`{"type":"TF","answer":"T"}` Une liste doublement chaînée permet une navigation bidirectionnelle. - Chaque noeud d'une liste chaînée contient une :quiz:`{"type":"FB","answer":"référence","flags":"fuzzy"}` vers le noeud suivant. - La complexité pour accéder au ième élément d'une liste chaînée est :quiz:`{"type":"SC","values":"en temps constant,linéaire,logarithmique,quadratique","answer":"linéaire"}` Table de hachage ---------------- Une table de hachage est une structure de données qui utilise une fonction de hachage pour mapper les clés à des positions dans un tableau. Elle permet un accès rapide aux éléments par clé, mais peut être coûteuse en termes de mémoire et peut souffrir de collisions (deux clés différentes qui mappent au même indice). .. figure:: images/prog-e3-05-structures-donnees-table-hachage.drawio.png :align: center :width: 80% .. quiz:: quiz-table-hachage :title: Table de hachage - :quiz:`{"type":"TF","answer":"T"}` Une table de hachage utilise une fonction de hachage pour mapper les clés à des positions en mémoire. - :quiz:`{"type":"TF","answer":"T"}` Une collision se produit quand deux clés différentes mappent au même indice. - :quiz:`{"type":"TF","answer":"F"}` Une table de hachage ne peut pas avoir de collisions. - L'accès par clé dans une table de hachage a une complexité moyenne en temps :quiz:`{"type":"FB","answer":"constant","size":6}` Arbre de recherche ------------------ Un arbre de recherche est une structure de données qui organise les éléments dans une hiérarchie d'arbres, où chaque noeud contient une clé et une valeur, et les clés sont organisées de manière à permettre une recherche efficace. Il permet un accès rapide aux éléments par clé, mais peut être plus complexe à implémenter que d'autres représentations. .. figure:: images/prog-e3-05-structures-donnees-arbre-recherche.drawio.png :align: center :width: 80% .. quiz:: quiz-arbre-recherche :title: Arbre de recherche - :quiz:`{"type":"TF","answer":"T"}` Un arbre de recherche organise les éléments dans une hiérarchie. - :quiz:`{"type":"TF","answer":"T"}` Un arbre de recherche permet une recherche efficace par clé. - :quiz:`{"type":"TF","answer":"F"}` Un arbre de recherche est plus simple à implémenter qu'une table de hachage. - Un arbre de recherche organise les :quiz:`{"type":"FB","answer":"clés","size":4}` de manière à permettre une recherche efficace. - La complexité de recherche dans un arbre binaire équilibré est en temps :quiz:`{"type":"SC","values":"constant,linéaire,logarithmique,quadratique","answer":"logarithmique"}` Les structures abstraites ========================= Une structure de données abstraite (Abstract Data Type, ADT) est une description formelle d'une collection de données et des opérations qui peuvent être effectuées sur ces données, sans spécifier comment ces données sont organisées ou implémentées. Elle définit un ensemble d'opérations et les propriétés que ces opérations doivent respecter, mais laisse la liberté de choisir la représentation et l'implémentation la plus appropriée pour répondre à ces exigences. .. quiz:: quiz-adt-intro :title: Structures abstraites de données (ADT) - :quiz:`{"type":"TF","answer":"T"}` Une ADT décrit les opérations sans spécifier l'implémentation. - :quiz:`{"type":"TF","answer":"T"}` Une ADT définit les propriétés que les opérations doivent respecter. - :quiz:`{"type":"TF","answer":"F"}` Une ADT spécifie comment les données sont organisées en mémoire. - Une ADT laisse la liberté de choisir la :quiz:`{"type":"FB","answer":"représentation","flags":"fuzzy"}` la plus appropriée. La séquence ----------- Une séquence est simplement une collection ordonnée d'éléments qui possède les opérations suivantes : * ajouter un élément à la fin de la séquence ; * accéder au ième élément ; * modifier un élément ; * parcourir les éléments. .. quiz:: quiz-sequence :title: La séquence - :quiz:`{"type":"TF","answer":"T"}` Une séquence est une collection ordonnée d'éléments. - :quiz:`{"type":"TF","answer":"F"}` Une séquence ne peut être implémentée que par un tableau dynamique. - En Python, une séquence est implémentée par le type :quiz:`{"type":"FB","answer":"list","size":4}` - Une séquence permet de :quiz:`{"type":"FB","answer":"parcourir","flags":"fuzzy"}` les éléments. - L'opération :quiz:`{"type":"SC","values":"ajouter,supprimer,trier,modifier","answer":"trier"}` n'est généralement pas définie pour une séquence. .. figure:: images/prog-e3-05-structures-donnees-sequence.drawio.png :align: center :width: 50% Comme on peut le voir sur la figure, l'implémentation la plus simple en langage C est un tableau statique. On confond souvent les deux alors que la séquence est une structure de données abstraite, tandis que le tableau est une représentation concrète. Voilà le prompt utilisé pour générer le code correspondant. .. prompt:: LLM - on va utiliser le langage C (C99) pour implémenter une séquence d'entiers ; - la séquence doit comporter les opérations suivantes : ajouter un élément à la fin, accéder au ième élément, modifier un élément et parcourir les éléments. Ces opérations doivent être implémentées sous forme de fonctions ; - le tableau doit être statique et avoir une taille maximale de 100 éléments. La fonction :func:`main` doit contenir des instructions de test pour vérifier le fonctionnement correct de l'implémentation. .. literalinclude:: files/prog-e3-05-sequence-tableau-statique.c :language: c :linenos: :caption: Séquence implémentée avec un tableau statique en C .. exercice:: Séquence implémentée avec un tableau statique (C) ✨ Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. Vous ne maitrisez vraisemblablement pas la totalité du code ci dessus. 👤 Utiliser une approche top-down pour comprendre la structuration du programme en fonctions. Pour chacune d'entre elles, essayer d'inférer leur rôle en identifiant les paramètres d'entrée, les structures de données mises en jeu (et éventuellement modifiées) et les valeurs de retour. ✨ Utiliser l'IA pour vérifier votre compréhension et compléter votre analyse. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. solution:: **Analyse des fonctions** : **ajouter(t, size, x)** : ajoute un élément à la fin du tableau si la taille maximale n'est pas atteinte. **acceder(t, i)** : récupère l'élément à l'index ``i`` si l'index est valide. **modifier(t, i, x)** : remplace l'élément à l'index ``i`` par ``x`` si l'index est valide. **parcourir(t, size)** : affiche tous les éléments du tableau jusqu'à la taille actuelle. **Différence majeure entre C et Python** : - En C, la gestion de la mémoire est manuelle, avec des pointeurs et des allocations explicites. En Python, la gestion de la mémoire est automatique, avec des structures de données intégrées comme les listes. - En C les signatures de fonctions sont plus complexes, avec des pointeurs et des paramètres supplémentaires pour gérer la taille et la capacité. En Python, les signatures sont simples, sans pointeurs ni gestion explicite de la capacité. - En C, le code est plus propice aux erreurs (fuites mémoire, débordements). En Python, le code est concis et sûr, avec moins de risques d'erreurs de segmentation ou de fuites mémoire. - En C, la performance est optimale mais requiert une expertise. En Python, la performance est acceptable, avec une priorité à la simplicité et à la sécurité. | Créer un fichier :file:`exercices/sequence-tableau-statique.c` et y insérer le code ci dessus. Compiler et exécuter le programme pour vérifier son bon fonctionnement. Cette implémentation est opérationnelle mais limitée par la taille fixe du tableau. Une implémentation plus flexible est un tableau dynamique, qui peut redimensionner le tableau lorsque sa capacité est dépassée. .. prompt:: LLM - on va utiliser le langage C (C99) pour implémenter une séquence d'entiers ; - la séquence doit comporter les opérations suivantes : ajouter un élément à la fin, accéder au ième élément, modifier un élément et parcourir les éléments. Ces opérations doivent être implémentées sous forme de fonctions ; - **le tableau doit être dynamique et doubler sa taille lorsqu'il est en limite de capacité.** La fonction :func:`main` doit contenir des instructions de test pour vérifier le fonctionnement correct de l'implémentation. .. note:: Pour écrire le prompt ci dessus, on pourrait utiliser le contexte (mémoire court terme du LLM) et ne pas répéter les instructions déjà données dans le prompt précédent. .. literalinclude:: files/prog-e3-05-sequence-tableau-dynamique.c :language: c :linenos: :caption: Séquence implémentée avec un tableau dynamique en C .. exercice:: Séquence implémentée avec un tableau dynamique (C) ✨ Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. 👤 Observer les différences avec l'implémentation précédente. Vous semblent elles marginales ou significatives ? Justifier votre réponse. ✨ Utiliser l'IA pour vérifier votre compréhension et compléter votre analyse. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. solution:: Les différences sont **très significatives** : **1. Allocation mémoire** : - **Statique** : ``int t[MAX_SIZE]`` alloue la mémoire sur la pile au compile-time - **Dynamique** : ``malloc(INITIAL_CAPACITY * sizeof(int))`` alloue la mémoire sur le tas à l'exécution **2. Gestion de la capacité** : - **Statique** : taille fixe (MAX_SIZE = 100), impossible de dépasser - **Dynamique** : capacité variable qui double automatiquement quand elle est dépassée (10 → 20 → 40 → 80 → ...) **3. Signature de la fonction ajouter** : - **Statique** : ``ajouter(int *t_ptr, int *size_ptr, int x)`` - **Dynamique** : ``ajouter(int **t_ptr, int *size_ptr, int *capacity_ptr, int x)`` Le passage en double pointeur ``int **t_ptr`` est nécessaire car ``realloc`` peut changer l'adresse du tableau. **4. Redimensionnement** : - **Statique** : retour d'erreur si plein - **Dynamique** : redimensionne automatiquement avec ``realloc`` **5. Libération mémoire** : - **Statique** : aucune action requise (pile) - **Dynamique** : ``free(t_ptr)`` obligatoire pour éviter les fuites mémoire **Impact** : L'implémentation dynamique est plus complexe mais bien plus flexible et scalable. Elle peut gérer des milliers d'éléments sans limite arbitraire. | Lorsque vous avez une compréhension suffisante, créer un fichier :file:`exercices/sequence-tableau-dynamique.c` et y insérer le code ci dessus. Compiler et exécuter le programme pour vérifier son bon fonctionnement. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. Comme on le voit, l'implémentation de la séquence est possible en C mais il faut gérer la mémoire manuellement, ce qui peut être complexe et source d'erreurs. En Python, la séquence est implémentée avec une liste intégrée, qui est un tableau dynamique sous-jacent. Dans ce cas, la gestion de la mémoire est automatique et transparente pour le programmeur. .. prompt:: LLM - on va utiliser le langage Python pour implémenter une séquence d'entiers ; - la séquence doit comporter les opérations suivantes : ajouter un élément à la fin, accéder au ième élément, modifier un élément et parcourir les éléments. Ces opérations doivent être implémentées sous forme de fonctions ; - utilise la :class:`list` comme strcuture de données de base. La fonction :func:`main` doit contenir des instructions de test pour vérifier le fonctionnement correct de l'implémentation. .. literalinclude:: files/prog-e3-05-sequence-liste.py :language: python :linenos: :caption: Séquence implémentée avec une liste Python .. exercice:: Séquence implémentée avec une liste (Python) ✨ Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. Observer les différences avec l'implémentation précédente. Vous semblent elles marginales ou significatives ? Justifier votre réponse. 👤 Même sans connaitre tous les détails de la syntaxe, utiliser une approche top-down pour comprendre la structuration du programme en fonctions. Pour chacune d'entre elles, essayer d'inférer leur rôle en identifiant les paramètres d'entrée, les structures de données mises en jeu (et éventuellement modifiées) et les valeurs de retour. En déduire la différence majeure entre l'implémentation C et l'implémentation Python. ✨ Utiliser l'IA pour vérifier votre compréhension et compléter votre analyse. Lorsque vous avez une compréhension suffisante, créer un fichier :file:`exercices/sequence-liste.py` et y insérer le code ci dessus. Exécuter le programme pour vérifier son fonctionnement. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. solution:: **Analyse des fonctions** : **ajouter(t, x)** : ajoute un élément à la fin de la liste avec ``append()`` **acceder(t, i)** : récupère l'élément à l'index ``i`` avec indexation ``[]`` **modifier(t, i, x)** : remplace l'élément à l'index ``i`` **parcourir(t)** : affiche tous les éléments avec une boucle ``for`` **Différence majeure entre C et Python** : +----------------------------------+--------------------------------------+ | **C** | **Python** | +==================================+======================================+ | Gestion **manuelle** de la | Gestion **automatique** de la | | mémoire (pointeurs, malloc, | mémoire (listes dynamiques natives) | | realloc, free) | | +----------------------------------+--------------------------------------+ | Signatures complexes | Signatures simples (pas de | | (int \*\*t_ptr, paramètres | pointeurs, pas de capacité) | | supplémentaires) | | +----------------------------------+--------------------------------------+ | Code verbeux et propice aux | Code concis et sûr (pas de | | erreurs (fuites mémoire, | segmentation faults, pas de fuites) | | débordements) | | +----------------------------------+--------------------------------------+ | Performance optimale mais | Performance acceptable, priorité à | | requiert expertise | la simplicité et la sécurité | +----------------------------------+--------------------------------------+ **Conclusion** : Python abstrait complètement la gestion mémoire en utilisant exclusivement des références (pointeurs). La pile ------- La pile (stack) est une structure de données qui suit le principe du **dernier entré, premier sorti** (LIFO). Elle permet d'empiler des éléments et de les dépiler dans l'ordre inverse de leur insertion. Elle possède les opérations suivantes : - empiler(x) - depiler() - sommet() .. figure:: images/prog-e3-05-structures-donnees-pile.drawio.png :align: center :width: 35% .. quiz:: quiz-pile :title: La pile (stack) - Une pile suit le principe :quiz:`{"type":"SC","values":"dernier entré premier sorti,premier entré premier sorti,aléatoire","answer":"dernier entré premier sorti"}` - :quiz:`{"type":"TF","answer":"F"}` Une pile suit le même principe qu'une file. - :quiz:`{"type":"TF","answer":"T"}` L'opération empiler ajoute un élément au sommet. - L'opération :quiz:`{"type":"FB","answer":"sommet","size":6}` retourne l'élément au sommet sans le retirer. .. exercice:: Pile implémentée avec un tableau statique (C) ✨ Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. ✨ Sur le modèle des prompts précédents, implémenter une pile avec un tableau statique en C. Lorsque vous avez une compréhension suffisante, créer un fichier :file:`exercices/pile-tableau-statique.c` et y insérer le code ci dessus. Exécuter le programme pour vérifier son fonctionnement. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. solution:: Voici une implémentation complète d'une pile avec un tableau statique en C : .. code-block:: c #include #define MAX_SIZE 100 int pile[MAX_SIZE]; int sommet = -1; // Index du sommet de la pile (-1 = pile vide) // Ajoute un élément à la pile int empiler(int x) { if (sommet >= MAX_SIZE - 1) { return -1; // Erreur : pile pleine } pile[++sommet] = x; return 0; // Succès } // Retire et retourne l'élément du sommet int depiler() { if (sommet < 0) { return -999999; // Erreur : pile vide } return pile[sommet--]; } // Retourne l'élément du sommet sans le retirer int sommet_pile() { if (sommet < 0) { return -999999; // Erreur : pile vide } return pile[sommet]; } // Affiche tous les éléments de la pile void afficher_pile() { if (sommet < 0) { printf("Pile vide\n"); return; } printf("Pile : "); for (int i = 0; i <= sommet; i++) { printf("%d ", pile[i]); } printf("\n"); } int main() { // Test 1 : Empiler des éléments printf("=== Test 1 : Empilage ===\n"); empiler(10); empiler(20); empiler(30); afficher_pile(); // Test 2 : Consulter le sommet printf("\n=== Test 2 : Consultation sommet ===\n"); printf("Sommet de la pile : %d\n", sommet_pile()); // Test 3 : Dépiler des éléments printf("\n=== Test 3 : Dépilage ===\n"); printf("Dépilé : %d\n", depiler()); afficher_pile(); printf("Dépilé : %d\n", depiler()); afficher_pile(); printf("Dépilé : %d\n", depiler()); afficher_pile(); // Test 4 : Pile vide printf("\n=== Test 4 : Pile vide ===\n"); int val = depiler(); if (val == -999999) { printf("Erreur : tentative de dépiler d'une pile vide\n"); } // Test 5 : Empilage et dépilage mixte printf("\n=== Test 5 : Opérations mixtes ===\n"); empiler(5); empiler(15); afficher_pile(); printf("Sommet : %d\n", sommet_pile()); depiler(); afficher_pile(); empiler(25); afficher_pile(); return 0; } **Différences clés avec la séquence** : - La pile n'a qu'un seul point d'accès : le sommet (empiler et dépiler) - Les éléments suivent l'ordre LIFO (dernier entré, premier sorti) - La variable ``sommet`` pointe toujours vers l'élément au sommet de la pile - Les opérations sont en O(1) (temps constant) .. exercice:: Pile implémentée avec une liste (Python) ✨ Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. ✨ Sur le modèle des prompts précédents, implémenter une pile avec une liste Python. Lorsque vous avez une compréhension suffisante, créer un fichier :file:`exercices/pile.py` et y insérer le code ci dessus. Exécuter le programme pour vérifier son fonctionnement. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. solution:: Voici une implémentation complète d'une pile en Python : .. code-block:: python def empiler(pile, x): """Ajoute un élément à la fin de la pile""" pile.append(x) def depiler(pile): """Retire et retourne l'élément du sommet""" if len(pile) == 0: return None # Pile vide return pile.pop() def sommet(pile): """Retourne l'élément du sommet sans le retirer""" if len(pile) == 0: return None # Pile vide return pile[-1] def afficher_pile(pile): """Affiche tous les éléments de la pile""" if len(pile) == 0: print("Pile vide") else: print("Pile : ", end='') for elt in pile: print(elt, end=' ') print() def main(): pile = [] # Pile vide # Test 1 : Empilage print("=== Test 1 : Empilage ===") empiler(pile, 10) empiler(pile, 20) empiler(pile, 30) afficher_pile(pile) # Test 2 : Consultation du sommet print("\n=== Test 2 : Consultation sommet ===") print(f"Sommet de la pile : {sommet(pile)}") # Test 3 : Dépilage print("\n=== Test 3 : Dépilage ===") print(f"Dépilé : {depiler(pile)}") afficher_pile(pile) print(f"Dépilé : {depiler(pile)}") afficher_pile(pile) print(f"Dépilé : {depiler(pile)}") afficher_pile(pile) # Test 4 : Pile vide print("\n=== Test 4 : Pile vide ===") val = depiler(pile) if val is None: print("Erreur : tentative de dépiler d'une pile vide") # Test 5 : Opérations mixtes print("\n=== Test 5 : Opérations mixtes ===") empiler(pile, 5) empiler(pile, 15) afficher_pile(pile) print(f"Sommet : {sommet(pile)}") depiler(pile) afficher_pile(pile) empiler(pile, 25) afficher_pile(pile) if __name__ == "__main__": main() **Comparaison avec la version C** : - Python utilise une liste native et des méthodes intégrées (``append()``, ``pop()``) - Pas besoin de gérer manuellement la taille ou la capacité - La vérification de pile vide est plus simple (``len(pile) == 0``) - Le code est beaucoup plus concis et lisible - Les performances sont acceptables pour la plupart des cas d'usage La file ------- La file (queue) est une structure de données qui suit le principe du **premier entré, premier sorti** (FIFO). Elle permet d'enfiler des éléments et de les défiler dans l'ordre de leur insertion. Elle possède les opérations suivantes : - enfiler(x) - defiler() .. figure:: images/prog-e3-05-structures-donnees-file.drawio.png :align: center :width: 80% .. quiz:: quiz-file :title: La file (queue) - Une file suit le principe :quiz:`{"type":"SC","values":"premier entré premier sorti,dernier entré premier sorti,aléatoire","answer":"premier entré premier sorti"}` - :quiz:`{"type":"TF","answer":"F"}` Une file suit le même principe qu'une pile. - :quiz:`{"type":"TF","answer":"T"}` L'opération enfiler ajoute un élément qui sera extrait en dernier. - En C, une file peut être implémentée avec un :quiz:`{"type":"FB","answer":"tableau circulaire","flags":"sequence,fuzzy"}` .. exercice:: File implémentée avec un tableau circulaire (C) ✨ Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. ✨ Sur le modèle des prompts précédents, implémenter une file avec un tableau circulaire en C. Lorsque vous avez une compréhension suffisante, créer un fichier :file:`exercices/file-tableau-circulaire.c` et y insérer le code ci dessus. Exécuter le programme pour vérifier son fonctionnement. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. solution:: Voici une implémentation complète d'une file avec un tableau circulaire en C. .. code-block:: c #include #define MAX_SIZE 100 int file[MAX_SIZE]; int debut = 0; int fin = 0; void enfiler(int x) { file[fin] = x; fin = (fin + 1) % MAX_SIZE; // file circulaire } int defiler() { int x = file[debut]; debut = (debut + 1) % MAX_SIZE; return x; } void afficher_file() { printf("File : "); for (int i = debut; i != fin; i = (i + 1) % MAX_SIZE) { printf("%d ", file[i]); } printf("\n"); } int main() { // Test 1 : Enfiler des éléments printf("=== Test 1 : Enfilage ===\n"); enfiler(10); enfiler(20); enfiler(30); afficher_file(); // Test 2 : Défiler des éléments printf("\n=== Test 2 : Défilage ===\n"); printf("Défilé : %d\n", defiler()); afficher_file(); printf("Défilé : %d\n", defiler()); afficher_file(); printf("Défilé : %d\n", defiler()); afficher_file(); return 0; } .. exercice:: File implémentée avec une deque (Python) ✨ Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. ✨ Sur le modèle des prompts précédents, implémenter une file avec une deque Python. La structure de données :class:`~collections.deque` (double-ended queue) est optimisée pour les opérations d'ajout et de suppression aux deux extrémités, ce qui la rend idéale pour implémenter une file. Lorsque vous avez une compréhension suffisante, créer un fichier :file:`exercices/file-deque.py` et y insérer le code ci dessus. Exécuter le programme pour vérifier son fonctionnement. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. solution:: Voici une implémentation complète d'une file en Python. .. code-block:: python from collections import deque file = deque() def enfiler(x): file.append(x) def defiler(): return file.popleft() def afficher_file(): print("File : ", end='') for elt in file: print(elt, end=' ') print() def main(): # Test 1 : Enfiler des éléments print("=== Test 1 : Enfilage ===") enfiler(10) enfiler(20) enfiler(30) afficher_file() # Test 2 : Défiler des éléments print("\n=== Test 2 : Défilage ===") print(f"Défilé : {defiler()}") afficher_file() print(f"Défilé : {defiler()}") afficher_file() print(f"Défilé : {defiler()}") afficher_file() L'ensemble ---------- Un ensemble est une collection d'éléments uniques, sans ordre particulier. Il permet de stocker des éléments et de vérifier rapidement leur présence. Il fonctionne avec une table de hachage. Il possède les opérations suivantes : - ajouter(x) - supprimer(x) - contient(x) L'implémentation en C est complexe et dépasse le cadre de ce cours. L'implémentation Python utilise le type de données intégré ``set``, qui est basé sur une table de hachage et offre des performances optimales pour ces opérations, avec une complexité temporelle moyenne en temps constant. Le ``set`` sera abordé en détail dans :ref:`python-sets`. .. quiz:: quiz-ensemble :title: L'ensemble (set) - :quiz:`{"type":"TF","answer":"T"}` Un ensemble ne contient que des éléments uniques. - :quiz:`{"type":"TF","answer":"T"}` Un ensemble n'a pas d'ordre particulier. - :quiz:`{"type":"TF","answer":"T"}` Un ensemble utilise une table de hachage pour son implémentation. - En Python, un ensemble est implémenté par le type :quiz:`{"type":"FB","answer":"set","size":3}` - La complexité moyenne de l'opération ``contient(x)`` dans un ensemble est en temps :quiz:`{"type":"FB","answer":"constant","size":4}` Le dictionnaire --------------- Un dictionnaire est une collection de paires clé-valeur, où chaque clé est unique. Il permet de stocker des associations entre des clés et des valeurs, et de récupérer rapidement la valeur associée à une clé donnée. Il possède les opérations suivantes : - ajouter(clé, valeur) - supprimer(clé) - contient(clé) - get(clé) L'implémentation en C est complexe et dépasse le cadre de ce cours. L'implémentation Python utilise le type de données intégré ``dict``, qui est basé sur une table de hachage et offre des performances optimales pour ces opérations, avec une complexité temporelle moyenne en temps constant. Le ``dict`` sera abordé en détail dans :ref:`python-dicts`. .. quiz:: quiz-dictionnaire :title: Le dictionnaire (dict) - :quiz:`{"type":"TF","answer":"T"}` Un dictionnaire stocke des paires clé-valeur. - :quiz:`{"type":"TF","answer":"T"}` Chaque clé dans un dictionnaire est unique. - En Python, un dictionnaire est implémenté par le type :quiz:`{"type":"FB","answer":"dict","size":4}` - La complexité moyenne de l'opération ``get(clé)`` est en temps :quiz:`{"type":"FB","answer":"constant","size":6}`