Rechercher élément dans une liste

Version imprimable

Bonjour,

Je fait une liste circulaire, c'est-à-dire doublement chaînée.
Je souhaite avoir les fonctionnalités suivantes:
- Lire l'élément en cours
- Se décaler sur l'élément suivant
- Ajouter / Supprimer un élément
- Calculer la longueur de la liste
- Rechercher la présence d'un élément dans la liste

Voici ce que j'ai fait. Pouvez-vous me dire si c'est correct et je bloque pour la recherche d'un élément dans la liste

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class CelluleCirculaire<X> {
	private X valeur;
	private CelluleCirculaire<X> celluleSuivante;
	private CelluleCirculaire<X> cellulePrecedente;
 
	//Creation d’une cellule contenant la valeur n
	CelluleCirculaire(X n){
		this.valeur = n;
		this.celluleSuivante = null;
		this.cellulePrecedente = null;
	}
 
	public X getValeur() {
		return valeur;
	}
 
	public void setValeur(X valeur) {
		this.valeur = valeur;
	}
 
	public CelluleCirculaire<X> getCelluleSuivante() {
		return celluleSuivante;
	}
 
	public void setCelluleSuivante(CelluleCirculaire<X> celluleSuivante) {
		this.celluleSuivante = celluleSuivante;
	}
 
	public CelluleCirculaire<X> getCellulePrecedente() {
		return cellulePrecedente;
	}
 
	public void setCellulePrecedente(CelluleCirculaire<X> cellulePrecedente) {
		this.cellulePrecedente = cellulePrecedente;
	}
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class ListeCellulesCirculaire<X>{
	private CelluleCirculaire<X> debut;
 
	//Liste vide
	ListeCellulesCirculaire(CelluleCirculaire<X> debut){
		this.debut = debut;
	}
 
    public void ajouterDebut(CelluleCirculaire<X> cellule){
		cellule.setCelluleSuivante(this.debut);
		if(this.debut != null)
			debut.setCellulePrecedente(cellule);
		debut = cellule;
		cellule.setCellulePrecedente(null);
    }
 
    public void ajouterApres(CelluleCirculaire<X> precedent, CelluleCirculaire<X> cellule){
    	if(precedent == null){
    		ajouterDebut(cellule);
    	}else{
    		cellule.setCelluleSuivante(precedent.getCelluleSuivante());
    		cellule.setCellulePrecedente(precedent);
    		if(precedent.getCelluleSuivante() != null){
    			precedent.getCelluleSuivante().setCellulePrecedente(cellule);
    		}
    		precedent.setCelluleSuivante(cellule);
    	}
    }
 
    public void supprimer(CelluleCirculaire<X> cellule){
    	if(cellule == debut){
    		debut = cellule.getCelluleSuivante();
    	}else{
    		//cas cellule précédente n'est pas null
    		cellule.getCellulePrecedente().setCelluleSuivante(cellule.getCelluleSuivante());
    	}
    	if(cellule.getCelluleSuivante() != null){
    		cellule.getCelluleSuivante().setCellulePrecedente(cellule.getCellulePrecedente());
    	}
    }
 
	//Renvoie la longueur de la liste
	public int longueur(){
		int longueur = 0;
		CelluleCirculaire<X> c = this.debut;
		while (c!=null) {
			longueur = longueur + 1;
			c = c.getCelluleSuivante();
		}
		return longueur;
	}
 
	//Renvoie une chaîne de caractères représentant la liste
	public String toString(){
		String s = "[";
		CelluleCirculaire<X> c = this.debut;
		while (c!=null) {
			s = s + c.getValeur();
			c = c.getCelluleSuivante();
			if (c!=null) s = s +"; ";
		}
		s = s + "]";
		return s;
	}
 
	public CelluleCirculaire<X> getDebut() {
		return debut;
	}
 
	public void setDebut(CelluleCirculaire<X> debut) {
		this.debut = debut;
	}
}

Merci de votre aide

13/11/2015, 11h06
joel.drigo

1 pièce(s) jointe(s)
Salut,
1. Pour faire une recherche, par valeur je suppose, il suffit de parcourir les CelluleCirculaire, de suivant en suivant jusqu')à ce qu'on trouve l'instance dont la valeur est égale à la valeur recherchée (attention aux boucles infinies en cas de liste circulaire). Ensuite décider ce qu'on retourne (la position (un index), ce qui nécessite de pouvoir accéder à un élément par son index), ou l'instance de CelluleCirculaire (mais cela peut poser un problème de modèle (qu'on peut résoudre éventuellement par interface) — voir remarque ci-après). Qu'est-ce qui te bloque exactement ?
2. Pour moi, une liste circulaire et une liste doublement chaînée sont deux choses différentes. Une liste circulaire est une liste qui boucle sur elle-même, qui fonctionnellement n'a ni début ni fin, dont le début suit la fin techniquement.
3. Il y a un problème de modèle pour moi :
  - ListCelluleCirculaire devrait être juste un cas particulier de CelluleCirculaire (spécialisation par extension) : on devrait pouvoir parcourir depuis le début de suivante en suivante, ou depuis la fin, de précédente précédente. La seule chose qu'elle a de particulier, c'est qu'on a des méthodes qui permette effectivement
  - autre solution : n'avoir qu'une seule classe (avec une classe interne pour gérer l'association valeur + liens)
  - au moins ne pas pouvoir intervenir indépendamment sur les liaisons entre cellules, sinon on peut obtenir des trucs du genre :
    Pièce jointe 192561
    donc plus un graphe qu'une liste, sans cohérence suivant/précédent, et impliquant possiblement des boucles infinies lors du parcours (calcul de la longueur) ou parcourt impossible ou incohérent (lors d'avance/recul)
  - En fait, un bon moyen d'éviter d'obtenir une implémentation qui s'engage sur ce type de travers est de partir de l'interface List, ou d'une interface limitée aux méthodes indispensables à la manipulation d'une liste d'éléments : ajouter, insérer, supprimer, getSuivant et getPrecedent (donc pas de setter setSuivant ou setPrecedent public, pour ne pas rendre la liste incohérente), taille (ou plutôt nombreDElements si la liste est vraiment circulaire, parce que dans ce cas, la taille est infinie en théorie), et si la liste est double chaînée (non circulaire), getDebut, getFin, (éventuellement estDebut, estFin()), et indexDe éventuellement pour la recherche, ou chercher() qui retourne un CelluleCirculaire.
