[C++] Dizionario con tavola hash

[pietrol83]

ciao a tutti, ho implementato la struttura dati dizionario utilizzando la realizzazione che vettore e funzione hash. nel test della struttura, precisamente al test del metodo appartiene, vi è un inserimento nel dizionario di un elemento, con relativa chiave. il problema è che il test va in crash sulla chiamata del metodo inserisci (la prima chiamata nel file testdizionari.cpp). dove avrei sbagliato???

questo è il link dei file che ho creato per l'implementazione del dizionario:

https://skydrive.live.com/redir.aspx...594&parid=root

[alka]

Originariamente inviato da pietrol83
questo è il link dei file che ho creato per l'implementazione del dizionario [...]

Posta la parte rilevante del codice qui, poiché il link a un file esterno non è detto che rimanga disponibile per sempre.

[pietrol83]

ok allora posto tutto il codice necessario:

dizionario.h

#ifndef dizionario_h
#define dizionario_h

#include<iostream>
#include<stdlib.h>

using namespace std;

template<class tipoelem>
class dizionario
{
   public:
      virtual void creadizionario() = 0;
      virtual bool appartiene(char *) = 0;
      virtual void inserisci(tipoelem) = 0;
      virtual void cancella(char *) = 0;
      virtual tipoelem recupera(char *) = 0;
      virtual void aggiorna(char *, tipoelem) = 0;
      
      void test();
};

#endif

template<class tipoelem>
void dizionario<tipoelem>::test()
{
   cout << "                     ***test del metodo APPARTIENE***\n\n";
   cout << "il metodo controlla se la chiave fornita come argomento e' presente o meno\n";
   cout << "nel dizionario.\n\n";
   cout << "         inserimento nel dizionario dell'elemento:\n";
   cout << "         valore dell'elemento: ";
   tipoelem elem;
   cin >> elem;
   this->inserisci(elem);
   cout << "    test con esito negativo:\n";
   cout << "         appartiene(totaro) = " << this->appartiene("totaro") << "\n\n";
   cout << "    test con esito positivo:\n";
   cout << "         appartiene(laforgia) = " << this->appartiene("laforgia") << "\n\n\n\n";
   
   cout << "                    ***test del metodo RECUPERA***\n\n";
   cout << "il metodo fornisce il valore dell'elemento con la relativa chiave che viene\n";
   cout << "passato come argomento.\n\n";
   cout << "        recupera(laforgia) = " << this->recupera("laforgia") << "\n\n";
   
   cout << "                    ***test del metodo AGGIORNA***\n\n";
   cout << "il metodo cambia il valore dell'elemento con la relativa chiave passata come\n";
   cout << "argomento.\n\n";
   cin >> elem;
   this->aggiorna("laforgia", elem);
   cout << "        recupera(laforgia) = " << this->recupera("laforgia") << "\n\n";
   
   cout << "                    ***test del metodo CANCELLA***\n\n";
   cout << "il metodo elimina dal dizionario l'elemento con la chiave fornita come argomento.\n";
   this->cancella("laforgia");
   cout << "        recupera(laforgia) = " << this->recupera("laforgia") << "\n\n";
}

dizionariothc.h

#ifndef dizionariothc_h
#define dizionariothc_h

#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<math.h>
#include<string>

#define maxdim 101

using namespace std;

template<class tipoelem>
class dizionariothc : public dizionario<tipoelem>
{
   public:
      dizionariothc();
      
      void creadizionario();
      bool appartiene(char *);
      void inserisci(tipoelem);
      void cancella(char *);
      tipoelem recupera(char *);
      void aggiorna(char *, tipoelem);
   private:
      int h(char *key);
      
      typedef struct bucket
      {
         char *chiave;
         tipoelem elemento;
         bool occupato;
      } bucket;
      bucket tavola[maxdim];
      int numbucket;
};

#endif

template<class tipoelem>
int dizionariothc<tipoelem>::h(char *key)
{
   int i = 0;
   int result = 0;
   int c = key[i];
   int tmp[strlen(key)];
      
   while(c != '\0')
   {
      if((c >= 48) && (c <= 57))
         tmp[i] = c - 48;
      else
      {
         if((c >= 65) && (c <= 90))
            tmp[i] = c - 64;
         else
         {
            if((c >= 97) && (c <= 122))
               tmp[i] = c - 96;
         }
      }
      i++;
      c = key[i];
   }
   i = strlen(key);
   while(i != 0)
   {
      result += tmp[i - 1] * (int)pow(13, (strlen(key) - i));
      i--;
   }
   result = result % 101;
   return result;
}

template<class tipoelem>
dizionariothc<tipoelem>::dizionariothc()
{
   this->creadizionario();
}

template<class tipoelem>
void dizionariothc<tipoelem>::creadizionario()
{
   for(int i = 0; i < maxdim; i++)
   {
      tavola[i].occupato = false;
   }
   numbucket = 0;
}

template<class tipoelem>
bool dizionariothc<tipoelem>::appartiene(char *k)
{
   assert(tavola[h(k)].occupato);
   return(tavola[h(k)].chiave == k);
}

template<class tipoelem>
void dizionariothc<tipoelem>::inserisci(tipoelem elem)
{
   cout << "inserire la chiave dell'elemento " << elem << ": ";
   char *key;
   cin >> key;
   int k = h(key);
   if(tavola[k].occupato)
      cout << "posizione occupata. impossibile inserire.\n\n";
   else
   {
      tavola[k].elemento = elem;
      tavola[k].chiave = key;
      tavola[k].occupato = true;
      numbucket++;
   }
}

template<class tipoelem>
void dizionariothc<tipoelem>::cancella(char *k)
{
   if(appartiene(k))
   {
      tavola[h(k)].occupato = false;
      numbucket--;
   }
   else
      cout << "chiave non presente nel dizionario.\n\n";
}

template<class tipoelem>
tipoelem dizionariothc<tipoelem>::recupera(char *k)
{
   assert(appartiene(k));
   return(tavola[h(k)].elemento);
}

template<class tipoelem>
void dizionariothc<tipoelem>::aggiorna(char *k, tipoelem elem)
{
   assert(appartiene(k));
   tavola[h(k)].elemento = elem;
}

testdizionari.cpp

#include "dizionario.h"
#include "dizionariothc.h"
#include<iostream>
#include<stdlib.h>

using namespace std;

int main()
{
   dizionariothc<char *> D;
   
   D.test();
   
   system("pause");
   return 0;
}

l'istruzione che va in crash è quella in rosso nel file dizionario.h

[oregon]

tipoelem in questo codice è un puntatore a char.

Quando esegui l'input con la cin, il puntatore a cosa punta?