ESERCIZIO
#include <iostream.h>
#include <string>struct node
{
string nome;
int voto;
node *next;};
node* ptr=0;
class lista
{
private:
/* Variabili 'private' sono i puntatori alla testa ed alla coda della losta linkata */node *head;
node *tail;public:
lista();
~lista();
void insert_head(string, int);
void insert_tail(string, int);
void print();
void print_head();
void print_tail();/* La member function 'clear' deve liberare la memoria allocata per la lista linkata e non solo 'perdere' il puntatore iniziale alla lista */
void clear();
node *search(string);};
class hash
{
private:
lista* dict;
int hashvalue (string key);
/* Indica la dimensione del vettore di lista.*/
int dictsize;public:
hash();
~hash();
/* Restituisce un valore booleano che indica se ha trovato la chiave "key" */
int get (string key);
void insert (string key, int);
/* Stampa tutti i dati delle lista linkata della chiave.*/
void printline (string key);};
/*-------------------------------------------------------------------------*/
hash::hash()
{
dictsize=256;
dict = new lista[dictsize];}
hash::~hash(){}
int hash::hashvalue (string key)
{
int hv=0;
for (int i=0; i<(key.size()); i++)
hv += key[i]%256;
return hv%256;
}
void hash::insert(string key, int v)
{
int hv = hashvalue(key);
dict[hv].insert_tail(key,v);}
/* Alla member function seguente viene passato il nome dello studente "key", al quale viene assegnato tramite la funzione "hasvalue" un'opportuna chiave (che rappresenta l'indiche all'interno della tabella hash). Alla variabile globale "ptr" poi viene assegnato il puntatote del nodo all'interno dalla lista, avente lo stesso nome (in caso contrario viene assegnato a 0)*/
int hash::get(string key)
{
int hv = hashvalue(key);
ptr = dict[hv].search(key);
if (!ptr)
hv=0;
return hv;
}
void hash::printline(string key)
{
int hv = hashvalue(key);
dict[hv].print();}
/*-------------------------------------------------------------------------*/
/* Il costruttore inizializza a 'zero' tutti gli attributi dell'oggetto */
lista::lista()
{
head=0;
tail=0;}
/* Il distruttore libera anche la memoria allocata per i puntatori alla testa e alla coda della lista linkata*/
lista::~lista()
{
delete head;
delete tail;}
/* La member function 'insert_head' inserisce un nuovo elemento di cui prende nome e voto in testa alla lista. Per fare cio' crea una copia di 'head' in 'lptr', crea un nuovo nodo della lista che viene messo in testa ed infine il puntatore al nuovo elemento creato viene reimpostato ad 'head'. In caso di lista vuota, si deve assegnare a 'tail' lo stesso valore di 'head' (poi per altri inserimenti in testa
'tail' rimane invariato).*/void lista::insert_head(string n, int v)
{
node * lptr;
lptr=head;
head=new node;
head->nome=n;
head->voto=v;
head->next=lptr;
if(head->next==0)
{
tail=head;
}
}
/* La member function 'insert_tail' inserisce un nuovo nodo in coda alla lista. Per fare cio', crea un nuovo elemento, lega l'ultimo elemento delle 'vecchia' lista al nuovo creato e 'sposta' 'tail'. Se, pero', la lista e' vuota 'head' e 'tail' vengono impostati al puntatore del nuovo elemento.*/
void lista::insert_tail(string n, int v)
{
node * lptr;
lptr=new node;
lptr->nome=n;
lptr->voto=v;
lptr->next=0;
if(tail!=0)
tail->next=lptr;
if(tail==0)
{
head=lptr;
}
tail=lptr;}
/* La member function 'print' stampa tutti i nodi della lista finche' 'lptr' non punta a null.*/
void lista::print()
{
node* lptr;
lptr=head;
while(lptr!=0)
{
cout << "nome: "<< lptr->nome << endl;
cout << "voto: "<< lptr->voto << endl;
lptr=lptr->next;}
}
void lista::print_head()
{
cout << "il primo nome e': "<< head->nome << endl;
cout << "il primo voto e': " << head->voto << endl;}
void lista::print_tail()
{
cout << "l'ultimo nome e': "<< tail->nome << endl;
cout << "l'ultimo voto e': " << tail->voto << endl;}
node* lista::search(string sc)
{
node* lptr;
lptr=head;if (lptr!=0)
{
while(lptr->nome!=sc)
{
if(lptr->next==0)
{
lptr=0;
break;}
lptr=lptr->next;}
}
return lptr;}
/* La member function 'clear' dealloca tutta la memoria utilizzata per la lista. Per fare cio' prende il nodo in testa crea una copia del puntatore al suo successivo, elimina l'elemento in testa e rinomina il puntatore della 'vecchia testa' a quella 'nuova' ( ad 'head' viene assosiato il puntatore 'head->next'). Viene infine deallocato lo spazio per la variabile di lavoro 'lptr'.*/
void lista::clear()
{
node* lptr;
lptr=head;
while(lptr!=0)
{
lptr=head->next;
delete head;
head=lptr;};
delete lptr;}
void main ()
{
int stop=1;
hash diz;
int v;
string n;
while (stop)
{
cout << "Vuoi inserire un nuovo elemento? (0=no)";
cin >> stop;
if (stop)
{
cout << "Inserisci il nome: ";
cin >> n;
cout << "Inserisci il voto: ";
cin >> v;
diz.insert(n,v);
}
}
stop=1;
while (stop)
{
cout << "Vuoi cercare un elemento? (0=no)";
cin >> stop;
if (stop)
{
cout << "Inserisci il nome: ";
cin >> n;
if(diz.get(n))
{
cout << "L'ho trovato" << endl;
}
else
{
cout << "Non l'ho trovato " << endl;
}
}
}
stop=1;
while(stop)
{
cout << "Vuoi stampare un elemento? (0=no)";
cin >> stop;
if (stop)
{
cout << "Inserisci il nome: ";
cin >> n;
if(diz.get(n))
{
cout << "Ho trovato: " << ptr->nome << " " << ptr->voto << endl;
}
else
{
cout << "Non ho trovato niente" << endl;
}
}
}
stop =1;
while(stop)
{
cout << "Vuoi stampare un intero indice? (0=no)";
cin >> stop;
if (stop)
{
cout << "Inserisci il nome: ";
cin >> n;
diz.printline(n);}
}
}