C# Verkettete Liste Rekursiv

[City Hunter]

Hallo,

ich habe ein Übungsprogramm geschrieben für eine verkettete liste. Jetzt will ich gerne das Programm so schreiben. das er nicht alle Elemente durch geht und bestätigt das er nicht das ende ist. Will das so umschreiben das er das ende speichert und gleich das nächste Element anfügt so das er nicht erst alles durch gehen muss. Hab schon viel Probiert aber mir fällt keine lösung ein.

vielleicht kann mit einer hier helfen.

Mfg
Patrick List

[RazorX]

Wenn ich dich richtig verstanden habe, dann such mal nach "Doppelt verkettete Liste" ("double linked list").

MfG

[City Hunter]

Code: Alles auswählen

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

namespace CShp4
{
    // 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 einfü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 < 10000000; element++)
             {
                 listenAnfang.Anhaengen("Element " + element);
             }
            // die Liste ausgeben
             listenAnfang.Ausgeben();
            Console.ReadLine();
        }
    }
} 

Also das ist mein Code. Und den will ich ja so um bauen das er mir immer gleichdas Letzte Element anhängt am letzten so das er nicht erst alle 20 000 Elemente durch laufen muss und sagt."Nicht das letzte Element"

Also wenn das so heißt double linked list muss ich mal danach suchen.

[RazorX]

Bei einer double linked list speicherst du halt wie der Name schon sagt zwei Zeiger, eben den Nachfolger und Vorgänger. Das letzte Element speicherst du dann in der Listenklasse. Es ist auch möglich das ganze als normale verkettete Liste zu implementieren, dabei zeigt das letzte Element nicht auf null sondern auf den Vorgänger und zusätzlich wird der Zeiger auf das letzte Element in der Klasse gespeichert. So kann halt auf das letzte Element durch Referenzgleichheit verglichen werden.

MfG

[City Hunter]

Uh Razor, das hört sich ja alles so Kompliziert an ^^. Hab doch erst angefangen mit C# *lach* Nach was könnte ich so genau googlen?

[RazorX]

Wenn du nach doppelt verketteter Liste gegoogelt hast, bist du bestimmt auch über Wikipedia gestolpert wo du dir die Datenstruktur genau durchlesen kannst.

http://de.wikipedia.org/wiki/Liste_(Datenstruktur)

[City Hunter]

Hab schon was gesucht aber kriege irgend wie nur such ergebnisse für C und ich gebe aber "C# Verkettete Liste" im google

[RazorX]

Was hällt dich denn davon ab den Wikipedia Artikel zu lesen und das Wissen nach C# zu portieren? Anfängerkenntnisse hin oder her, es geht dabei ja um eine allgemeingültige Datenstruktur, die nicht sprachspezifisch ist. Wenn du es soweit schon ohne Artikel hinbekommen hast eine einfache Liste zu basteln, wirst du es mit dem Artikel doch auch schaffen es funktionsfähig zu bekommen.

Edit: Ich könnte jetzt auch einfach dir hier den Quellcode schreiben wie das ganze auszusehen hat, du hättest davon aber so ziemlich keinen Lerneffekt.

[City Hunter]

Habe das doch in Wikipedia gelesen. verstehe halt nur nicht warum ich das alles nur in C oder C++ die ergebnisse angezeigt bekomme.

[City Hunter]

Ja habe auch schon den gedanken gehabt das Ende in ein Feld noch mal zuspeichern und denn eine Methode zu schreiben was den wert übergibt.

[RazorX]

Naja C++ ist imho ein größerer Standard als C#, und so Themen wie verkettete Listen sind auch einfach älter wodurch du auch chronologisch eher auf C++ Referenzen triffst.

Wie ich weiter oben ja schon angemerkt habe wird das genauso wie du meintest gemacht. Du speicherst das Ende separat und lässt das letzte Element auf das davor zeigen, so kannst du die Zeiger des vorletzten Elementes auch manipulieren. Das erfordert allerdings auch eine Entkopplung der Datenstruktur, wodurch du einmal eine Listenklasse und eine Datenklasse hättest.

Code: Alles auswählen

public class LinkedList<T>
{
     private class Node
     {
           public T Data {get; set;}
           public Node Next {get; set;}
     }

