spezielle Listenfunktionen für eine generische Liste



  • Hallo,

    ich stehe gerade vor folgendem Problem.

    Ich will eine generische (typenunabhängige) Liste implementieren von der ich dann spezielle Sachen (z.B. Liste mit Zahlen, Strings, etc.) ableiten kann.

    Soweit so gut. Ich habe also eine Klasse "List" und eine Klasse "ListNode" erstellt, welche die generischen Funktionen bereitstellen. In der Klasse "List" sind also Funktionen enthalten zum Anhängen eines Knoten (append, prepend). Weiterhin enthält die Klasse einen Zeiger auf den ersten sowie auf den letzten Listenknoten. Die Klasse "ListNode" enthält einen Zeiger aufs nächste sowie aufs vorherige Listenelement. Das funktioniert bisher alles super und dient als Grundlage.

    Nun will ich eine Liste mit String Elementen erstellen. Dazu leite ich von der Klasse "ListNode" eine Klasse "StringListNode" ab in der ein Zeiger auf das Stringobjekt sowie die Ausgabefunktion "print" implementiert ist. Weiterhin leite ich von der Klasse "List" eine Klasse "StringList" ab, in der nun eine Funktion zum sortierten einfügen und zum suchen implementiert werden soll und genau dort liegt mein Problem.

    Ich erstelle beim Aufruf ein Objekt von "StringList" und füge dort nun Objekte von "StringListNode" ein. Das funktioniert auch noch. Wenn ich aber nun in der Klasse "StringList" alle Elemente durchlaufen will stoße ich auf ein Problem. Ich durchlaufe die Liste mir folgendem Code:

    ListNode* n = getFirst();
    while(n != NULL)
    {		
    	n = n->getNext();
    }
    

    Dadurch, dass das Objekt n vom Typ ListNode ist, kann ich nicht auf die Funktionen in StringListNode zugreifen. Wenn ich das Objekt n vom Typ "StringListNode" erstelle kann ich die Funktion getNext etc. nicht verwenden, da diese ein Objekt vom Typ ListNode zurückliefert. Ich könnte hier mit einem Cast das ganze Problem lösen was auch funktioniert aber das ist sicher nicht die eleganteste bzw. nicht die ObjekOrientierteste Lösung.

    Ist sicher eine lange Beschreibung für ein kleines Problem. Ich probiere hier schon einige Zeit dran rum aber komme einfach auf keine vernünftige Lösung.

    Ich darf/will übrigens keine STL benutzen! Aus dem Grund findet man im Netz auch eher wenige Beispiele/Lösungen zu dem Problem. Selbst mein C++ Buch reißt das Kapitel nur grob an und geht nicht ins Detail (sortiert Einfügen, etc.).

    Bin für jeden Hinweis/Ratschlag/Tipp und alles in die Richtung dankbar.

    Gruß, Tim



  • in C++ löst man das mit Templates

    ansonsten:
    ListNode definiert das Interface und alle konkreten Nodes müssen dieses Implementieren.

    dh ListNode hat eine virtuelle methode next() welches eben die nächste Node liefert... Dabei sollte für die Klasse egal sein, welches konkrete Node es gerade hat.

    Da Templates aber die beste Lösung sind, will ich hier nicht ins Detail gehen (frag nach, falls Templates nicht in Frage kommen)



  • Hallo,

    erstmal danke für die schnelle Antwort. Templates sollten wir nicht unbedingt verwenden (es geht übrigens um eine Belegaufgabe für die Uni).

    Die Liste durchlaufen funktioniert ja soweit auch ohne Probleme bzw. unabhängig was die Listenknoten eigentlich enthalten.

    Da aber StringListNode von ListNode abgeleitet ist, liefert getNext() nur einen ListNode* Pointer zurück.

    ListNode* n = getFirst();
    while(n != NULL)
    {       
        n = n->getNext();
    }
    

    In dieser Schleife kann ich aber nur auf Methoden in n zugreifen welche in ListNode implementiert sind. Diese Schleife führe ich aber in StringList aus welche List abgeleitet ist. Wenn ich jetzt folgendes schreibe meckert der Compiler mit folgender Meldung (invalid conversion from `ListNode*' to `StringListNode*').

    StringListNode* n = getFirst();
    while(n != NULL)
    {       
        n = n->getNext();
    }
    

    Da ich aber in der Schleife auf Methoden aus StringListNode zugreifen muss habe ich das Problem. Mit einem Cast ist das alles wie beschrieben kein Problem aber sowas ist halt nicht wirklich schön wie ich finde.

    Was mir spontan dazu einfällt ist, wenn ich in List eine virtuelle Funktion compare oder so einfüge welche dann von StringList überschrieben wird und über die ich dann in der Schleife Zugriff drauf habe. Es geht hier speziell um die Funktionen Suchen in der Liste und sortiert Einfügen.

    Gruß, Tim



  • Hi,

    nach einer Nacht mit vielen Überlegungen bin ich immernoch nicht weitergekommen. Ich denke mal in meinem Fall kommt man um ein Cast nicht herrum.

    Unser Prof. meinte, dass wir eine abstrakte Klasse "Entry" einfügen können, welche dann den eigentlichen Inhalt des Knotens abbildet. Im ListNode existiert dann also ein Zeiger auf Entry. Von Entry kann man dann z.B. StringEntry ableiten. Allerdings stößt man dort auch wieder auf das selbe Problem, wenn man spezielle Funktionen aus StringEntry nutzen will, denn in ListNode steht ja, dass es nur ein Entry Objekt ist.

    Es besteht ja in C++ noch die Möglichkeit Operatoren zu überladen. Wenn ich jetzt den Vergleichsoperator "==" irgendwie so modifizieren kann, dass ich 2 Entry's vergleichen kann, würde das sicher schon weiterhelfen oder? Kann man beim ableiten den Operator auch nocheinmal überschreiben? Also wenn ich in Entry den Operator "==" als virtual deklariere und erst in StringEntry implementiere und beim ableiten überschreibe? Hier sehe ich momentan die einzigste Möglichkeit das Problem ohne einen Cast zu lösen.

    Gruß, Tim


Log in to reply