Table d'allocation

On considère un tableau $T$ de taille $n$ dans lequel

• $p<n$ cases sont occupées. Chaque donnée $d$ est indexée par l'adresse $i<n$ donnant sa position dans le tableau & on connaît sa taille $m$ ($d$ occupe $m$ cases consécutives de $T$).
• On suppose de plus
  • que la table d'allocation des différentes cases du tableau est codé au format binaire dans un entier $B$ de $n$ bits :

  B=0010010100100...01

• qu'il existe une fonction $f(B,i)$ donnant le i$^{eme}$ bit de $B$ ($f(B,i)$ vaut 1 si la i$^{eme}$ case de $T$ est occupée, & 0 si elle est libre).

Écrire un algorithme permettant d'insérer une donnée $d$ dans le premier bloc de $m$ cases disponible (pensez à mettre à jour la table d'allocation $B$).

Peut-on faire mieux en appliquant un pré-traitement à $B$~?

Ancien sujet