Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<list>
- #include<vector>
- #include<cmath>
- using namespace std;
- class hashtable{
- public:
- list<string> table[5];
- int size;
- int elements_count;
- int collisions_count;
- void insert(string s){
- //consists in generating the hash function of the correspondent string and doing the push_back in table[hash]
- int h = hash(s);
- table[h].push_back(s);
- collisions_count++;
- }
- int hash(string s){
- int cont=0;
- int hax=0;
- int ind =0;
- int p=31; //arbitrary value that fits very well when equal to 31.
- for(int i=0;i<s.size();i++)
- {
- hax=int(hax+ int(s[i])*pow(p,cont))%size;
- cont++;
- };
- return hax;
- }
- void search(string s){
- int index = hash(s);
- int cont=0;
- for(auto x: table[index])
- {
- cont++;
- if(x == s)
- {
- cout<<s<<" encontrado(a) no index: "<<index<<" apos: "<<cont<<" acessos.";
- break;
- }
- }
- }
- void del(string s){
- }
- void print(){
- //just in case
- for(int i=0;i<size;i++)
- {
- for(auto d: table[i])
- cout<<d<<" ";
- cout<<", ";
- }
- cout<<endl;
- }
- };
- int main(void){
- hashtable h;
- h.size = 5;
- h.elements_count = 0;
- h.collisions_count=0;
- //time to learn to print an array of lists of strings :]
- //think we should start declaring one ;]
- int v=3;
- list<string>l[v];
- string au;
- getline(cin,au);
- h.insert(au);
- getline(cin,au);
- h.insert(au);
- getline(cin,au);
- h.insert(au);
- h.print();
- cout<<"insira uma palavra para ser buscada"<<endl;
- getline(cin,au);
- h.search(au);
- cout<<endl;
- //h.print();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement