[C++] Dizionario con liste di trabocco

[pietrol83]

ciao a tutti, oltre al dizionario con semplice tavola hash che ho implementato nel post precedente, sto implementando anche un dizxionario con liste di trabocco. in fase di test dei metodi l'esecuzione va in crash in appena arriva su un'istruzione che è fatti in modo corretto, cioè su una semplice

cin >> k

che prende da tastiera una stringa e la memorizza nella variabile k che è di tipo char *.

posto i codici che ho implementato per la struttura dizionario con liste di trabocco.

nodop.h

#ifndef nodop_h
#define nodop_h

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

using namespace std;

template<class tipoelem>
class nodop
{
   public:
      nodop();
      
      void setprec(nodop *);
      void setelem(tipoelem);
      void setsuc(nodop *);
      
      nodop *getprec();
      tipoelem getelem();
      nodop *getsuc();
      
      nodop operator=(nodop);
   private:
      nodop *precedente;
      tipoelem elemento;
      nodop *successivo;
};
#endif

template<class tipoelem>
nodop<tipoelem>::nodop()
{
   precedente = NULL;
   successivo = NULL;
}

template<class tipoelem>
void nodop<tipoelem>::setprec(nodop *prec)
{
   precedente = prec;
}

template<class tipoelem>
void nodop<tipoelem>::setelem(tipoelem elem)
{
   elemento = elem;
}

template<class tipoelem>
void nodop<tipoelem>::setsuc(nodop *suc)
{
    successivo = suc;
}

template<class tipoelem>
nodop<tipoelem> *nodop<tipoelem>::getprec()
{
   return(precedente);
}

template<class tipoelem>
tipoelem nodop<tipoelem>::getelem()
{
   return(elemento);
}

template<class tipoelem>
nodop<tipoelem> *nodop<tipoelem>::getsuc()
{
   return(successivo);
}

template<class tipoelem>
nodop<tipoelem> nodop<tipoelem>::operator=(nodop<tipoelem> node)
{
   this->precedente = node.getprec();
   this->elemento = node.getelem();
   this->successivo = node.getsuc();
}

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 = new char;
   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";
   cout << "   inserire il valore da sostituire: ";
   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";
}

dizionariolt.h

#ifndef dizionariolt_h
#define dizionariolt_h

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

using namespace std;

template<class tipoelem>
class dizionariolt : public dizionario<tipoelem>
{
   public:
      dizionariolt(int);
      
      void creadizionario();
      bool appartiene(char *);
      void inserisci(tipoelem);
      void cancella(char *);
      tipoelem recupera(char *);
      void aggiorna(char *, tipoelem);
   private:
      int dimtavola;
      typedef struct Elemento
      {
         tipoelem valore;
         char *chiave;
      } elemento;
      nodop< struct Elemento> **tavola;
      
      int h(char *);
};

#endif

template<class tipoelem>
int dizionariolt<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 % dimtavola;
   return result;
}

template<class tipoelem>
dizionariolt<tipoelem>::dizionariolt(int dimvet)
{
   dimtavola = dimvet;
   this->creadizionario();
}

template<class tipoelem>
void dizionariolt<tipoelem>::creadizionario()
{
   tavola = new nodop<struct Elemento> *[dimtavola];
   for(int i = 0; i < dimtavola; i++)
      tavola[i] = NULL;
}

template<class tipoelem>
bool dizionariolt<tipoelem>::appartiene(char *k)
{
   bool risultato = false;
   
   nodop<struct Elemento> *tmp = tavola[h(k)];
   bool trovato = false;
   while(!trovato && (tmp != NULL))
   {
      if(tmp->getelem().chiave == k)
         trovato = true;
      else
         tmp = tmp->getsuc();
   }
   return risultato;
}

template<class tipoelem>
void dizionariolt<tipoelem>::inserisci(tipoelem elem)
{
   cout << "inserire la chiave dell'elemento " << elem << ": ";
   char *k = new char;
   cin >> k;
   if(this->appartiene(k))
      cout << "elemento gia' esistente nel dizionario.\n\n";
   else
   {
      elemento el;
      el.valore = elem;
      el.chiave = k;
      nodop<struct Elemento> *tmp = new nodop<struct Elemento>;
      tmp->setelem(el);
      if(tavola[h(k)] == NULL)
         tavola[h(k)] = tmp;
      else
      {
         tmp->setsuc(tavola[h(k)]);
         tavola[h(k)] = tmp;
      }
   }
}

template<class tipoelem>
void dizionariolt<tipoelem>::cancella(char *k)
{
   if(!this->appartiene(k))
      cout << "elemento non presente nel dizionario.\n\n";
   else
   {
      if(tavola[h(k)]->getsuc() == NULL)
         tavola[h(k)] = NULL;
      else
      {
         bool trovato = false;
         nodop<struct Elemento> *p = tavola[h(k)];
         while(!trovato)
         {
            if(p->getelem().chiave == k)
               trovato = true;
            else
               p = p->getsuc();
         }
         
         nodop<struct Elemento> *tmp = tavola[h(k)];
         while(tmp->getsuc() != p)
            tmp = tmp->getsuc();
         
         tmp->setsuc(p->getsuc());
         delete p;
      }
   }
}

template<class tipoelem>
tipoelem dizionariolt<tipoelem>::recupera(char *k)
{
   assert(this->appartiene(k));
   bool trovato = false;
   nodop<struct Elemento> *p = tavola[h(k)];
   while(!trovato)
   {
      if(p->getelem().chiave == k)
         trovato = true;
      else
         p = p->getsuc();
   }
   
   return(p->getelem().valore);
}

template<class tipoelem>
void dizionariolt<tipoelem>::aggiorna(char *k, tipoelem elem)
{
   assert(this->appartiene(k));
   bool trovato = true;
   nodop<struct Elemento> *p = tavola[h(k)];
   while(!trovato)
   {
      if(p->getelem().chiave == k)
      {
         elemento el;
         el.chiave = p->getelem().chiave;
         el.valore = elem;
         p->setelem(el);
         trovato = true;
      }
      else
         p = p->getsuc();
   }
}

testdizionari.cpp

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

using namespace std;

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

l'istruzione che fa andare in crash l'esecuzione è quella in rosso. perchè fa questo???

[shodan]

Perché stai cercando di inserire qualcosa in un puntatore.
L'istruzione corretta è:

cin>> *k;

[pietrol83]

ops!!! non me ne sono accorto. grazie 1000.

[pietrol83]

avrei un altro problema: quando faccio il test del metodo appartiene, passo prima una chiave non appartenente al dizionario e l'esito è negativo (cosa giusta), poi ne passo una appartenente al dizionario e mi dà anche esito negativo. ho notato che quando viene eseguito il metodo appartiene non si entra nel ciclo while perchè viene violata la condizione tmp != NULL, il che è strano perchè sel la chiave appartiene, la posizione nel vettore fornita dalla funzione hash dovrebbe non essere NULL in quanto c'è un nodo. perchè fa questo???

in pratica il sto testanto i seguenti frammenti di codice:

dizionario.h sto nella parte ***test del metodo appartiene***
qui entrano in gioco solo i metodi appartiene e inserisci, oltre alla funzione hash.

dove ho sbagliato???

[shodan]

Per quel che vedo, sei già fortunato (o sfortunato a seconda dei punti di vista) a non avere errori di accesso.
Crei un singolo char si cui passi il puntatore ad [/b]appartiene[/b]. Quest'ultima lo inoltra a h dove ne fai una strlen() che non si sa dove finisce; infine usi il valore di quella strlen() come indice per accedere a un array. Non contento usi lo stesso puntatore come fosse un array di char.
Ma questa istruzione:

char *k = new char;

crea un solo char non una sequenza di char.
Domanda: ma è così brutto usare std::string?