Cours CNAM par J. Laforgue

Exercice14_ListeSort2

Retour

Télécharger

Implémentation d'une classe ListeSort qui maintient une liste ordonnée croissante des éléments grâce à un arbre binaire infixé et dont l'itérateur des éléments utilise un double chainage. De plus on veut être générique sur le type d'élément.

Exercice14.pdf

            compil.bat
      fr
         cnam
            util
               ListeSort.java

package fr.cnam.util;

import java.util.*;
import fr.cnam.ihm.*;

//Implementation d'une classe ListeSort qui maintient une liste ordonnee croissante des elements grace a un arbre binaire infixe.
//
// Cette classe utilise une classe interne ArbreLS<T> pour creer l'arbre binaire
//
// Cette classe implemente l'interface Iterable<T> pour parcourir les elements
//
// La liste gere des elements de type T generique.
//
// Les elements sont en plus, dans l'ordre croissant, doublement chaines.
// Ceci afin d'avoir un moyen de parcourir les elements dans l'ordre croissant.
// Le chainage est mis a jour quand on ajoute un nouvel element.
//
public class ListeSort<T extends Comparable<T>> implements Iterable<T>, Iterator<T>
{
    private int        nb;        // Nombre d'element de la liste
    private ArbreLS<T> data;      // L'arbre binaire contenant les elements
    private int        compteur;  // Compteur pour faire du calcul statistique
    private ArbreLS<T> current;
    private ArbreLS<T> first;

// Constructeur : l'arbre est vide
    //
    public ListeSort()
    {
        nb=0;
        data=null;
        first = null;
    }
    
    // Nombre d'élement
    public int size(){return nb;}
    
    // Ajout d'un nouvel element dans la liste
    // Cete methode utilise la methode recursive interne addRec pour parcourir
    //   l'arbre afin d'y ajouter le nouvel elemene
    //
    public void add(T valeur)
    {
        ArbreLS<T> a = new ArbreLS<T>();
        a.gauche=null;
        a.droit=null;
        a.valeur = valeur;
        a.next=null;
        a.previous=null;
        
        if (data==null)
            {
                data=a;
                first=a;
            }
        else
            {
                addRec(data,a);
            }
        nb++;
    }
    private void addRec(ArbreLS<T> noeud,ArbreLS<T> ajout)
    {
        if (ajout.valeur.compareTo(noeud.valeur)<0)
            {
                if (noeud.gauche==null)
                    {
                        noeud.gauche=ajout;
                        // Mise a jour du double chainage
                        ajout.next=noeud;
                        ajout.previous=noeud.previous;
                        if (noeud.previous==null)
                            first=ajout;
                        else
                            noeud.previous.next=ajout;
                        noeud.previous=ajout;
                    }
                else
                    addRec(noeud.gauche,ajout);
            }
        else
            {
                if (noeud.droit==null)
                    {
                        noeud.droit=ajout;
                        // Mise a jour du double chainage
                        ajout.next=noeud.next;
                        ajout.previous=noeud;
                        if(noeud.next!=null)
                            noeud.next.previous=ajout;
                        noeud.next=ajout;
                    }
                else
                    addRec(noeud.droit,ajout);
            }
    }
    
    // Methode qui affiche les elements de la liste
    // Cette methode utilise l'iterateur
    //
    public void afficher()
    {
        for(T e:this)
            System.out.print(e+" ");
        System.out.println();
    }

// Methode qui retourne les elements ordonnes dans un ArrayList
    //
    public ArrayList<T> getArrayList()
    {
        ArrayList<T> liste = new ArrayList<T>();
        arrayRec(data,liste);
        return liste;
    }
    private void arrayRec(ArbreLS<T> noeud,ArrayList<T> tab)
    {
        if (noeud!=null)
            {
                arrayRec(noeud.gauche,tab);
                tab.add(noeud.valeur);
                arrayRec(noeud.droit,tab);
            }
    }

// Methode qui recherche si un element existe dans la liste
    // Cette methode utilise une methode recursive interne searchRec qui
    //  descent dans l'arbre afin de rechercher l'element
    //
    public boolean search(T valeur)
    {
        compteur=0;
        return searchRec(data,valeur);
    }
    private boolean searchRec(ArbreLS<T> noeud,T valeur)
    {
        boolean trouve;
        if (noeud==null) trouve=false;
        else
            {
                if (noeud.valeur.equals(valeur)) trouve=true;
                else
                    {
                        compteur++;
                        if (valeur.compareTo(noeud.valeur)<0)
                            trouve=searchRec(noeud.gauche,valeur);
                        else
                            trouve=searchRec(noeud.droit,valeur);
                    }
            }
        return trouve;
    }

// Retourne le compteur utilise dans les methodes de recherche
    public int getCompteur() {return compteur;}

// Methode de recherche dans la liste mais sans utiliser l'arbre
    // La recherche est donc iterative donc plus longte.
    // Ceci afin de faire une comparaison statistique entre une recherche
    //   classique dans un tableau et la recherche dans un arbre infixe.
    //
    public boolean searchIter(T valeur)
    {
        compteur=0;
        for(T e:this)
            {
                compteur++;
                if (e.equals(valeur)) return true;
                if (valeur.compareTo(e)<0) return false;
            }
        return false;
    }

// Pour l'interface Iterable<T>
    // Retourne un iterateur
    // ---------------------------------------
    //
    public Iterator<T> iterator()
    {
        current=first;
        return this;
    }

// Pour l'interface Iterator<T>
    // ---------------------------------------

// Teste s'il existen encore un element a parcourir
    //
    public boolean hasNext()
    {
        if (current==null) return false;
        else return true;
    }

// Retourne l'element courant et passe a l'element suivant
    //
    public T next()
    {
        T e = current.valeur;
        current = current.next;
        return e;
    }

// Pas implemente
    public void remove()
    {
    }

// --------------- Pour dessiner un arbre
    public void dessiner()
    {
        int widthCadre=300;
        int heightCadre=150;
        int decalage=20;
        CanvasIHM ihm = CanvasIHM.creerCanvasIhmDansFrame(widthCadre,heightCadre,
                                                          1,1,1);

ihm.desafficherGrille();
        int p = profondeurRec(data,0,0);
        System.out.println("\nprofondeur: "+p);
        dessinerRec(data,ihm,
                    widthCadre,heightCadre,p,
                    widthCadre/2,decalage,0,(int)(10*Math.pow(2,p))/2,
                    -1,-1);
    }
    
