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 :

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

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

Une structure de données abstraite (ADT) spécifie les opérations sans préciser l’implémentation.
Une séquence ne peut être implémentée que par un tableau dynamique.
La d’une structure de données décrit comment elle est organisée en mémoire.
Une est la réalisation concrète dans un langage de programmation.
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.

Chaque représentation a des avantages et inconvénients différents.
La même structure abstraite peut avoir plusieurs représentations différentes.
Le choix de la représentation affecte la des opérations.
Une représentation doit permettre l’accès et la efficaces des données.
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.

La taille d’un tableau statique est définie à la compilation.
Un tableau statique peut redimensionner automatiquement sa taille.
Un tableau statique permet un accès rapide aux éléments par index.
Un tableau statique a une taille et ne peut pas croître.
Le principal inconvénient d’un tableau statique est la

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.

Un tableau dynamique peut redimensionner sa capacité automatiquement.
Un tableau dynamique permet un accès par index aussi rapide que pour un tableau statique.
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 en termes de temps.
La complexité du redimensionnement d’un tableau dynamique est en temps

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.

Un tableau immuable ne peut pas être modifié après sa création.
Un tableau immuable permet un accès rapide aux éléments par index.
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
Le principal avantage d’un tableau immuable est la

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.

Un tableau circulaire peut écraser des données.
Un tableau circulaire est utile pour implémenter une file (FIFO).
L’opération est utilisée pour implémenter la circularité dans le tableau.
Un tableau circulaire est plus à implémenter que d’autres représentations.
La structure 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.

../_images/prog-e3-05-structures-donnees-liste-chainee-simple.drawio.png

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.

../_images/prog-e3-05-structures-donnees-liste-chainee-double.drawio.png

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.

Une liste chaînée permet une insertion et suppression efficaces.
Une liste chaînée est plus rapide qu’un tableau pour accéder aux éléments par index.
Une liste doublement chaînée permet une navigation bidirectionnelle.
Chaque noeud d’une liste chaînée contient une vers le noeud suivant.
La complexité pour accéder au ième élément d’une liste chaînée est

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).

../_images/prog-e3-05-structures-donnees-table-hachage.drawio.png

Une table de hachage utilise une fonction de hachage pour mapper les clés à des positions en mémoire.
Une collision se produit quand deux clés différentes mappent au même indice.
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

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.

../_images/prog-e3-05-structures-donnees-arbre-recherche.drawio.png

Un arbre de recherche organise les éléments dans une hiérarchie.
Un arbre de recherche permet une recherche efficace par clé.
Un arbre de recherche est plus simple à implémenter qu’une table de hachage.
Un arbre de recherche organise les de manière à permettre une recherche efficace.
La complexité de recherche dans un arbre binaire équilibré est en temps

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.

Une ADT décrit les opérations sans spécifier l’implémentation.
Une ADT définit les propriétés que les opérations doivent respecter.
Une ADT spécifie comment les données sont organisées en mémoire.
Une ADT laisse la liberté de choisir la 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.

Une séquence est une collection ordonnée d’éléments.
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
Une séquence permet de les éléments.
L’opération n’est généralement pas définie pour une séquence.

../_images/prog-e3-05-structures-donnees-sequence.drawio.png

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.

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 main() doit contenir des instructions de test pour vérifier le fonctionnement correct de l’implémentation.

Séquence implémentée avec un tableau statique en C

#include <stdio.h>

#define MAX_SIZE 100

int ajouter(int *t_ptr, int *size_ptr, int x)
{
     if (*size_ptr >= MAX_SIZE)
     {
          return -1;  // Échec : tableau plein
     }

     t_ptr[*size_ptr] = x;
     *size_ptr = *size_ptr + 1;
     return 0;  // Succès
}

int acceder(int *t_ptr, int i)
{
     return t_ptr[i];
}

void modifier(int *t_ptr, int i, int x)
{
     t_ptr[i] = x;
}

void parcourir(int *t_ptr, int taille)
{
     for (int i = 0; i < taille; i++)
     {
          printf("%d ", t_ptr[i]);
     }
}

int main()
{

     int t[MAX_SIZE];     // tableau statique de 100 éléments
     int size = 0; // nombre d'éléments actuellement dans le tableau

     if (ajouter(t, &size, 1) != 0) {
          printf("Erreur : impossible d'ajouter l'élément\n");
     }
     if (ajouter(t, &size, 2) != 0) {
          printf("Erreur : impossible d'ajouter l'élément\n");
     }
     if (ajouter(t, &size, 3) != 0) {
          printf("Erreur : impossible d'ajouter l'élément\n");
     }

     printf("Séquence : ");
     parcourir(t, size);

     printf("\nAccéder à l'élément d'indice 1 : %d\n", acceder(t, 1));

     modifier(t, 1, 42);
     printf("Séquence après modification : ");
     parcourir(t, size);

     printf("\n");
     return 0;
}

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 revue de code, ajouter la documentation, et s’assurer que les repos local et distant soient correctement 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 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.

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 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.

Séquence implémentée avec un tableau dynamique en C

#include <stdio.h>
#include <stdlib.h>

#define INITIAL_CAPACITY 10

int ajouter(int **t_ptr, int *size_ptr, int *capacity_ptr, int x)
{
     if (*size_ptr >= *capacity_ptr)
     {
          // Doubler la capacité
          *capacity_ptr *= 2;
          int *new_ptr = realloc(*t_ptr, *capacity_ptr * sizeof(int));
          if (new_ptr == NULL)
          {
               return -1;  // Échec : allocation mémoire
          }
          *t_ptr = new_ptr;
     }

     (*t_ptr)[*size_ptr] = x;
     *size_ptr = *size_ptr + 1;
     return 0;  // Succès
}

