Vererbung

[brotbernd]

Felixxx schrieb:

Nochmal die Frage : Wieso macht das wenig Sinn?

Es macht keinen Sinn nur für das Markieren des Endes einer Liste virtuelle Knoten zu benutzen.
Und generell macht es keinen Sinn (ausser zu Übungszwecken) Dinge zu schrieben, die schon zig mal und sogar in der Standardbiblothek implemetiert sind. Ein Bäumchen findest du in std::set (normalerweise als Rot-Schwarz-Baum implementiert).

[Felixxx]

brotbernd schrieb:

Felixxx schrieb:

Nochmal die Frage : Wieso macht das wenig Sinn?

Es macht keinen Sinn nur für das Markieren des Endes einer Liste virtuelle Knoten zu benutzen.
Und generell macht es keinen Sinn (ausser zu Übungszwecken) Dinge zu schrieben, die schon zig mal und sogar in der Standardbiblothek implemetiert sind. Ein Bäumchen findest du in std::set (normalerweise als Rot-Schwarz-Baum implementiert).

Ich finde, dass es nur logisch ist, Knoten zu benutzen, da man die Daten nicht direkt in einer beispielsweise Warteschlange speichert, sondern sie trennt und als Verwaltung dieser Daten Knoten benutzt. Der Abschluss dient dann dazu, das ganze schön rekursiv durchlaufen zu lassen, ohne dass man jedes mal überprüfen muss, ob man denn schon am Ende der Liste ( Nachfolger == NULL) angekommen ist.

[brotbernd]

Natürlich brauhct man Knoten, aber nicht mit virtuellen Methoden.
Schau dir das mal an std::cout << sizeof(Knoten); Das gibt 12 aus. Sparst du Dir die virtuelle Methode, kannst du in jedem Knoten ein ganzen Zeiger mehr speichern. Das macht dann einiges einfacher. Außerdem sparst du den Aufruf einer virtuellen Funktion. Und deine Rekursion ist ja sowieso der Wahnsinn. Du musst ja die ganze Liste durchrattern um hinten eins ranzuhängen.

Mal was ganz simples:

template<typename T>
class Liste
{
    struct Knoten
    {
        typedef T ValueType;
        Knoten* prev, * next;
        T val;
        Knoten() : prev(nullptr), next(nullptr)
        {}
        ~Knoten()
        {
            delete prev;
        }
    };
    Knoten ende; // prev = last, next = first

public:
    void Add(const T& val)
    {
        Knoten* k = new Knoten;
        k->val = val;
        if (ende.prev)
            ende.prev->next = k;
        else
            ende.next = k;  // first
        k->prev = ende.prev;
        ende.prev = k; // new last
    }
};

[Felixxx]

Naja, das mit abstrakter Oberklasse war um ein Kompositum zu haben.
Anders gehts nicht, es sei denn man gibt der Liste eine Variable "Ende" oder was auch immer. Aber das wollte der Lehrer nicht so haben.

Dein Bsp. verstehe ich nicht so ganz, was ist "last", als was ist das definiert ? last.prev-> next ?

[brotbernd]

oh sorry, da ist was durcheinander gekommen. Ich hab das mal korrigiert.

[Felixxx]

Okay, aber ich steig immer noch nicht ganz durch ^^

Also :
Knoten* k = new Knoten;

Klar, neuer Knoten wird erzeugt.

k->val = val;

Auch klar, der neue Knoten soll die entsprechenden Daten enthalten.

if (ende.prev)
ende.prev->next = k;

Wenn der Endknoten einen Vorgänger hat, soll dieser Vorgänger den neuen Knoten als Nachfolger haben. Der neue Knotenw wird also vor Knoten eingefügt. Müsste hier nicht noch der neue Knoten als Nachfolger ende bekommen ?

else
ende.next = k; // first

Wenn ende KEIN Vorgänger hat, wird der neue Knoten zum Nachfolger von Ende. Hmmm ?

k->prev = ende.prev;
ende.prev = k; // new last

o.0 HIer steigt ich ganz aus, in Fall 1 ( ende hat ein Vorgänger) bekommt der neue Knoten als Vorgänger den Vorgänger von Knoten. Okay, verständlich, der neue Knoten soll vor dem Vorgänger eingefügt werden, hat nun als Vorgänger den ehemaligen Vorgänger, der wiederrum als Nachfolger den neuen Knoten hat. Dann wird noch der Vorgänger von Ende als der neue Knoten bestimmt, macht auch Sinn.
Aber im Fall else ( Ende hat keinen Vorgänger) wird der Vorgänger von dem neuen Knoten zu null, wirft das nicht eine Nullpointerexception ?

Wenn ich das richtig durchdenke, erzeugst du hier ein Art Kreis ? Danach siehts in der else-Verzeigung aus.

[brotbernd]

Vielelicht verstehst du es besser, wenn du dir nochmal den Kommentar hier ansihest

Knoten ende; // prev = last, next = first

