Verkettete Liste in C#



  • Hallo,
    Ich mache seit einiger zeit ein Fernstudium (Informatiker) und bin bisher auch gut durchgekommen mit dem Stoff.

    nun komme ich aber bei zwei Aufgabenstellungen in C# einfach nicht weiter, und der Hilfestellungen vom Fernlehrer bringen mich bzw mein Verständnis auch kein Stück weiter.

    Das Lehrheft hab ich nun einige male durch, aber wirklich schlauer bin ich nicht, ich verstehe grob was das Programm macht und wie es arbeitet (wenn es richtig ist das die Instanzen sich selbst aufrufen und wieder eine instanz erzeugen, eine Art Baumstruktur?) aber mir fehlt einfach der Anfang wie man da herangeht oder es lösen soll.

    Vielleicht kann mir hier jemand auf die Sprünge helfen.
    Danke

    1. Aufgabe
    Erweitern Sie die zweite Version der einfach verketteten Liste so, dass das Listenende beim Anhängen nicht immer wieder neu ermittelt werden muss, sondern neue Elemente direkt am Ende der Liste angehängt werden können.
    Dazu ein paar Hilfestellungen:
    •	Sie müssen neben dem Anfang der Liste jetzt auch das Ende der Liste in einer eigenen Instanz speichern können.
    •	Erstellen Sie eine Methode, die Ihnen das aktuelle Ende der Liste zurückliefert. Alternativ können Sie sich das Listenende auch von der Methode zum Anhängen liefern lassen.
    •	Setzen Sie den Wert der Instanz für das Listenende nach dem Anhängen neuer Elemente jeweils auf das aktuelle Ende der Liste und rufen Sie dann die Methode zum Anhängen neuer Listenelemente mit diesem Wert neu auf.
    
    1. aufgabe
    Erweitern Sie die zweite Version der einfach verketteten Liste so, dass die Liste auch rückwärts ausgegeben werden kann.
    Erstellen Sie dazu eine entsprechende Methode, die sich rekursiv aufruft.
    

    Und der vorgabe Code

    using System;
    
    namespace Cshp
    {
        //die Klasse für die Listenelemente
        //jetzt auch mit Methoden
        class Listenelement
        {
            string daten;
            Listenelement naechster;
    
            //die Methode zum Setzen der Daten
            public void SetDaten(string datenNeu)
            {
                //die Zeichenkette setzen
                daten = datenNeu;
                //das Ende markieren
                naechster = null;
            }
    
            //die Methode zum Anhängen eines neuen Elements
            //sie ruft sich rekursiv auf, bis das Ende erreicht ist
            public void Anhaengen(string datenNeu)
            {
                //wenn das Ende erreicht ist, ein neues Element erzeugen
                if (naechster == null)
                {
                    naechster = new Listenelement();
                    naechster.SetDaten(datenNeu);
                }
                //sonst ruft sich die Methode selbst wieder auf
                else
                    naechster.Anhaengen(datenNeu);
                //zur Veranschaulichung der Rekursion
                Console.WriteLine("Daten {0} wurden eingefügt.", datenNeu);
            }
    
            //die Methode zur Ausgabe der Liste
            //sie ruft sich ebenfalls rekursiv auf, bis das 
            //Ende erreicht ist
            public void Ausgeben()
            {
                Console.WriteLine(daten);
                if (naechster != null)
                    naechster.Ausgeben();
            }
        }
    
        class Program
        {
            static void Main(string[] args)
            {
                //ein neues Listenelement erzeugen
                Listenelement listenAnfang = new Listenelement();
    
                //die Daten im ersten Listenelement setzen
                listenAnfang.SetDaten("Element 1");
    
                //weitere Elemente in einer Schleife anfügen
                for (int element = 2; element < 4; element++)
                    listenAnfang.Anhaengen("Element " + element);
    
                //die Liste ausgeben
                listenAnfang.Ausgeben();
    
                Console.WriteLine("Enter Drücken zm Beenden");
                while (Console.ReadKey().Key != ConsoleKey.Enter) { }
            }
        }
    }
    
    
    


  • also in der ersten aufgabe geht es darum, vom ersten listenelement aus auf das letzte listenelement bzw. das (nicht vorhandene) element hinter dem letzten element zugreifen zu können, damit du dann unkompliziert ein neues element einfügen kannst. nachdem du das neue element eingefügt hast, musst du dann natürlich dieses letzte element aktualisieren.

    bei der zweiten aufgabe geht es darum, die liste rekursiv zu durchlaufen. du weißt doch, was rekursion ist, oder?



  • okay, soweit versteh ich das, mir fehlt im Moment jede Vorstellung das umzusetzen

    Rekursion ist doch wenn sie die Funktion/Methode selbst immer wieder aufruft bis ein event es unterbricht?



  • naja wenn ich dir jetzt erzähle, was du machen musst, lernst du ja nicht selber zu überlegen und zu probieren und erfahrungsgemäß kann das halt schonmal zwei, drei tage lang (bei 8std/tag) dauern......😀

    wie gesagt: du musst eine möglichkeit finden, vom ersten listenelement aus auf das letzte zugreifen zu können und beim anfügen eines neuen listenelements diese zugriffsmöglichkeit zu aktualisieren.

    bei rekursion ruft sich die funktion so lange selbst auf, bis die abbruchbedingung erfüllt ist. bsp.:

    void ZeileSchreiben(int anzahl)
    {
         if(anzahl == 0)
         {
              return;
         }
    
         ZeileSchreiben(anzahl - 1);
    
         Console.WriteLine("Funktion mit anzahl = " + anzahl);
    
         
    }
    

    wenn du dann

    ZeileSchreiben(5);
    

    aufrufst, wird diese funktion zuerst (im hauptprogramm) mit dem wert 5 aufgerufen, dann (in der funktion selbst) mit 4, 3, 2, 1 und 0 und da zuerst alle funktionen aufgerufen werden und dann die ausgabe erfolgt, erfolgt die ausgabe rückwärts bzw. wenn du zuerst ausgibst und dann aufrufst, vorwärts. damit kannst du dann die reihenfolge steuern.

    und sowas ähnliches kannst du auch mit der verketteten liste machen.



  • ich hab es wohl hinbekommen, danke.

    1. aufgabe
    using System;
    
    namespace Cshp1
    {
        //die Klasse für die Listenelemente
        //jetzt auch mit Methoden
        class Listenelement
        {
            string daten;
            Listenelement naechster;
    
            //die Methode zum Setzen der Daten
            public void SetDaten(string datenNeu)
            {
                //die Zeichenkette setzen
                daten = datenNeu;
                //das Ende markieren
                naechster = null;
                Console.WriteLine("Daten {0} wurden eingefügt.", datenNeu);
            }
    
            //die Methode zum Anhängen eines neuen Elements
            public Listenelement Anhaengen(string datenNeu)
            {
                //neues listenende
                naechster = new Listenelement();
                naechster.SetDaten(datenNeu);
               //rückgabe des listenendes
                return naechster;
            }
            //rekursive suche nach dem listenendes
            public static Listenelement Letzter(Listenelement element)
            {
                Listenelement durchgang = element;
            Start:
                if (null == durchgang.naechster)
                    return durchgang;
                durchgang = durchgang.naechster;
                goto Start;
            }
            //die Methode zur Ausgabe der Liste
            //sie ruft sich ebenfalls rekursiv auf, bis das 
            //Ende erreicht ist
            public void Ausgeben()
            {
                Console.WriteLine(daten);
                if (naechster != null)
                    naechster.Ausgeben();
            }
        }
    
        class Program
        {
            static void Main(string[] args)
            {
                //ein neues Listenelement erzeugen
                Listenelement listenAnfang = new Listenelement();
                
                //die Daten im ersten Listenelement setzen
                listenAnfang.SetDaten("Element 1");
    
                
                //instanz für speicherung listenende
                Listenelement ende = null;
                //weitere Elemente in einer Schleife anfügen
                for (int element = 2; element < 4; element++)
                {
                    //Einmalige Suche nach Listenende
                    if (ende == null)
                        //methode zur ermittlung listenende
                        ende = Listenelement.Letzter(listenAnfang); 
    
                    if (null != ende)
                    {
                        //methode zum anhängen und rückgabe eines neuen listenelementende
                        Listenelement neuesende = ende.Anhaengen("Element " + element);
                        //ende ist neues ende (und die erde eine scheibe XD)
                        ende = neuesende; 
                    }
                }
    
                //die Liste ausgeben
                listenAnfang.Ausgeben();
    
                Console.WriteLine("Enter Drücken zm Beenden");
                while (Console.ReadKey().Key != ConsoleKey.Enter) { }
            }
        }
    }
    
    
    1. aufgabe
    using System;
    using System.Collections.Generic;
    
    namespace Cshp2
    {
        //die Klasse für die Listenelemente
        //jetzt auch mit Methoden
        class Listenelement
        {
            string daten;
            Listenelement naechster;
            Listenelement vorgaenger;
    
    
            //die Methode zum Setzen der Daten
            public void SetDaten(string datenNeu)
            {
                //die Zeichenkette setzen
                daten = datenNeu;
                //das Ende markieren
                naechster = null;
            }
    
            //die Methode zum Anhängen eines neuen Elements
            //sie ruft sich rekursiv auf, bis das Ende erreicht ist
            public void Anhaengen(string datenNeu)
            {
                //wenn das Ende erreicht ist, ein neues Element erzeugen
                if (naechster == null)
                {
                    naechster = new Listenelement();
                    naechster.SetDaten(datenNeu);
                    naechster.vorgaenger = this;
                    
                }
                //sonst ruft sich die Methode selbst wieder auf
                else
                    naechster.Anhaengen(datenNeu);
                //zur Veranschaulichung der Rekursion
                Console.WriteLine("Daten {0} wurden eingefügt.", datenNeu);
            }
    
            //die Methode zur Ausgabe der Liste
            //sie ruft sich ebenfalls rekursiv auf, bis das 
            //Ende erreicht ist
            public void Ausgeben()
            {
                Console.WriteLine(daten);
                if (naechster != null)
                    naechster.Ausgeben();
            }
            public void RueckwaertsAusgeben()
            {          
                
                Console.WriteLine(daten);
                if (vorgaenger != null)
                    vorgaenger.RueckwaertsAusgeben();
            }
            //rekursive suche nach dem listenendes
            public static Listenelement Letzter(Listenelement element)
            {
                Listenelement durchgang = element;
            Start:
                if (null == durchgang.naechster)
                    return durchgang;
                durchgang = durchgang.naechster;
                goto Start;
            }
        }
    
        class Program
        {
            static void Main(string[] args)
            {
                //ein neues Listenelement erzeugen
                Listenelement listenAnfang = new Listenelement();
    
                //die Daten im ersten Listenelement setzen
                listenAnfang.SetDaten("Element 1");
    
                //weitere Elemente in einer Schleife anfügen
                for (int element = 2; element < 4; element++)
                    listenAnfang.Anhaengen("Element " + element);
    
                //die Liste ausgeben
                listenAnfang.Ausgeben();
                Listenelement.Letzter(listenAnfang).RueckwaertsAusgeben();
    
                Console.WriteLine("Enter Drücken zm Beenden");
                while (Console.ReadKey().Key != ConsoleKey.Enter) { }
    
            }
        }
    }
    
    


  • Ich sehe keine Liste. // edit: liegt wahrscheinlitsch an mir.