Lektion 65:

Die Klasse Set

Um einen Zuweisungsoperator, einen Copy-Konstruktor und einen Destruktor brauchen wir uns in der Klasse Set nicht mehr zu kümmern. Das alles wird vom Compiler automatisch gemacht. Zum Beispiel funktioniert der vom Compiler automatisch generierte Zuweisungsoperator

   Set &operator=(const Set &s)
   {
      m_data=s.m_data;
      m_size=s.m_size;
      return *this;
   };

völlig korrekt. Das liegt daran, daß in der Zeile

      m_data=s.m_data;

der Zuweisungsoperator der Klasse Vector aufgerufen wird.

Die einzigen Methoden, die also noch benötigt werden sind Einfügen, Suchen und Löschen. Mit dem Suchen fangen wir an:

   double &find(const double &toFind)
   {
      for(int i=0;i<m_size;++i)
         if(m_data[i]==toFind)
            return m_data[i];
      //nichts gefunden! Was tun?
   };

Was soll getan werden, wenn der Wert nicht in der Set vorkommt? Man müßte einen besonderen Wert kennen, von dem man weiß, daß er nicht in der Liste vorkommen kann. Leider gibt es im Allgemeinen keinen solchen Wert. Für double ließe sich vielleicht noch ein Wert finden, aber wenn die Klasse Set zu einer Template-Klasse ausgebaut wird, dann geht das nicht mehr.

Es gibt aber für Zeiger einen solchen Wert: den Wert 0. Man kann sich also damit behelfen, daß ein Zeiger auf das gefundene Element zurückgegeben wird, falls es vorhanden ist, anderenfalls wird 0 zurückgegeben.

   double *find(const double &toFind)
   {
      for(int i=0;i<m_size;++i)
         if(m_data[i]==toFind)
            return &m_data[i];
      //nichts gefunden!
      return 0;
   };

Eine sehr praktische aber nicht notwendige Methode ist die has-Methode. Sie gibt einfach nur an, ob ein bestimmtes Element in der Set vorhanden ist.

   bool has(const double &toFind)
   {
      return find(toFind)!=0;
   };

Das Einfügen ist ebenfalls eine sehr einfache Methode.

   void insert(const double &toInsert)
   {
      if(!has(toInsert))
      {
         if(m_size==m_data.getSize())
            m_data.grow(m_data.getSize()+10); // gleich 10 Elemente mehr
               // anfordern, damit grow() nicht so oft aufgerufen werden muß
         m_data[m_size]=toInsert;
         ++m_size;
      };
   };

Diese Methode ist aber nicht hübsch geworden. Die Zeilen

      if(m_size==m_data.getSize())
            m_data.grow(m_data.getSize()+10);

sind einfach unpassend,

  • weil die magic number 10 vorkommt und
  • weil diese Zeilen in der Klasse Vector besser aufgehoben wären.

Zuerst werden diese Zeilen in die Klasse Vector verfrachtet. Dazu muß nur die Bedeutung dieser grow-Methode ein wenig verändert werden. Ab jetzt darf sie immer aufgerufen werden, aber sie vergrößert den Datenbereich nur, wenn die angeforderte Größe größer als die aktuelle Größe ist. In der Klasse Vector wird also folgende Nachbesserung angebracht:

   void grow(int newSize)
   {
      if(newSize>m_size)
      {
         newSize+=GROW_SIZE;
         T *newData=new T[newSize];
         for(int i=0;i<m_size;++i)
            newData[i]=m_data[i];
            delete[] m_data;
         m_size=newSize;
         m_data=newData;
      };
   };

Und in der private-Sektion der Klasse Vector kommt folgende Zeile hinzu:

   static const int GROW_SIZE=10;

Das vereinfacht die Methode insert der Klasse Set zu folgendem:

   void insert(const double &toInsert)
   {
      if(!has(toInsert))
      {
         m_data.grow(m_size+1);
         m_data[m_size]=toInsert;
         ++m_size;
      };
   };

Die Methode remove ist schon komplizierter!

Zunächst muß die Position des zu entfernenden Elementes gefunden werden. Dann werden alle darauf folgenden Elemente um eine Position nach vorne verschoben.

Für das Finden des Index wird wieder eine eigene Methode geschrieben. Weil keine klassenfremden Funktionen mit solch einem Index etwas anfangen können, wird sie ihren Platz in der private-Sektion finden. Sie gibt als Ergebnis den Index des gefundenen Elementes zurück. Falls kein Element gefunden wurde, dann wird der Index -1 zurückgegeben.

   int findIndex(const double &toFind)

Weil nach Möglichkeit kein Code doppelt vorhanden sein soll, wird die find-Methode entsprechend verändert.

   double *find(const double &toFind)
   {
      int found=findIndex(toFind);
      if(found!=-1)
         return &m_data[found];
      else
         return 0;
   };

Für das Verschieben der Elemente wird am besten in der Klasse Vector eine entsprechende Methode zur Verfügung gestellt. Sie bekommt drei Parameter:

  • start: Die Position des Anfangs des zu bewegenden Bereichs
  • end: Die Position des Endes des zu bewegenden Bereichs plus 1
  • newStart: Die neue Position des Bereichsanfangs

Die remove-Methode wird als

   void remove(const double &toRemove)
   {
      int found=findIndex(toRemove);
      if(found!=-1)
      {
         m_data.moveDown(found+1,m_size,found);
         --m_size;
      };
   };

recht übersichtlich.

Vergleichen Sie bitte diese Klasse mit der Klasse StackAsVector! In der Klasse StackAsVector gab es das Attribut m_topIndex, in dieser Klasse gibt es das Attribut m_size. Da immer gilt m_topIndex==m_size-1, ist fast egal, welche Version man verwendet. Die Version mit m_size ist aber ein wenig schöner, weil z.B. die Zuweisung m_topIndex=-1 im Konstruktor schon ein wenig abwegig ist. Ein m_size=0 ist einfacher zu verstehen.

Übung

Schreiben Sie die noch nicht ausgefüllten Methoden findIndex() und moveDown().

Übung

Spielen Sie das folgende Spiel, bis Sie drei mal hintereinander gewonnen haben! Die Lösungsstrategie, die Sie herausfinden werden, wird in der nächsten Lektion verwendet werden, um die Klasse Set erheblich schneller zu machen.

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

void main()
{
   srand(time(0));
   int gewonnen=0;
   while(gewonnen<3)
   {
      int ziel=rand()%100;// Zufallszahl zwichen 0 und 99
      int geraten;
      for(int versuch=1;versuch<=7;++versuch)
      {
         cout<<"Zahl eingeben: ";
         cin>>geraten;
         if(ziel<geraten)
            cout<<"kleiner"<<endl;
         else
            cout<<"nicht kleiner"<<endl;
      };
      cout<<"Wie heisst die Zahl ? "<<endl;
      cin>>geraten;
      if(geraten==ziel)
      {
         cout<<"Sie haben es geschafft!"<<endl;
         ++gewonnen;
      }
      else
      {
         cout<<"Nein! Die Zahl war "<<ziel<<endl;
         gewonnen=0;
      };
   };
   cout<<"Sie haben drei mal hintereinender gewonnen."<<endl;
   cout<<"Die nächste Lektion ist jetzt gut vorbereitet."<<endl;
};


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: 09/06/00