PDA

Visualizza la versione completa : [C++] Dizionario con tavola hash


pietrol83
02-05-2012, 13:30
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?cid=f9fe0d3e54198821&resid=F9FE0D3E54198821!594&parid=root

alka
02-05-2012, 14:03
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
02-05-2012, 14:17
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
02-05-2012, 14:32
tipoelem in questo codice un puntatore a char.

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

Loading