AIUTO tabelle hash

filmon97

il 01 gen 2015, 18:01

21 risposte

filmon97

Pochi posts

Iscritto da: gen, 2015

Messaggi:: 14

AIUTO tabelle hash

01 gen 2015, 18:37

AIUTO RAGAZZI sono nuovo del forum
il testo dell'esercizio che ci ha dato il prof è questo :
Scrivere una applicazione C++ completa di documentazione per gestire una piccola biblioteca domestica di un centinaio di libri. Ogni libro è identificato da un codice ISBN (stringa 13 cifre), un autore, un titolo, un editore ed un anno di pubblicazione. Progettare le classi ed implementare in C++ una classe Libreria che memorizzi gli oggetto di tipo Libro in una tabella ad indirizzamento hash. I metodi della classe Libreria devono consentire:
• la ricerca dei dati di un libro a partire dal proprio codice ISBN;
• la memorizzazione di un nuovo libro;
• l’eliminazione di un libro;
Nella documentazione si scriva una breve analisi sul dimensionamento della tabella indicando il fattore di carico scelto per la tabella e si indichi il tipo di funzione hash ed il metodo di gestione delle collisioni utilizzati.
------------
Il mio problema è che non ho mai fatto un programma con le tabelle hash ma ho solo studiato la teoria mentre la classe Libro che contiene le informazioni mi riesce ,ma la classe Libreria non so proprio da dove partire

21 Risposte

F
filmon97
Pochi posts
Iscritto da
gen, 2015
Messaggi:
14
Re: AIUTO tabelle hash
06 gen 2015, 11:14
Up
S
SVNiko
Molto attivo
Iscritto da
set, 2014
Messaggi:
535
Re: AIUTO tabelle hash
06 gen 2015, 12:01
Dovresti realizzare la tua libreria hash table?

Per farlo devi intanto dimensionare un vettore di puntatori agli oggetti che vuoi memorizzare, poi scriverti una funzione di hash che calcola l'indice del vettore, nel tuo caso penso che la chiave di ricerca più naturale sia il codice ISBN.

Prova a scriverla e magari posta qui quello che hai scritto in modo che possiamo aiutarti correggendo o dandoti piccoli suggerimenti.

filmon97

Pochi posts

Iscritto da: gen, 2015

Messaggi:: 14

Re: AIUTO tabelle hash

06 gen 2015, 12:05

Se ho capito bene vanno fatte due classi di questo tipo


// LIBRO.h
#ifndef LIBRO_H
#define LIBRO_H

class Libro
{
private:
    char ISBN[13];                      //ISBN (stringa 13 cifre)
    char autore[20];                    //un autore
    char titolo[50];                    //un titolo
    char editore[20];                   //un editore
    char anno_di_pubblicazione[5];      //anno di pubblicazione
public:
    Libro();
    //setter
    void setISBN(char ISBN[13]);
    void setAuthor();
    void setTitle();
    void setEditor();
    void setPublishYear();
};

#endif // LIBRO_H

// libreria.h
#ifndef LIBRERIA_H
#define LIBRERIA_H

class Libreria
{
private:
   /*
    • la ricerca dei dati di un libro a partire dal proprio codice ISBN;
    • la memorizzazione di un nuovo libro;
    • l’eliminazione di un libro;
    */
public:
    Libreria();
   
};

#endif // LIBRERIA_H

F
filmon97
Pochi posts
Iscritto da
gen, 2015
Messaggi:
14
Re: AIUTO tabelle hash
06 gen 2015, 12:07
Il problema è che non so proprio come si fa una funzione hash a scuola ci hanno spiegato solo il teorico e su internet non ho trovato nessun esempio che riguardasse una funzione simile alla mia
F
filmon97
Pochi posts
Iscritto da
gen, 2015
Messaggi:
14
Re: AIUTO tabelle hash
06 gen 2015, 12:20
SVNiko ha scritto:
Dovresti realizzare la tua libreria hash table?

