Liste à double entrée

quaze Messages postés 9 Date d'inscription Statut Membre Dernière intervention -
quaze Messages postés 9 Date d'inscription Statut Membre Dernière intervention - 4 févr. 2014 à 16:11

Bonjour,

Je me suis remis à Java récemment et pour me dérouiller, j'ai décider d'implémenter une structure de donnée dans laquelle on peut ajouter/supprimer des données au deux extremités genre deque. Je veux évidemment pas utiliser les structures de données de java qui existe déjà. J'ai défini mon interface et les fonctions classiques :


public int taille(); //Nb d'élements
public boolean isEmpty(); 
public EltType first(); //Renvoie 1er elt (ne supprime pas)
public EltType last(); //Renvoie dernier elt (ne supprime pas)
public void insertFirst(EltType element);  //Rajoute en début
public void insertLast(EltType element); /Rajoute en fin
public EltType removeFirst(); //Supprime en début
public EltType removeLast(); //Supprime en fin

Je ne m'occupe pas des exceptions, en gros si on appelle first sur la liste vide ca plante...

J'ai voulu pour m'amuser avoir comme structure de donnée un tableau ("circulaire"), avec deux indices :
front -> le premier elt de la liste
end -> la prochaine place vide en queue de liste.

Quand mon tableau est plein et qu'on ajoute un élement, je recopie toutes les données dans un tableau plus grand. Le problème, est que j'ai du mal a trouver la condition pour dans un tableau.
Si je fais pour un tableau de capacité 3 :
this.insertFirst(1)
this.insertFirst(2)
this.insertFirst(3)
this.removeFirst()
et bien le tableau va être recopié juste après le this.insertFirst(3), alors qu'en fait il n'y en avait pas besoin.

Le code :


package a1;

public class ArrayBasedDoubleList<Type> implements DoubleList<Type> {
	
	private final static int CAPACTE = 8;
	private int capacite;
	private int end;
	private int front;
	private Type[] contenu;
	
	
	public ArrayBasedDoubleList() {
		capacite =   CAPACTE;
	    contenu = (Type[])(new Object[capacite]);
		this.end = -1;
		this.front = 0;
	}

	 
	public int taille() {
		int taille = (capacite - front + end ) % capacite;
		if (end == -1) {
			taille = 0;
		}
		return taille;
	}

	 
	public boolean isEmpty() {
		return this.taille()==0;
	}

	 
	public Type first() {
		return contenu[front];
	}

	 
	public Type last() {
		int temp = ArrayBasedDoubleList.sensContraire(end, capacite);
		return contenu[temp];
	}

	private static int sensContraire(int indice, int capacite) {
		return (indice-1) & (capacite-1);
	}
	
	private static int sens(int indice, int capacite) {
		return (indice+1) & (capacite-1);
	}

	 
	public void insertFirst(Type element) {
		if (this.taille()==capacite-1) {
			this.copy();
		}
		front = ArrayBasedDoubleList.sensContraire(front,capacite);
		this.contenu[front]=element;
		if (end==-1) {
			end=0;
		}
	}

	 
	public void insertLast(Type element) {
		if (this.taille()==capacite-1) {
			this.copy();
		}
		if (end==-1) {
			end=0;
		}
		this.contenu[end]=element;	
		end = ArrayBasedDoubleList.sens(end, capacite);
				
	}

	 
	public Type removeFirst() {
		Type elementReturned;
		
			elementReturned = this.contenu[front];
			//not necessary :
			this.contenu[front]=null;
			
			front = ArrayBasedDoubleList.sens(front, capacite);
			return elementReturned;
	}


	 
	public Type removeLast() {
		Type elementReturned = null;

			end = ArrayBasedDoubleList.sensContraire(end, capacite);
			elementReturned = this.contenu[end];
			this.contenu[end]=null;
			
	
		return elementReturned;
	}
	
	private void copy() {
		Type temp[] = (Type[])(new Object[2*capacite]);
	    for (int i = 0; i < capacite; i++) {
	    	temp[i] = contenu[i];
	    }
	    contenu = temp;
	    capacite = 2*capacite;
	    this.end=capacite;
	}

merci ;)

Afficher la suite

A voir également:

Liste à double entrée
Double ecran - Guide
Liste déroulante excel - Guide
Whatsapp double sim - Guide
Double driver - Télécharger - Pilotes & Matériel
Liste déroulante en cascade - Guide

2 réponses

Réponse 1 / 2

KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention 3 020

Pour l'instant tu augmente le tableau avec la condition

this.taille()==capacite-1

, mais cela est effectivement maladroit, il vaut mieux considérer l'égalité

taille()==capacite

, ainsi on n'augmentera le tableau que lorsque celui est complètement rempli.

Au passage, ta méthode de copie ne fonctionne pas, car les éléments à la fin du tableau sont censés correspondre au début de la liste circulaire, ils devront donc se retrouver également à la fin du nouveau tableau, or ici ils restent à leur place d'origine, ce qui est faux.

Actuellement: [ 3 4 1 2 ] devient [ 3 4 1 2 . . . . ]
Normalement : [ 3 4 1 2 ] devient [ 3 4 . . . . 1 2 ]

Je penses que tes problèmes d'indices viennent du choix de tes deux index (front, end) je te conseilles de plutôt partir sur un index et la taille (offset, size), cela revient globalement au même mais c'est plus simple à gérer, cela t'évitera notamment d'avoir des cas avec des valeurs à -1 qui n'ont pas de sens.

Attention :

(Type[]) (new Object[capacite])

est faux et plantera.
Il vaut mieux ne manipuler que des Object dans tout le code lorsque tu travailles sur le tableau, et ne faire la conversion en <Type> qu'au moment où tu travailles sur la case.

Voici ton code revu et corrigé :

public class ArrayBasedDoubleList<Type> // implements DoubleList<Type>
{
    private final static int DEFAULT_CAPACITY = 16;
    
    private int capacity;
    private Object[] data;
    
    private int offset;
    private int size;
    
    public ArrayBasedDoubleList()
    {
        capacity = DEFAULT_CAPACITY;
        data = new Object[capacity];
        offset = 0;
        size = 0;
    }
    
    public int size()
    {
        return size;
    }
    
    public int capacity()
    {
        return capacity;
    }
    
    public boolean isEmpty()
    {
        return size == 0;
    }
    
    @SuppressWarnings("unchecked")
    public Type first()
    {
        if (size == 0)
            throw new IllegalStateException("list is empty");
        
        return (Type) data[offset];
    }
    
    @SuppressWarnings("unchecked")
    public Type last()
    {
        if (size == 0)
            throw new IllegalStateException("list is empty");
        
        int pos = offset + size - 1;
        
        if (pos >= capacity)
            pos -= capacity;
        
        return (Type) data[pos];
    }
    
    private void grow()
    {
        Object temp[] = new Object[2 * capacity];
        
        int i, j;
        
        for (i = 0, j = offset; j < capacity; i++, j++)
            temp[i] = data[j];
        
        for (j = 0; j < offset; i++, j++)
            temp[i] = data[j];
        
        data = temp;
        offset = 0;
        capacity *= 2;
    }
    
    public void insertFirst(Type element)
    {
        if (size == capacity)
            grow();
        
        offset-- ;
        
        if (offset < 0)
            offset += capacity;
        
        data[offset] = element;
        
        size++ ;
    }
    
    public void insertLast(Type element)
    {
        if (size == capacity)
            grow();
        
        int pos = offset + size;
        
        if (pos >= capacity)
            pos -= capacity;
        
        data[pos] = element;
        
        size++ ;
    }
    
    @SuppressWarnings("unchecked")
    public Type removeFirst()
    {
        if (size == 0)
            throw new IllegalStateException("list is empty");
        
        Type elementReturned = (Type) data[offset];
        
        // nécessaire pour libérer la référence de l'objet et permettre sa libération de la mémoire si celui ci n'est plus utilisé
        data[offset] = null;
        
        offset++ ;
        
        if (offset >= capacity)
            offset -= capacity;
        
        size-- ;
        
        return elementReturned;
    }
    
    @SuppressWarnings("unchecked")
    public Type removeLast()
    {
        if (size == 0)
            throw new IllegalStateException("list is empty");
        
        Type elementReturned = (Type) data[offset];
        
        int pos = offset + size - 1;
        
        if (pos >= capacity)
            pos -= capacity;
        
        data[pos] = null;
        
        size-- ;
        
        return elementReturned;
    }
}

Réponse 2 / 2

quaze Messages postés 9 Date d'inscription Statut Membre Dernière intervention

Merci pour les conseils et les corrections ;)

Discussions similaires

comment ecrire un double cote " "

Supprimer le paramètre "Stockage interne, messagerie double"

Votre réponse

Discussions similaires