PROFDINFO.COM

Votre enseignant d'informatique en ligne

Travail pratique (15%) - Le graphique manquant

Contexte

https://www.youtube.com/watch?v=YQs6IC-vgmo

Directives

On peut modéliser la liste doublement chainée de la façon suivante:

typedef int montype; 
      
struct CNoeud
{
   CNoeud* Suivant_;
   CNoeud* Precedent_;
   montype Valeur_;
   CNoeud(montype Valeur);
   CNoeud(montype Valeur, CNoeud* Suivant, CNoeud* Precedent);
};

class CListe
{
public:
	CListe();
	~CListe(); 
	bool EstVide() const;
	void AjouterDebut(const montype& Valeur);
	void AjouterFin(const montype& Valeur)
	void AjouterAvant(CNoeud* Position, const montype& Valeur); 
	void RetirerDebut(); 
	void RetirerFin(); 
	void Retirer(CNoeud* Position); 
	CNoeud* Debut_;
	CNoeud* Fin_;
};       

 

  1. Implémenter la liste doublement chainée de int telle que vue en classe. Testez correctement toutes les méthodes de votre liste avant de continuer.
  2. Générez N nombres entiers au hasard et insère-les à la bonne position en ordre croissant dans votre liste, de telle sorte que 5 1 4 2 donne:
    • 5
    • 15
    • 145
    • 1245

    Ensuite, lorsque les N nombres sont insérés dans la liste, retirez les éléments un à un en choisissant une position au hasard et en supprimant l'élément à cette position. Les positions 1 2 0 0 donnent:

    • 1 2 4 5
    • 1 4 5
    • 1 4
    • 4
  3. Mesurez le temps que cela prend pour effectuer les opérations du point 2 lorsque N vaut 10 000, 20 000, 30 000, 40 000 et 50 000. Utilisez le code suivant pour mesurer une série d'instructions:

    auto avant = chrono::system_clock::now();
    // Instruction
    auto apres = chrono::system_clock::now();
    cout << chrono::duration_cast<chrono::milliseconds>(apres-avant).count() << "ms" << endl;
  4. Recommencez les points 2 et 3 mais avec la classe STL list<int>, puis avec vector<int>.
  5. À l'aide d'Excel, illustrez sur un graphique la rapidité de chaque conteneur (votre liste chaînée, list<int> et vector<int>) en fonction de N.
  6. Quelle est la conclusion de cette expérience?

Documents à remettre

Vous devez remettre pour mardi le 20 octobre 23h59 dans la boîte Colnet prévue à cet effet: