Exercice : Suppression de valeurs

Indication

N’oubliez pas de tester au fur et à mesure chaque nouvelle fonction.

Lors de la suppression de valeurs dans un tableau dynamique, il est possible que le bloc de mémoire alloué devienne beaucoup trop grand, et donc qu’une importante quantité de mémoire soit gaspillée si on ne change pas la mémoire allouée. Pour éviter cela, on redimensionne le bloc mémoire. On choisit cependant, comme pour l’insertion, de ne pas redimensionner le bloc de mémoire à chaque fois: on utilise la même stratégie que pour l’insertion, en réduisant la taille du bloc alloué de moitié lorsque la moitié ou moins de celui-ci est utilisée.

1. Commencez par définir une fonction qui réduit la taille du bloc alloué, si cela est possible.

   void reduire(vecteur *v);
   

   BEGIN SOLUTION

   void reduire(vecteur *v) {
       if (v->count >= v->size / 2) {
           return;
       }
       if (v->count == 0) {
           free(v->data);
           v->data = NULL;
           v->size = 0;
       } else {
           v->size = v->size / 2;
           v->data = (int *)realloc(v->data, sizeof(int) * v->size);
       }
   }
   

   END SOLUTION

2. Définissez maintenant une fonction qui retire et renvoie la dernière valeur présente dans le tableau. Si le tableau est vide, votre fonction renverra la valeur -1.

   int retirer_en_queue(vecteur *v);
   

   BEGIN SOLUTION

   int retirer_en_queue(vecteur *v) {
       if (v->count == 0) {
           return -1;
       }
       v->count--;
       int res = v->data[v->count];
       reduire(v);
       return res;
   }
   

   END SOLUTION

3. Enfin, définissez une fonction qui retire et renvoie la première valeur présente dans le tableau. Si le tableau est vide, votre fonction renverra la valeur -1.

   int retirer_en_tete(vecteur *v);
   

   BEGIN SOLUTION

   int retirer_en_tete(vecteur *v) {
       if (v->count == 0) {
           return -1;
       }
       int res = v->data[0];
       v->count--;
       for (int i = 0; i < v->count; i++) {
           v->data[i] = v->data[i + 1];
       }
       reduire(v);
       return res;
   }
   

   END SOLUTION