Résumé
Listes chaînées simples et doubles, conteneurs de la Standard Template Library.
Table des matières
Pour expérimenter les listes, nous travaillerons au début en mode texte et non pas avec la librairie QT.
Une liste chaînée simple est une liste d'éléments où chaque élément connaît l'adresse de l'élément qui le suit. Le dernier élément a pour adresse de suivant: 0 (pointeur NULL)
Une liste chaînée est accessible lorsqu'on connaît le premier élément de la liste. Pour accéder au 3ème élément il faudra passer par le premier, puis aller au suivant du premier et ensuite au suivant du deuxième.
Ainsi pour afficher le nom du 3ème élément de la liste, il faudra faire: afficher ((premier->suivant)->suivant->nom).
On peut disposer de liste de n'importe quel type d'objet à condition que chaque élément de la liste connaisse l'adresse de son suivant.
Nous allons définir une liste de contacts. Chaque contact, devra disposer en plus des informations qui lui sont propres, de l'adresse du contact suivant. Définissons donc ainsi notre classe contact :
class contact
{
public:
string nom;
string prenom;
string email;
// et maintenant l'adresse du contact suivant
contact * suivant;
//le constructeur
contact (string n, string p,string e, contact * s);
}
Notre application doit connaître le premier contact. On rajoutera donc en "variable globale" "contact * premierDeLaListe=0".
Au départ on n'a pas encore de contact, c'est pourquoi "premierDeLaListe" ne pointe sur rien, on l'initialise donc à 0.
Exercice: écrire le code du constructeur de la classe contact. Écrire aussi la fonction main.
Lorsque l'on crée un contact, on l'ajoute en tête de liste c'est à dire qu'il va remplacer le premier contact.
contact * nouv =new contact("dupond ", "jean ","[3]jdupond@fd.be",premierDeLaListe);
Un nouveau contact est créé. Son adresse est mise dans "nouv". L'adresse du suivant de nouv est celle de l'ancien premier de la liste donc celle que contient la variable "premierDeLaListe".
Il ne nous reste plus qu'à remplacer l'adresse du premierDeLaListe par "nouv". Puisqu'en l'ajoutant en tête de liste il est devenu le premier de la liste
premierDeLaListe=nouv;
À noter : ces deux instructions sont à mettre dans le main().
Nous allons ici afficher chaque contact.
contact * courant = premierDeLaListe;
while(courant!=0)
{
[4] //on affiche courant->nom
[5] //on affiche courant->prenom
[6] //on affiche courant->email
[7] //on passe au suivant:
courant=courant->suivant; [8]//s'il n'y a pas de suivant rappelons que
// le dernier a pour suivant 0
}
Exercice : Après avoir ajouté deux nouveaux contacts, tester cet algorithme sur votre liste
Un autre constructeur : Écrire un constructeur permettant de saisir un nouveau contact tout en l'ajoutant en tête de liste.
Recherche d'un élément : Écrire une fonction renvoyant l'adresse mémoire d'un contact dont le nom est passé en paramètre. La fonction renverra 0 si elle n'a pas trouvé le contact.
Nombre d'élément de la liste : Écrire une fonction qui renvoie le nombre de contacts se trouvant dans la liste.
Suppression d'un élément de la liste : Écrire une procédure qui détruit un élément de la liste tout en laissant accessibles les autres éléments.
Accès à un élément par son numéro d'ordre : Écrire une fonction qui renvoie l'adresse mémoire d'un contact dont le numéro d'apparition dans la liste est fournit en paramètre.
Liste triée.(insertion d'élément dans une liste triée) : On s'arrangera pour que l'insertion dans la liste ne se fasse pas systématiquement en tête de liste mais plutôt à la bonne place dans la liste. C'est à dire que si on ajoute dupond , il sera entre david et goliath.
Suppression d'une liste : La suppression des éléments d'une liste demande réflexion. Écrire l'algorithme qui permet de supprimer une liste entière en en supprimant tout ses éléments.
Interface graphique : Écrire une interface graphique pour votre liste de contact.
Ajouter à votre application les fonctionnalités suivantes :
Sauvegarde dans un fichier: écrire un slot qui écrit dans un fichier les informations sur tous les contacts.
Construction d'une liste à partir d'un fichier: Écrire un slot qui construit la liste des contacts à partir d'un fichier texte.
Une liste chaînée double est une liste d'éléments où chaque élément connaît l'adresse de l'élément qui le suit, mais aussi l'adresse de l'élément qui le précède.
Le dernier élément a pour adresse de suivant: 0 (pointeur NULL) Le premier élément a pour adresse de précédent: 0 (pointeur NULL)
Reprendre les algorithmes précédents en les appliquant à la gestion d'une liste chaînée double.
Sujet : On souhaite gérer un projet contenant des tâches. Pour chaque tâche on retiendra son numéro, son nom et sa durée. Un projet a un nom et dispose d'une première tâche. Pour chaque tâche, on connaît la tâche suivante, la dernière tâche ayant pour suivante 0;
Une tâche pourra s'afficher. Une tâche pourra être saisie par l'utilisateur. Le projet sera capable de s'afficher. Il sera capable de calculer sa durée.
Écrire un ensemble de classe permettant de résoudre ce problème de gestion.
S'il est intéressant de savoir programmer une liste chaînée de toute pièce, cela entretient les neurones, il va de soi qu'il n'est pas envisageable de réinventer la roue à chaque nouveau programme. Utiliser des composants prêts à l'emploi permet un gain de temps, et vous assure de plus un niveau de fiabilité et de performance que vous auriez du mal à atteindre dans vos débuts.
La Standard Template Library (librairie des modèles standards) propose toutes sortes de structures de données avec les algorithmes associés. On trouvera entre autres: les vecteurs tableaux redimensionnables à la volée, les listes les piles et les tableaux associatifs. Bref tout ce qu'il faut pour stocker et retrouver des infos en mémoire.
Nous verrons ici le "QvalueVector" #include<qvaluevector.h> équivalent du "std::vector".
Ses caractéristiques :
Accès direct contrôlé ou non,
Redimensionnement à la volée,
Contient n'importe quoi.
Déclaration :
Vecteur vide de chaînes: Qvaluevector<string> monPremierVecteur;
Vecteur vide d'entiers: Qvaluevector<int> monDeuxiemeVecteur;
Vecteur d'une capacité de 500 doubles: Qvaluevector<double> monTroisiemeVecteur(500);
Vecteur de 5 chaînes initialisées à "bidon": Qvaluevector<string> monquatriemeVecteur(5,"bidon");
C'est un modèle cela signifie donc qu'il peut contenir n'importe quel type d'info, à la déclaration toutefois, le type du contenu est précisé entre "<" et ">".
Nos deux premiers vecteurs ne contiennent pas de cellule. Au fur et à mesure des ajouts d'éléments, le tableau s'agrandira automatiquement. Il est toutefois préférable de lui réserver un certain nombre de cellules.
monPremierVecteur.reserve(200); //réservation de 200 cases monDeuxiemeVecteur.resize(50,-1);//réservation et remplissage de 50 cellules avec la valeur -1
La capacité est le nombre de cellules réservées. La taille est le nombre de cellules remplies.
monPremierVecteur.capacity() renvoie 200 monPremierVecteur.size() renvoie 0 monDeuxiemeVecteur.capacity() renvoie 50 monDeuxiemeVecteur.size() renvoie 50
monPremierVecteur.push_back("Leon");
L'ajout se fait à la première cellule disponible. Ici l'ajout se fera dans la cellule 0;
monDexiemeVecteur.push_back(12);
Aucune cellule du tableau n'est disponible elles sont toutes remplies avec la valeur (-1) , une nouvelle cellule va être ajoutée et l'entier 12 y sera stocké.
Façon classique :
QValueVector<int> v( 4,1 );
v.push_back( 3 );
v.push_back( 2 );
v.push_back( 1 );
v.push_back( 0 );
qBubbleSort( v );
int somme=0;
for(int i=0;i>v.size();i++)
{
listBox1->insertItem(QString::number(v[i]));
}
Façon moderne : Les itérateurs - un itérateur est un pointeur sur élément.
QvalueVector<int>::iterator it;
for( it = v.begin(); it != v.end(); ++it ){
listBox1->insertItem(QString::number(*it));}
QvalueVector<int>::iterator it;
it=qFind(v.begin(),v.end(),125)
if(it!=v.end()) {//alors trouvé}
remarquez les deux bornes de la recherche.
Exercice : En utilisant cette caractéristique, écrivez le programme qui compte le nombre de fois où l'entier 125 est trouvé dans le vecteur.
Dans les structures séquentielles on trouve les listes chaînées et les piles, nous allons nous intéresser aux listes doublement chaînées. La liste dispose en gros des mêmes méthodes que le vecteur (excepté reserve et resize) .
On trouvera en plus l'ajout en tête de liste push_front. De plus une liste pourra être remplie comme ceci :
liste<<"eleme1"<<"elem2"<<"eleme3";
On pourra aussi ajouter une liste à une liste :
l3=l1+l2;
Il y a aussi une méthode qui renvoie l'index d'un élément :
int index=maListe.findIndex("Dupond");
Exercice : Faîtes saisir une liste de noms puis faîtes les afficher dans l'ordre alphabétique.
Le mapping permet d'associer à un élément, une valeur de clé. En PHP ou en Perl, on appelle cela des tableaux associatifs :
$TRepas=array("matin"=>45,"midi"=>60,"soir"=>100);
La STL appelle cela des map, et le composant associé est un QMap chez QT.
Déclaration :
QMap <string,int> tRepas; tRepas["midi"]=60; tRepas["matin"]=45;
Exercice : À l'aide d'un Qmap<char,int>, faites saisir une phrase puis affichez les statistiques sur le nombre de lettres, et pour chaque caractère le nombre de fois où on le retrouve dans la phrase. Exemple :
le livre est foutu :
e 3
f 1
i 1
l 2
o 1
r1
s 1
t 1
u 2
v 1
\ 3
elem=mapLettre.find("a");
if(elem==mapLettre.end())
{
mapLettre["a"]=1;
}
else
{
mapLettre["a"]+=1;
}