Einsendung:

Lösungsvorschlag

#include<iostream>
#include<string>
#include<ctype.h>
#include<assert.h>
using  namespace std;

template<class T>
class Vector
{
private:
   T *m_data;
   int m_size;
   enum{GROW_SIZE=10};
public:
   Vector(int size)
   {
      m_size=size;
      m_data=new T[m_size];
   };
   
   Vector(const Vector &derAndereVector)    
   {
      m_size=derAndereVector.m_size;
      m_data=new T[m_size];
      for(int i=0;i<m_size;++i)
         m_data[i]=derAndereVector.m_data[i];
   };
   ~Vector()
   {
      delete[] m_data;
   };
   T& operator[](int index)    
   {
      assert(index>=0);
      assert(index<m_size);
      return m_data[index];
   };
   int getSize()
   {
      return m_size;
   };
   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;
      };
   }; 
   Vector &operator=(const Vector &derAndereVector)    
   {
      if(&derAndereVector!=this)
      {
         delete[] m_data;
         m_size=derAndereVector.m_size;
         m_data=new T[m_size];
         for(int i=0;i<m_size;++i)
            m_data[i]=derAndereVector.m_data[i];
      }
      return *this;
   }
   void moveDown(int pa, int pe, int newstart)
   {
      int einheit = pa - newstart;
      for (int n=newstart;n<=pe-einheit;n++)
      {
         m_data[n]=m_data[n + einheit];
      }
   };
   void moveUp(int pa, int pe, int newstart)
   {
      int einheit = newstart - pa;
      for(int i=pe;i>=pa;i--)
         m_data[i+einheit]=m_data[i];
   }
};

