Fouille dichotomique String

Version imprimable

Voila, je veux faire une recherche dans un tableau d'objet avec ce type de fouille.

Par contre, j'ai des problèmes quand à l'implémentation de celui-ci.

Il faudrait q'il recherche dans le tableau d'objet "tabMotsDict".

Merci

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
public class MotDictionnaire {
 
	private String mot;
	private char type;
	private char genre;
	private char nombre;
 
	public MotDictionnaire(String mot, char type, char genre, char nombre) 
	{
 
		this.mot = mot;
		this.type = type;
		this.genre = genre;
		this.nombre = nombre;
 
	}
 
	public String getMot() {
 
		return mot;
 
	}
 
	public char getType() {
 
		return type;
 
	}
 
	public char getGenre() {
 
		return genre;
 
	}
 
	public char getNombre() {
 
		return nombre;
 
	}
 
}

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
public class Dictionnaire
{
	public MotDictionnaire[] tabMotsDict;
 
	public Dictionnaire(){};
 
	public Dictionnaire(MotDictionnaire[] tabMotsDict)
	{
		this.tabMotsDict = tabMotsDict;
	}
 
 
	public MotDictionnaire[] getTabMotsDict() {
		return tabMotsDict;
	}
 
	public void setTabMotsDict(MotDictionnaire[] tabMotsDict) {
		this.tabMotsDict = tabMotsDict;
	}
 
	/*******************************
         * Fonction qui vérifie si un mot existe dans le dictionnaire
         * 
         *Recoit un mot
         * 
         *Retourne un boolean (true / false)
         * 
         */
	public boolean motExiste(String mot) 
	{
		int debut;
		int fin;
		int valeur = 0;
		int milieu = 0;
		int tab[] = new int[100];
		boolean trouve;
 
		debut = 0;
		fin = 100;
		trouve = false;
 
		while(valeur < tab[0] || valeur >= tab[100])
			milieu = debut + ((fin - debut) / 2);
		if(tab[milieu] == valeur)
			trouve = true;
		else
			if(valeur > tab[milieu])
				debut = milieu + 1;
			else
				fin = milieu - 1;
		while(trouve = false && debut < fin);
 
		return trouve;

11/03/2010, 17h55
dinobogan

Bonjour,

On ne peut guère t'aider avec si peu d'informations
Explique le problème, donne un exemple concret illustrant la ou les erreurs et on verra ce qu'on peut faire.

J'ai réussi à implémenter mais je crois qu'il y a un erreur sans l'a trouvé....

Merci

Code:

1
2
3
4
5
6
7
8
9
10
11
12
ArrayList<MotDictionnaire> tabMotsDict = new ArrayList<MotDictionnaire>();
		Dictionnaire monDict = new Dictionnaire();
		try {
			tabMotsDict.add(new MotDictionnaire("notions", 'N', 'F', 'P'));
			tabMotsDict.add(new MotDictionnaire("objectif", 'N', 'M', 'S'));
			tabMotsDict.add(new MotDictionnaire("operateurs", 'N', 'M', 'P'));
			tabMotsDict.add(new MotDictionnaire("pratique", 'N', 'F', 'S'));
			tabMotsDict.add(new MotDictionnaire("references", 'N', 'F', 'P'));
			tabMotsDict.add(new MotDictionnaire("travail", 'N', 'M', 'S'));
 
			monDict = new Dictionnaire(tabMotsDict);
			System.out.println(monDict.motExiste("notions"));

Il retourne false quand le mot notions est bel et bien dans le tableau.

Voici ma fonction.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean motExiste(String mot) {
 
		int pointMilieu = 0;
		int iDebut = 1;
		int iFin = getTabMotsDict().size() - 1;
 
		do {
			pointMilieu = (iDebut + iFin) / 2;
 
			if (mot.compareTo(getTabMotsDict().get(pointMilieu).getMot()) > 0)
				iFin = pointMilieu - 1;
 
			else if (mot.compareTo(getTabMotsDict().get(pointMilieu).getMot()) < 0)
				iDebut = pointMilieu + 1;
 
			else if (mot.compareTo(getTabMotsDict().get(pointMilieu).getMot()) == 0)
				return true;
 
		} while (iDebut <= iFin);
 
		return false;
	}

Merci

Essaie de changer le signe de comparaison à 0.

< devient > et > devient <

Tu as, à mon avis, simplement inversé ces signes.

P.S. Je ferais ceci également afin de gagner en performance :
Code:

1 2 3 4 5 6 7 int cmp = mot.compareTo(getTabMotsDict().get(pointMilieu).getMot()); if (cmp > 0) iFin = pointMilieu - 1; else if (cmp < 0) iDebut = pointMilieu + 1; else return true;