int acceder(int *t_ptr, int i)
{
     return t_ptr[i];
}

void modifier(int *t_ptr, int i, int x)
{
     t_ptr[i] = x;
}

void parcourir(int *t_ptr, int taille)
{
     for (int i = 0; i < taille; i++)
     {
          printf("%d ", t_ptr[i]);
     }
}

int main()
{
     int *t_ptr = malloc(INITIAL_CAPACITY * sizeof(int));
     if (t_ptr == NULL)
     {
          printf("Erreur : allocation mémoire impossible\n");
          return 1;
     }

     int size = 0;
     int capacity = INITIAL_CAPACITY;

     if (ajouter(&t_ptr, &size, &capacity, 1) != 0) {
          printf("Erreur : impossible d'ajouter l'élément\n");
     }
     if (ajouter(&t_ptr, &size, &capacity, 2) != 0) {
          printf("Erreur : impossible d'ajouter l'élément\n");
     }
     if (ajouter(&t_ptr, &size, &capacity, 3) != 0) {
          printf("Erreur : impossible d'ajouter l'élément\n");
     }

     printf("Séquence : ");
     parcourir(t_ptr, size);

     printf("\nAccéder à l'élément d'indice 1 : %d\n", acceder(t_ptr, 1));

     modifier(t_ptr, 1, 42);
     printf("Séquence après modification : ");
     parcourir(t_ptr, size);

     printf("\n");

     // Ajouter plus d'éléments pour tester le redimensionnement
     for (int i = 0; i < 15; i++)
     {
          if (ajouter(&t_ptr, &size, &capacity, i * 10) != 0) {
               printf("Erreur : impossible d'ajouter l'élément\n");
          }
     }

     printf("Séquence après ajout de 15 éléments (capacity=%d) : ", capacity);
     parcourir(t_ptr, size);
     printf("\n");

     free(t_ptr);
     return 0;
}

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 revue de code, ajouter la documentation, et s’assurer que les repos local et distant soient correctement 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 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 revue de code, ajouter la documentation, et s’assurer que les repos local et distant soient correctement 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.

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 list comme strcuture de données de base. La fonction main() doit contenir des instructions de test pour vérifier le fonctionnement correct de l’implémentation.

Séquence implémentée avec une liste Python

def ajouter(t, x):
    t.append(x)

def acceder(t, i):
    return t[i]

def modifier(t, i, x):
    t[i] = x

def parcourir(t):
    for elt in t:
        print(elt, end=' ')

def main():
    t = [] # liste vide
    ajouter(t, 1)
    ajouter(t, 2)
    ajouter(t, 3)
    print("Séquence après ajout : ", end='')
    parcourir(t)
    print("\nAccéder au 2ème élément : ", acceder(t, 1))
    modifier(t, 1, 42)
    print("Séquence après modification : ", end='')
    parcourir(t)
    print()

if __name__ == "__main__":
    main()

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 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 revue de code, ajouter la documentation, et s’assurer que les repos local et distant soient correctement 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 mémoire (pointeurs, malloc, realloc, free)	Gestion automatique de la mémoire (listes dynamiques natives)
Signatures complexes (int **t_ptr, paramètres supplémentaires)	Signatures simples (pas de pointeurs, pas de capacité)
Code verbeux et propice aux erreurs (fuites mémoire, débordements)	Code concis et sûr (pas de segmentation faults, pas de fuites)
Performance optimale mais requiert expertise	Performance acceptable, priorité à 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()

../_images/prog-e3-05-structures-donnees-pile.drawio.png

Une pile suit le principe
Une pile suit le même principe qu’une file.
L’opération empiler ajoute un élément au sommet.
L’opération retourne l’élément au sommet sans le retirer.

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 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 revue de code, ajouter la documentation, et s’assurer que les repos local et distant soient correctement synchronisés.

💡 Solution

Voici une implémentation complète d’une pile avec un tableau statique en C :

#include <stdio.h>

#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)

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 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 revue de code, ajouter la documentation, et s’assurer que les repos local et distant soient correctement synchronisés.

💡 Solution

Voici une implémentation complète d’une pile en 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()

../_images/prog-e3-05-structures-donnees-file.drawio.png

Une file suit le principe
Une file suit le même principe qu’une pile.
L’opération enfiler ajoute un élément qui sera extrait en dernier.
En C, une file peut être implémentée avec un

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 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 revue de code, ajouter la documentation, et s’assurer que les repos local et distant soient correctement synchronisés.

💡 Solution

Voici une implémentation complète d’une file avec un tableau circulaire en C.

#include <stdio.h>

#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;
}

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 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 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 revue de code, ajouter la documentation, et s’assurer que les repos local et distant soient correctement synchronisés.

💡 Solution

Voici une implémentation complète d’une file en 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 Les sets.

Un ensemble ne contient que des éléments uniques.
Un ensemble n’a pas d’ordre particulier.
Un ensemble utilise une table de hachage pour son implémentation.
En Python, un ensemble est implémenté par le type
La complexité moyenne de l’opération contient(x) dans un ensemble est en temps

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 Les dictionnaires.

Un dictionnaire stocke des paires clé-valeur.
Chaque clé dans un dictionnaire est unique.
En Python, un dictionnaire est implémenté par le type
La complexité moyenne de l’opération get(clé) est en temps