Discussion :

[Izzy94]

Bonjour,

je cherche à créer trié par ordre croissant une liste chaîné simple mais lorsque j’exécute mon code rien ne se passe mais mon code est toujours exécuté, j'imagine qu'il tourne fou mais je n'arrive pas à comprendre. pour cette exercice j'ai décidé de ne pas utilisé les outils comme ArrayList,etc...

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
	public static Fibo2 triV2(Fibo2 tete) {
		Fibo2 courant = tete,  suivant = courant.jePointeVers, i = tete;
 
 
		while(courant.jePointeVers !=null) {
 
			if(suivant.data < courant.data) {
 
				courant.jePointeVers = suivant.jePointeVers;
				suivant.jePointeVers = courant;
				tete = suivant;
			}
		//	i.jePointeVers=tete;
		}
 
 
 
		return tete;
 
	}

[yotta]

Bonjour,
Pour être honnête, j'ai un peu de mal à comprendre ce que vous voulez faire, mais ce n'est pas le but, et cela ne m'empêche pas de répondre à votre question.
Lorsque l'on utilise les boucles While, il faut être très vigilant, et vous en payez le prix, car à la moindre erreur, on obtient rapidement une boucle infinie qui ne fait rien, et donc un code figé qui n'évolue plus, bref, une appli plantée.
Ici, votre boucle While traite une condition de non nullité sur courant.jepointevers. comme il n'y a aucune "échappatoire" dans le code exécuté par ce While, il est impératif qu'à un moment donné, courant.jepointevers devienne nul, sinon, le While tournera en boucle. Ce qui semble être le cas.
Alors la question à se poser c'est : Pourquoi courant.jepointevers ne devient jamais nul ?
Si on examine votre code, celui qui est exécuté dans le While, il est conditionné par le fait que suivant.data soit impérativement inférieur à courant.data, et si ce n'est pas le cas, alors on ne fait strictement rien ?!
Du coup, lorsque ce n'est pas le cas, ce qui semble se produire, comme on ne fait rien, il n'y a aucune raison que courant.jepointevers devienne nul, et comme rien ne change, la condition de traitement ne sera toujours pas remplie lors de l'occurrence suivante, et nous voilà dans une belle boucle infinie qui ne fait rien...
La réponse à la première question : Pourquoi courant.jepointevers ne devient jamais nul ?
est : Parce que suivant.data n'est pas forcément inférieur à courant.data.
Comment y remédier, deux solutions :
Soit vous désirez ne traiter que le cas où suivant.data est inférieur à courant.data, il vous suffit alors d'ajouter à votre code la clause Else tel que :

Code :

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

1
2
3
4
5
6
if(suivant.data < courant.data) {
   courant.jePointeVers = suivant.jePointeVers;
   suivant.jePointeVers = courant;
   tete = suivant;
   }
else courant.jepointevers = null;

Si par contre vous voulez traiter tous les cas de figure, alors il faut faire quelque chose lorsque suivant.data est égale à courant.data, et quelque chose lorsque suivant.data est supérieur à courant.data.

[Izzy94]

ce que je souhaite faire avec ce code c'est pouvoir trier de manière croissante une liste avec des données aléatoire.

j'ai essayé la solution du else mais aucun changement, ma boucle tourne en continu

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 static Fibo2 triV2(Fibo2 tete) {
		Fibo2 courant = tete, suivant = courant.jePointeVers;
 
 
 
		while(courant.jePointeVers !=null) {
 
			if(suivant.data < courant.data) {
 
				courant.jePointeVers = suivant.jePointeVers;
				suivant.jePointeVers = courant;
				tete = suivant;
			}
			else {
				courant.jePointeVers = null;
 
			}
 
		}
 
 
		return tete;
 
	}

[joel.drigo]

Salut,

Ce serait utile d'avoir le modèle (la classe Fibo2) pour comprendre ce que tu fais et évaluer ce que tu voudrais faire.

Ensuite, au sujet de la remarque de Yotta, sur la condition du while : ce qui est important c'est que la condition soit fausse à un moment donné. Donc que, comme dit, courant.jePointeVers puisse être null. Mais courant.jePointeVers peut être null en le forçant à null, mais aussi si courant change et que sa valeur est justement un "Fibo2" qui a jePointeVers à null. Or, dans le cadre du parcours d'une liste chaînée, il semblerait logique que courant varie (et suivant donc), sinon on ne traite qu'un nœud (le premier à priori), et, donc, il y a peu de chances que ça trie l'ensemble des nœuds de la liste.

A noter que, dans ton code,

Code :

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

1
2
 
tete = suivant;

ça n'a de sens que si courant est la tête, sinon, tu perds forcément le début de ta liste (la tête devient le suivant du courant), si tu fais effectivement varier courant (et suivant).

Ensuite, il y a le principe du tri. Ici, semble-t-il, tu tentes une approche par un algorithme "tri à bulles", donc parcourt, comparaison 2 à 2 et échange. Mais ce type de tri nécessite de parcourir la liste (entièrement, parce que le dernier élément est peut-être bien le plus petit). Et de le faire tant qu'elle n'est pas triée (sauf cas exceptionnel, on ne peut pas trier en une seule passe, par exemple, 4,3,2,1 va donner 3,2,1,4 à la première passe). Donc au moins d'avoir un booléen qui dit qu'on a fait au moins un échange. Sinon, pouvoir déterminer jusqu'à quel élément il faut faire le parcourt, et quand cet élément est le premier, on sait qu'on peut arrêter. Avec une liste à accès direct, par index, c'est plutôt simple à gérer : on sait que le dernier des éléments à traiter est forcément le plus grand (pour un tri croisant), on décrémente donc le nombre d'éléments à parcourir. Mais pour une liste chaînée, c'est déjà un peu plus complexe.

