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, 040);

   stack.setElementAt(400087);
   cout << "Element bei Stelle 4000: " << stack.elementAt(4000) << endl;
   cout << "Groesse: " << stack.size() << endl;

   printDaten(stack, 1060);
};

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

   void grow(int newSize)

die in push() und setElementAt() gegebenenfalls aufgerufen wird.

Einfügen einer Methode

      void flush()

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