Frage zur einfach verketteten Liste / Rekursion

arcHack

Hallo,

folgender Sachverhalt: Angenommen, es gibt eine Verkettete Liste. Jede Node hat ein "char c" und eine Referenz auf die nächste Node, also "CharacterNode next".

Zitat

z.B. so --> informatik-forum.net/attachment/22219/ Quelle http://www.google.com/url?sa=i&rct=j…361388169138675

Demnach wäre A.next = L, L.next = I usw... bis T.next=null.

Meine Frage lautet nun, wie man die Liste ab einem beliebigen Startknoten (darf willkürlich gewählt werden) durchläuft, und die darin enthaltenen char's zu einem String zusammenfasst, um anschließend die Länge des Strings zurückzugeben. Wenn der Startknoten also I wäre, sollte das Ergebnis 3 lauten (IST) lauten. Das ganze soll rekursiv geschehen, und jeder Knoten darf max. einmal besucht werden.

Der Methodenkopf sieht so aus: public int xyz(int start) { ... }

int start bestimmt die Startposition für den Ergebnis-String, also ab welchem Knoten angefangen werden soll zu einem String zusammenzufassen, und dann die Länge des Strings zurückzugeben.

Bitte um Rat, und bitte keine Alternativansätze vorschlagen, sondern an die Angabe halten, da die Aufgabenstellung es so haben will...

Code

public int xyz(int start){
    if(start < 0 || (next==null && start > 0)){
        throw new IndexOutOfBoundsException();
    }
    if(start>0) return next.xyz(--start);

    String help = new String("");
    if(start==0 && next != null){
       ...
    }
    return help.length();
}

Alles anzeigen

Ich weiß nicht so genau, wie ich den String bei jedem Rekursionsschritt wachsen lassen kann.
Vielen Dank jetzt schon mal.

Bradon

Willst du den Code oder nur generell wissen, wie man das implementieren koennte?

Du hast zwei Teilprobleme:
1. den Knoten zu finden, bei dem du beginnen musst,
2. die chars zu einem String zusammenzustoepseln

Ad 1.:
Am einfachsten ist es, wenn du den Parameter bei jedem rekursiven Aufruf dekrementierst (start--), bis er gleich 0 ist (wenn du die Knoten bei 0 zu zaehlen beginnst, sonst 1). Wenn du also xyz(0) aufrufst, erhaeltst du "ALIST", mit xyz(1) "LIST", etc.
Negative Startparameter sind der Einfachheit halber verboten

Ad 2.:
Der String ist dein Rueckgabeparameter, das heisst er wird erst beim zurueckkehren aus der Rekursion angelegt. Du faengst also beim letzten Knoten (dessen Nachfoler null ist) an und legst dort einen String an, der T.c (also "T") enthaelt. Danach musst du nur noch in jedem Rekursionsschritt den char des entsprechenden Knotens vorne an den String anhaengen und den String zurueckgeben.

Hoffe das hilft dir weiter

/edit: public String xyz(int start) hat schon gepasst. Du musst den String ja auch irgendwie an den Aufrufer zurueckgeben. Die Laenge des Strings ist egal

Ausserdem geht es bei der Rekursion (meistens) darum, die gleiche Methode, in der du dich befindest, noch einmal (auf einem anderen Objekt) aufzurufen, das heisst eine sublist(int x)-Methode brauchst du nicht

arcHack

Vielen Dank für deine Antwort. Hast du meinen Post in aktueller Form gesehen? Da ist mein Rückgabewert nicht mehr der String, sondern die Länge vom String. Hast du ne Idee, wie ich vorankomme.

Code oder Herangehensweise, beides ist willkommen. Aber wäre schon hilfreich, wenn du den Code-Teil, der für den String zuständig ist, mit hinschreiben könntest.

Bradon

Die Fragestellung zu aenderen, waehrend ich ne Antwort schreibe, ist nicht nett

Wie gesagt, die Laenge des Strings ist uninteressant /edit: ups, hab mir den geaenderten Post doch nicht gruendlich genug durchgelesen

PHP

public int xyz(int start) {

  // Code-Teil, der den Startknoten bestimmt


  if (next == null) {
    return 1; // Es wird von hinten nach vorne gezaehlt: Das ist der erste Knoten
  } else { //Wenn dieser Knoten nicht der letzte ist, einfach 1 dazuzaehlen
    return next.xyz(0)++;
  }
}

Alles anzeigen

So in etwa wuerd ichs mir vorstellen. Ich garantiere nicht fuer syntaktische Korrektheit

//edit2: Die geaenderte Aufgabenstellung verwirrt mich etwas. Mit jedem Zeichen waechst die Laenge des Strings um 1, daher kann man einfach immer 1 dazuzaehlen. Ist das so gedacht?

arcHack

Ja, du hast schon recht, +1 funktioniert hier super. Ich habe versucht, die Originalaufgabenstellung umzuändern, weil sie zu lang war, was dazu führte

1) dass deine erste Antwort nicht mehr gepasst hatte weil ich beim umändern der Aufgabenstellung nicht so genau war (was ich im Nachhinein festgestellt habe) und
2) in der ursprünglichen Angabe muss man schon den String erzeugen (statt +1 zu rechnen), und dann die Länge zählen.

Dein voriger Code hat mich aber fürs erste weitergebracht, das mit dem String s += s+c usw... daher vielen Dank! Ich poste später bestimmt nochmal..

Frage zur einfach verketteten Liste / Rekursion

Jetzt mitmachen!

Benutzer online in diesem Thema