Per farlo devi intanto dimensionare un vettore di puntatori agli oggetti che vuoi memorizzare, poi scriverti una funzione di hash che calcola l'indice del vettore, nel tuo caso penso che la chiave di ricerca più naturale sia il codice ISBN.

Prova a scriverla e magari posta qui quello che hai scritto in modo che possiamo aiutarti correggendo o dandoti piccoli suggerimenti.
il vettore di puntatori di tipo Libro lo devo implementare nella classe Libreria?
funzione hash da dove parto???
F
filmon97
Pochi posts
Iscritto da
gen, 2015
Messaggi:
14
Re: AIUTO tabelle hash
06 gen 2015, 13:27
Heelpp è per domani !!!!!!!!!!
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6012
Re: AIUTO tabelle hash
06 gen 2015, 13:52
Allora:

1) spiegaci la teoria di funzione hash
2) mostra il primo esempio che ti viene in mente di funzione hash, ad esempio (e qui ti do una graaante mano) sui numeri interi
F
filmon97
Pochi posts
Iscritto da
gen, 2015
Messaggi:
14
Re: AIUTO tabelle hash
06 gen 2015, 14:09
migliorabile ha scritto:
Allora:

1) spiegaci la teoria di funzione hash
2) mostra il primo esempio che ti viene in mente di funzione hash, ad esempio (e qui ti do una graaante mano) sui numeri interi
una tabella è una successione di elementi ciascuno dei quali è composta da una chiave e dall'informazione associata alla chiave ;
mi immagino in questo caso di passare alla funzione la stringa ISBN;
while(p[key]!=NULL)
{
key=(key+2*i)%125; //125 è la dimensione dell'array e 100 è il numero max di libri da inserire! fattore di carico = 0,8
i++
}

filmon97

Pochi posts

Iscritto da: gen, 2015

Messaggi:: 14

Re: AIUTO tabelle hash

06 gen 2015, 18:34

Questa è la funzione che sono riuscito a realizzare


int Hash:: Hashk(string key)
{
    int hash =0;
    int index;
   // index = key.length(); // lughezza stringa

  for(int i = 0; i < key.length(); i++) 
  {
    hash = hash + (int)key[i]; // l' int convertono i caratteri nel lora valore ascii
    cout << "hash = " << hash << endl;
  }
  index = hash % tableSize; /// 400/100 fa 4 con resto di 2


  return index;

}

filmon97

Pochi posts

Iscritto da: gen, 2015

Messaggi:: 14

Re: AIUTO tabelle hash

06 gen 2015, 21:37

Sono riuscito a finirlo ma mi da un errore insolito allego solo la parte importante
libreria.h


#include <iostream>
#include<string>
#include<string.h>
#include<cstdlib>
#include"libro.h"

using namespace std;

