Hallo, ich bin grade dabei eine doppelt verkettete Liste zu implementieren und komme bei der letzten Methode einfach nicht weiter:

Wir sollen eine rekursive print-Methode schreiben, welche die Liste in umgekehrter Reihenfolge ausgibt. Das Ganze soll effizient implementiert werden, d.h. ein vorheriges Durchlaufen der Liste um das Ende zu suchen ist unzulässig. Es soll auch kein Zusatzfeld "foot" eingefügt werden.

Kann mir jemand dazu vll. einen Denkanstoß geben? Ich kann es mir nur so vorstellen, wie bei meiner Mathode print_rekursiv() (nur halt in umgekehrter Reihenfolge), aber da wird ja das Ende gesucht.

Danke schonmal im Voraus

Mein Code:

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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179

public class Student {      public class Student_Node {         String name;     int matr_nr;           Student_Node prev; // vorheriges Element     Student_Node next; // naechstes Element             Student_Node(String name, int matrikelnummer) {                  this.name = name;          this.matr_nr = matrikelnummer;           }     }        Student_Node first;    Student_Node last;        Student_Node temp2;            // neues Element (Knoten) in die Liste einfuegen ----------------------------        void insert(String name, int matr_nr) {            // Erzeugen eines neuen Knotens      Student_Node studi = new Student_Node(name, matr_nr);            // falls Liste leer      if (first == null) {                 studi.prev = studi;         studi.next = null;         first = studi;                 temp2 = first;      }            else {            studi.next = first;            if (first != null) {                     first.prev = studi;                 }              first = studi;      studi.prev = last;            temp2 = first;            }    }            // Element aus Liste loeschen -----------------------------------------------        void delete(int matr_nr) {         Student_Node temp = first;            while (temp != null) {                    if (temp.matr_nr == matr_nr) {                                //wenn temp nicht erstes Element                if (temp.prev != null) {                             (temp.prev).next = temp.next;                                    }                else {                                         //wenn temp erstes Element                     first = temp.next;                }                                //wenn temp nicht letztes Element                       if (temp.next != null) {                             (temp.next).prev = temp.prev;                }          }                    temp = temp.next;      }         }            // Studenten nach Matrikelnummer suchen -------------------------------------        void search(int matr_nr) {         Student_Node temp = first;     boolean found = false;         // gesuchtes Element = erstes Element ? ...     if (temp.matr_nr == matr_nr) {                 found = true;     }     // ...falls nicht laufe durch Liste     while (temp.next != null && temp.matr_nr != matr_nr) {                   if (temp.next != null) {                     temp = temp.next;               }                 if (temp.matr_nr == matr_nr) {                         found = true;         }       }         if (found == true) {                 System.out.println("Folgender Student wurde gefunden: " + temp.name);     }     else {                 System.out.println("Die Liste enthaelt keinen Studenten mit der Matrikelnummer " + matr_nr);     }    }        // Ausgabe der gesamten Liste (iterativ) ------------------------------------        void print_iterativ() {          Student_Node temp = first;               while(temp != null) {                 System.out.println(temp.matr_nr + " - " +temp.name);         temp = temp.next;      }    }             // Ausgabe der gesamten Liste (rekursiv) -----------------------------------        void print_rekursiv() {                 if (temp2 != null) {                         System.out.println(temp2.matr_nr + " - " +temp2.name);             temp2 = temp2.next;             print_rekursiv();         }    }        // --------------------------------------------------------------------------       public static void main (String[] args) {         Student test = new Student();         test.insert("Max Mustermann", 123);     test.insert("Christian Mueller", 456);     test.insert("Stefanie Meier", 789);     test.print_iterativ(); //  test.search(788);     System.out.println(""); //  test.delete(123); //  System.out.println("");     test.print_iterativ(); //  System.out.println("");     test.print_rekursiv();   } }

Hallo,

wie wäre denn der Vorschlag?:

Code :

1 2 3 4 5 6 7 8

// Ausgabe der gesamten Liste (rekursiv) -----------------------------------        void print_rekursiv() {                 if (next != null)             next->print_rekursiv();             System.out.println(matr_nr + " - " + name);    }

Gruß

RedWing

hm....was bedeutet denn der Pfeil bei "next->print_rekursiv();" ist das nicht eine Zuweisung in C? Kenne C nicht, darum frag ich?

also nur mit next wird das natürlich nichts, man müsste sich wieder ein temp3 o.ä. erzeugen, also irgendwie so

Code :

1 2 3 4 5 6 7

void print_rekursiv_reverse() {                 if (temp3.next != null)             ? print_rekursiv();             System.out.println(temp3.matr_nr + " - " + temp3.name);    }

aber gilt das nicht auch als Durchlaufen der Liste? Man läuft ja quasi durch, bis es "null" wird?

Hallo,
sorry dein Pfeil hatte ich aus C++ intus Normalerwiese sollte da ein . stehen...

Code :

1 2 3 4 5 6 7 8

// Ausgabe der gesamten Liste (rekursiv) -----------------------------------        void print_rekursiv() {                 if (next != null)             next.print_rekursiv();             System.out.println(matr_nr + " - " + name);    }

Somit ist diese Funktion iauf die Objekte bezogen rekursiv...
Natuerlich muss man die Liste durchlaufen, aber sie wird eben in dem Bsp nur
einmal durchlaufen womit wir bei einem linearen Aufwand wären. Schneller geht es
meiner Meinung nach nicht.

Also nochmal:
Zuerst einmal durchlaufen bis zum Schluss. Danach einfach nur noch das Element
ausgeben. Der Rest erledigt das zurückpoppen aus der Rekursion...

Gruß

RedWing

Hallo!

In abgewandelter Form würde das dann so aussehen:

Code java:

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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

/**  *  */ package de.tutorials;     /**  * @author Tom  *  */ public class LinkedListExample {       /**      * @param args      */     public static void main(String[] args) {         Node head, node = head = new Node("A");         node.setNext(new Node("B"))             .setNext(new Node("C"))             .setNext(new Node("D"))             .setNext(new Node("E"))             .setNext(new Node("F"));           System.out.println(head);         System.out.println(head.toStringReverse());             }       static class Node {         Node previous;           Node next;           Object data;           public Node(Object data) {             this.data = data;         }           public String toStringReverse() {             String str = data.toString();             if (this.next != null) {                 str = this.next.toStringReverse() + " " + str;             }             return str;         }           public String toString() {             String str = data.toString();             if (this.next != null) {                 str += " " + this.next.toString();             }             return str;         }           public Node getNext() {             return next;         }           public Node setNext(Node next) {             this.next = next;             if (next != null) {                 next.setPrevious(this);             }             return next;         }           public Node getPrevious() {             return previous;         }           public void setPrevious(Node previous) {             this.previous = previous;         }     } }

Gruß Tom

Hi,

danke nochmal. Habs jetzt doch über ein foot-Element gemacht... "zeiger" zeigt auf mein letztes Element

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public void print_reverse_rekursiv() {             print_reverse_rekursiv(zeiger);         }   public void print_reverse_rekursiv(Student_Node studi) {                 if (studi != null) {                 System.out.println(studi.matr_nr + " - " +studi.name);             print_reverse_rekursiv(studi.prev);     } }

so funktioniert es...ohne vorher das Ende zu suchen oder einen Zeiger auf das letzte Element zu haben, funktioniert es meiner Meinug nach auch nicht
Mal sehen was mein Prof. sagt.

so, hab´s nun doch mit den vorgegebenen Einschränkungen hin bekommen:

Code :

1 2 3 4 5 6 7 8

public void printRek() {printRek(first);} public void printRek(Student studi) {   if (studi != null) {     printRek(studi.next);     System.out.println(studi);   } }