séparer une liste chainée en deux listes

Version imprimable

30/10/2016, 18h16
momo-mtl

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

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
30/10/2016, 18h23
adiGuba

Salut,

Et quel est le bug ?

a++
30/10/2016, 18h24
momo-mtl

Citation:

Envoyé par adiGuba

Salut,

Et quel est le bug ?

a++

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

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:

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;
	}

30/10/2016, 18h38
adiGuba

Citation:

Envoyé par momo-mtl

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++

Citation:

Envoyé par adiGuba

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:

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

30/10/2016, 19h45
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.