class Libreria
{

private:
    static const int tableSize = 5;
/*
    struct item
    {
        string name;
        string drink;
        item* next;
    };
*/
    Libro *HashTable[tableSize];  // qui mi da  l'errore

Libro.h


#include<iostream>
#include<string>
#include"libreria.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

using namespace std;

class Libro
{
private:
    string ISBN;                      //ISBN (stringa 13 cifre)
    string autore;                    //un autore
    string titolo;                    //un titolo
    string editore;                   //un editore
    string anno_di_pubblicazione;      //anno di pubblicazione
    Libro* next;

public:
    Libro();
    //setter
    void setISBN(string ISBN);
    void setAuthor(string autore);
    void setTitle(string titolo);
    void setEditor(string editore);
    void setPublishYear(string anno_di_pubblicazione);
    void setNext(Libro* next);
};

M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6012
Re: AIUTO tabelle hash
06 gen 2015, 21:53
La funzione hash dovrebbe ritornare SOLO il valore hash, perche' lo stesso valore potrebbe essere utilizzato per fare cose diverse.

Altro problema: l'implementazione che hai utilizzato, non e' gran che.

Ricordati il concetto di collisione: hai una collisione quando due chiavi generano lo stesso valore hash.

Cosi' come hai scritto la funzione, "ab" e "ba" generano lo stesso valore hash, il che non e' una grande idea. Ma, ovviamente, e' pure peggio di cosi' !

Devi ingegnarti a trovare una funzione piu' furba che cerca, in qualche modo, di ritornare numeri diversi per chiavi che differiscono non solo per i caratteri usati, ma anche per l'ordine.

Ci sono seri studi su come realizzare una funzioni hash che riduca al minimo le collisioni (vengono usate massicciamente in campo crittografico), ma non ti serve una cosa complicata, ma solo qualcosa di un po' piu' intelligente.

Che errore strano ti segnala?

Perche' da me questo funziona:
```
#include <iostream>

struct Libro {
    int i;
    Libro(){ }
};

struct S
{
    static const int tableSize = 5;
    
    Libro t[tableSize];
};

int main(int argc, char **argv)
{
    S s;
    s.t[4].i = 1;
    
    std::cout << s.t[4].i << "\n";
}
```
Stai usando una versione del compilatore raggionevolmente recente?
F
filmon97
Pochi posts
Iscritto da
gen, 2015
Messaggi:
14
Re: AIUTO tabelle hash
06 gen 2015, 22:18
migliorabile ha scritto:
La funzione hash dovrebbe ritornare SOLO il valore hash, perche' lo stesso valore potrebbe essere utilizzato per fare cose diverse.

Altro problema: l'implementazione che hai utilizzato, non e' gran che.

Ricordati il concetto di collisione: hai una collisione quando due chiavi generano lo stesso valore hash.

Cosi' come hai scritto la funzione, "ab" e "ba" generano lo stesso valore hash, il che non e' una grande idea. Ma, ovviamente, e' pure peggio di cosi' !

Devi ingegnarti a trovare una funzione piu' furba che cerca, in qualche modo, di ritornare numeri diversi per chiavi che differiscono non solo per i caratteri usati, ma anche per l'ordine.

Ci sono seri studi su come realizzare una funzioni hash che riduca al minimo le collisioni (vengono usate massicciamente in campo crittografico), ma non ti serve una cosa complicata, ma solo qualcosa di un po' piu' intelligente.

Che errore strano ti segnala?

Perche' da me questo funziona:

#include <iostream> struct Libro { int i; Libro(){ } }; struct S { static const int tableSize = 5; Libro t[tableSize]; }; int main(int argc, char **argv) { S s; s.t[4].i = 1; std::cout << s.t[4].i << "\n"; }

Stai usando una versione del compilatore raggionevolmente recente?
si ho provato su due compilatori diversi qt e visual e tutti e due mi danno un errore strano perchè non riconoscono il tipo Libro (classe)

filmon97

Pochi posts

Iscritto da: gen, 2015

Messaggi:: 14

Re: AIUTO tabelle hash

07 gen 2015, 16:57

Questo è il mio programma per chi cercherà soluzioni di questo tipo
#main


#include <iostream>
#include<string>
#include<string.h>
#include<cstdlib>
#include"libreria.h"

using namespace std;

/**
 * \author 
 */
int main()
{

    Libreria Hashy;
    string ISBN ="";
    string autore ="";
    string titolo ="";
    string editore ="";
    string anno_di_pubblicazione ="";
    int scelta=0,termina=0,n;
   do
   {
        system("CLS");
    cout << "1.ADD BOOK"<<endl;
    cout << "2.SEARCh BOOK" <<endl;
    cout << "3.REMOVE BOOK" <<endl;
    cout << "4.PRINT BOOK LIST"<<endl;
    cout << "5.LEAVE FROM THE PROGRAM"<<endl;
    cout << "CHOOSE:";
    cin >> scelta;
    switch (scelta)
    {
    case 1:
        /// inserimento
        system("CLS");
        cout << "how many books you want to add:";
        cin >> n;
        cout << endl;
        for(int i=0;i<n;i++)
        {
            cout << "ISBN:";
            cin >> ISBN;
            cout << "title:";
            cin >> titolo;
            cout << "author:";
            cin >> autore;
            cout << "editor:";
            cin >> editore;
            cout << "publish year:";
            cin >> anno_di_pubblicazione;
             Hashy.AddItem(ISBN,titolo,autore,editore,anno_di_pubblicazione);
        }
        break;
    case 2:
        ///ricerca
        system("CLS");
        while(ISBN != "exit")
        {
           cout << "tap exit to leave..." << endl;
           cout << "Search for: ";
           cin >> ISBN;
           cout << endl;
           if(ISBN != "exit")
           {
              Hashy.FindBook(ISBN);
           }
        }
        break;

    case 3:
        /// cancellazione
        while(ISBN != "exit")
        {
           cout << "tap exit to leave..." << endl;
           cout << "Remove: ";
           cin >> ISBN;
           cout << endl;
           if(ISBN != "exit")
           {
              Hashy.RemoveItem(ISBN);
           }
        }
          break;
     case 4:
        /// stampa
           Hashy.PrintTable();
           break;
     case 5:
         /// uscita programma
         termina++;
         break;
    default:
         /// in caso in cui non venga scelta una operazione valida
         cout<<"Invalid choice"<<endl;
        break;
    }
    }while(termina==0);

}

#header


libreria.h...
#ifndef LIBRERIA_H
#define LIBRERIA_H
#include <iostream>
#include<string>
#include<string.h>
#include<cstdlib>
#include"libro.h"

using namespace std;

class Libro;

class Libreria
{

private:
    static const int tableSize = 5;


