Topic outline

  • General

    • Cours de Structures de données en C++ écrit par Yvan Maillot et Frédéric Cordier de l'université de Haute Alsace (UHA) dans le cadre du projet HILISIT. 

      Crédits : 
      Logo Unisciel
      Conférences des Doyens et Directeurs des UFR Scientifiques
      Ministère de l'Enseignement supérieur, de la Recherche et de l'Innovation
      France Relance
      Contributeur au projet :
      Aix-Marseille Université



  • Introduction

    Text and media area: 1

  • Pré-Requis

    Pour suivre ce cours dans de bonnes conditions, l'étudiant doit avoir acquis les connaissances suivantes :

    • la programmation impérative et procédurale (quel que soit le langage, en C de préférence)
      • savoir utiliser les alternatives (if then else)
      • savoir utiliser les itératives (for, while)
      • savoir décomposer un programme en fonctions et procédures
      • connaître les notions de paramètres par valeur et par référence
      • savoir déclarer et utiliser des tableaux
    • les notions élémentaires de la programmation orientée objet (quel que soit le langage, en C++ de préférence)
      • savoir utiliser un objet et accéder à ses membres
      • savoir déclarer et définir une classe
      • connaître les niveaux de visibilité privée et publique
      • savoir ce qu'est un membre, une méthode, un attribut
      • comprendre la liaison amicale qui peut exister entre deux classes

  • Avis aux enseignants

    Ce module est divisé en sections.

    Chaque section comprend :

    • un cours
    • des exercices auto-évaluables

    Ce module offre différents usages :

    1. en totale autonomie : tout étudiant ayant les pré-requis attendu peut lire le cours et s'auto-évaluer en faisant les exercices proposés.
    2. hybride
      Son format se prête bien à une classe inversée dont le cours et une partie des exercices se font en autonomie et le reste des exercices se font en présentiel. L'enseignant peut assez facilement choisir la part à faire en autonomie.
    3. traditionnel

  • Les Pointeurs

    Objectifs : Démystifier et faire comprendre les pointeurs


    Text and media areas: 3 Files: 2 Virtual programming labs: 2

  • Les Tableaux

    Objectifs:

    • (Re)découvrir les tableaux statiques
    • Découvrir les tableaux dynamiques et leurs performances.
    Text and media areas: 3 Files: 2 Virtual programming labs: 12

  • Les Listes Chaînées

    Objectif

    • Découvrir une nouvelle structure de données : la liste chaînée.
    • Identifier ses avantages et ses inconvénients par rapport à ceux des tableaux.
    • Savoir la manipuler.
    • Savoir la programmer.
    Text and media areas: 4 File: 1 Virtual programming labs: 10

  • Les Listes Doublement Chaînées

    Les listes (simplement) chaînées ont été abordées. Chaque élément d'une telle liste connaît son successeur.

    Certains lecteurs se sont peut-être posés la question suivante : pourrait-on ajouter à ces éléments la connaissance de leur prédécesseur ?

    La réponse est oui. Ce sont les listes doublement chaînées.

    L'objectif de ce cours est de montrer et d'expliquer cette possibilité.

    Text and media areas: 3 File: 1 Virtual programming labs: 10

  • Constructeur par recopie

    Objectif

    1. Connaître l'existence du constructeur par recopie implicite
    2. Comprendre le fonctionnement du constructeur par recopie implicite
    3. Reconnaître le constructeur par recopie d'une classe (en général).
    4. Savoir quand le constructeur par recopie  est utilisé.
    5. Savoir pourquoi, quand et comment il faut explicitement le déclarer et le définir
    Text and media areas: 3 File: 1 Virtual programming labs: 5

  • Surcharge des Opérateurs

    Objectif

    1. Découvrir la surcharge des opérateurs.
    2. Lever quelques ambiguïtés.
    3. Savoir les écrire.

    Remarque : l'apprentissage de la surcharge des opérateurs sort un peu du cadre des structures de données. Toutefois, ils sont particulièrement pratiques pour les manipuler. Il serait dommage de s'en passer.



    Text and media areas: 3 File: 1 Virtual programming labs: 5

  • Tableaux 2D

    Objectifs

    • Comparer deux structures de données pour implanter un tableau à deux dimensions.
    • Illustrer l'écriture du constructeur par recopie, nécessaire dans les deux cas.
    • Approfondir l'écriture de la surcharge (efficace) de l'affectation à laquelle l'exemple présent se prête particulièrement bien, dans les deux cas.
    Text and media areas: 3 File: 1 Virtual programming labs: 6

  • Matrices (grâce à la Délégation)

    Objectif : comprendre le principe de, ce qu'on appelle, la délégation sur un exemple.


    Text and media areas: 3 File: 1 Virtual programming labs: 2

  • Suites et itérateurs

    Objectifs :
    • Réaliser une classe de bout en bout qui encapsule une structure de données dont le but est de permettre la manipulation d'une liste d'éléments tout en privilégiant leur insertion et leur suppression.
    • Montrer au travers de cet exemple :
      • l'intérêt des itérateurs dans une collection et
      • l'intérêt de ce qu'on appelle une ancre dans une liste chaînée.


    Text and media areas: 3 File: 1 Virtual programming lab: 1

  • Suites (doublement chaînées) et itérateurs bidirectionnels

    Objectifs :
    • Montrer un exemple assez complet d'une suite à l'aide d'une liste doublement chaînées circulaire avec ancre pour aboutir à une classe très proche de la classe list de la STL (Standard Template Library) du C++.
    • Montrer l'intérêt du choix de la liste doublement chaînées circulaire avec ancre.


    Text and media areas: 3 File: 1 Virtual programming lab: 1