Discussion :

[Roud9]

Bonjour,

J'écris présentement un petit programme me permettant de trier une liste chaînée en ordre croissant. Je fais ma propre implémentation de cette liste au lieu d'utiliser directement LinkedList. Voici ce que j'ai jusqu'à maintenant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean ajouter(T elt) {
		boolean ajout = false;
		Noeud<T> courant = tete;
		if (!verifierSiExiste(elt)) {
			if (estVide()
					|| elt.obtenirPriorite() < tete.getElement()
							.obtenirPriorite()) {
				tete = new Noeud<T>(elt, tete);
			} else {
				while (courant != null) {
					if (elt.obtenirPriorite() > courant.getElement().obtenirPriorite() && !ajout) {
						Noeud<T> unNoeud = new Noeud<T>(elt);
						unNoeud.setSuivant(courant.getSuivant());
						courant.setSuivant(unNoeud); 
						ajout = true;
					} else {
						courant = courant.getSuivant();
					}
				}
			}	
		}
		nbElements++;
		return ajout;
	}

Cependant, lorsque j'ajoute les éléments 4,1,2,5,3, les éléments sont classés selon l'ordre suivant (après l'ajout de tous les éléments): 1,3,5,2,4 au lieu de 1,2,3,4,5.

J'ai vu que je pouvais utiliser l'interface Comparable, mais je ne comprends pas très bien.

Merci

[tchize_]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if (elt.obtenirPriorite() > courant.getElement().obtenirPriorite() && !ajout) {

Ton test est écirt à l'envers. C'est uniquement si l'elt < courant que tu dois faire l'insertion, sinon tu n'est pas cohérent par rapport à ta règle de tête. Aussi, quelque remarques:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if (!verifierSiExiste(elt)) {

Ce test n'a pas de sens, il nécessite de parcourir une première fois la liste. Tu le verra bien pendant l'insertion si oui ou non l'élément est déjà présent, quand tu tombera dessus.

Ta variable ajout ne sert à rien, tu peux te contenter de sortir de la méthode une fois l'ajout fait. Pourquoi continuer inutilement à parcourir la liste?

[Roud9]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if (elt.obtenirPriorite() > courant.getElement().obtenirPriorite() && !ajout) {

Ton test est écirt à l'envers. C'est uniquement si l'elt < courant que tu dois faire l'insertion, sinon tu n'est pas cohérent par rapport à ta règle de tête. Aussi, quelque remarques:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if (!verifierSiExiste(elt)) {

Ce test n'a pas de sens, il nécessite de parcourir une première fois la liste. Tu le verra bien pendant l'insertion si oui ou non l'élément est déjà présent, quand tu tombera dessus.

Ta variable ajout ne sert à rien, tu peux te contenter de sortir de la méthode une fois l'ajout fait. Pourquoi continuer inutilement à parcourir la liste?

Merci de ta réponse (rapide en plus). Donc, j'ai changé le signe > pour <, mais seuls trois éléments sont ajoutés sur les cinq, soit 1,2 et 3 (dans l'ordre). Il me manque donc 4 et 5.

Merci

[tchize_]

Oui, tu n'a pas géré les cas où l'ajout se fait en fin de liste.