    Libro* HashTable[tableSize];
public:
    /**
       * Costruttore di default
       */
   Libreria();

   /**
    * Funzione Hash
    */
   int hashFun(string key);
   /**
      * Funzione di Inserimento nuovo elemento
      */
   void AddItem(string ISBN, string titolo, string autore, string editore, string anno_di_pubblicazione);
   /**
      * passandogli la posizione della cella questa funzione ritornerà
      * il numero degli elementi condividono la stessa posizione della cella
      * se NumberOfItemsInIndex >1 = collisione
      */
   int NumberOfItemsInIndex(int index);
   /**
      * Funzione di Ricerca
      */
   void FindBook(string name);
   /**
      * Funzione di Stampa
      */
   void PrintTable();
   /**
      * Funzione di Cancellazione
      */
   void RemoveItem(string name);
};

#endif // LIBRERIA_H

libro.h
#ifndef LIBRO_H
#define LIBRO_H
#include<iostream>
#include<string>
#include"libreria.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

using namespace std;

class Libro
{
private:
    string ISBN;                      //ISBN (stringa 13 cifre)
    string autore;                    //un autore
    string titolo;                    //un titolo
    string editore;                   //un editore
    string anno_di_pubblicazione;      //anno di pubblicazione
    Libro* next;

public:
    Libro();
    //setter
    void setISBN(string ISBN);
    void setAuthor(string autore);
    void setTitle(string titolo);
    void setEditor(string editore);
    void setPublishYear(string anno_di_pubblicazione);
    void setNext(Libro* next);
    //getter
    string getISBN();
    string getAuthor();
    string getTitle();
    string getEditor();
    string getPublishYear();
    Libro* getNext();
};

#endif // LIBRO_H

# source file .cpp


libreria.cpp...
#include"libreria.h"


Libreria::Libreria()
{
    for(int i = 0; i < tableSize;i++)
    {
        HashTable[i] = new Libro;

        HashTable[i]->setISBN("empty");
        HashTable[i]->setTitle("empty");
        HashTable[i]->setAuthor("empty");
        HashTable[i]->setEditor("empty");
        HashTable[i]->setPublishYear("empty");
        HashTable[i]->setNext(NULL);
    }
}
/// inserimento
void Libreria::AddItem(string ISBN, string titolo, string autore, string editore, string anno_di_pubblicazione)
{
    int index = hashFun(ISBN);  /// la posizione viene creata dalla funzione Hash

    /// ANALISI E GESTIONE DELLE COLLISIONI

    /// Caso 0 se la cella nella posizione index è vuota
    if(HashTable[index]->getISBN() == "empty")
    {
        HashTable[index]->setISBN(ISBN);
        HashTable[index]->setTitle(titolo);
        HashTable[index]->setAuthor(autore);
        HashTable[index]->setEditor(editore);
        HashTable[index]->setPublishYear(anno_di_pubblicazione);
    }
    /// Caso 1 se la cella nella posizione index non è vuota
    else
    {
        Libro* Ptr = HashTable[index];
        Libro* n = new Libro;

        /// setto il nuovo elemento con i parametri passati alla funzione
        n->setISBN(ISBN);
        n->setAuthor(autore);
        n->setTitle(titolo);
        n->setEditor(editore);
        n->setPublishYear(anno_di_pubblicazione);
        n->setNext(NULL);
        while(Ptr->getNext() != NULL)
        {
            Ptr = Ptr->getNext();
        }
        Ptr->setNext(n);   /// next punterà al nuovo elemento
    }
}

int Libreria::NumberOfItemsInIndex(int index)
{
    int count = 0;

    if(HashTable[index]->getISBN() =="empty")
    {
        return count;
    }
    else
    {
       count++;
       Libro* Ptr = HashTable[index];
       while(Ptr->getNext() != NULL)
       {
           count++;
           Ptr = Ptr->getNext();
       }
    }
    return count;
}
/// ricerca
void Libreria:: FindBook(string ISBN)
{
 int index = hashFun(ISBN);
 bool foundISBN = false;
 string titolo;
 string autore;
 string editore;
 string anno_di_pubblicazione;
 Libro* Ptr = HashTable[index];
 while(Ptr != NULL)
 {
     if(Ptr->getISBN() == ISBN)
     {
         foundISBN =true;
         titolo= Ptr->getTitle();
         autore= Ptr->getAuthor();
         editore= Ptr->getEditor();
         anno_di_pubblicazione= Ptr->getPublishYear();
     }
     Ptr = Ptr->getNext();
 }
 if(foundISBN == true)
 {
     cout << endl;
     cout << "BOOK IDENTIFICATION" << endl;
     cout << "-------------------" << endl;
     cout << "-------------------" << endl;
     cout << "TITLE:" << titolo << endl;
     cout << "AUTHOR:" << autore << endl;
     cout << "EDITOR:" << editore << endl;
     cout << "PUBLISH YEAR:" << anno_di_pubblicazione << endl;
     cout << "-------------------" << endl;
     cout << "-------------------" << endl;
 }
 else
 {
     cout << ISBN<< "'s info was not found in the Hash Table\n";
 }
}
/// funzione hash
int Libreria:: hashFun(string key)
{
    int hash =0;
    int index;
   // index = key.length(); // lughezza stringa

  for(int i = 0; i < key.length(); i++)
  {
    hash = hash + (int)key[i]; // l' int convertono i caratteri nel lora valore ascii
    //cout << "hash = " << hash << endl;    mi serviva solo per la stampa delle key
  }
  index = hash % tableSize; /// 400/100 fa 4 con resto di 2


  return index;

}
/// stampa
void Libreria::PrintTable()
{
    int number;

    for(int i = 0; i <tableSize; i++)
    {

        number = NumberOfItemsInIndex(i);
        if(HashTable[i]->getISBN() != "empty")
        {cout << "-----------------\n";
        cout << "index = " << i << endl;
        cout << HashTable[i]->getISBN() << endl;
        cout << HashTable[i]->getTitle() << endl;
        cout << HashTable[i]->getAuthor() << endl;
        cout << HashTable[i]->getEditor() << endl;
        cout << HashTable[i]->getPublishYear() << endl;
        cout << "# Libri nella cella = " << number << endl;
        cout << "-----------------\n";
        }
    }
}

void Libreria:: RemoveItem(string ISBN)
{
    int index = hashFun(ISBN);

    Libro* delPtr;
    Libro* P1;
    Libro* P2;
/// ANALISI DEI VARI CASI DI CORRISPONDENZA


/// Caso 0 - la cella è vuota
  if(HashTable[index]->getISBN() == "empty" && HashTable[index]->getTitle() == "empty" && HashTable[index]->getAuthor() == "empty" && HashTable[index]->getEditor() == "empty" && HashTable[index]->getPublishYear() == "empty")
  {
      cout << ISBN << " was not found in the Hash Table\n";
  }

/// Caso 1 - solo un elemento è contenuto nella cella e l'elemento contiene quel nome
  else if(HashTable[index]->getISBN() == ISBN && HashTable[index]->getNext() == NULL)
  {
      HashTable[index]->setISBN("empty");
      HashTable[index]->setTitle("empty");
      HashTable[index]->setAuthor("empty");
      HashTable[index]->setEditor("empty");
      HashTable[index]->setPublishYear("empty");

      cout << ISBN << " was removed from the Hash Table\n";
  }
/// Caso 2 - la corrispondenza vi è nel primo elemento della cella ma ci sono molti altri elementi nella cella
  else if(HashTable[index]->getISBN()== ISBN)
  {
      delPtr = HashTable[index];
      HashTable[index] = HashTable[index]->getNext();
      delete delPtr;

      cout << ISBN << " was removed from the Hash Table\n";
  }
/// Caso 3 - la cella contiene degli elementi ma il primo elemento non ha corrispondenza
  else
  {
      P1 = HashTable[index]->getNext();
      P2 = HashTable[index];

      while(P1 != NULL && P1->getISBN() != ISBN)
      {
          P2 = P1;
          P1 = P1->getNext();
      }

/// Caso 3.1 - nessuna corrispondenza
      if(P1 == NULL)
      {
          cout << ISBN << " was not found in the Hash Table\n";
      }
/// Caso 3.2 - corrispondenza
      else
      {
          delPtr = P1;
          P1 = P1->getNext();
          P2->setNext(P1);
          delete delPtr;
          cout << ISBN << " was removed from the Hash Table\n";
      }
}
}
libro.cpp ...
#include "libro.h"

Libro::Libro()
{
}
// setter
void Libro::setISBN(string ISBN)
{
    this->ISBN=ISBN;
}
void Libro:: setAuthor(string autore)
{
    this->autore=autore;
}
void Libro:: setTitle(string titolo)
{
    this->titolo=titolo;
}
void Libro:: setEditor(string editore)
{
    this->editore=editore;
}
void Libro::setPublishYear(string anno_di_pubblicazione)
{
    this->anno_di_pubblicazione=anno_di_pubblicazione;
}
void Libro::setNext(Libro* next)
{
    this->next=next;
}
// getter
string Libro::getISBN()
{
    return ISBN;
}

string Libro::getAuthor()
{
    return autore;
}

string Libro::getTitle()
{
    return titolo;
}

string Libro::getEditor()
{
    return editore;
}

string Libro::getPublishYear()
{
    return anno_di_pubblicazione;
}

Libro *Libro::getNext()
{
    return next;
}

vi chiedo soltanto un ultima cosa se mi potete aiutare con una funzione hash piu performante
grazie mille a tutti !!!

S
SVNiko
Molto attivo
Iscritto da
set, 2014
Messaggi:
535
Re: AIUTO tabelle hash
07 gen 2015, 17:57
Che cosa intendi per funzione di hash più performante? Che non produce collisioni? In realtà ci sono studi matematici che dimostrano l'impossibilità dell'asserzione.

Ad ogni modo ci sono molte funzioni di hash realizzabili tutte con la loro dignità. Per una stringa potresti usare l'algoritmo di horner.

Devi accedere o registrarti per scrivere nel forum

21 risposte