     private Node First {get; set;}
     private Node Last{get; set;}
     public int Size {get; private set;}
     public T this[int index]
     {
          get { /* Abfrage und Exception */ }
          set { /* Element setzen */ }
     }

     public LinkedList()
     {
            First = new Node();
            Last = new Node();
            First.Next = Last;
            Last.Next = First;
     }

     public void pushBack(T data)
     {
           Node newNode = new Node();
           newNode.Data = data;
           newNode.Next = Last;
           Last.Next.Next = newNode;
           Last.Next = newNode;
           ++Size;
     }
}

Habs jetzt nicht getestet, sollte aber funktionieren.

MfG

[City Hunter]

Na denn versuche ich das mal so um zuschreiben das es auch in meiner klasse einsetz bar ist. Da ich ja neu auf den gebet bin in C# und mit C++ halt noch nicht viel gemacht habe.

[Alexander Kornrumpf]

Nur so aus Neugier: Wo wolltest du diese "Einsendeaufgabe" denn einsenden?

[City Hunter]

Eigendlich nirgend wohin. Hab das als vorlage vom Freund bekommen und nun will ich dadurch C# lernen.

[City Hunter]

So Razor, habe jetzt Listenelement listEnd; oben eingefügt und eine neue Methode.

Kumpel meint er speichert mit der Methode nur das aktuellste Objekt.

Code: Alles auswählen

Listenelement listEnd;
public void EndList()
{
       listEnd = this;
}

Habe ich da irgend wie ein Denk fehler drin? er soll mir ja immer das letzte element oder index in ein Feld speichern oder?

Ist auch das erste mal das ich mit Klassen arbeite durch das Programm.

[City Hunter]

Kennt einer ein gutes Buch mit C# lernen wo auch Verkettete Liste drin steht?

[RazorX]

So Razor, habe jetzt Listenelement listEnd; oben eingefügt und eine neue Methode.

Kumpel meint er speichert mit der Methode nur das aktuellste Objekt.

Code: Alles auswählen

Listenelement listEnd;
public void EndList()
{
       listEnd = this;
}

Habe ich da irgend wie ein Denk fehler drin? er soll mir ja immer das letzte element oder index in ein Feld speichern oder?

Ist auch das erste mal das ich mit Klassen arbeite durch das Programm.

Das wird nicht viel Sinn machen, da wenn die Methode in der Klasse Listenelement liegt das Listenende immer das jeweilige Element ist. Du brauchst dafür wie ich sagte eine Entkopplung der Daten und der Logik. Und das speichern des aktuellen Elements ist eher eine Funktionalität für Iterationen über die Liste.

[City Hunter]

Oh man ich werde das wohl nicht hin bekommen. die Verkettete Liste so zu schreiben das er nicht alles durch zählt. So schwer kann doch der müll nicht sein.

[RazorX]

Den Code den ich dir geschrieben habe und der Wikipedia Artikel sollten mehr als ausreichend sein um das Konzept zu verstehen. Ein rekursives Vorgehen macht im Sinne der Laufzeitoptimierung absolut kein Sinn (sofern halt am Ende eingefügt werden soll).

[City Hunter]

Den text in Wikipedia und den code verstehe ich ja aber irgend wie bekomme ich das halt nicht hin das das Ende noch gespeichert werden muss. da hapert es wohl bei mir.

[RazorX]

Es hapert bei dir eben weil du nur eine Klasse für eine Liste benutzt. Du brauchst zwei, eben eine die die Logik (einfügen, suchen, ...) implementiert und die andere, die die Daten (Zeiger auf nächstes Element, Daten, ...) beinhaltet. Wenn du diese Entkopplung hast kannst du zwei Elemente erstellen, den Anfang und das Ende und lässt beide auf einander zeigen. Dann beim Einfügen musst du nur noch die Zeiger manipulieren, sowohl für Einfügen am Anfang als auch am Ende wodurch das ganze zu einer konstanten Laufzeit wird O(1).

Hier einmal in Paint ein Zeigerdiagramm:

list.png (5.24 KiB) 4264 mal betrachtet

Oben sind die Daten, unten der Zeiger. Wenn du nun am Ende einfügen willst musst du nur die Zeiger umändern, so wie ich es schon im Code gezeigt habe.

[City Hunter]

Ok vielen dank für die zeichnung.