Liste rückwärts ausgeben

Ritzeratze · Beiträge: 101

Moin,

ich weiß das das Thema schon einmal hier behandelt wurde. Ich habe die Technik fast verstanden, ein kleines Problem habe ich noch dabei. Ausgangslage ist eine Liste rückwärts über eine rekursive Methode auszugeben. In dem Code wird aber nur das letzte Element der Liste ausgegeben. Im Debugger werden aber alle Element in den entsprechenden Durchläufen angezeigt. Die Ausgabe der Elemente in Vorwärtsrichtung mit entsprechender Codeänderung klappt einwandfrei. Kann mir vielleicht jemand bei meinem Fehler einen Tipp geben ? Und hier der entsprechende Code.

markieren

C#-Quelltext

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:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Rekursion
{
  
  class Listenelement
  {
    string daten;
    Listenelement naechster;

    //Setzen der Daten
    public void SetDaten(string datenNeu)
    {
      //die Zeichenkette setzen
      daten = datenNeu;
    }

    //Anhängen eines neuen Elements        
    public Listenelement Anhaengen(string datenNeu)
    {
      naechster = new Listenelement();
      naechster.SetDaten(datenNeu);

      return naechster;
    }

    //Ausgabe der Liste        
    public void Ausgeben()
    {
      Console.WriteLine(daten);
      if (naechster != null)
        naechster.Ausgeben();
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      //neue Listenelemente erzeugen
      Listenelement listenAnfang = new Listenelement();
      Listenelement listenEnde = new Listenelement();

      listenEnde = listenAnfang;

      //die Daten im ersten Listenelement setzen
      listenEnde.SetDaten("Element 1");

      //weitere Elemente in einer Schleife anfügen
      for (int element = 2; element < 10; element++)

        listenEnde = listenEnde.Anhaengen("Element " + element);

      //die Liste ausgeben
      listenEnde.Ausgeben();
    }
  }
}

Gruss
Ritze

Moderiert von Christian S.: Code- durch C#-Tags ersetzt

jaenicke · Verfasst: Sa 11.01.14 01:31

Überlege dir einmal was in dem Feld naechster des letzten Elements steht, wenn darin immer das nächste Element steht...
(Welches ist denn das nächste Element des letzten Elements?)

Willst du rückwärts und vorwärts durch die Liste, brauchst du eine doppelt verkettete Liste, damit du auch das vorhergehende Element herausbekommen kannst.

Ritzeratze · Beiträge: 101

Hallo jaenicke,

Danke für Deine Antwort.
Ja ich bin da ein bisschen mit meinen Überlegungen ins Schleudern gekommen. Das letzte Element ist ja irgendwann NULL.
Ich müßte schauen, wenn das letzte Element NULL ist. Aber wie komme ich dann zurück zum vorhergehenden Element.?

Gruss
Ritze

jfheins · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

Ginge das nicht relativ einfach durch Tail-Recursion ?

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:

    //Ausgabe der Liste        
    public void ReverseAusgeben()
    {
      if (naechster != null)
        naechster.ReverseAusgeben();
      Console.WriteLine(daten);
    }

jaenicke · Verfasst: Sa 11.01.14 10:48

Ritzeratze hat folgendes geschrieben :

Aber wie komme ich dann zurück zum vorhergehenden Element.?

Gar nicht ohne Rückwärtsverkettung. Wenn du keinen Verweis auf das vorherige Element hast, kannst du auch ausschließlich vom ersten Element aus durch die Liste gehen.

jfheins hat folgendes geschrieben :

Ginge das nicht relativ einfach durch Tail-Recursion ?

Der Code hat doch das gleiche Problem. Du bist bereits beim letzten Element. Das Feld naechster ist also null, das weißt du. Sprich was dein Code wie auch user profile icon

Ritzeratzes macht ist nur das aktuelle Element auszugeben.

Ritzeratze · Beiträge: 101

Moin Jaenicke,

wie bekomme ich den Verweis auf das vorherige Element? Wenn ich vom Listenanfang lese, werde ich am Ende irgendwann auf NULL stoßen.
Um die Liste Rückwärts ausgeben zu können, brauche ich das letzte Element, aber genau da ist mein Problem. Wie kann ich dieses ermitteln?

Gruss Ritze

Ralf Jansen · Verfasst: Sa 11.01.14 12:40

Zitat:

wie bekomme ich den Verweis auf das vorherige Element?

Den mußt du in der Anhaengen Methode mit verwalten. Dort erzeugst du ein neues Element wenn du dem Element nicht nur ein naechster Verweis plegst sondern auch ein voherigen genauso pflegst. In der Anhaengen Methode hast du ja beide Elemente am Wickel und kannst Verweise in beide Richtungen pflegen.

Zitat:

Der Code hat doch das gleiche Problem

Nein. Trotz Namen beginnt Tail-Recursion trotzdem am Anfang der Liste

Wenn man

jfheins Code am ersten Listenelement aufruft wird das funktionieren.

jaenicke · Verfasst: Sa 11.01.14 12:40

Ermitteln gar nicht. Du musst dir das analog zu naechster selbst in jedem Element speichern. Sprich beim Anhängen nicht nur naechster im aktuellen Element setzen, sondern auch in dem anzuhängenden Element das aktuelle Element als vorheriges speichern.

// EDIT:

Ralf Jansen hat folgendes geschrieben :

Nein. Trotz Namen beginnt Tail-Recursion trotzdem am Anfang der Liste

Wenn man

jfheins Code am ersten Listenelement aufruft wird das funktionieren.

Stimmt, die Aufgabe ist ja gar nicht beim letzten Element anzufangen... :oops:

jfheins · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

Ralf Jansen hat folgendes geschrieben :

Trotz Namen beginnt Tail-Recursion trotzdem am Anfang der Liste

Wenn man

jfheins Code am ersten Listenelement aufruft wird das funktionieren.

Genau - es war aber gestern wohl schon zu spät, weil der wesentliche Fehler ja genau das hier ist:

markieren

C#-Quelltext

1:
2:

      //die Liste ausgeben
      listenEnde.Ausgeben();

Da die Liste nur einfach verkettet ist, muss man immer beim ersten Element anfangen. Je nach Methodeninhalt der Rekursion wird die Liste dann entweder vorwärts oder rückwärts ausgegeben.

Zu Beginn lässt sich übrigens auch eine Zeile sparen:

markieren

C#-Quelltext

1:
2:

      Listenelement listenAnfang = new Listenelement();
      Listenelement listenEnde = listenAnfang;

Ritzeratze · Beiträge: 101

Sorry, jetzt habt Ihr mich abgehangen.
Ich blicke einfach nicht, wie ich das vorherige Element speichere.

markieren

C#-Quelltext

1:
2:
3:
4:

Listenelement listenAnfang = new Listenelement();
Listenelement listenEnde = new Listenelement();

listenEnde = listenAnfang;

Moderiert von Th69: Code- durch C#-Tags ersetzt

Moderiert von Th69: Beiträge zusammengefasst

VorwärtsAusgabe funktioniert ja auch super. Aber rückwarts ......

jaenicke · Verfasst: Sa 11.01.14 15:57

Rückwärts geht schon so wie jfheins geschrieben hat:

jfheins hat folgendes geschrieben :

Ginge das nicht relativ einfach durch Tail-Recursion ?

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:

    //Ausgabe der Liste        
    public void ReverseAusgeben()
    {
      if (naechster != null)
        naechster.ReverseAusgeben();
      Console.WriteLine(daten);
    }

Und dann noch aufrufen:

markieren

C#-Quelltext

1:	listenAnfang.ReverseAusgeben();

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme