Utilisateur:DJ K-Jtan/Programmation

Voici une page où je travaillerai la programmation Structurer en C++

Programmation : Structure de données

Introduction

Il est bien de penser à une structure comme étant une grande boîte divisé en deux. D'un coté on trouve les informations et de l'autre un pointeur. Cette boite est appelée un noeud ou Node en anglais. L'image ci-dessous représente une liste liée (ou chainé) où l'on peut voir la structure d'un noeud.

La partie de gauche où figure les lettres A, B et C est la partie où l'on retrouve l'information. Vous devinez donc que la partie de droite est le pointeur. Dans une structure de données, le pointeur pointe au prochain noeud et non à l'information que ce noeud suivant contient. Il est possible d'avoir plus de trois cases à notre structure de donnée. En fait, il peut y en avoir un nombre théorique infinie car pour l'ordinateur, il ne s'agit que le regroupement de 1 et de 0.

L'image suivante montre une liste liée double. Elle contient un pointeur suivant et un pointeur précédent (auquel nous parlerons plus en détail dans la section de la liste

Structures de données appliquées

• Liste
• Pile et Pile par héritage
• Queue et Queue par héritage

Construire une structure de données

La structure de données possède le mot clé (Token en anglais) suivant : struct. Comme une classe, il faut donner un nom à notre structure en utilisant la même méthode. Par la suite, entre les "{" et "}" on y insère les informations et les pointeurs que nous voulons avoir dans un noeud. Définissons un noeud que nous appellerons noeudEtudiant où il contiendra des informations sur les attributs qu'un étudiant peut avoir.

struct noeudEtudiant
{
    char prenom[];
    char nom[];
    int age;
};     //Fin de la structure noeudEtudiant

Voilà la déclaration de l'information est fait. Chaque fois que nous allons créé un noeud portant le nom de noeudEtudiant, un prenom, un nom et un age pourrons lui être affecter. Maintenant faut ajouter un pointeur. Puisque que noeudEtudiant sera créé dynamiquement, nous aurons besoin d'un pointeur pour trouver le prochain élément (voir la liste).

Pour pouvoir pointer à un autre noeudEtudiant, le pointeur devra avoir comme type un noeudEtudiant. Le code suivant contient une ligne supplémentaire avec la déclaration du nouveau pointeur.

struct noeudEtudiant
{
    char prenom[];
    char nom[];
    int age;
    noeudEtudiant *suivant;
};     //Fin de la structure noeudEtudiant

Programmation : Structure de données/Liste

Cette section contient une liste créé dynamiquement. Pour créé une liste statique, regarder la section des tableaux.

Structure de la liste Une liste dynamique est construit à partir de structure de données. Une partie de la structure est pour les données et l'autre est pour les pointeurs. L'exemple suivant correspond à un noeud pour un étudiant. Vous devrez insérer cette structure dans la partie privé de votre classe.

struct NoeudEtudiant
{
    int  NI            //Numéro unique d'identification de l'étudiant
    char prenom[];     //Prénom de l'étudiant
    char nom[];        //Nom de l'étudiant
    int  age;          //L'âge de l'étudiant
    noeudEtudiant *suivant;     //Pointeur vers un autre noeudEtudiant
};     //Fin de la structure noeudEtudiant

Classe de la liste

La définition de la classe suivante, appelé Liste, pourra être dérivé (voir les pages : Pile et Pile par héritage Queue et Queue par héritage)

Déclaration de la classe

class Liste
{
Public:
    Liste();
    ~Liste();

    bool EstVide();     //Est-ce que la liste est vide ?
    void Ajouter(char NewPrenom, char NewNom, int NewAge);     //Ajouter un noeud au début de la liste
    void Supprimer(int numIdentification);                     //Supprimer un étudiant en utilisant son numéro d'identification

private:
    NoeudEtudiant *debutListe;                            //Pointe au début de la liste (présentement n'est pas encore déclaré)
    int NumIdent;                                         //Numéro d'identification de l'étudiant. Ce numéro doit être différent pour chaque étudiant.

    //Fonctions privées
    Retrouver(int numIdentification)                      //Retrouver un étudiant en utilisant son numéro d'identification
    Retrouver(char prenom, char nom);                     //Retrouver un étudiant en utilisant son prénom et son nom

}; //fin de la classe Liste

Explication des fonctions

