Les listes d'objets doublement chaînées

Création d'objets dynamique. Création de liste. Ajout dans une liste. Suppression d'un objet dans la liste. La récursivité.

Article lu   fois.

L'auteur

Site personnel

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

0. Présentation

Les listes chaînées constituent une alternative aux tableaux. L'ajout, l'insertion et le retrait d'information y sont très rapides et la longueur totale de la liste est inconnue au départ. Cependant, la recherche est lente, la sauvegarde délicate.


Une liste chaînée est un ensemble de cellules, d'objets, de structures, relié entre eux par des pointeurs


On pourrait représenter une liste chaînée comme ceci :

image


L'inconvénient majeur des listes simplement chaînées est qu'on ne peut les parcourir que du début vers la fin.


La solution c'est la liste doublement chaînée :

image


Ce nouveau support va vous faire programmer une liste doublement chaînée.


Pour commencer, créez un nouveau projet nommé "ListeDC", ce projet ne gère aucune analyse. Il contiendra une fenêtre et une classe.

I. La fenêtre :

Créez une nouvelle fenêtre que vous nommerez "Départ".


Voici ses dimensions : 350x230

Tp10-1

I-A. Tableau d'objets :

Type de champ Nom Libelle Position relative Taille
Bouton Bremplir Remplir 150, 153 80X24
Bouton Bvoir Voir la liste 6, 6 80X24
Bouton Bsupprime Supprimer 6, 48 80X24
Champ liste Listeprénom Aucun 121, 8 150x128


Vous n'oublierez pas de mettre cette fenêtre comme première du projet.


Le rôle du bouton "Remplir" est de remplir la liste doublement chaînée d'éléments, ici une liste de prénoms et de les ajouter dans la liste chaînée.


Le bouton "Voir la liste" efface les éléments présents dans la zone d'affichage "liste" et inscrit ceux contenus dans la liste chaînée.


Le bouton "Supprimer" supprime à la fois dans la liste chaînée et dans la zone d'affichage "liste".


Voilà pour le décor, passons à que tout fonctionne, nous avons besoin d'une classe nommée "Cliste".


Je vous laisse la concevoir à partir de ce diagramme UML.

Tp10-2


Voyons ensemble cette classe.


Les attributs comportent :

  • Un objet nommé Oprécédent chargé de contenir la référence de l'objet Cliste précédent (ce qui explique le lien de ré-entrance).
  • Un objet nommé Osuivant chargé de contenir l'objet Cliste suivant.
  • Une chaine nommée Lenom qui contiendra la valeur à faire afficher.


Les méthodes publiques sont celles qui seront nécessaires à la mise en ouvre de la classe :


Pour faire fonctionner une liste nous avons besoin :

  • D'ajouter un élément à l'intérieur,
  • De supprimer un élément,
  • De lire.


Nous aurions aussi besoin d'insérer et de modifier mais je vous laisse le soin de créer vous même ces 2 méthodes là !


Les méthodes privées sont des méthodes fonctionnelles inaccessibles de l'extérieur. Elles servent aux différents positionnements ou déplacement dans les besoins du cours, il n'y a aucune optimisation donc les puristes vont pouvoir trouver de quoi s'amuser en exercice.


Je pense que vous venez de voir quelles méthodes vont activer les 3 boutons ?


On décortique la classe ?

Tp10-3


Comme vous le voyez dans la déclaration de on lui signifie qu'elle contiendra 2 objets Cliste dynamiques ( par référence ).

I-B. La méthode ajouter :

Tp10-4


Explications : La méthode ajouter est chargée d'ajouter une valeur dans notre liste chaînée. On vérifie que la valeur passée en paramètre est valide. Ensuite on teste si l'attribut "lenom" de l'objet en cours est affecté ou pas s'il n'est pas affecté on lui affecte la variable passée en paramètre sinon on appelle la méthode parcourir en lui passant en paramètre l'objet en cours et la valeur à ajouter dans la liste chaînée.

