|
Einsendung:
Lösung mit vielen Extras
Ich habe mir gerade mal die Lektion "Der Freispeicher" durchgelesen (als eine der ersten Lektionen; ich hatte allerdings schon etwas Vorwissen...). Ich habe versucht, die Klasse StackAsVector so zu ändern, daß man keine feste Größe für den Stack angeben muß, sondern daß er sich dynamisch vergrößert. Es ist also mehr oder weniger ein dynamisches Array geworden, da ich auch noch einige Funktionen hinzugefügt habe. Meine Lösung funktioniert wirklich (!), sogar recht schnell ;-).
#include <iostream.h>
#include <assert.h>
class StackAsVector
{
private:
int *data;
int topIndex;
int max;
static const int ERHOEHEN_UM = 10; // um wieviel soll das Array
// vergrößert werden, wenn es voll ist ?
public:
StackAsVector(int startgroesse) // Konstruktor
{
max= startgroesse;
data = new int[max];
topIndex = -1;
};
~StackAsVector() // Destruktor
{
delete [] data;
};
void push(int wert) // ein Element oben drauflegen
{
// Prüfen, ob die Obergrenze erreicht wurde
topIndex++;
if(topIndex == max)
{
// wenn ja, dann alte Daten zwischenspeichern
int *tmp = data;
// Obergrenze um ERHOEHEN_UM erhöhen
max += ERHOEHEN_UM;
// neues, um ERHOEHEN_UM größeres Array anlegen
data = new int[max];
// alte Daten ins größere Array einlesen
int i;
for(i=0; i<topIndex; i++)
data[i] = tmp[i];
// alte Daten löschen
delete [] tmp;
}
data[topIndex] = wert;
};
int top() // das oberste Element lesen
{
assert(topIndex != -1);
return data[topIndex];
};
void pop() // das oberste Element entfernen
{
assert(topIndex != -1);
topIndex--;
};
bool isEmpty() // ist der Stack leer ?
{
return topIndex == -1;
};
void empty() // Stack leeren
{
delete [] data;
topIndex = -1;
max = ERHOEHEN_UM;
data = new int[max];
};
int size() // wie viele Elemente liegen auf dem Stack ?
{
return topIndex+1;
};
int elementAt(int nr) // Element an einer bestimmten Stelle zurückgeben
{
assert(nr <= topIndex);
return data[nr];
};
void setElementAt(int nr, int wert)
{
if(nr > topIndex)
{
// wenn ja, dann alte Daten zwischenspeichern
int *tmp = data;
max = nr + ERHOEHEN_UM;
// neues, größeres Array anlegen
data = new int[max];
// alte Daten ins größere Array einlesen
int i;
for(i=0; i<=topIndex; i++)
data[i] = tmp[i];
// alte Daten löschen
delete [] tmp;
}
data[nr] = wert;
topIndex = nr;
};
void remove(int nr) // Element an einer bestimmten Stelle löschen
{
assert(nr <= topIndex);
// Daten ohne das zu löschende Element zwischenspeichern
int tmp[topIndex];
int i;
for(i=0; i<nr; i++)
tmp[i]=data[i];
for(i=nr+1; i<=topIndex; i++)
tmp[i-1] = data[i];
// ein Element wurde gelöscht
topIndex--;
// Das alte Array löschen
delete [] data;
// neues Array anlegen, das um ERHOEHEN_UM größer ist als benötigt
max = topIndex + ERHOEHEN_UM;
data = new int[max];
// neue Daten einlesen
for(i=0; i<=topIndex; i++)
data[i] = tmp[i];
};
};
void printDaten(StackAsVector& stack, int anfang, int ende)
{
cout << "Inhalt des Stacks von " << anfang << " bis " << ende-1 << ": ";
for(int i=anfang; i<ende; i++)
cout << stack.elementAt(i) << ", ";
cout << endl;
};
void main()
{
StackAsVector stack(5);
int i;
for(i=0; i<9; i++)
stack.push(i*3);
printDaten(stack, 0, stack.size());
stack.empty();
for(i=0; i<20; i++)
stack.push(i*i);
printDaten(stack, 0, stack.size());
cout << endl << "Element an der Stelle 15: " << stack.elementAt(15) <<
", Groesse des Stacks: " << stack.size() << endl;
stack.remove(15);
cout << "Neues Element an der Stelle 15: "<< stack.elementAt(15) <<
", Groesse des Stacks: " << stack.size() << endl;
cout << "letztes Element: " << stack.top() << endl;
printDaten(stack, 0, stack.size());
for(i=0; i<2000; i++)
stack.push(i);
cout << "neue Groesse des Stacks: " << stack.size() << endl;
printDaten(stack, 0, 40);
stack.setElementAt(4000, 87);
cout << "Element bei Stelle 4000: " << stack.elementAt(4000) << endl;
cout << "Groesse: " << stack.size() << endl;
printDaten(stack, 10, 60);
}; |
Verbesserungsvorschläge ?
Umnennen in DynamicVector, denn die Methoden
int elementAt(int nr)
void setElementAt(int nr, int wert)
void remove(int nr) |
machen die Klasse zu einem Vector, der zufällig noch die Methoden
void push(int wert)
int top()
void pop() |
hat. Einfügen der Methode
die in push() und setElementAt() gegebenenfalls aufgerufen wird.
Einfügen einer Methode
die den Stack leert.
Sonst habe ich keine Änderungen vorzuschlagen. Ihr Code ist wunderschön einfach zu lesen. Das ist gut.
Noch eine Anmerkung an alle, die eine Fehlermeldung der Art
==> error C2258: Ungueltige Syntax fuer rein virtuelle Methode; '= 0' erforderlich
erhalten. Die Zeile
static const int ERHOEHEN_UM = 10;
wird noch nicht von allen Compilern verstanden. Falls Ihr Compiler diese Syntax versteht, dann verwenden Sie diese auch. Falls nicht, dann können Sie sich damit behelfen, daß Sie diese Zeile aus der Klasse herausnehmen.
Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann
schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern.
[aktuelle Version]
[inhalt]
[index]
[Fehlerkorrektur, Verbesserungsvorschlag]
© Volkard Henkel <volkard@normannia.de>,
last update: 08/25/00
|
|