#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int modulo=91; //od tego zalezy ile będzie pozycji w tablicy, proponowałbym liczbe pierwszą w okolicach np. ilosc wyrazow / 2 albo /3
struct Node
{
char* val;
Node* next;
};
int hash(const char* slowo);
void add(char* klucz, Node*& lista);
void search(char* klucz, Node* lista);
int main()
{
char* buf=new char[150]; //zakładam ze dłuższego slowa nie będzie :P
int ile;
cout<<"Ile elementow?"<<endl;
cin>>ile;
Node** tablica = new Node*[modulo]; //nasza tablica z hashująca
for (int i=0;i<modulo;i++)
tablica[i]=NULL;
for (int i=0;i<ile;i++)
{
cin>>buf; //wczytywanie wyrazów do tablicy
char* str = new char[150];
strcpy(str,buf);
add(str, tablica[hash(str)]); //dodawanie kolejnych wyrazów do tablicy
}
for (int i=0;i<modulo;i++) //wypisanie tablicy
{
Node* rob=tablica[i];
cout<<"Tablica["<<i<<"] =";
while(rob)
{
cout<<" "<<rob->val;
rob=rob->next;
}
cout<<endl;
}
cout<<"Czego szukac?"<<endl;
cin>>buf;
search(buf, tablica[hash(buf)]);
cin.sync();
cin.get();
return EXIT_SUCCESS;
}
//////////////////////////////////////////////////////////
int hash(const char* slowo)
{
int ret=0;
int n=strlen(slowo); //dlugosć słowa
while(n>=sizeof(int)) //dopóki są kawałki po 4 bajty
{
ret^=*(int*)slowo; //xor na 4 bajtach
n-=sizeof(int); //"skracamy słowo"
slowo+=sizeof(int); //przesuwamy sie dalej
}
int rem=0; //to co nam zostało, tzn 1,2 lub 3 bajty
while(n--)
{
rem<<=8; //przesuwamy się o 1 bajt
rem^=*slowo++; //xor
}
ret^=rem;
return ret%modulo;
}
//////////////////////////////////////////////////////////
void add(char* klucz, Node*& lista)
{
Node* tmp = new Node;
tmp->val = klucz;
tmp->next = lista;
lista=tmp;
}
/////////////////////////////////////////////////////////////
void search(char* klucz, Node* lista)
{
int ile = 1;
if (!lista)
cout<<"Brak, lista dla danego hasha pusta"<<endl;
else
{
while((lista) && (strcmp(lista->val,klucz)))
{
lista=lista->next;
ile++;
}
if (lista && !strcmp(lista->val,klucz))
cout<<klucz<<" znalezione po "<<ile<<" porownaniach"<<endl;
}
}