4. Ton constructeur a une visibilité package : c'est plutôt limité pour une classe utilitaire par principe
5. C'est dommage de devoir faire new ListCelluleCirculaire(null) pour créer une liste vide.
15/11/2015, 15h39
totot

En effet, je travail plutôt sur les listes circulaires.
Dis-moi ce qui ne va pas dans ce que j'ai fait et si tu pouvais m'aider à corrigé. Et comment faire les méthodes qui me dans ce que j'ai cité
16/11/2015, 16h35
Yonito

Salut,

ton souci a deja ete traite a ce lien ci :

http://www.developpez.net/forums/d15...re-genericite/

Voilà ce que j'ai fait :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class CelluleCirculaire<X> {
	private X valeur;
	private CelluleCirculaire<X> celluleSuivante;
	private CelluleCirculaire<X> cellulePrecedente;
 
	//Creation d’une cellule contenant la valeur n
	CelluleCirculaire(X n){
		this.valeur = n;
		this.celluleSuivante = null;
		this.cellulePrecedente = null;
	}
 
	public X getValeur() {
		return valeur;
	}
 
	public void setValeur(X valeur) {
		this.valeur = valeur;
	}
 
	public CelluleCirculaire<X> getCelluleSuivante() {
		return celluleSuivante;
	}
 
	public void setCelluleSuivante(CelluleCirculaire<X> celluleSuivante) {
		this.celluleSuivante = celluleSuivante;
	}
 
	public CelluleCirculaire<X> getCellulePrecedente() {
		return cellulePrecedente;
	}
 
	public void setCellulePrecedente(CelluleCirculaire<X> cellulePrecedente) {
		this.cellulePrecedente = cellulePrecedente;
	}
}
 
public class ListeCellulesCirculaire<X>{
	private CelluleCirculaire<X> debut;
	private CelluleCirculaire<X> fin;
 
	//Liste vide
	ListeCellulesCirculaire(){
		this.debut = null;
		this.fin = null;
	}
 
	public void ajouter(CelluleCirculaire<X> cellule){
 
        if (this.isEmptyList()) {
            debut = cellule;
            fin = cellule;
            cellule.setCellulePrecedente(debut); // liste circulaire : le dernier element pointe sur le premier
            cellule.setCelluleSuivante(fin); // liste circulaire : le premier element pointe sur le dernier
        }
        else {
        	cellule.setCelluleSuivante(this.debut); // on lie le nouvel element a la tete de liste existante.
            cellule.setCellulePrecedente(this.fin); //  on lie le nouvel element se trouvant en debut de liste au dernier element de la liste (Propriete circulaire)
            this.debut.setCellulePrecedente(cellule); // on lie l'ancien element debut au nouvel element ajoute
            this.fin.setCelluleSuivante(cellule); // La dernier element deja existant pointe sur le nouvel element ajoute en debut de liste.
            this.debut = cellule;
        }
	}
 
	//Renvoie la longueur de la liste
	public int longueur(){
		CelluleCirculaire<X> c = debut;
	    int size = 0;
	    while (c != fin || c.getCelluleSuivante() != debut) {
	        size++;
	        c = c.getCelluleSuivante();
	    }
	    return size;
	}
 
	//Renvoie une chaîne de caractères représentant la liste
	public String toString(){
		String s = "[";
		CelluleCirculaire<X> c = this.debut;
		while (c!=null) {
			s = s + c.getValeur();
			c = c.getCelluleSuivante();
			if (c!=null) s = s +"; ";
		}
		s = s + "]";
		return s;
	}
 
	public CelluleCirculaire<X> getDebut() {
		return debut;
	}
 
	public void setDebut(CelluleCirculaire<X> debut) {
		this.debut = debut;
	}
 
	public CelluleCirculaire<X> getFin() {
		return fin;
	}
 
	public void setFin(CelluleCirculaire<X> fin) {
		this.fin = fin;
	}
}

Voilà mes différents problèmes:
- La méthode ajout ne compile pas: il ne connait pas le isEmptyList du if
- Je n'arrive pas à faire la méthode supprimer sur le même principe que la méthode ajouter
- Je n'arrive pas non plus à faire les autres méthode : lire l'élément en cours, se déplacer, rechercher un élément dans une liste

Merci de votre aide