Je tenterais plutôt une approche par insertion sur une liste chaînée, qui me semble plus simple : pour chaque élément, on le sort de la liste, on cherche sa position (parcourt + comparaison) dans la liste et on l'insère à cette position. Avec une seule liste, on risque de traiter plusieurs fois un élément déjà traité, mais en utilisant deux listes, sans toucher à la liste à trier et en construisant directement une nouvelle liste triée, c'est assez facile à implémenter pour une version de base sans optimisation ou parallélisme. Pour te simplifier le traitement, commence par écrire celle qui créé la liste triée, donc une méthode qui insert un élément (avant ou après, ça je te laisse y réfléchir, à ce qui est le plus adapté au tri croissant) le premier élément de la liste qui est (plus grand ou plus petit, ça aussi je te laisse réfléchir) que celui que tu cherches à insérer (si la liste est vide, qui insert simplement au début dans tous les cas). Ensuite, tu n'as plus qu'à parcourir tous les éléments de ta liste à trier et d'appeler pour chaque la méthode en question.

Si tu dois absolument mettre en place un tri à bulle, commence par découper chaque sous-fonction : une fonction qui échange 2 éléments, une fonction qui parcourt une liste, etc. Les assembler me semble plus simple que de vouloir écrire tout l'algorithme d'une traite.

[Izzy94]

@joel.drigo
voila ma classe Fibo2,

Code :

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

1
2
3
4
5
6
7
8
package fibo2;
 
public class Fibo2 {
 
	public int data;
	public Fibo2 jePointeVers;
 
}

[yotta]

Bonjour,
Je ne sais pas d'où sort votre astuce mais elle est surprenante de simplicité en fait !
Bref, je n'ai toujours pas compris l'objectif réel de cette méthode, pour autant, j'ai élaboré un résultat fonctionnel en modifiant très peu de chose et en partant de l'hypothèse que l'objectif de cette méthode est d'extraire l'élément le plus petit d'un ensemble d'objet Fibo2 se pointant l'un vers l'autre.
Mon code de test crée trois instances de l'objet Fibo2, toto1, toto2 et toto3. toto1 pointe vers toto2, toto2 pointe vers toto3 et toto3 pointe vers null. Pour tester la méthode, j'ai exécuté le code en modifiant les valeurs de la propriété data de mes toto pour vérifier tous les cas de figure d'infériorité, d'égalité et de supériorité. Pour pouvoir visualiser le plus simplement possible le comportement de la méthode j'ai quelque peu modifié la classe Fibo2 en lui ajoutant deux propriétés, un boolean nommé 'egalite' et une String nommée 'nom'. Le boolean egalite est mis à faux par défaut et ne passe à vrai pour un Fibo2 que pour signaler qu'il est égale au Fibo2 qui pointe vers lui.
Voilà ce que cela donne.

Fibo2 modifié :

Code :

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

1
2
3
4
5
6
public class Fibo2 {
    public int data;
    public Fibo2 jePointeVers;
    public boolean egalite = false;    
    public String nom;
    }

Méthode triV2 :

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public Fibo2 triV2(Fibo2 tete) {
		Fibo2 courant = tete,  suivant = courant.jePointeVers;
                int i = 0;
		while(courant.jePointeVers !=null) {
                    if (suivant.data < courant.data) i = 1; // Cas 1 : suivant < courant
                    if (suivant.data == courant.data) i = 2; // Cas 2 : suivant = courant
                    if (suivant.data > courant.data) i = 3; // Cas 3 : suivant > courant
                    switch (i) {
 
                        case 0:
                            break;
 
                        case 1:
                            courant = suivant;
                            suivant = suivant.jePointeVers;
                            tete = courant;
                            break;
 
                        case 2:
                            suivant.egalite = true; // Signifie que ce Fibo2 est égale à celui qui pointe vers lui.
                            courant = suivant;
                            suivant = suivant.jePointeVers;
                            tete = courant;
                            break;
 
                        case 3:
                            tete = courant;
                            courant = suivant;
                            suivant = courant.jePointeVers;
                            break;
                        }
		}
 
 
 
		return tete;
 
	}

Et le code de l'application de test :

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
    public static void main(String[] args) {
        Fibo2 toto1 = new Fibo2();
        toto1.data = 3;
        toto1.nom = "toto1";
        Fibo2 toto2 = new Fibo2();
        toto2.data = 2;
        toto2.nom = "toto2";
        toto1.jePointeVers = toto2;
        Fibo2 toto3 = new Fibo2();
        toto3.data = 2;
        toto3.nom = "toto3";
        toto2.jePointeVers = toto3;
        Fibo2 reponse;
        reponse = Main.triV2(toto1); // Appel de votre méthode
        System.out.println("Valeur renvoyée = " + reponse.nom + ", état de l'égalité : " + reponse.egalite);
        }

Comme vous le voyez, il suffit de jouer avec les totox.data = y pour examiner comment se comporte la méthode ainsi réécrite.
J'espère que cela vous permettra d'avancer dans votre élaboration.