Les listes d'objets doublement chaînées

Jean Luc Baptiste

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

- Titre : Les listes d'objets doublement chaînées

- Auteur : Jean Luc Baptiste

- Parution : 27 novembre 2008

- Licence : 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.

Sommaire

- I. Présentation

- II. La fenêtre

- II-A. Tableau d'objets

- II-B. La méthode ajouter

- II-C. La méthode Parcourir

- II-D. La méthode Débutliste

- II-E. La méthode lire

- II-F. Méthode Lire_suivant

- II-G. La méthode Rechercher

- II-H. La méthode Avance

- II-I. La méthode Supprimer

- III. Exercices

I - Présentation

Les listes chaînées constituent un substitut aux tableaux. L'ajout, l'insertion et le retrait d'informations 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és entre eux par des pointeurs

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

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 :

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.

II - La fenêtre

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

Voici ses dimensions : 350x230

II-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 à ce que tout fonctionne, nous avons besoin d'une classe nommée « Cliste ».

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

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 œuvre 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 deux 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éplacements 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 trois boutons ?

On décortique la classe ?

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

II-B - La méthode ajouter

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.

II-C - La méthode Parcourir

La méthode parcourir a 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 qu’elle est récursive, c'est-à-dire qu’elle se rappelle jusqu'à ce qu'elle 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 dont le but est de renvoyer le premier objet de la liste chaînée. Étudiez son comportement.

II-D - La méthode Débutliste

II-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.

II-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 de l'analyser.

II-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 ».

II-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.

II-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) :

C'est magique, non ? Voici le code :

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 »

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 base et enfin il ajoute tous les éléments de la liste dans la liste doublement chaînée.

Voici le code du bouton « Bsupprime ».

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

Voici le dernier code, celui du bouton « Bvoirliste » :

On exécute quelques clics ?

Lancez 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énoms 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.

III - 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.