M3103 – TP3 Exercice 1

Récupérer l’archive suivante : List.zip.

Cette liste contient une tête fictive en début de liste ainsi qu’un pointeur vers le dernier élément réel de la liste (utile notamment pour faire l’instruction push_back ()).

Transformer tous les pointeurs du c en pointeur intelligent (voir amphi2 et amphi4)

Dans un premier temps, transformer la classe CNode, puis modifier le corps de ListeSimple ().
Dans un second temps, transformer la classe CList, l’unique modification de la fonction ListeSimpleV2 () ne doit être que sur la nature du pointeur de recherche (NB: auto est autorisé exceptionnellement car, normalement, on ne devrait pas connaitre la structure interne de la liste en dehors de la classe CList).

M3103 – TP3 Exercice 2

Nous avons montré précédemment que les listes simplement chaînées présentent entre autres un inconvénient majeur : celui d’interdire le retour arrière. Cette impossibilité nécessite, même pour les opérations élémentaires et indispensables comme la suppression d’un élément, de mémoriser au minimum le pointeur vers l’élément précédent au fur et à mesure du parcours. Cependant, toute permutation, tout déplacement (en particulier les tris) deviennent inutilement complexes et malcommodes.

L’alternative est de construire des éléments possédant un double chaînage, vers le précédent et vers le suivant. En fait, chaque information appartient à deux listes simples inverses l’une de l’autre.

Le parcours de la liste double pouvant être effectué à tout moment dans les deux sens, il est normal qu’elle possède deux points d’entrée, la Tete et la Queue.

Dans l’exercice “Sentinelle dans une liste simple”, nous avons montré que les ajouts/suppressions en tête pouvaient être banalisés en insérant au début de la liste, et dès sa construction, un élément “vide”, appelé sentinelle.

Le problème est le même pour les listes doubles, et se reproduit avec les opérations d’ajout/suppression en queue. C’est pourquoi les listes doublement chaînées sont généralement implémentées avec deux sentinelles, appelées naturellement sentinelles de tête et sentinelle de queue. Ainsi, la structure d’une liste double vide est illustrée dans l’encadré supérieur de la figure ci-dessous :

Travail à effectuer
Ajouter à la classe CNode :

  1. la donnée membre m_Prev;
  2. l’accesseur et le modifieur correspondants;
  3. le corps du constructeur et du destructeur de la classe.

Modifier, dans la classe CList, le constructeur, les fonctions AddAfter() et Delete().
Ajouter la fonction AddBefore() de profil :

void AddBefore (const std::shared_ptr < CNode < T>> &, const T & val);    

M3103 – TP3 Exercice 3

L’ordre des éléments dans une liste LRU ne dépend que de l’ancienneté du dernier accès à chaque élément, ce qui implique deux conséquences :

  1. même si la liste est triée à un instant donné, chaque insertion ou recherche a probablement pour effet de modifier l’ordre de la liste (sauf si ce ne sont que de accès en tête). L’algorithme de recherche à utiliser est donc celui d’une recherche séquentielle dans un ensemble non trié.
  2. l’utilisateur ne peut plus choisir la position à laquelle un élément doit être inséré dans la liste : la propriété “LRU” impose qu’elle soit toujours effectuée en tête.
  3. Travail à effectuer
    Modifier la classe CList pour qu’elle réponde au propriété “LRU”.

    Nb: on considère que l’affichage ne modifie pas l’ordre des éléments de la liste.