I
interessant - d.h., dass Start- und Endknoten von unterschiedlichem Typ sind. Ich unterstelle mal, dass der Endknoten keinen Data*-Pointer hat. Aber man kann trotzdem auf ihm z.B. insert aufrufen. Was soll dann passieren?
Sein insert liefert einfach false zurück, und weist somit den Knoten davor an, die Daten hinter sich zu plazieren, somit werden neue Daten immer bis zum Ende durchgereicht und hinter das letzte Element - also vor Endnode angebracht.
Aber bevor ich weiter spekuliere - der Member next eines Knotens zeigt doch auf den Nachfolger des Knotens. Wo wird dann nach einem insert der neue Knoten eingefügt?
Ganz einfach: Die Liste hat eine Methode insert und die Addresse des Startknotens gespeichert, welchem sie in ihrem Konstruktor erstellt - genauso wie den Endknoten, dessen Addresse beim Erstellen der Liste in _next vom Startknoten gespeichert werden. Am Anfang speichert also die Liste die Addy des Startknotens, welcher als Nachfolger den Endknoten hat - eine leere Liste. Auch die Liste hat natürlich eine Methode insert, welche wie gesagt vom Startknoten ausgehend die Daten bis zum Ende durchreicht. Hier mal ein wenig mehr Code, vllt wird es dir dann klarer, wie ich mir das gedacht hab.
bool Node::insert(const Data& dat)
{
/*if (*_data < dat) //if the current element is smaller then the given one, the function returns false
return false; //which means that the element has to be put between this and the last Node
if (!_next->insert(dat)) //which is done here -> if insert is false for the current node, the element
_next = new Node(dat, _next); // is smaller then the next one but bigger or equal this one
// tho it is inserted as the new one relatively to the current node
// or as the one before relatively to the next node
//(which has returned false)
return true;*/
if (!_next->insert(dat)) //if insert returns false for the next node (can only happen if next node is
_next = new Node(dat, _next/*, _position+1*/); // end node, because Node::insert always returns true) insert is
return true; //called for the next node -> all nodes are added directly before the end node
}
Node::Node(const Data& dat, bNode* next/*, int pos*/)
: _data(new Data(dat)), _next(next)//, _position(pos)
{
}
class List
{
Startnode* _start;
public:
List();
List(const List&);
~List();
const List& operator=(const List&);
void insert(const Data&);
void print() const;
};
List::List()
: _start(new Startnode(new Endnode))
{
}
void List::insert(const Data& dat)
{
_start->insert(dat);
}
class Startnode : public bNode
{
bNode* _next;
public:
Startnode(bNode*);
Startnode(const Startnode&);
~Startnode();
const Startnode& operator=(const Startnode&);
bool insert(const Data&);
void print() const {_next->print();}
};
Startnode::Startnode(bNode* next)
: _next(next)
{
}
bool Startnode::insert(const Data& dat)
{
if (!_next->insert(dat))
_next = new Node(dat, _next);
return true;
}
class Endnode : public bNode
{
public:
~Endnode() {std::cout << "Destructor of class Endnode\n";}
bool insert(const Data& dat) {return false;}
void print() const {}
};
Sry, wenns zuviel Code ist :x
das kannst Du ja gerne tun, aber warum nicht mit Hilfe von Iteratoren. Auch das ist eine prima Übung.
Gut, ok, das wäre dann mein nächster Schritt.