C25. Vecteurs  Corrigé 

Soit à ranger un ensemble de données dans un vecteur V(1..M). On suppose qu' initialement, seul le sous-vecteur V(1..N) est rempli (N = M Div 2). Puis, des mises à jour ( insertions et suppressions ) très fréquentes sont éffectuées sur ce vecteur. Une insertion se fait toujours après une valeur donnée. Une suppression est faite logiquement, c'est à dire par le positionnement d'un bit faisant ainsi apparaître un " trou". Quand le nombre de "trous" devient supérieur à 1/3 du nombre de données effectivement présentes, un algorithme de récupération de "trous" doit être lancé. Le traitement s'effectue alors sur le même vecteur.

- Définir la structure de données ( c'est à dire la description algorithmique du vecteur V).

- Comment l'initialiser ?

- Ecrire le module de recherche R.

- Utiliser R pour écrire l'algorithme I d'insertion d'une valeur v donnée après une valeur v' donnée du vecteur.

- Utiliser R pour écrire l'algorithme de suppression.

- Quel est le temps moyen de R et de I ( Nombre de Comparaisons et d'affectations).

- Quel est le gain sur le temps de R après le lancement de l'algorithme de récupération de "trous".

- qu'un tableau à 3 dimensions est un vecteur de vecteurs de vecteurs,

- et qu'un vecteur est une suite contigu� d'éléments en mémoire, écrire un algorithme qui engendre tous les éléments dans leur ordre de rangement en mémoire puis donner la formule donnant

la position de l’élément T(i, j, k) dans le tableau T(1..N, 1..M, 1..P). Généraliser la formule pour un tableau à n dimensions.