In dem Programm für den Rückblick auf die zweiten Woche sind viele der Techniken vereint, die Sie im Laufe der letzten 14 Tage kennengelernt haben - entsprechend leistungsstark ist das Programm.
Das Programm demonstriert die Implementierung verketteter Listen und verwendet dazu virtuelle Funktionen, abstrakte Funktionen, überschriebene Funktionen, Polymorphie, öffentliche Vererbung, überladene Funktionen, Endlosschleifen, Zeiger, Referenzen und vieles mehr. Beachten Sie, daß diese verkettete Liste sich von der vorher vorgestellten unterscheidet. In C++ führen viele Wege nach Rom.
Das Ziel dieses Programms ist die Erstellung einer verketteten Liste. Die Knoten der Liste sind so konzipiert, daß man in ihnen Teile (Parts), wie sie in einer Fabrik vorkommen könnten, speichern kann. Obwohl dieses Programm noch keine endgültige Fassung darstellt, veranschaulicht es die anspruchsvolle Datenstruktur bereits recht gut. Der Code hat einen Umfang von 311 Zeilen. Versuchen Sie, den Code erst einmal selbst durchzugehen, bevor sie die Analyse im Anschluß an die Ausgabe lesen.
Listing R2.1 Rückblick auf die zweite Woche
1: // ******************************************
2: //
3: // Titel: Rueckblick auf die zweite Woche
4: //
5: // Datei: Week2
6: //
7: // Beschreibung: Demonstrationsprogramm zu verketteten Listen
8: //
9: // Klassen: PART - enthaelt die Teilenummern und eventuell andere
10: // Informationen ueber die Teile
11: //
12: // PartNode - fungiert als Knoten in einer PartsList
13: //
14: // PartsList - stellt die Mechanismen fuer eine
15: // verkettete Liste von Teilen bereit
16: //
17: // **************************************************
18:
19: #include <iostream.h>
20:
21:
22:
23: // **************** Teile ************
24:
25: // Abstrakte Basisklasse fuer die Teile
26: class Part
27: {
28: public:
29: Part():itsPartNumber(1) {}
30: Part(int PartNumber):itsPartNumber(PartNumber){}
31: virtual ~Part(){};
32: int GetPartNumber() const { return itsPartNumber; }
33: virtual void Display() const =0; // muss ueberschrieben werden
34: private:
35: int itsPartNumber;
36: };
37:
38: // Implementierung einer abstrakten Funktion, damit
39: // abgeleitete Klassen die Funktion ueberschreiben
40: void Part::Display() const
41: {
42: cout << "\nTeilenummer: " << itsPartNumber << endl;
43: }
44:
45: // **************** Autoteile ************
46:
47: class CarPart : public Part
48: {
49: public:
50: CarPart():itsModelYear(94){}
51: CarPart(int year, int partNumber);
52: virtual void Display() const
53: {
54: Part::Display(); cout << "Baujahr: ";
55: cout << itsModelYear << endl;
56: }
57: private:
58: int itsModelYear;
59: };
60:
61: CarPart::CarPart(int year, int partNumber):
62: itsModelYear(year),
63: Part(partNumber)
64: {}
65:
66:
67: // **************** Flugzeugteile ************
68:
69: class AirPlanePart : public Part
70: {
71: public:
72: AirPlanePart():itsEngineNumber(1){};
73: AirPlanePart(int EngineNumber, int PartNumber);
74: virtual void Display() const
75: {
76: Part::Display(); cout << "Motor-Nr.: ";
77: cout << itsEngineNumber << endl;
78: }
79: private:
80: int itsEngineNumber;
81: };
82:
83: AirPlanePart::AirPlanePart(int EngineNumber, int PartNumber):
84: itsEngineNumber(EngineNumber),
85: Part(PartNumber)
86: {}
87:
88: // **************** Teile-Knoten ************
89: class PartNode
90: {
91: public:
92: PartNode (Part*);
93: ~PartNode();
94: void SetNext(PartNode * node) { itsNext = node; }
95: PartNode * GetNext() const;
96: Part * GetPart() const;
97: private:
98: Part *itsPart;
99: PartNode * itsNext;
100: };
101:
102: // Implementierungen von PartNode ...
103:
104: PartNode::PartNode(Part* pPart):
105: itsPart(pPart),
106: itsNext(0)
107: {}
108:
109: PartNode::~PartNode()
110: {
111: delete itsPart;
112: itsPart = 0;
113: delete itsNext;
114: itsNext = 0;
115: }
116:
117: // Liefert NULL zurueck, wenn kein naechster PartNode vorhanden
118: PartNode * PartNode::GetNext() const
119: {
120: return itsNext;
121: }
122:
123: Part * PartNode::GetPart() const
124: {
125: if (itsPart)
126: return itsPart;
127: else
128: return NULL; // Fehler
129: }
130:
131: // **************** Teileliste ************
132: class PartsList
133: {
134: public:
135: PartsList();
136: ~PartsList();
137: // benötigt Kopierkonstruktor und Zuweisungsoperator!
138: Part* Find(int & position, int PartNumber) const;
139: int GetCount() const { return itsCount; }
140: Part* GetFirst() const;
141: static PartsList& GetGlobalPartsList()
142: {
143: return GlobalPartsList;
144: }
145: void Insert(Part *);
146: void Iterate(void (Part::*f)()const) const;
147: Part* operator[](int) const;
148: private:
149: PartNode * pHead;
150: int itsCount;
151: static PartsList GlobalPartsList;
152: };
153:
154: PartsList PartsList::GlobalPartsList;
155:
156: // Implementierungen fuer Liste...
157:
158: PartsList::PartsList():
159: pHead(0),
160: itsCount(0)
161: {}
162:
163: PartsList::~PartsList()
164: {
165: delete pHead;
166: }
167:
168: Part* PartsList::GetFirst() const
169: {
170: if (pHead)
171: return pHead->GetPart();
172: else
173: return NULL; // Fehler auffangen
174: }
175:
176: Part * PartsList::operator[](int offSet) const
177: {
178: PartNode* pNode = pHead;
179:
180: if (!pHead)
181: return NULL; // Fehler auffangen
182:
183: if (offSet > itsCount)
184: return NULL; // error
185:
186: for (int i=0;i<offSet; i++)
187: pNode = pNode->GetNext();
188:
189: return pNode->GetPart();
190: }
191:
192: Part* PartsList::Find(int & position, int PartNumber) const
193: {
194: PartNode * pNode = 0;
195: for (pNode = pHead, position = 0;
196: pNode!=NULL;
197: pNode = pNode->GetNext(), position++)
198: {
199: if (pNode->GetPart()->GetPartNumber() == PartNumber)
200: break;
201: }
202: if (pNode == NULL)
203: return NULL;
204: else
205: return pNode->GetPart();
206: }
207:
208: void PartsList::Iterate(void (Part::*func)()const) const
209: {
210: if (!pHead)
211: return;
212: PartNode* pNode = pHead;
213: do
214: (pNode->GetPart()->*func)();
215: while (pNode = pNode->GetNext());
216: }
217:
218: void PartsList::Insert(Part* pPart)
219: {
220: PartNode * pNode = new PartNode(pPart);
221: PartNode * pCurrent = pHead;
222: PartNode * pNext = 0;
223:
224: int New = pPart->GetPartNumber();
225: int Next = 0;
226: itsCount++;
227:
228: if (!pHead)
229: {
230: pHead = pNode;
231: return;
232: }
233:
234: // ist dieser kleiner als head
235: // dann ist dies der neue head
236: if (pHead->GetPart()->GetPartNumber() > New)
237: {
238: pNode->SetNext(pHead);
239: pHead = pNode;
240: return;
241: }
242:
243: for (;;)
244: {
245: // gibt es keinen naechsten Knoten, den neuen anhaengen
246: if (!pCurrent->GetNext())
247: {
248: pCurrent->SetNext(pNode);
249: return;
250: }
251:
252: // gehört der Knoten zwischen diesen und den naechsten,
253: // dann hier einfuegen, ansonsten zu naechstem Knoten
254: pNext = pCurrent->GetNext();
255: Next = pNext->GetPart()->GetPartNumber();
256: if (Next > New)
257: {
258: pCurrent->SetNext(pNode);
259: pNode->SetNext(pNext);
260: return;
261: }
262: pCurrent = pNext;
263: }
264: }
265:
266: int main()
267: {
268: PartsList&pl = PartsList::GetGlobalPartsList();
269: Part * pPart = 0;
270: int PartNumber;
271: int value;
272: int choice;
273:
274: while (1)
275: {
276: cout << "(0)Beenden (1)Auto (2)Flugzeug: ";
277: cin >> choice;
278:
279: if (!choice)
280: break;
281:
282: cout << "Neue Teilenummer?: ";
283: cin >> PartNumber;
284:
285: if (choice == 1)
286: {
287: cout << "Baujahr?: ";
288: cin >> value;
289: pPart = new CarPart(value,PartNumber);
290: }
291: else
292: {
293: cout << "Motor-Nummer?: ";
294: cin >> value;
295: pPart = new AirPlanePart(value,PartNumber);
296: }
297:
298: pl.Insert(pPart);
299: }
300: void (Part::*pFunc)()const = Part::Display;
301: pl.Iterate(pFunc);
302: return 0;
303: }
(0)Beenden (1)Auto (2)Flugzeug: 1
Neue Teilenummer?: 2837
Baujahr? 90
(0)Beenden (1)Auto (2)Flugzeug: 2
Neue Teilenummer?: 378
Motor-Nummer?: 4938
(0)Beenden (1)Auto (2)Flugzeug: 1
Neue Teilenummer?: 4499
Baujahr? 94
(0)Beenden (1)Auto (2)Flugzeug: 1
Neue Teilenummer?: 3000
Baujahr? 93
(0)Beenden (1)Auto (2)Flugzeug: 0
Teilenummer: 378
Motor-Nr.: 4938
Teilenummer: 2837
Baujahr: 90
Teilenummer: 3000
Baujahr: 93
Teilenummer: 4499
Baujahr: 94
Das Listing aus dem Rückblick auf die zweite Woche zeigt die Implementierung einer
verketteten Liste für Part-Objekte. Eine verkettete Liste ist eine dynamische Datenstruktur.
Sie ähnelt einem Array, kann jedoch in der Größe angepaßt werden, wenn
Objekte hinzugefügt oder gelöscht werden.
Die verkettete Liste aus obigem Programm soll Objekte der Klasse Part aufnehmen,
wobei Part ein abstrakter Datentyp ist, der als Basisklasse für alle Objekte mit einer
Teilenummer dient. In diesem Beispiel gibt es zu Part die Unterklassen CarPart und
AirPlanePart.
Die Klasse Part wird in den Zeilen 26 bis 36 deklariert und besteht aus einer Teilenummer
und einigen Zugriffsfunktionen. Man könnte diese Klasse weiter ausbauen,
um andere wichtige Informationen über die Teile aufzunehmen, wie zum Beispiel, in
welchen Komponenten die Teile eingebaut werden, wie viele davon auf Lager sind,
und so weiter. Part ist ein abstrakter Datentyp, denn er enthält die abstrakte Funktion
Display().
Beachten Sie, daß es für Display() in den Zeilen 40 bis 43 eine Implementierung
gibt. Der Entwickler der Klasse erzwingt damit, daß für abgeleitete Klassen eigene
Display()-Methode aufgesetzt werden müssen, und erlaubt gleichzeitig, dabei auf den
Code der bereits implementierten Funktion zurückzugreifen.
Die Zeilen 47 bis 59 und 69 bis 87 deklarieren zwei einfache abgeleitete Klassen,
CarPart und AirPlanePart. Jede verfügt über eine überschriebene Display()-Methode,
die in der Tat die Display()-Methode der Basisklasse verwenden.
Die Klasse PartNode dient als Schnittstelle zwischen der Klasse Part und der Klasse
PartList. Sie enthält einen Zeiger auf ein Part-Objekt und einen Zeiger auf den nächsten
Knoten in der Liste. Ihre Methoden haben lediglich die Aufgabe, den nächsten
Knoten in der Liste einzulesen und zu setzen und das Part-Objekt zurückzuliefern, auf
das der Knoten zeigt.
Die eigentliche Listenfunktionalität findet sich in der Klasse PartsList, deren Deklaration
in den Zeilen 132 bis 152 erfolgt. PartsList enthält einen Zeiger auf das erste
Element in der Liste (pHead) und nutzt dieses Element, um die Liste durchzugehen und
dabei auf alle anderen Knoten zuzugreifen. Das Durchgehen der Liste sieht so aus,
daß jeder Knoten in der Liste nach dem nächsten Knoten gefragt wird, bis ein Knoten
erreicht wird, dessen nächster Zeiger NULL ist.
Sie sehen hier nur eine partielle Implementierung. Eine vollständig implementierte Liste würde entweder weitreichendere Zugriffsmöglichkeiten auf ihren ersten und letzten Knoten bieten oder ein Iterator-Objekt bereitstellen, mit dem Klienten leicht die Liste durchgehen können.
PartsList verfügt nichtsdestotrotz über eine Reihe interessanter Methoden, die in alphabetischer
Reihenfolge aufgeführt sind. Dies ist durchaus empfehlenswert, da man
so die Funktionen leichter wiederfinden kann.
Find() übernimmt eine PartNumber und einen int. Wurde das Teil (Part-Objekt), das
mit PartNumber übereinstimmt, gefunden, wird ein Zeiger auf Part zurückgeliefert und
dem int-Parameter wird die Position des Teils in der Liste zugewiesen. Wurde PartNumber
nicht gefunden, wird NULL zurückgeliefert und die Position ist ohne Bedeutung.
GetCount() liefert die Anzahl der Elemente in der Liste. PartsList speichert diese Zahl
als Elementvariable itsCount, auch wenn es diese Zahl jederzeit wieder durch Abarbeiten
der Liste ermitteln könnte.
GetFirst() liefert einen Zeiger auf das erste Part-Objekt in der Liste zurück, oder
NULL, wenn die Liste leer ist.
GetGlobalPartsList() liefert eine Referenz auf die statische Elementvariable GlobalPartsList
. Dabei handelt es sich um die statische Instanz dieser Klasse. Jedes Programm
mit einer PartsList weist auch eine GlobalPartsList-Liste auf. Darüber hinaus
steht es dem Programm jedoch frei, weitere PartsList-Listen anzulegen. Eine
vollständige Implementierung dieser Idee würde den Konstruktor von Part modifizieren,
um sicherzustellen, daß jedes Teil auch in die GlobalPartsList aufgenommen
würde.
Insert() übernimmt einen Zeiger auf Part, erzeugt einen PartNode und fügt das Part-
Objekt gemäß seiner PartNumber in die Liste ein.
Iterate() übernimmt einen Zeiger auf eine Elementfunktion von Part, die keine Parameter
übernimmt, void zurückliefert und const ist. Iterate() ruft diese Funktion für
jedes Part-Objekt in der Liste auf. In dem Beispielprogramm wird die Funktion Display()
übergeben. Dabei handelt es sich um eine virtuelle Funktion, so daß die Display()
-Methode auf der Basis des Laufzeittyps des aktuellen Part-Objekts aufgerufen
wird.
Operator[] erlaubt den direkten Zugriff auf das Part-Objekt am gegebenen Offset. Es
wird eine rudimentäre Bereichsprüfung durchgeführt. Wenn die Liste NULL ist oder der
angeforderte Offset größer als die Liste, wird NULL als Fehlerwert zurückgeliefert.
Beachten Sie, daß in einem richtigen Programm diese Kommentare zu der Funktion in die Klassendeklaration geschrieben worden wären.
Das Hauptprogramm befindet sich in den Zeilen 266 bis 303. Zeile 268 deklariert
eine Referenz auf PartsList und initialisiert sie mit GlobalPartsList. Beachten Sie,
daß GlobalPartsList bereits in Zeile 154 initialisiert wurde. Dies ist notwendig, da die
Deklaration einer statischen Elementvariablen keine Definition beinhaltet. Die Definition
muß außerhalb der Deklaration einer Klasse erfolgen.
In den Zeilen 274 bis 299 wird der Anwender wiederholt aufgefordert, anzugeben, ob ein Autoteil oder ein Flugzeugteil in die Liste aufgenommen werden soll. In Abhängigkeit von der Wahl des Anwenders wird ein entsprechender Wert angefordert und das entsprechende Teil erzeugt. Nachdem das Teil erzeugt wurde, wird es in Zeile 298 in die Liste eingefügt.
Die Implementierung der Insert()-Methode von PartsList befindet sich in den Zeilen
218 bis 264. Nachdem die erste Teilenummer, 2837, eingegeben wurde, wird ein
CarPart-Objekt mit dieser Teilenummer und dem Baujahr 90 erzeugt und LinkedList::Insert()
übergeben.
Zeile 220 erzeugt einen neuen PartNode für das Teil, und die Variable New wird mit der
Teilenummer initialisiert. Zeile 226 inkrementiert die Elementvariable itsCount von
PartsList.
In Zeile 228 wird der Test, ob pHead NULL ergibt, als true ausgewertet. Da es sich um
den ersten Knoten handelt, stimmt es, daß der pHead-Zeiger von PartsList gleich Null
ist. Entsprechend wird in Zeile 230 pHead so gesetzt, daß er auf den neuen Knoten
zeigt, und die Funktion kehrt zurück.
Der Anwender wird zur Eingabe eines zweiten Teils aufgefordert und diesmal wird ein
AirPlane-Teil mit der Teilenummer 37 und der Motor-Nummer 4938 eingegeben. Es wird
erneut PartsList::Insert() aufgerufen und pNode wird mit dem neuen Knoten initialisiert.
Die statische Elementvariable itsCount wird auf 2 inkrementiert und pHead getestet.
Da pHead das letzte Mal zugewiesen wurde, ist es nicht länger Null und der Test
schlägt fehl.
Zeile 236 vergleicht die Teilenummer von pHead, 2837, mit der aktuellen Teilenummer
378. Da die neue Teilenummer kleiner ist als die von pHead, wird der neue Knotenzeiger
zum neuen Kopfzeiger und der Test in Zeile 236 ergibt true.
In Zeile 238 wird der neue Knoten so gesetzt, daß er auf den Knoten zeigt, auf den
gegenwärtig pHead weist. Beachten Sie, daß damit der neue Knoten nicht auf pHead
weist, sondern auf den Knoten, auf den pHead zeigte! In Zeile 239 wird pHead so gesetzt,
daß er auf den neuen Knoten zeigt.
Beim dritten Durchlauf durch die Schleife gibt der Anwender die Teilenummer 4499
für ein Auto (Car) des Baujahrs 94 ein. Der Zähler wird inkrementiert, und die Zahl ist
diesmal nicht kleiner als die Zahl, auf die pHead zeigte. Deshalb wird in die for-Schleife,
die in Zeile 243 beginnt, eingetreten.
Der Wert, auf den pHead zeigte, lautet 378. Der Wert, auf den der zweite Knoten zeigte,
beträgt 2837. Der aktuelle Wert liegt bei 4499. Der Zeiger pCurrent zeigt auf den
gleichen Knoten wie pHead und hat deshalb einen Folgeknoten next. pCurrent zeigt
auf den zweiten Knoten und aus diesem Grund schlägt der Test in Zeile 246 fehl.
Der Zeiger pCurrent wird auf den nächsten Knoten gesetzt und die Schleife wird noch
einmal durchlaufen. Diesmal ist der Test in Zeile 246 erfolgreich. Es gibt kein weiteres
Element. Deshalb wird der aktuellen Knoten angewiesen, auf den neuen Knoten zu
zeigen (Zeile 248) und die Einfüge-Operation ist beendet.
Beim vierten Durchlauf wird die Teilenummer 3000 eingegeben. Dabei wird wie bei
der vorigen Iteration vorgegangen. Wenn der aktuelle Knoten auf 2837 und der nächste
Knoten auf 4499 zeigt, liefert der Test in Zeile 256 true zurück und der neue Knoten
wird an seiner Position eingefügt.
Wenn der Anwender zum Schluß die 0 drückt, ergibt der Test in Zeile 279 true und
die while(1)-Schleife endet. Zeile 300 weist dem Elementfunktionszeiger pFunc die
Elementfunktion Display()zu. In einem realen Programm würde diese Zuweisung auf
der Grundlage der Benutzerauswahl dynamisch erfolgen.
Der Zeiger auf die Elementfunktion wird der Methode Iterate() von PartsList übergeben.
In Zeile 208 stellt Iterate() sicher, daß die Liste nicht leer ist. Danach wird in
den Zeilen 213 bis 215 für jedes Teil der Liste die Funktion aufgerufen, auf die der
Funktionszeiger weist - letztendlich also an die Display()-Methode des jeweiligen Teil,
wie in der Ausgabe zu sehen.
© Markt&Technik Verlag, ein Imprint der Pearson Education Deutschland GmbH