Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.8 kB
2
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

#define key 5

class Hash{
    private:
        int table[key];
        int flag[key];
        int chain[key];
    public: 
        Hash();
        void Insert(int);
        void Display();
        int Search(int );
        void DisplayFlags();
        void DisplayChain();
};

Hash :: Hash(){
    for(int i=0; i<key; i++){
        table[i] = -1;
        flag[i] = 0;
        chain[i] = -1;
    }
}

void Hash :: Insert(int x){
    int loc = x%5;
    if(loc<key){
        if(flag[loc]==0){
            table[loc] = x;
            flag[loc] = 1; 
        }
        else{
            int origLoc = loc;
            int prevLoc = loc;
            while(flag[(loc)%key]==1){
                loc = (loc+1)%key;
                if(loc==origLoc){
                    cout<<"Table is full\n";
                    return;
                }
                if(table[loc]%key == origLoc && flag[loc]==1)
                    prevLoc = loc;
            }
            table[loc] = x;
            flag[loc] = 1;
            chain[prevLoc] = loc;
        }
    }
}

void Hash :: Display(){
    int i = 0;
    cout<<"Table is: \n";
    for(auto ele: table){
        cout<<i<<" -> "<<ele<<endl;
        i++;
    }
}

int Hash :: Search(int x){
    int index, newIndex;
    index = x%key;
    if(table[index] == x)
        return index;
    else{
        newIndex = chain[index];
        while(newIndex != -1){
            if(table[newIndex] == x)
                return newIndex;
            newIndex = chain[newIndex];
        }
        return -1;
    }
}

void Hash :: DisplayFlags(){
    cout<<"\nFlags: "<<endl;
    int j = 0;
    for(auto ele: flag){
        cout<<j<<" -> "<<ele<<endl;
        j++;
    }
}

void Hash :: DisplayChain(){
    cout<<"\nChain: "<<endl;
    int j = 0;
    for(auto ele: chain){
        cout<<j<<" -> "<<ele<<endl;
        j++;
    }
}

int main(){
    Hash h;
    int ele;
    int ch;

    do{
        cout<<"\n1.Insert\n2.Print\n3.Search \n4.Print Flags \n5.Print Chain \n0.Exit\n";
		cout<<"Enter choice : "<<endl;
		cin>>ch;

        switch(ch){
            case(1):
                cout<<"Enter element: ";
                cin>>ele;
                h.Insert(ele);
                break;
            case(2):
                h.Display();
                break;
            case(3):
                cout<<"Enter search element: ";
                cin>>ele;
                cout<<ele<<" found at index: "<<h.Search(ele);
                break;
            case(4):
                h.DisplayFlags();
                break;
            case(5):
                h.DisplayChain();
                break;
        }
    }while(ch<6 && ch>0);

    return 0;
}