000
03.03.2006, 16:10 Uhr
ref
|
Die eingabe 15,3,8,0
Die ausgabe :
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
die Frage: warum soll myValue anderes als theOtherData.myValue sein, warum nicht gleich?
nehmen wir die zweite for( ; ; ) schleife runde
myValue=15 , theOtherData.myValue =3
hier
| C++: |
int Data::Compare(const Data & theOtherData)
{
if (myValue < theOtherData.myValue)
return kIsSmaller;
if (myValue > theOtherData.myValue)
return kIsLarger;
else
return kIsSame;
}
|
myValue hat sein wert von Data-konstruktor bekommen also hier:
| C++: |
class Data
{
public:
Data(int val):myValue(val){}
~Data(){}
int Compare(const Data &);
void Show() { std::cout << myValue << std::endl; }
private:
int myValue;
};
|
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) |
