Frage zur einfach verketteten Liste / Rekursion

  • 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".


    Quote


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



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

    Edited 2 times, last by arcHack: fehler im code. statt sublist(--start) / xyz(--start) ().

  • 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

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

    Edited 2 times, last by Bradon ().

  • 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. :rolleyes:

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


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



    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?

    Ex-PP-Tutor und genereller [strike]Besser[/strike]Schlechterwisser

    Edited 3 times, last by Bradon: String -> int ().

  • 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.. :)