Für den Knoten ende missbrauche ich die beiden Zeiger als anfang und ende der ganzen Liste. Der letzte Knoten muss nicht unbedingt auf ende zeigen, der zeigt einfach auf nullptr , das ist halt das Zeichen für das Ende.
Das ist einfach nur eine sehr simple, minimale Lösung. Kannste mit einer einfach verlinkten Liste genauso oder ähnlich machen. Allerdings nicht ohne Anfang und Ende zu markieren. Wenn man sich nur den Anfang merkt muss man halt durchrattern um hinten was anzuhängen. Aber dann ohne Rekursion und virtuelle Funktionen.

[Felixxx]

brotbernd schrieb:

Vielelicht verstehst du es besser, wenn du dir nochmal den Kommentar hier ansihest

Knoten ende; // prev = last, next = first

Für den Knoten ende missbrauche ich die beiden Zeiger als anfang und ende der ganzen Liste. Der letzte Knoten muss nicht unbedingt auf ende zeigen, der zeigt einfach auf nullptr , das ist halt das Zeichen für das Ende.
Das ist einfach nur eine sehr simple, minimale Lösung. Kannste mit einer einfach verlinkten Liste genauso oder ähnlich machen. Allerdings nicht ohne Anfang und Ende zu markieren. Wenn man sich nur den Anfang merkt muss man halt durchrattern um hinten was anzuhängen. Aber dann ohne Rekursion und virtuelle Funktionen.

Okay, verstanden.
Das mit den virtuellen Funktionen leuchtet ein, aber wieso ohne Rekursion ? Die entsprechende while-Schleife dazu schaut grottig aus, vor allem wenn andere Funktionen als Add hinzukommen. Was spricht gegen Rekursion ? Der erhöhte Speicherbedarf?

[brotbernd]

Wieso denn grottig? Die normale iteration ist doch viel simpler und natürlich dazu noch effizienter.

template<typename T>
class Liste
{
    struct Knoten
    {
        typedef T ValueType;
        Knoten* next;
        T val;
        Knoten() : next(nullptr)
        {}
        ~Knoten()
        {
            delete next;
        }
    };
    Knoten anfang;

public:
    void Add(const T& val)
    {
		Knoten* k = &anfang;
		for(; k->next; k = k->next);
        k->next = new Knoten;
		k->next->val = val;
    }
};

[Felixxx]

Okay, bei einer doppelt verketteten Liste, d.h die einzelnen Elemente wissen sowohl über Vorgänger als auch Nachfolger "bescheid" hält sich das in Grenzen.
Mit nur Nachfolger nicht, wenn man zum Beispiel eine Funktion " EinfuegenVor(T Daten) implementieren will. Dann muss man erst alle Knoten mit dem Datenelement vergleichen und das vor dem Knoten einfuegen umständlich lösen.

[brotbernd]

Für solche Spielereien bietet sich dann das Iteratorkonzept an. Etwa so (is jetzt nur auf die schnelle...aber sollte laufen)

template<typename T>
class Liste
{
    struct Knoten
    {
        typedef T ValueType;
        Knoten* next;
        T val;
        Knoten() : next(nullptr)
        {}
        ~Knoten()
        {
            delete next;
        }
    };

	class ListIterator
	{
	public:
		typedef ListIterator MyIter;
		typedef typename Knoten::ValueType ValueType;
		typedef ValueType& Reference;

		ListIterator(Knoten* n) : node_(n)
		{}
		Reference operator*()
		{
			CheckRange();
			return node_->val;
		}
		MyIter& operator++()
		{
			CheckRange();
			node_ = node_->next;
			return *this;
		}
		bool operator==(const MyIter& rh)
		{
			return node_ == rh.node_;
		}
		bool operator!=(const MyIter& rh)
		{
			return !(*this == rh);
		}
		void CheckRange()
		{
			if(!node_)
				throw std::out_of_range("list iterator out of range");
		}
		Knoten* node_;
	};

    Knoten anfang;

public:
	typedef ListIterator Iterator;

    void Add(const T& val)
    {
		Knoten* k = &anfang;
		for(; k->next; k = k->next);
        k->next = new Knoten;
		k->next->val = val;
    }

	Iterator Find(const T& search)
	{
		Iterator i = Begin();
		for(Iterator e = End(); i != e && *i != search; ++i);	
		return i;
	}

	void Add(Iterator position, const T& val)
	{
		Knoten* next = position.node_->next;
		position.node_->next = new Knoten;
		position.node_->next->val = val;
		position.node_->next->next = next;
	}

	Iterator Begin()
	{
		return Iterator(anfang.next);
	}

	Iterator End()
	{
		return Iterator(nullptr);
	}
}; 
int main(int argc, char* argv[])
{
	Liste<int> l;
	l.Add(1);
	l.Add(2);
	l.Add(3);
	Liste<int>::Iterator pos = l.Find(2);
	l.Add(pos, 999);
	for(Liste<int>::Iterator i = l.Begin(), e = l.End();
		i != e; ++i)
	{
		std::cout << *i << "\n";
	}
	return 0;
}