TP 7: Tableaux dynamiques

TP 7: Tableaux dynamiques#

À faire

2025-2026

  1. Utiliser le terme «construire» plutôt que «créer»?

  2. Utiliser plutôt tableau que vecteur comme nom de type?

  3. Extraire le code dans un fichier à trous vecteur.cpp (ou tableau.cpp).

  4. Une interface alternative serait:

    vecteur creer_vecteur();
void afficher_vecteur(vecteur & v); // voire avec const
void liberer_vecteur(vecteur &v);

    Elle serait plus cohérente avec les conventions de la bibliothèque C++ et réduirait l’usage des pointeurs.

    Mais c’est peut-être un choix pédagogique pour donner une occasion supplémentaire de manipuler des pointeurs? Dans ce cas, il serait utile de le signaler aux étudiants.

Dans ce TP, vous allez implémenter des fonctions de manipulation de tableaux dynamiques (similaires aux vecteurs du C++) sur un modèle similaire à ce que vous avez vu en cours. Vous ne devez pas utiliser le type vector du C++ : l’idée est de faire comme si ce type n’existait pas et que vous deviez l’implémenter.

Pour cela, vous allez devoir écrire des fonctions permettant de créer afficher et détruire ces tableaux dynamique, puis d’autres pour ajouter et supprimer des valeurs et y accéder. L’utilisation des tableaux que vous allez définir ici est bien plus verbeuse que celle des vecteurs du C++ mais le principe est exactement le même. Vous allez voir en cours de Programation Modulaire les objets et la surcharge d’opérateurs qui permettent de simplifier l’utilisation de ces tableaux. De même, nous ne nous intéressons ici qu’aux tableaux d’entiers, mais les technique de programation générique permettent de gérer des tableaux de n’importe quels types.

Contrairement à ce qui à été vu en cours, nous allons ici essayer de réduire le nombre de fois où la taille du bloc mémoire doit changer. Pour cela lorsque le tableau est plein et que l’on souhaite ajouter un élément, on doublera la taille du bloc mémoire. Les ajouts suivants n’auront donc pas à agrandir le bloc mémoire tant que toute la place ajoutée ne sera pas remplie.

Cela implique que la taille du bloc ne coïncide pas forcément avec le nombre d’éléments effectivement présents. Il va donc être nécessaire de mémoriser les deux informations dans le tableau.

Attention

Vos toutes premières fonctions ne pourront pas être testées individuellement: par exemple, pour tester la fonction d’ajout en queue, il faut commencer par créer un tableau. Il vous est conseillé de commencer par écrire les fonctions permettant respectivement de créer un tableau dynamique, de l’afficher et d’ajouter un élément en queue. À ce moment là, vous ferrez une pause pour bien tester tout votre code avant de poursuivre. Par la suite, testez bien au fur et à mesure chaque nouvelle fonction.

Rappels de cours#

La fonction malloc permet d’allouer un nouveau bloc de mémoire dynamique:

void *malloc(size_t size)

  • Elle prend en paramètre la taille du bloc à allouer; celle-ci est généralement calculée en multipliant la taille du type obtenue à l’aide de l’opérateur sizeof avec le nombre d’éléments que l’on souhaite.

  • Elle renvoie une pointeur brut, c’est-à-dire une adresse pointant vers de la mémoire de type indéfini. Il est nécessaire de convertir ce pointeur en un pointeur du bon type.

Par exemple, pour allouer un bloc permettant de stocker trois entiers, on utilisera le code suivant:

int *p = (int *)malloc(3 * sizeof(int));

La fonction realloc permet de changer la taille d’un bloc mémoire dynamique déjà alloué:

void *realloc(void *ptr, size_t new_size);

  • Elle prend en paramètre le bloc de mémoire dont on souhaite changer la taille ainsi que la nouvelle taille. Si ce paramètre vaut NULL, la fonction realloc à le même comportement que la fonction malloc.

  • Elle renvoie l’adresse du nouveau bloc de la taille demandée.

Dans la mesure du possible, la fonction realloc essaye de ne pas déplacer le bloc de mémoire. Cela n’est toutefois pas toujours possible et elle doit parfois allouer un nouveau bloc plus grand et copier les données de l’ancien bloc vers le nouveau bloc. Il est donc nécessaire de toujours bien prendre en compte la nouvelle adresse renvoyée par cette fonction. Attention de ne jamais utiliser l’ancienne adresse car, si le bloc à été déplacé, celle-ci pointe vers de la mémoire qui a été libérée.

La fonction free permet de libérer un bloc de mémoire dynamique lorsque l’on en a plus besoin:

void free(void *ptr);

Il est important de libérer la mémoire lorsque celle-ci n’est plus nécessaire mais attention de ne plus utiliser le bloc ensuite. Mettre le pointeur à NULL est une bonne habitude à prendre; ne pas oublier cependant que l’adresse peut avoir été stockée ailleurs et que cela ne protège donc pas complètement des problèmes.

Exercices#

Effectuez les exercices suivants dans l’ordre, en cochant les cases au fur et à mesure.

Contenu