Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.7 kB
1
Indexable
Never
#include <iostream>
#define SIZE 11              
#define FALSE 0
#define TRUE 1
#define h(x) x%SIZE         

class HashTable {
    int data[SIZE];
    int flag[SIZE];
    int chain[SIZE];

    public:
    HashTable() {
        for(int i = 0; i < SIZE; i++) {
            flag[i] = FALSE;
            chain[i] = -1;
        }
    }

    void insert(int x) {
        int i = 0, j, start;
        start = h(x); 
        while(flag[start] && i < SIZE) {
            if(data[start] % SIZE == x % SIZE)   
                break;                  
            i++;
            start = (start + 1) % SIZE;
        }

        if(i == SIZE) {
            std::cout << "\n***hash table is full****";
            return;
        }

        while(chain[start] != -1)
            start = chain[start];

        j = start;
        while(flag[j] && i < SIZE) {
            j = (j + 1) % SIZE;
            i = i + 1;
        }
        if(i == SIZE) {
            std::cout << "\n***hash table is full****";
            return;
        }

        data[j] = x;   
        flag[j] = TRUE;
        if(j != start)
            chain[start] = j;
    }

    int search(int x) {
        int i = 0, j;
        j = h(x); 
        while(i < SIZE && flag[j] && data[j] % SIZE != x % SIZE) {
            i++;
            j = (j + 1) % SIZE;
        }
        if(!flag[j] || i == SIZE)
            return -1;

        while(j != -1) {
            if(data[j] == x)
                return j;
            j = chain[j];
        }
        return -1;
    }

    void print() {
        for(int i = 0; i < SIZE; i++) {
            if(flag[i])
                std::cout << "\n(" << i << ") " << data[i] << "     " << chain[i];
            else
                std::cout << "\n(" << i << ") ---    " << chain[i];
        }
    }
};

int main() {
    HashTable table;
    int x, op, loc;

    do {
        std::cout << "\n\n1)Insert\n2)Search\n3)Print\n4)Quit";
        std::cout << "\nEnter Your Choice : ";
        std::cin >> op;
        switch(op) {
            case 1: 
                std::cout << "\n Enter a number to be inserted:";
                std::cin >> x;
                table.insert(x);
                break;
            case 2: 
                std::cout << "\n Enter a number to be searched :";
                std::cin >> x;
                loc = table.search(x);
                if(loc == -1)
                    std::cout << "\n****Element not found****";
                else
                    std::cout << "\n***Found at the location=" << loc;
                break;
            case 3: 
                table.print();
                break;
        }
    } while(op != 4);

    return 0;
}