INF3105 — Structures de données et algorithmes
Été 2024
UQAM
Département d'informatique

Laboratoire 8 : Dictionnaires et arbres binaire de recherche (ArbreMap)

Objectifs

Lectures préalables

Tâches


Fichiers du Lab8

wget http://cria2.uqam.ca/INF3105/lab8/lab8.zip
unzip lab8.zip

Récupérer la classe ArbreAVL des labs 6 et 7

Remplacez le fichier arbreavl.h par votre plus récente version réalisée au Lab7.

Il est important de compléter les Lab6 et Lab7 avant d'amorcer le Lab8.

Tests de base

Application : analyse du fichier journal du serveur web du cours

Complétez le programme lab8_ip.cpp qui compte le nombre d'adresses IP différentes ayant accédé aux fichiers PDF dans le site Web du cours. Un squelette de départ est fourni dans lab8_ip.cpp.

Voici un extrait du fichier journal fourni apachelogs.txt: 

...
218.156.26.2      01/Sep/2023:08:58:35    GET    /INF3105/diapos/00-debut.pdf
198.96.185.2      01/Sep/2023:15:43:36    GET    /INF3105/diapos/00-debut.pdf
95.168.175.169    01/Sep/2023:16:36:49    GET    /INF3105/diapos/00-debut.pdf
95.168.175.169    01/Sep/2023:16:36:54    GET    /INF3105/diapos/00-debut.pdf
95.168.175.169    01/Sep/2023:16:37:02    GET    /INF3105/diapos/00-debut.pdf
95.168.175.169    01/Sep/2023:16:37:06    GET    /INF3105/diapos/00-debut.pdf
87.110.154.48     01/Sep/2023:19:22:58    GET    /INF3105/diapos/00-debut.pdf
113.47.35.134     01/Sep/2023:19:23:30    GET    /INF3105/diapos/00-debut.pdf
113.47.35.134     01/Sep/2023:19:23:30    GET    /INF3105/diapos/00-debut.pdf
198.96.185.2      02/Sep/2023:10:07:17    GET    /INF3105/diapos/00-debut.pdf
20.242.215.79     02/Sep/2023:11:38:14    GET    /INF3105/diapos/00-debut.pdf
...

Notez que le fichier a été simplifié et que les adresses IP ont été anonymisées.

Le présent exercice est légèrement plus complexe que l'exercice 1 présenté dans les diapositives sur ArbreMap. L'exercice dans les diapositives demande d'associer chaque chaîne de caractères avec un entier servant de compteur. Ici, l'astuce consiste à associer chaque nom de fichier à un ensemble d'adresses IPs. Cela demande l'imbrication de deux arbres, le premier étant un dictionnaire et le deuxième un arbre binaire de recherche. Pour la syntaxe, cela ressemble à l'imbrication d'un tableau de listes : Tableau< Liste<int> > tab;.

Itérateurs

La représentation d'un ArbreMap<K,V>::Iterateur est tout simplement un autre itérateur de type ArbreAVL<Entree>::Iterateur. La déclaration d'un itérateur devrait ressembler à cela. 

class ArbreMap {
  // ...
  public:
    class Iterateur {
      public:
        Iterateur(const ArbreMap& a) : iter(a.entrees.debut()) {}
        Iterateur(typename ArbreAVL<Entree>::Iterateur i) : iter(i) {}
        operator bool() const;
        bool operator!() const;

        Iterateur& operator++();
        Iterateur operator++(int);

        const K& cle() const;
        const V& valeur() const; // constant ou non ?

      private:
        typename ArbreAVL<Entree>::Iterateur iter;
    };
    // ...

    Iterateur debut() const;
    Iterateur fin() const;
    Iterateur rechercher(const K& cle) const;
    Iterateur rechercherEgalOuSuivant(const K& cle) const;
    Iterateur rechercherEgalOuPrecedent(const K& cle) const;
};

Utilisation appropriée des mots clés const

Il ne faut pas perdre de vue qu'on peut utiliser des itérateurs d'ArbreMap sur des dictionnaires constants ou non constants. Voici deux cas d'utilisation.

Cas #1 : ArbreMap constant :

void fonction(const ArbreMap<string, int>& dictionnaire) {
    ArbreMap<string, int>::Iterateur iter = dictionnaire.debut();
    const string& cle = iter.cle();
    const int& v = iter.valeur();
    ...
}

Cas #2 : ArbreMap non constant :

void fonction(ArbreMap<string, int>& dictionnaire) {
    ArbreMap<string, int>::Iterateur iter = dictionnaire.debut();
    const string& cle = iter.cle();
    int& v = iter.valeur();
    v++;
    ...
}

Il y a plusieurs façons de bien gérer les const. En voici deux :

  1. Deux types d'itérateurs :
  2. Un seul type d'itérateur :

L'option B est plus simple à implémenter. L'option A peut être plus conviviale pour l'utilisateur. À vous de choisir!

Enfin, décommentez les fonctions test3() et test4() dans test_arbremap.cpp et les appels de ces fonctions dans main(), et assurez-vous que ces tests réussissent.

Application: historique de températures

Vous devez écrire un programme qui reçoit en entrée des lectures de température. Chaque ligne comporte une date exprimée en heure et une température en Celsius séparées d’un espace blanc. Tous les nombres sont des nombres réels (float). Les données sont dans l’ordre chronologique. Voici un exemple d’entrée. 

0.00 9.0
1.00 10.0
2.00 10.4
3.00 11.0
4.00 12.5
5.00 13.7
6.05 14.7
7.00 13.4
8.10 11.5

Étape 1

Complétez le programme lab8_temperature.cpp qui permet :

  1. d’estimer la température à une date donnée; et
  2. de calculer la température moyenne entre deux dates.

On suppose que la température varie de façon linéaire entres deux dates pour lesquelles la température est connue. Exemples:

Votre solution doit être construite autour d’une classe Historique qui permet de stocker l’historique des températures en mémoire. Vous devez compléter la représentation de la classe Historique et coder les fonctions estimeTemperature(...) et calculeMoyenne(...). 

class Historique {
   private:
     // Représentation
   public:
     Historique();
     ~Historique();
     void ajouter(float date, float temperature);
     float estimeTemperature(float date) const;
     float calculeMoyenne(float datedebut, float datefin) const;
};

Étape 2

Modifiez votre programme (si nécessaire) pour traiter le cas où les données n’arriveraient pas en ordre chronologique.

Si vous jugez qu’aucune modification n’est requise, expliquez pourquoi la solution en A est «parfaite». Si vous jugez que des modifications sont requises, expliquez pourquoi la solution en A demeure pertinente dans le cas où les données seraient en ordre chronologique.

Étape 3

Évaluez la complexité temporelle des fonctions estimeTemperature(...) et calculeMoyenne(...) en A et B.