    private void dessinerRec(ArbreLS noeud,CanvasIHM ihm,
                             int widthCadre,int heightCadre,int profondeur,
                             int posx,int decalage,int niveau,int marge,
                             int posxPrec,int posyPrec)
    {
        if (noeud!=null)
            {
                int posy = decalage+niveau*25;
                ihm.ajouterTexte(""+noeud.valeur,posx-5,
                                 posy,1);
                if (posyPrec!=-1)
                    ihm.ajouterLigne(1,posxPrec,posyPrec,posx,posy-15);
                dessinerRec(noeud.gauche,ihm,
                            widthCadre,heightCadre,profondeur,
                            posx-marge/2,decalage,niveau+1,marge/2,
                            posx,posy);
                dessinerRec(noeud.droit,ihm,
                            widthCadre,heightCadre,profondeur,
                            posx+marge/2,decalage,niveau+1,marge/2,
                            posx,posy);
            }
    }
    private int profondeurRec(ArbreLS noeud,int profondeur,int max)
    {
        if (noeud==null)
            {
                if (profondeur>max) return(profondeur);
                else return(max);
            }
        else
            {
                return(profondeurRec(noeud.droit,profondeur+1,
                                     profondeurRec(noeud.gauche,profondeur+1,max)));
            }
    }

// =====================================================================

// Methode principale permettant de tester les methodes de la liste
    //  et faire une petite etude de comparaison entre une recherche 
    //  arborescente et une recherche iterative
    //
    public static void main(String... str)
    {

// Ajout d'elements et affichage de la liste
        ListeSort<Integer> l = new ListeSort<Integer>();
        l.add(23);
        l.afficher();

l.add(17);
        l.afficher();
        l.add(35);
        l.afficher();
        l.add(42);
        l.afficher();
        l.add(3);
        l.afficher();
        l.add(18);
        l.afficher();
        l.add(24);
        l.add(1);
        l.add(5);
        l.add(18);
        l.add(20);
        l.add(30);
        l.add(100);

l.dessiner();

// Utilisation de l'iterateur
        System.out.println("Par un iterator:");
        for(Integer v:l) System.out.print(v+" ");
        System.out.println();

// Recherche d'elements

System.out.print("Recherche de 23 : ");
        if (l.search(23)) System.out.println("trouve");
        else System.out.println("non trouve");

System.out.print("Recherche de 42 : ");
        if (l.search(42)) System.out.println("trouve");
        else System.out.println("non trouve");

System.out.print("Recherche de 18 : ");
        if (l.search(18)) System.out.println("trouve");
        else System.out.println("non trouve");

System.out.print("Recherche de 77 : ");
        if (l.search(77)) System.out.println("trouve");
        else System.out.println("non trouve");
        
        // Etude statistique

System.out.print("Comparaison statistique");
        // Ajout de 10000 entier aleatoire entre 0 et 1000
        Random rdm = new Random();
        l = new ListeSort<Integer>();
        for(int i=0;i<40;i++)
            l.add(rdm.nextInt(1000));
        
        System.out.println("Recherche infixe de 100 elements parmi 10000");
        int somme=0;
        for(int i=0;i<100;i++)
            {
                l.search(rdm.nextInt(1000));
                somme=somme+l.getCompteur();
                System.out.print(l.getCompteur()+" ");
            }
        int moyenne=somme/100;
        System.out.println("\nMoyenne: "+moyenne);

System.out.println("\nRecherche iterative de 100 elements parmi 10000");
        somme=0;
        for(int i=0;i<100;i++)
            {
                l.searchIter(rdm.nextInt(1000));
                somme=somme+l.getCompteur();
                System.out.print(l.getCompteur()+" ");
            }
        moyenne=somme/100;
        System.out.println("\nMoyenne: "+moyenne);
    }
}

// Classe interne pour coder l'arbre binaire
//
class ArbreLS<T> 
{
    ArbreLS<T> gauche;   // sous-arbre gauche
    ArbreLS<T> droit;    // sous-arbre droit
    T valeur;            // valeur de l'element
    ArbreLS<T> next;     // element suivant (ordonne croissant)
    ArbreLS<T> previous; // element precedent (ordonne croissant)
}

run.bat

Cours d'Informatique par Jacques LAFORGUE

Retour

Télécharger

Cours d'Informatique
par Jacques LAFORGUE