Objectif

Implémenter une gestion des données en C selon deux approches différentes défini dans les sections suivantes.
Elle devront respecter les contraintes suivantes :

  • Utilisé majoritairement l’allocation dynamique (malloc et free)
  • Aucune fuite mémoire : Toute mémoire allouée doit être libérée au bon moment.
  • Les cas d’erreur (structure vide, échec d’allocation).
  • Aucun comportement indéfini ne doit subsister.
  • Idéalement, le code doit compiler sans warning avec : -Wall -Wextra

Pour chaque implémentation :

  1. Déterminer la complexité asymptotique (notation ( $O(\cdot)$ ) ) de chaque fonction.
    • O (Big O) : Limite supérieure, pire cas (e.g., O(n) = jamais plus que n).
    • Ω (Big Omega) : Limite inférieure, meilleur cas (e.g., Ω(1) = au moins constant).
    • Θ (Theta) : Limite exacte quand O = Ω (e.g., Θ(n) = exactement linéaire).
  2. Comparer les deux solutions selon :
    • complexité temporelle
    • complexité spatiale
    • avantages et inconvénients pratiques
  3. Proposez des solutions pour optimiser les fonctions

Mémoire contigues

On souhaite implémenter une structure basée sur l’utilisation de tableau dynamique (comprendre ici malloc) et redimensionnable (cette propriétés sera construite). Vous avez le choix pour la définition de la structure, nous pouvons considéré la gestion d’entier (init) pour simplifier, dans tous les cas je vous propose la base suivante :

struct Buffer {
     int *data; // pointeur vers la mémoire gérée
     unsigned int size; // quantité de donnée réelement utilisée
     unsigned int capacity; // taille mémoire allouée
};

typedef struct Buffer Buffer; // alias

Implémentation des fonctions suivantes:

  • Buffer* init() on pourra considérer une capacité initial (eg: 32)
  • void destroy(Buffer*)
  • void push_front(Buffer*, int value)
  • void push_back(Buffer*, int value)
  • int pop_front(Buffer*)
  • int pop_back(Buffer*)

Les fonctions push doivent agrandir le buffer si la capacity est inssufisante (ie celui représenté par @data). On pourra prendre un facteur multiplicatif (eg x2). Il faudras donc allouer un nouveaux buffer tempon, copier les datas dans le ouveaux et bien pensé a libéré l’ancien pointeur, donc en évitant les fuite mémoire ou les dangling pointers. Vous devez donc gérer correctement :

  • le redimensionnement du tableau
  • les cas limites

Mémoire fragmentées

On souhaite implémenter la même interface en utilisant une liste chaînée simple. De la même façon, vous pouvez proposer votre propre struture et nous considérerons aussi des entiers pour le stockage. Dans tous les cas je vous propose un point de départ : une structure de base pour représenté la liste

struct LinkedList {
     int data; // La valeur do noeud
     struct LinkedList  *next; // Le pointeur/lien vers le suivant
};

typedef struct LinkedList LinkedList; // alias

Implémentation des fonctions suivantes

  • LinkedList *begin = NULL représente une liste vide
  • void destroy(LinkedList*) supprime toute la liste et tous les noeud en mémoire
  • void push_front(LinkedList**, int) attention dois modifier begin
  • void push_back(LinkedList*, int)
  • int pop_front(LinkedList*)
  • int pop_back(LinkedList*)

gestion correcte des cas limites :

  • liste vide
  • liste avec un seul élément