Utilisateur:DJ K-Jtan/Programmation
Voici une page où je travaillerai la programmation Structurer en C++
Programmation : Structure de données
[modifier | modifier le wikicode]
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
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
[modifier | modifier le wikicode]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.
}
Programmation : Structure de données/Pile
[modifier | modifier le wikicode]Programmation : Structure de données/Queue
[modifier | modifier le wikicode]Exercices : Structure de données
[modifier | modifier le wikicode]Exercices : Structure de données/Liste
[modifier | modifier le wikicode]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.)
}
}