Cours CNAM par J. Laforgue

Exercice13_ListeSort

Retour

Télécharger

Implementation d'une classe ListeSort qui maintient une liste ordonnee croissante des elements grace a un arbre binaire infixe.

exercice13.pdf

      compil.bat
            fr
         cnam
            util
               ListeSort.java

package fr.cnam.util;

import java.util.*;

//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 pour creer l'arbre binaire
//
// Cette classe implemente l'interface Iterable pour parcourir les elements
//
public class ListeSort implements Iterable<Integer>
{
    private int     nb;        // Nombre d'element de la liste
    private ArbreLS data;      // L'arbre bianire contenant les elements
    private int     compteur;  // Compteur pour faire du calcul statistique
    
    // Constructeur : l'arbre est vide
    //
    public ListeSort()
    {
        nb=0;
        data=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(int valeur)
    {
        ArbreLS a = new ArbreLS();
        a.gauche=null;
        a.droit=null;
        a.valeur = valeur;
        
        if (data==null)
            data=a;
        else
            {
                addRec(data,a);
            }
        nb++;
    }
    private void addRec(ArbreLS noeud,ArbreLS ajout)
    {
        if (ajout.valeur < noeud.valeur)
            {
                if (noeud.gauche==null)
                    noeud.gauche=ajout;
                else
                    addRec(noeud.gauche,ajout);
            }
        else
            {
                if (noeud.droit==null)
                    noeud.droit=ajout;
                else
                    addRec(noeud.droit,ajout);
            }
    }
    
    // Methode qui affiche les elements de la liste
    // Cette methode utilise la methode recursive interne affRec qui
    //  realise un parcours infixe de l'arbre
    //
    public void afficher()
    {
        affRec(data);
        System.out.println();
    }
    private void affRec(ArbreLS noeud)
    {
        if (noeud!=null)
            {
                affRec(noeud.gauche);
                System.out.print(noeud.valeur+" ");
                affRec(noeud.droit);
            }
    }

// Pour l'interface Iterable<Integer>
    // Retourne un iterateur
    // Cet iterateur est issu de la transformation de l'arbre en un 
    //   ArrayList contenant les elements ordonnes
    //
    public Iterator<Integer> iterator()
    {
        ArrayList<Integer> liste = new ArrayList<Integer>();
        arrayRec(data,liste);
        return liste.iterator();
    }
    private void arrayRec(ArbreLS noeud,ArrayList<Integer> 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(int valeur)
    {
        compteur=0;
        return searchRec(data,valeur);
    }
    private boolean searchRec(ArbreLS noeud,int valeur)
    {
        boolean trouve;
        if (noeud==null) trouve=false;
        else
            {
                if (noeud.valeur==valeur) trouve=true;
                else
                    {
                        compteur++;
                        if (valeur<noeud.valeur)
                            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(int valeur)
    {
        Iterator<Integer> iter = iterator();
        compteur=0;
        while(iter.hasNext())
            {
                int v = iter.next().intValue();
                compteur++;
                if (v==valeur) return true;
                if (valeur<v) return false;
            }
        return false;
    }

// 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 l = new ListeSort();
        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();

// 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();
        for(int i=0;i<10000;i++)
            l.add(rdm.nextInt(1000));
        //l.afficher();
        
        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
{
    ArbreLS gauche;
    ArbreLS droit;
    int valeur;
}

run.bat

Cours d'Informatique par Jacques LAFORGUE

Retour

Télécharger

Cours d'Informatique
par Jacques LAFORGUE