Exercice n° 2: implanter les listes pointées par une structure de données récursive

squelette à compléter du code de ListeP_Rec :

ListeP_Rec 
import java.util.*;
/**
 * Décrivez votre classe ListeP_Rec ici.
 * 
 * @author TD NFP121
 * @version v0.0
 */
public  class ListeP_Rec implements ListePointInterface
{    
        private int lg;
        private Maillon elem;
       
    /**
     * retourne la valeur du premier élément de la liste sans destruction
     * remarque :  on ne peut pas obtenir la tête d'une liste vide
     */ 
    public  Object car(){
        return elem.valeur();
    }
    
    /**
     * supprime la tete de la liste
     * remarque :  on ne peut pas supprimer la tête d'une liste vide
     */
    public  void cdr() {  
        elem=elem.suite();
        lg--;
    }
    /**
     * ajoute 'obj' au début de la liste;
     * la longueur de la liste est augmentée de 1
     */
    public  void cons(Object obj){
                /* 
                 *à compléter...
                 */
    }
    /**
     * ajoute en fin de liste la liste 'liste'
     */
    public  void conc(ListePointInterface liste ){
                /* 
                 *à compléter...
                 */
    }

    /**
     * retourne 'this'
     */
    public  void renverse()  {
                /* 
                 *à compléter...
                 */
    }
    
    /**
     *'objet' appartient-il à la liste ?
     */   
    public  boolean membre(Object objet){
                /* 
                 *à compléter...
                 */
                return false;
    }
    public  boolean listeVide(){
        return lg==0;
    }
    public  int longueur(){
        return lg;
    }
    
    public String toString(){
                /* 
                 *à compléter...
                 */
                return null;
    } 
    
     public boolean  equals(Object obj){
         if(!(obj instanceof ListePointInterface)) return false;
                /* 
                 *à compléter...
                 */
                return false;
     }

/*
 * on va avoir besoin d'énumérer les éléments d'une chaine de maillons
 * et on choisit pour cela un iterator implanté au moyen d'une classe anonyme
 * cf. ci dessous...
 */                      
        public Iterator<Object> iterator(){
        return new Iterator<Object>(){
            Maillon temp=elem;
            public boolean hasNext(){
                /* 
                 *à compléter...
                 */
                return false;
               }
               public Object next(){
                /* 
                 *à compléter...
                 */
                   return null;
               }
               public void remove(){
                   throw new UnsupportedOperationException();
               }
           };
       }
       /*
        * ...
        * 
        */
}

remarques et rappels :

  • car() et cdr() : l'application de ces méthodes sur une liste vide est une erreur il faudra donc prévoir de traiter cette erreur (crash du programme dans tous les cas et il faut cacher à l'utilisateur l'implémentation par un tableau..).
    • "à la main"
    • par une levée d'exception (cf. exercice 1 classe 'ListeVideException' extends Exception {...} )
    • par une instruction assert
  • structure de données récursive : classe Maillon  (cf. cours)
    sqel. classe Maillon 
    /**
 * 
 * @author TD NFP121
 * @version v 0.007
 */

 class Maillon implements Iterable{
    private Object valeur;
    private Maillon suite;
    /**
     * création d'un nouveau maillon i.e. il est tout seul sans 'suite' (null)
     */
    public Maillon(Object valeur){
    this.valeur=valeur;
    this.suite=null;
    }
    /**
     * ajout d'un nouveau maillon devant une chaine existante par la
     * création d'un nouveau maillon qui est 'accroché' à la chaine existante...
     */
    public Maillon(Object valeur,Maillon suite){
        this.valeur=valeur;
        this.suite=suite;
    }

    public Object valeur(){
        return valeur;
    }
    public Maillon suite(){
        return suite;
    }
    public void modifSuite(Maillon m){
        suite=m;
    }
    
    public boolean equals(Object that){
        /* 
         * à compléter
         */
        return false;
     }

    public String toString(){
        /* 
         * à compléter
         */
        return "";
    }
/*
 * on va avoir besoin d'énumérer les éléments d'une chaine de maillons
 * et on choisit pour cela un iterator implanté au moyen d'une classe anonyme
 * cf. ci dessous...
 */           
     public java.util.Iterator iterator(){
        return new java.util.Iterator(){            
            Maillon temp=new Maillon(valeur , suite);
            public boolean hasNext(){
                /* 
                 *à compléter...
                 */
                return false;
               }
               public Object next(){
                /* 
                 *à compléter...
                 */
                   return null;
               }
               public void remove(){// non implémenté
                   throw new UnsupportedOperationException();
               }
           };
       }
    }
  • ATTENTION aux parcours de la donnée récursive Maillon ATTENTION aux destructions...
  • pour membre et equals bien poser le problème et si il  est trop compliqué attendre les listes génériquespour une solution robuste.
  • enfin ajouter un "iterator" à la classe pour pouvoir énumérer les éléments de la liste. l'entête de la classe devient lors :
    public class ListeP_Rec implements ListePointInterface , Iterable
  • la classe Maillon peut être une classe interne de la classe ListeP_Rec. elle sera alors private...

tests :

developper avec Bluej une classe de tests (pertinents) couvrant tous les cas particuliers et généraux que vous "voyez"