Liste::Liste()
{
     //Dans notre constructeur il faudra créé une nouvelle variable debutListe. Pour se faire vous n'avez qu'à
     //écrire debutListe = new NoeudEtudiant();
     //Ceci aura pour but de créé le noeud où tout ses éléments sont NULL.

     //Il faudra aussi initialiser le NumIdent (qui devra augmenter de 1 pour un nouvel étudiant). 
     //Pour l'instant nous utilisons un int (de 32 bits) et sa valeur ne peux être plus grande que 
     //32,767 alors, 1000 serait un bon nombre pour commencer.
}

Liste::~Liste()
{
     //Question de bien terminer votre programme et de tout libéré la mémoire que vous avez utilisée,
     //vous devrez faire une boucle qui vérifie s'il existe un élément dans la liste. Si oui vous supprimez
     //le premier élément et vous faite pointer le début au suivant (l'utilisation d'un pointeur temporaire 
     //est fortement recommander pour ne pas perdre le reste de votre liste.
}

bool Liste::EstVide()
{
     //Retourne vrai ou faux si la liste est vide. Il suffit de déclarer une variable booléenne,
     //de vérifier si le début est == NULL. Si oui retournez true, sinon retournez false.
}

void Liste::Ajouter(char NewPrenom, char NewNom, int NewAge)
{
     //Nouvel étudiant, on augmente le NumIdent de 1.

     //Par la suite créé un nouveau noeud avec les valeur de NewPrenom, NewNom, NewAge et de NumIdent.
     //Maintenant il faut l'insérer. Pour l'insertion, il existe plusieurs façon de procéder :
          //1. Toujours au début
          //2. Toujours à la fin
          //3. En ordre croissant (décroissant)
          //4. Ordre Alphabétique
          //5. Ordre de priorité
          //Et beaucoup d'autre.
}

Exercices : Structure de données

Exercices : Structure de données/Liste

Voici la solution pour créer une liste dynamique.

class Liste
{
public:
     Liste();
     ~Liste();

     bool EstVide() const;                                      //Est-ce que la liste est vide ?
     void Ajouter(char newPrenom, char newNom, int newAge);     //Ajouter un noeud au début de la liste
     void Supprimer(int numIdentification);                     //Supprimer un étudiant en utilisant son numéro d'identification

private:
     struct NoeudEtudiant
     {
         int  NI            //Numéro unique d'identification de l'étudiant
         char prenom[];     //Prénom de l'étudiant
         char nom[];        //Nom de l'étudiant
         int  age;          //L'âge de l'étudiant
         noeudEtudiant *suivant;     //Pointeur vers un autre noeudEtudiant
     };     //Fin de la structure noeudEtudiant

    NoeudEtudiant *debutListe;                            //Pointe au début de la liste (présentement n'est pas encore déclaré)
    int NumIdent;                                         //Numéro d'identification de l'étudiant. Ce numéro doit être différent pour chaque étudiant.

    //Fonctions privées
    Retrouver(int numIdentification)                      //Retrouver un étudiant en utilisant son numéro d'identification
    Retrouver(char prenom, char nom);                     //Retrouver un étudiant en utilisant son prénom et son nom
};


Liste::Liste()
{
     //Constructeur défaut
     debutListe = new NoeudEtudiant();

     NumIdent = 1000;
}

Liste::~Liste()
{

}

bool Liste::EstVide() const
{
     if (debutListe->NI == NULL)
     {
         //La liste est vide
         return true;
     }

     else
     {
         //Il y a au-moins un élément dans la liste
         return false;
     }
}

void Liste::Ajouter(char newPrenom, char newNom, int newAge)
{
     //Cette fonction insère par ordre alphabétique du nom de famille
     if (debutListe->NI == NULL)
     {
          //Premier élément de la liste
          debutListe->NI = NumIdent;
          NumIdent++;                           //Incrémente pour le prochain nom
          debutListe->prenom = newPrenom;
          debutListe->nom = newNom;
          debutListe->age = newAge;
          debutListe->suivant = NULL;
     }

     else
     {
          //Il faut trouver le bon endroit pour insérer
          //1. Si le nom de famille doit être insérer dans la liste.
          //2. Si le nom de famille est dans le milieu de la liste.
          //2.1 Si le nom de famille est à la fin (faire la même chose que l'étape 2.)
     }
}