I-C. La méthode Parcourir :

Tp10-5


La méthode parcourir à comme but de parcourir la liste chaînée vers la fin jusqu'à ce qu'elle trouve un emplacement "Objet suivant" vide (Null). Dès qu'elle a une place libre, elle y affecte la référence du nouvel objet.

Toute l'élégance de cette méthode tient au fait quelle est récursive, c'est à dire quelle se rappelle jusqu'à ce quelle trouve une place libre. Remarquez la chose suivante : au début a comme paramètre objet l'objet en cours, ensuite en récursivité elle prend l'objet suivant et si elle n'a pas trouvé, elle progresse d'objet suivant en objet suivant.

Je suis clair ?


Voici une autre méthode utilisant but est de renvoyer le premier objet de la liste chaînée. Etudiez son comportement.

I-D. La méthode Débutliste :

Tp10-7

I-E. La méthode lire:

Cette méthode fait passer l'objet en cours à la méthode "débutliste" qui recherche le premier objet de la liste chaînée et donne la référence du premier objet à "lobjet". Une fois ceci réalisé, la méthode supprime tout le contenu de la liste de la fenêtre "départ". Ensuite, elle enclenche une méthode de lecture de la liste chaînée.

Tp10-6

I-F. Méthode Lire_suivant:

Cette méthode récursive remplit la liste de la fenêtre "départ" du début de la liste chaînée à vous laisse l'analyser.

Tp10-8

I-G. La méthode Rechercher :

Comme vous le voyez cette méthode recherche dans un objet une valeur, pour progresser dans la liste chaînée il emploie la méthode "Avance".

image

I-H. La méthode Avance :

C'est beau la récursivité, je ne m'en lasse pas.Allez je vous laisse comprendre ce qu'elle fait, c'est simple.

Tp10-10

I-I. La méthode Supprimer :

Celle là c'est ma préférée ! Elle utilise la méthode "débutliste" pour se positionner en début de liste, elle lance ensuite la méthode de recherche de valeur.

Une fois l'objet contenant la valeur trouvé, elle le supprime. En fait elle ne le supprime pas pour de vrai, on pourrait dire qu'elle le débranche de ce qu'elle fait sur ce dessin (on débranche p_1) :

Tp10-12
Tp10-13


C'est magique, non ? Voici le code :

Tp10-11


Voilà la définition de la classe est finie.

Voyons le code des objets de la fenêtre :


On démarre par le code de la fenêtre "départ" :

Ici on définit un objet "maliste" de type "Cliste"

Tp10-14


Voyons maintenant le code du bouton "Bremplir".

Comme vous le voyez, il vide la liste contenant les prénoms, ensuite il la remplit avec les valeurs de bases et enfin il ajoute tout les éléments de la liste dans la liste doublement chaînée.

Tp10-15


Voici le code du bouton "Bsupprime" :


On supprime la valeur pointée et ensuite on fait réafficher la liste doublement chaînée.

Tp10-16


Voici le dernier code, celui du bouton "Bvoirliste" :

Tp10-17


On exécute quelques clics ?

Lancer le projet et commencez par cliquer sur le bouton voir liste, comme vous pouvez le constater rien ne s'affiche dans la zone liste.

Maintenant cliquez sur remplir, la liste de prénom est remplie ainsi que la liste doublement chaînée.

Sélectionnez un élément (moi par exemple NdL : moi c'est Jean-Luc) et hop on le supprime !

Magique, je viens de disparaître !


Voilà, je viens de finir de vous parler des listes doublement chaînées.

II. Exercices.

Pour vous entraîner :

  • Cliquez sur le premier élément de la liste : Comme vous le voyez il y a un big problème. Je vous laisse analyser le problème et y trouver une solution (en fait, il y en a deux possibles)


Programmez les méthodes permettant :

  • D'insérer un élément avant la position de l'élément sélectionné.
  • De trier la liste par ordre croissant ou décroissant.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2008 Jean Luc Baptiste. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.