Discussion :

[momo-mtl]

Bonjour,
Je voudrais séparer une liste simplement chainée en deux listes, mais j'ai un bug. Voici mon code

Code :

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

1
2
3
4
5
6
7
8
9
 
public void Separer(int k, Liste l1, Liste l2){
		Noeud n = premier;
		while(n!= null){
			if (n.valeur<=k) l1.AjoutFin(n.valeur);
			else l2.AjoutFin(n.valeur);
			n = n.prochain;
		}
	}

dites moi si vous voyez quelque chose qui cloche et merci

[adiGuba]

Salut,


Et quel est le bug ?


a++

[momo-mtl]

Salut,


Et quel est le bug ?


a++

J'ai le message d'erreur suivant
Exception in thread "main" java.lang.StackOverflowError

[momo-mtl]

Pour être plus précis, mon problème c'est de faire un quicksort sur une liste simplement chainée, et voila mon code au complet

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
 
public void Separer(int k, Liste l1, Liste l2){
		Noeud n = premier;
		while(n!= null){
			if (n.valeur<=k) l1.AjoutFin(n.valeur);
			else l2.AjoutFin(n.valeur);
			n = n.prochain;
		}
	}
 
	public void Concatener(Liste l){
		if (premier == null){
			premier = l.premier;
			return;
		}
		Noeud n = premier;
		while (n.prochain != null) n=n.prochain;
		n.prochain = l.premier;
	}
 
	public void QuickSort(){
		if (premier == null) return;
		Liste l1 = new Liste();
		Liste l2 = new Liste();
		Separer(premier.valeur, l1, l2);
		System.out.print("test");
		l1.QuickSort();
		l2.QuickSort();
		l1.Concatener(l2);
		premier = l1.premier;
	}

[adiGuba]

J'ai le message d'erreur suivant
Exception in thread "main" java.lang.StackOverflowError

Cela veut dire que tu boucles à l'infini.
Le reste du message d'erreur t'indique l'origine du problème...


a++

[momo-mtl]

Cela veut dire que tu boucles à l'infini.
Le reste du message d'erreur t'indique l'origine du problème...


a++

Justement, je ne vois pas ou je boucle à l'infini
Le reste du message d'erreur est le suivant

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
at java.io.FileOutputStream.write(Unknown Source)
	at java.io.BufferedOutputStream.flushBuffer(Unknown Source)
	at java.io.BufferedOutputStream.flush(Unknown Source)
	at java.io.PrintStream.write(Unknown Source)
	at sun.nio.cs.StreamEncoder.writeBytes(Unknown Source)
	at sun.nio.cs.StreamEncoder.implFlushBuffer(Unknown Source)
	at sun.nio.cs.StreamEncoder.flushBuffer(Unknown Source)
	at java.io.OutputStreamWriter.flushBuffer(Unknown Source)
	at java.io.PrintStream.write(Unknown Source)
	at java.io.PrintStream.print(Unknown Source)
	at projet.Liste.QuickSort(Liste.java:39)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)
	at projet.Liste.QuickSort(Liste.java:40)

que je ne comprends pas du tout

[adiGuba]

Ben c'est ta méthode QuickSort() : il y a une quinzaine de ligne dessus (et probablement plus car le stacktrace doit être coupé).


A vue de nez je dirais que tu ne testes pas les cas d'arrêt.
Lorsque tu arrives à une liste d'un élément tu continue de la "couper" en deux et tu refais un QuickSort dessus... à l'infini.



a++


PS : au passage en Java les noms de méthode commencent par une lettre minuscule.