Cours CNAM par J. Laforgue

Exemple44_ListeChainee

Retour

Exemple de l'implémentation d'une liste dont les
elements sont chaines (recursivite)

Exemple44.java

// Exemple de l'implémentation d'une liste dont les
//  elements sont chaines (recursivite)
//
public class Exemple44
{
    // Programme principal
    //
    public static void main(String... args)
    {
        ListeChainee l = new ListeChainee();

l.add(2);
        l.add(3);
        l.add(1);

System.out.println(l.toString());
        System.out.println("indice 0 : "+l.get(0));
        System.out.println("indice 1 : "+l.get(1));
        System.out.println("indice 5 : "+l.get(5));

l.insert(4,0);
        System.out.println(l.toString());
        
        l.insert(5,3);
        System.out.println(l.toString());

l.insert(300,5);
        System.out.println(l.toString());

for(int i=0;i<l.size();i++)
            System.out.println(l.get(i));

System.out.println("\nTest de l'iteration:");
        l.initIter();
        while (l.getCourant()!=null){
            System.out.print(l.getCourant()+" ");
            l.suivant();
        }
        System.out.println("-----");
        l.initIter();
        l.dernier();
        System.out.println(l.getCourant());
        l.premier();
        l.suivant();
        System.out.println(l.getCourant());
        l.suivant();
        System.out.println(l.getCourant());
        l.precedent();
        l.precedent();
        System.out.println(l.getCourant());
        l.dernier();
        l.precedent();
        System.out.println(l.getCourant());

System.out.println("\n==============================");
        ListeChainee l2 = new ListeChainee();

l2.add("LAFONT Pierre");
        l2.add("DURAND Paul");
        l2.add("DUBOIS Zoe");
        System.out.println(l2.toString());

for(int i=0;i<l2.size();i++)
            System.out.println(l2.get(i));

}
}

ListeChainee.java

// Classe de definition d'une liste dont les elements sont
//  chaines physiquement avec chainage suivant, precedent et dernier
//
public class ListeChainee
{
    private int nb;        // Nombre d'element de la liste
    // Cet attribut permet de ne pas parcourir tous les elements
    //  afin de les compter
    private Cellule prem;  // Pointe sur le 1er element de la liste
    private Cellule dern;  // Pointe sur le deuxieme element de la liste

private Cellule courant; // Pointeur courant pour iterateur
    
    // Constructeur
    //
    public ListeChainee()
    {
        nb=0;
        prem=null;
        dern=null;
        courant=null;
    }
    
    // Ajoute a la fin de la liste un nouvel element
    //
    public void add(Object value)
    {
        Cellule cel = new Cellule();
        cel.value = value;
        nb++;
        if (prem==null)
            {
                prem = cel;
                dern = cel;
            }
        else
            {
                cel.prec=dern;
                cel.suiv=null;
                dern.suiv=cel;
                dern=cel;
            }
    }
    
    // Retourne le i-ieme element de la liste (de 0 a n-1)
    //  Cela necessite de parcourir tous les elements et de les compter
    //
    public Object get(int indice)
    {
        Cellule p = getCellule(indice);
        if (p==null) return null;
        return(p.value);
    }

// Insere un nouvel element a un rang de la liste
    //
    public Cellule insert(Object value,int indice)
    {
        Cellule p = getCellule(indice);
        if (p==null) return null;
        
        Cellule cel = new Cellule();
        cel.value = value;
        cel.prec = p.prec;
        cel.suiv = p;
        if (p==prem) prem = cel;
        else p.prec.suiv = cel;
        p.prec = cel;
        nb++;
        return cel;
        
    }

// Retourne la taille de la liste
    //
    public int size()
    {
        return nb;
    }
    
    // Retourne en chaine tous les elements de la liste
    //
    public String toString()
    {
    return toStringRec(prem,"");
    }
    private static String toStringRec(Cellule p,String res)
    {
    if(p!=null) return toStringRec(p.suiv,
                                       res+" "+p.value.toString());
        else return res;
    }

// Retourne la cellule de la liste a un indice (de 0 a n-1)
    //
    private Cellule getCellule(int indice)
    {
        return getCelluleRec(indice,0,prem);
        /*
        int n=0;
        Cellule p = prem;
        while(p!=null)
            {
                if(n==indice) return p;
                n++;
                p=p.suiv;
            }
        return(null);
        */
    }
    private static Cellule getCelluleRec(int indice,int n,Cellule p)
    {
        if (p==null) return null;
        else if (n==indice) return p;
        else return getCelluleRec(indice,n+1,p.suiv);
    }

// Initialisation de l'iterateur
    //
    public void initIter(){courant=prem;}

// Retourne l'element courant
    // 
    public Object getCourant(){
        if (courant!=null) return courant.value;
        else return null;
    }

// Passe a l'element suivant
    //
    public void suivant(){
        if (courant!=null) courant = courant.suiv;
    }

// Passe a l'element precedent
    //
    public void precedent(){
        if (courant!=null) courant=courant.prec;
    }

// Positionne le courant au premier element
    //
    public void premier() {courant=prem;}

// Positionne le courant au dernier element
    //
    public void dernier() {courant=dern;}

}

// Classe interne de la definition d'une cellule
//  = la donnee inforrmatique qui supporte le
//   chainage et contient la valeur de l'element : un Object
//
class Cellule
{
    Cellule prec;  // Cellule precedente
    Object  value; // Valeur de la cellule
    Cellule suiv;  // Cellule suivante
}

compil.bat
run.bat

Cours d'Informatique par Jacques LAFORGUE

Retour

Cours d'Informatique
par Jacques LAFORGUE