000
01.03.2006, 17:47 Uhr
ref
|
Tja habe ich keine einfache code um über Verkettete Liste zu erfahren gefunden, vielleicht
findet ein expert diese code nicht schwer aber für mich es ist ein bisschen schwer zu verfolgen.
ich bin gerade zu der stelle gekommen wo:
Node *TailNode::Insert(Data * theData)
{
InternalNode * dataNode=new InternalNode(theData, this);
return dataNode;
}
ist
und genau hier: InternalNode * dataNode=new InternalNode(theData, this);
die frage ist wohin nach diese stelle weitergehen soll??, wird hier den konstruktor von InternalNode aufgerufen
oder wird an diese stelle die funktion Insert in InternalNode aufgerufen?
der code soll die folgende ausgabe liefern:
Welcher Wert? (0 zum Beenden): 15
Welcher Wert? (0 zum Beenden): 3
Welcher Wert? (0 zum Beenden): 8
Welcher Wert? (0 zum Beenden): 0
3
8
15
und hier ist der code :
| C++: |
// ***********************************************
// Listing 19.1
//
// Demonstriert verkettete Liste
//
//
//
//
//
// Zeigt objektorientierte Lösung für verkettete Listen.
// Die Liste delegiert die eigentliche Arbeit an die Knoten
// Die Knoten sind abstrakte Datentypen. Es gibt drei
// Knotentypen: Kopfknoten, Endeknoten und interne Knoten.
// Nur die internen Knoten nehmen Daten auf.
//
// Die Klasse Data dient als Objekt, das in der
// verketteten Liste gespeichert wird.
//
// ***********************************************
#include <iostream>
enum { kIsSmaller, kIsLarger, kIsSame};
// Data-Klasse für die Speicherung in der Liste. Jede
// Klasse in dieser verketteten Liste muss zwei Methoden
// unterstützen: Show (zeigt den Wert an) und Compare
// (gibt die relative Position zurück).
class Data
{
public:
Data(int val):myValue(val){}
~Data(){}
int Compare(const Data &);
void Show() { std::cout << myValue << std::endl; }
private:
int myValue;
};
// Compare entscheidet, wohin ein bestimmtes Objekt
// in der Liste gehört.
int Data::Compare(const Data & theOtherData)
{
if (myValue < theOtherData.myValue)
return kIsSmaller;
if (myValue > theOtherData.myValue)
return kIsLarger;
else
return kIsSame;
}
// Vorwärtsdeklarationen
class Node;
class HeadNode;
class TailNode;
class InternalNode;
// ADT, der das Knotenobjekt in der Liste darstellt. Alle
// abgeleiteten Klassen müssen Insert und Show redefinieren.
class Node
{
public:
Node(){}
virtual ~Node(){}
virtual Node * Insert(Data * theData)=0;
virtual void Show() = 0;
private:
};
// Dieser Knoten nimmt das eigentliche Objekt auf.
// Hier hat das Objekt den Typ Data.
// Bei der Behandlung von Templates wird eine
// Verallgemeinerung vorgestellt.
class InternalNode: public Node
{
public:
InternalNode(Data * theData, Node * next);
virtual ~InternalNode(){ delete myNext; delete myData; }
virtual Node * Insert(Data * theData);
virtual void Show()
{ myData->Show(); myNext->Show(); } // delegieren!
private:
Data * myData; // die eigentlichen Daten
Node * myNext; // zeigt auf nächsten Knoten in der verketteten Liste
};
// Der Konstruktor führt nur Initialisierungen aus.
InternalNode::InternalNode(Data * theData, Node * next):
myData(theData),myNext(next)
{
}
// Der Kern der Listenkonstruktion. Stellt man ein
// neues Objekt in die Liste, wird es an den Knoten
// weitergereicht, der ermittelt, wohin das Objekt
// gehört, und es in die Liste einfügt.
Node * InternalNode::Insert(Data * theData)
{
// Ist das neue Objekt größer oder kleiner als ich?
int result = myData->Compare(*theData);
switch(result)
{
// Ist das neue Objekt gleich groß, kommt es per Konvention vor das aktuelle.
case kIsSame: // zum nächsten case-Zweig "durchfallen"
case kIsLarger: // neue Daten vor mir einordnen
{
InternalNode * dataNode =
new InternalNode(theData, this);
return dataNode;
}
// Größer als ich, also an den nächsten Knoten
// weiterreichen. ER soll sich darum kümmern.
case kIsSmaller:
myNext = myNext->Insert(theData);
return this;
}
return this; // Tribut an Compiler
}
// Endeknoten ist einfach eine Markierung
class TailNode : public Node
{
public:
TailNode(){}
virtual ~TailNode(){}
virtual Node * Insert(Data * theData);
virtual void Show() { }
private:
};
// Wenn Daten zu mir kommen, müssen sie vor mir eingefügt werden,
// da ich der Endeknoten bin und NICHTS nach mir kommt.
Node * TailNode::Insert(Data * theData)
{
InternalNode * dataNode = new InternalNode(theData, this);
return dataNode;
}
// Kopfknoten hat keine Daten, sondern zeigt einfach
// auf den Beginn der Liste.
class HeadNode : public Node
{
public:
HeadNode();
virtual ~HeadNode() { delete myNext; }
virtual Node * Insert(Data * theData);
virtual void Show() { myNext->Show(); }
private:
Node * myNext;
};
// Nach Erzeugen des Kopfknotens erzeugt dieser
// sofort den Endeknoten.
HeadNode::HeadNode()
{
myNext = new TailNode;
}
// Vor dem Kopf kommt nichts, also die Daten einfach
// an den nächsten Knoten weiterreichen
Node * HeadNode::Insert(Data * theData)
{
myNext = myNext->Insert(theData);
return this;
}
// Ich stehe im Mittelpunkt, mache aber gar nichts.
class LinkedList
{
public:
LinkedList();
~LinkedList() { delete myHead; }
void Insert(Data * theData);
void ShowAll() { myHead->Show(); }
private:
HeadNode * myHead;
};
// Bei Geburt erzeuge ich den Kopfknoten.
// Er erzeugt den Endeknoten.
// Eine leere Liste zeigt damit auf den Kopf, dieser
// zeigt auf das Ende, dazwischen ist nichts.
LinkedList::LinkedList()
{
myHead = new HeadNode;
}
// Delegieren, delegieren, delegieren
void LinkedList::Insert(Data * pData)
{
myHead->Insert(pData);
}
// Rahmenprogramm zum Testen
int main()
{
Data * pData;
int val;
LinkedList ll;
// Benutzer zum Erzeugen von Werten auffordern.
// Diese Werte in die Liste stellen.
for (;;)
{
std::cout << "Welcher Wert? (0 zum Beenden): ";
std::cin >> val;
if (!val)
break;
pData = new Data(val);
ll.Insert(pData);
}
// Jetzt Liste durchlaufen und Daten anzeigen.
ll.ShowAll();
return 0; // ll verliert Gültigkeitsbereich und wird abgebaut!
}
|
--
Man kann ein Problem nicht mit der gleichen Denkweise lösen, mit der es erschaffen wurde. (Albert Einstein) |
