INF3105 —­­­­­ Structure de données et algorithmes
Automne 2016

Laboratoire 4 : Classes génériques Pile<T> et File<T>

Lectures préalables

Objectifs

Tâche 1 - Téléchargement des fichiers du lab4

wget http://ericbeaudry.ca/INF3105/lab4/lab4.zip
unzip lab4.zip

Temps suggéré : 5 minutes.

Tâche 2 - Analyse sur papier

Temps suggéré : 15 minutes.

Tâche 3 - Expérimentation

Temps suggéré : 15 minutes.

Débogueur DGB

Débogueurs dans les environnements de développement intégré


Tâche 4 - Corrections

Temps suggéré : 20 minutes.

Tâche 5 - Tests unitaires pour Pile<T>

Temps suggéré : 25 minutes.

Tâche 6 - Tests unitaire pour File<T>

Temps suggéré : 30 minutes.

/* Fin du lab4 */

Autres exercices complémentaires

Tâche 7 - Vérification de la libération de la mémoire

Les tests unitaires proposés ne valident pas la libération correcte de la mémoire. Comment pourriez-vous vérifier si la mémoire est correctement libérée? Il y a plusieurs stratégies possibles. La méthode la plus simple est une méthode empirique consistant à faire un grand nombre d'opérations et vérifier la consommation de mémoire. Si jamais une fuite de mémoire (memory leak) était présente, la quantité de mémoire utilisée par le processus augmenterait continuellement.

Voici un programme permettant une telle vérification. 

int main(){
    int n=0;
    while(true){
        cout << (n++) << " ";
        Pile<int> pile1;
        for(int i=0;i<100000;i++)
            pile1.empiler(i);
        Pile<int> pile2 = pile1;
        pile1.vider();
        
        Pile<int> pile3;
        pile3.empiler(10);
        pile3 = pile2;
        pile3 = pile1;
   }
}

Procédure :

  1. Dans un premier terminal, compilez le programme ci-haut.
  2. Optionnel : tapez dans le premier terminal la commande « ulimit -v 32768 » afin de fixer la limite de mémoire à 32 Mo.
  3. Lancez le programme ci-haut dans le premier terminal.
  4. Dans un deuxième terminal, lancez la commande «top» afin de voir les processus en cours d'exécution.
  5. Repérez votre programme en cours d'exécution.
  6. Vérifiez si la mémoire consommée (colonne SIZE) est constante. Si la taille augmente constamment, il y a peut-être un problème.
  7. Pour vous assurez que cette procédure permet de détecter des fuites de mémoires, essayez d'enlever les appels à «delete» dans pile.h, et refaites les tests.

La méthode ci-haut est empire. S'il y a une petite fuite de mémoire, se produisant rarement, cela prendra beaucoup de temps avant de la détecter. De plus, cela ne teste pas tous les cas possible.

À noter qu'il existe des outils permettant de détecter les fuites de mémoire. L'un d'eux est Valgrind.

Tâche 8 - Intégration avec Tableau<>

Il est possible de combiner les structures de données vues jusqu'à présent. Par exemple, on peut faire une tableau de piles! Essayez le programme suivant.

#include "tableau.h"
#include "pile.h"

int main()
{
    Tableau<Pile<int> > tab1;
    for(int i=0;i<100;i++){
        Pile pile<int>;
        pile.empiler(-1);
        tab1.ajouter(pile);
        for(int j=0;j<i;j++)
            tab1[i].empiler(j);
    }
    Tableau<Pile<int> > tab2;
    tab2 = tab1;
    for(int i=0;i<100;i++)
        tab1[i] = Pile<int>();
}

Tâche 9 - Opérateur = efficaces

Pile& Pile::operator = (const Pile& autre){
    if(this==&autre) return *this; // cas special lorsqu'on affecte un objet a lui-meme

    vider(); // ou: while(sommet!=NULL){Cellule*t=sommet->suivante; delete sommet; sommet=t;}
    if(autre.sommet !=NULL){
        sommet = new Cellule(autre.sommet->element);
        Cellule *cp = autre.sommet;
        Cellule *c = sommet;
        while(cp->suivante != NULL){
            c->suivante = new Cellule(cp->suivante->element);
            c = c->suivante;
            cp = cp->suivante;
        }
    }
    return p;
}
/* Fin des exercices complémentaires */