StackOverflowError bei Rekursion

[Reen]

Hallo!

Ich will's mal kurz beschreiben. Verkettete Liste sieht stark vereinfacht so aus -> [index][name][nächster_index] d.h. eine ArrayList in jedem Listenknoten.

z.B. würde so ein Teil der Liste aussehen.
[1][Eintrag][2]
[2][---------][-]

Aufgabe ist es, diese Einträge wieder zu löschen und mit vordefinierten Werten zu füllen, die quasi anzeigen, dass diese Listeneinträge wieder frei sind.
z.B
[1][$wieder_frei][-]
[2][$wieder_frei][-]

Im ersten Teil suche ich den Namen, der gelöscht werden soll und halte den Index fest, wo dieser auf den nächsten Eintrag hinzeigt. Das ist auch kein Problem.

Im nächsten Schritt übergebe ich den Folgeindex an eine neue Funktion, die nur noch nach den Index'en sucht. Da ich diese Funktion aber jedesmal rekursiv aufrufe, tritt der im Titel genannte Fehler auf.

public static void index(String naechster_index)
{  
     // werte aktuellen Konten aus
     // folgen weite, wenn JA
    index(naechster);
}

Habe auch schon versucht, den aktuellen Knoten immer als Startpunkt zu übergeben, damit die Liste nich immer von ganz oben durchlaufen werden muss. Hat aber auch nicht gefunzt.

Jemand ne Idee, wie man das anders machen könnte? Wenn das eventuell zu wenig war, poste ich das nächste Mal mehr orginalen Code!

Danke
Reen

 

[SlaterB]

eine Rekursion über 100te Listenelemente ist nun mal nicht sinnvoll,

was spricht gegen ein einfaches

Element e = first;
boolean break = false;
while (!break) {
  e = e.next();
  ...
}

oder ähnlich?

 

[Reen]

Die Idee ist vllt nicht schlecht, habe aber noch vergessen zu sagen, dass der Index, der auf den nächsten Listenknoten zeigt, nicht unbedingt auf seinen direkten Nachfolgeknoten zeigen muss. Es kann auch sein, dass dieser auf einen übernächsten oder oder oder zeigt.

z.B.
[1][EintragEINS][3]
[2][EintragZWEI][-] -> kein Folgeknoten
[3][----------------][-] -> kein Folgeknoten

d.h. in diesem Fall würde dein Ansatz ja versagen, wenn ich das richtig sehe, da ich ja hier nicht jeden beliebigen Knoten beachten darf. Falls es doch geht, würde ich mich über einen Tipp von dir freuen.

Ich habe jetzt einen anderen Ansatz probiert, der auch erstma soweit funktionieren zu scheint. Ich habe mir eine Klassenbasierte ArrayList definiert, in der ich die Index'e sammle und gleichzeitig immer den letzten Index als Vergleichsindex für den nächsten Listenknoten verwende. z.B. nächster Index wäre die 3, dann kommt die in die ArrayList und beim weiteren Durchsuchen der Liste nutze ich die 3, um den Knoten mit dem Index 3 auf einen FolgeIndex auszuwerten. Im obrigen Bsp hätte der 3.te Knoten dann keinen Verweiss mehr.

Hoffe das habe ich halbwegs verständlich rübergebracht :lol:

gruss
Reen

 

[SlaterB]

> d.h. in diesem Fall würde dein Ansatz ja versagen, wenn ich das
> richtig sehe, da ich ja hier nicht jeden beliebigen Knoten beachten
> darf. Falls es doch geht, würde ich mich über einen Tipp von dir freuen.

ich habs nicht genau verstanden, aber in der Rekursion kannst du ja auch nicht zaubern,
wenn du dort zum nächsten Elment gelangst, dann genausogut nichtrekursiv

 

[DaKo]

Du musst nur die Methode next richtig definieren

D.h. next geht nicht zum nächsten Index sondern zum Nachfogerindex. SlaterBs Ansatz ist der weitaus einfachere (und bessere, finde ich). Es würde ja auch niemand die Fakultät rekursiv berechnen (hoffe ich zumindest).

 

[ARadauer]

Es würde ja auch niemand die Fakultät rekursiv berechnen (hoffe ich zumindest).

das sind aber immer die Bispiele die benutzt werden um die Rekursion zu lehren.
man lernt ja nicht fürs leben sondern für die schule :autsch: :autsch:

 

[Reen]

Ok...dann hier mal ein wenig Code. Das wäre jetzt meine Methode um erstmal nach den Namen zu suchen und den ersten Verweis auf einen eventuell dazugehörigen anderen Listenknoten festzuhalten.

Vllt kennt ihr ja ne Möglichkeit, die Idee von Slater dirket in der Methode mit umzusetzen, anstatt das in eine neue Methode zu verpacken.

Mal an einer Beispielliste.
[1][javaforum][3]
[2][c_plusplus][ED]
[3][-------------][5]
[4][delphi___][ED]
[5][-------------][ED]

d.h. ich möchte jetzt z.B. die Index'e 1, 3 und 5 rausgreifen und die Namenseinträge durch den String $free und die Index'e die auf einen anderen Listenknoten zeigen durch "-1" ersetzen. "ED" heisst, dass es keine Verweise gibt. Als erstes würde ich ja den String "javaforum" an diese Methode übergeben und den Index 3 festhalten. Muss hier auch mit RegEx arbeiten, da ich die String's aus einem ByteArray hole.

Wie könnte man das jetzt mit Slaters Methode machen?

Danke
Reen

public static void loeschen(String name)
	{
		 Knoten aktuellerKnoten = kopf;
	    String free = "$free";
		 String nextcl = "-1";
	    ArrayList<byte[]> v;
	   
	    while (aktuellerKnoten != null)                
		    { 
		      if (aktuellerKnoten.element instanceof ArrayList)	{ 	
		  			v = (ArrayList) aktuellerKnoten.element;
		  			
		  		  String namef = new String(((byte[])(v.get(1))));
		  		  Pattern p = Pattern.compile(name, Pattern.CASE_INSENSITIVE);
			       Matcher m = p.matcher(namef); 
			       boolean result = m.lookingAt();
			       if (result == true)	{
			    		byte[] fname  = new byte[190];
						 byte[] nextc   = new byte[7];
		    			
						 String nextindex = new String((byte[])(v.get(2)));
				       Pattern pb = Pattern.compile("[0-9]+");
				       Matcher mb = pb.matcher(nextindex);
				       while (mb.find())
				    	{	del_nextcluster(mb.group());	}   // Methode aufrufen, die nur die Folgeindex'e auswertet
						
				    	System.out.println(" READY!\n");
				    	
				    	/**
			    		free.getBytes(0, 5, fname, 0);
		    			v.set(1, fname);
		    			
		    			nextcl.getBytes(0, 2, nextc, 0);
		    			v.set(5, nextc);
		    			
				    	**/
				    	//break;
			    		}
		  		}		      
		      aktuellerKnoten = aktuellerKnoten.naechster;
		    }  
	}

 

[SlaterB]

was ist denn das Problem, geht es nicht so wie es ist?

while {
  naechster Knoten in Reihenfolge
  if (bedingung an Knoten) {
    ..
  }
}

ist doch eine respektable Alternative und spontan gesagt sogar besser als

while {
  berechne kompliziert naechsten Treffer-Knoten
  ..
}