5.4  Listes contigües 1/2

• Structure de données Collection.
• Implantation statique en C :

  typedef struct {
    element_t contenu[MAX_ELEMENTS];
    int nombre;
    } liste_t;
  liste_t liste={{},0};
  

• Implantation dynamique en C :

  typedef struct {
    element_t *contenu;
    int nombre;
    int alloue;
    } liste_t;
  liste_t liste={NULL,0,0};
  

• Opérations sur les listes contigües
  • accès, direct O(1) ;
  • recherche :
    • sur liste non ordonnée, séquentielle O(n) ;
    • sur liste ordonnée, dichotomie O(log₂(n)).
  • ajout :
    • sur liste non ordonnée, direct O(1) ;
    • sur liste ordonnée, insertion O(n) ;
    • implantation dynamique, éventuelle ré-allocation.
  • suppression :
    • sur liste non ordonnée, échange O(1) ;
    • sur liste ordonnée, décalage O(n) ;
    • implantation dynamique, éventuelle dé-allocation.
• Exercice "Bibliothèque liste contigüe ordonnée" :
  • créez un répertoire Structures ;
  • créez un sous-répertoire ListeContigue ;
  • écrivez le fichier de configuration makefile ;
  • implantez les fonctions recherche et ajout ;
  • écrivez dans un sous-répertoire TriParListe ...
  • ... un programme de tri de nombres via votre bibliothèque.