Entwickler-Ecke

Basistechnologien - Liste rückwärts ausgeben


Ritzeratze - Sa 11.01.14 01:06
Titel: Liste rückwärts ausgeben
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.


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 user profile iconChristian S.: Code- durch C#-Tags ersetzt


jaenicke - 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 - Sa 11.01.14 02:18
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 - Sa 11.01.14 02:43
Ginge das nicht relativ einfach durch Tail-Recursion ?


C#-Quelltext 
1:
2:
3:
4:
5:
6:
7:
 
    //Ausgabe der Liste        
    public void ReverseAusgeben()
    {
      if (naechster != null)
        naechster.ReverseAusgeben();
      Console.WriteLine(daten);
    }


jaenicke - Sa 11.01.14 10:48
user profile iconRitzeratze hat folgendes geschrieben Zum zitierten Posting springen:
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.

user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
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 iconRitzeratzes macht ist nur das aktuelle Element auszugeben.


Ritzeratze - Sa 11.01.14 11:50
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 - 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 user profile iconjfheins Code am ersten Listenelement aufruft wird das funktionieren.


jaenicke - 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:
user profile iconRalf Jansen hat folgendes geschrieben Zum zitierten Posting springen:
Nein. Trotz Namen beginnt Tail-Recursion trotzdem am Anfang der Liste ;) Wenn man user profile iconjfheins Code am ersten Listenelement aufruft wird das funktionieren.
Stimmt, die Aufgabe ist ja gar nicht beim letzten Element anzufangen... :oops:


jfheins - Sa 11.01.14 14:37
user profile iconRalf Jansen hat folgendes geschrieben Zum zitierten Posting springen:
Trotz Namen beginnt Tail-Recursion trotzdem am Anfang der Liste ;) Wenn man user profile iconjfheins 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:

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:

C#-Quelltext 
1:
2:
 
      Listenelement listenAnfang = new Listenelement();
      Listenelement listenEnde = listenAnfang;


Ritzeratze - Sa 11.01.14 14:41
Sorry, jetzt habt Ihr mich abgehangen.
Ich blicke einfach nicht, wie ich das vorherige Element speichere.


C#-Quelltext 
1:
2:
3:
4:
 
Listenelement listenAnfang = new Listenelement();
Listenelement listenEnde = new Listenelement();

listenEnde = listenAnfang;


Moderiert von user profile iconTh69: Code- durch C#-Tags ersetzt

Moderiert von user profile iconTh69: Beiträge zusammengefasst

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


jaenicke - Sa 11.01.14 15:57
Rückwärts geht schon so wie jfheins geschrieben hat:
user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
Ginge das nicht relativ einfach durch Tail-Recursion ?


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:

C#-Quelltext 
1:
 
listenAnfang.ReverseAusgeben();


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!