5.6  Listes chaînées 1/2

• Implantation en C :

  typedef struct cellule_s {
    element_t contenu;
    struct cellule_s *suivant;
    } liste_t;
  liste_t *liste=NULL;
  

• Opérations sur les listes chaînées
  • accès et recherche, séquentiel O(n) ;
  • ajout :
    • sur liste non ordonnée, ajout en tête, direct O(1) ;
    • sur liste ordonnée, recherche puis ajout, séquentiel O(n).
  • suppression, séquentiel O(1) (si pointeur sur précédent).
• Exercice "Bibliothèque liste chainée" :
  • créez un sous-répertoire Structures/ListeChainee ;
  • écrivez le fichier de configuration makefile ;
  • implantez les fonctions recherche, ajout et suppression ;
  • écrivez dans un sous-répertoire Allocation un programme :
    • qui analyse des ordres comme alloc 50 ou free 1 ;
    • un ordre alloc n simule l’allocation de n octets ;
    • un ordre free i simule la libération du bloc de rang i ;
    • représentez les blocs libres et alloués par une unique liste chaînée ;
    • affichez l’état des blocs après chaque ordre ;
    • deux blocs de même type doivent être fusionnés.