template<class T,class C=DefaultComparator<T> >
class SortedArray
{
private:
   Vector<T> m_data;
   C m_comp;
   int m_size;
   int findIndex(const T &tofind)
   {
      if(m_size > 2)
      {
         int oben=m_size-1, unten=0, mitte=int(oben/2);
         do
         {
            if (!(m_comp.lessThan(tofind,m_data[mitte])))
            {
               unten=mitte;
               mitte=int(mitte+((oben-mitte)/2));
            }
            else
            {
               oben=mitte-1;
               mitte=int(mitte-(mitte-unten)/2); 
            };
         }while(oben-unten>1);
         if(!(m_comp.lessThan(tofind,m_data[oben])))
            return oben;
         else
            return unten;
      }
      else
      {
         if (m_size == 2)
         {
            if(!(m_comp.lessThan(tofind,m_data[1])))
               return 1;
            else
               return 0;
         }
         else 
            return 0;
      }
   };
public:
   SortedArray()
      :m_data(10)
   {
      m_size=0;
   }; 
   bool has(const T &toFind)
   {
      return find(toFind)!=0;
   }; 
   void insert(const T &toInsert)
   {
      int pos;//Position, hinter der eingefügt werden soll
      m_data.grow(m_size+1);
      if(m_size==0)
         pos=-1;
      else
      {
         pos=findIndex(toInsert);
         if(pos==0)
            if(m_comp.lessThan(toInsert,m_data[pos]))
               pos=-1;
      };
      m_data.moveUp(pos+1,m_size-1,pos+2);
      m_data[pos+1]=toInsert;
      ++m_size;
   }; 
   int find(const T &toFind)
   {
      if(m_size==0
         return -1;
      else
      {    
         int index=findIndex(toFind);
         if(m_comp.isEqual(toFind,m_data[index]))
            return index;
         else
            return -1;
      }
   }; 
   int remove(const T &toRemove)
   {
      if(m_size>0)
      {
         int found=findIndex(toRemove);
         if(m_comp.isEqual(m_data[found],toRemove))
         {
            m_data.moveDown(found+1,m_size,found);
            --m_size;
            return found;
         }
         else
            return -1;
         
      }
      else
         return -1;
   }; 
   void print()
   {
      
      for(int n=0;n<m_size;n++)
         cout<<n<<": "<<m_data[n]<<endl;
      cout<<endl;
   };
   int getSize()
   {
      return m_size;
   };
   const T &operator[](int index)
   {
      assert(index<m_size);
      return m_data[index];
   }; 
};

string tolower(const string &str)
{
   string result=str;
   for(int i=0;i<result.size();++i)
      result[i]=tolower(result[i]);
   return result;
};
class IgnoreCaseStringComparator
{
public:
   bool lessThan(const string &a,const string &b)
   {
      return tolower(a)<tolower(b);
   };
   bool isEqual(const string &a,const string &b)
   {
      return tolower(a)==tolower(b);
   };
};

template<class T>
class DefaultComparator
{
public:
   bool lessThan(const T &a,const T &b)
   {
      return a<b;
   };
   bool isEqual(const T &a,const T &b)
   {
      return a==b;
   };
};

template<class KEY,class VALUE>
class DictionaryEntry
{
private:
   KEY m_key;
   VALUE m_value;
public:
   DictionaryEntry()
   {
   };
   DictionaryEntry(const KEY &key)
      :m_key(key)
   {
   };
   DictionaryEntry(const KEY &key,const VALUE &value)
      :m_key(key),m_value(value)
   {
   };
   const KEY &getKey() const
   {
      return m_key;
   };
   VALUE &getValue() const
   {
      return const_cast<VALUE&>(m_value);
      
   };
};

template<class KEY,class VALUE,class KEY_COMPARATOR>
class DictionaryEntryComparator
{
private:
   KEY_COMPARATOR m_comp;
public:
   bool lessThan(const DictionaryEntry<KEY,VALUE> &a,const
      DictionaryEntry<KEY,VALUE> &b)
   {
      return m_comp.lessThan(a.getKey(),b.getKey());
   };
   bool isEqual(const DictionaryEntry<KEY,VALUE> &a,const
      DictionaryEntry<KEY,VALUE> &b)
   {
      return m_comp.isEqual(a.getKey(),b.getKey());
   };
};

template<class KEY,class VALUE,class KEY_COMPARATOR=DefaultComparator<KEY> >
class Dictionary
{
private:
   SortedArray
      <
      DictionaryEntry<KEY,VALUE>,
      DictionaryEntryComparator<KEY,VALUE,KEY_COMPARATOR> 
      > m_data;
public:
   void insert(const KEY &key,const VALUE &value)
   {
      m_data.insert(DictionaryEntry<KEY,VALUE>(key,value));
   };
   int getSize()
   {
      return m_data.getSize();
   };
   const DictionaryEntry<KEY,VALUE> &operator[](int index)
   {
      return m_data[index];
   };
   int find(const KEY &key)
   {
      return m_data.find(DictionaryEntry<KEY,VALUE>(key));
   }
   int remove(const KEY &toremove)
   {
      return m_data.remove(DictionaryEntry<KEY,VALUE>(toremove));
   }
   
};

void main()
{
   Dictionary<string,string> buch;
   DictionaryEntry<string,string> temp;
   
   bool nochmal=true;
   while(nochmal)
   {
      cout<<"Menue"<<endl;
      cout<<"1 Name einfuegen"<<endl;
      cout<<"2 Name suchen"<<endl;
      cout<<"3 Name aendern"<<endl;
      cout<<"4 Name loeschen"<<endl;
      cout<<"5 Liste anzeigen"<<endl;
      cout<<"0 Programm beenden"<<endl;
      int eingabe;
      
      cin>>eingabe;
      
      string name;
      string nummer;
      switch(eingabe)
      {
         int index,i;
      case 0:
         nochmal=false;
         break;
      case 1:// Name einfügen
         cout<<"Name : ";
         cin>>name;
         cout<<"Nummmer: ";
         cin>>nummer;
         buch.insert(name,nummer);
         break
      case 2:// Name suchen
         cout<<"Gesuchter Name: ";
         cin>>name;
         index = buch.find(name);
         if(index == -1)
            cout<<"Name befindet sich nicht im Telefonbuch!"<<endl;      
         else
         {
            temp = buch[index];
            cout<<"Name : "<<temp.getKey()<<endl;
            cout<<"Nummer: "<<temp.getValue()<<endl;
         }
         break;
      case 3:// Name aendern
         cout<<"Zu aenderner Name: ";
         cin>>name;
         
         if(buch.remove(name) == -1)
            cout<<"Name befindet sich nicht im Telefonbuch!"<<endl;
         else
         {
            cout<<"Bitte Aenderungen eintragen:"<<endl;
            cout<<"Name :";cin>>name;
            cout<<"Nummer:";cin>>nummer;
            buch.insert(name,nummer);
         }
         break;
      case 4:// Name loeschen
         cout<<"Zu loeschender Name: ";
         cin>>name;
         if(buch.remove(name) == -1)
            cout<<"Name befindet sich nicht im Telefonbuch!"<<endl;
         else
            cout<<"Eintrag wurde erfolgreich geloescht!"<<endl;
         break;
      case 5:// Liste anzeigen
         for (i=0;i<buch.getSize();i++)
         {
            temp=buch[i];
            cout<<"Name : "<<temp.getKey()<<endl;
            cout<<"Nummer: "<<temp.getValue()<<endl;
         }                        
         break;
      default:
         cout<<"Diesen Menuepunkt gibt es nicht!"<<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: 08/25/00