Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.3 kB
5
Indexable
Never

#include<iostream>
#define size 11
#define h(x) x%size
#define FALSE 0
#define TRUE 1
using namespace std;

class Hash{
	public:
		void insert(int data[],int flag[],int chain[],int x);
		int search(int data[],int flag[],int chain[],int x);
		void print(int data[],int flag[],int chain[]);
};

void Hash::insert(int data[],int flag[],int chain[],int x){
	int i=0,j,start;
	start=h(x);
	if(flag[start]==0){
		data[start]=x;
		flag[start]=1;
		return;
	}
	
	if(h(data[start])!=h(x)){
		i=0;
		j=start;
		while(flag[j] && i<size){
			j=(j+1)%size;
			i++;			
		}
		if(i==size){
			cout<<"\nHash is full"<<endl;
			return;
		}
		i=data[start]%size;
		while(chain[i] != start)
			i=chain[i];
		chain[i]=chain[start];
		while(chain[i]!=-1)
			i=chain[i];
		chain[i]=j;
		data[j]=data[start];
		chain[start]=-1;
		flag[j]=1;
		chain[j]=-1;
		data[start]=x;
		chain[start]=-1;
		return;		
	}
	
	i=0;
	j=start;
	while(flag[j] && i<size){
		j=(j+1)%size;
		i++;
	}
	if(i==size){
		printf("\nTable is full ...");
		return;
	}
	data[j]=x;
	flag[j]=1;
	chain[j]=-1;
	i=start;
	while(chain[i] != -1)
		i=chain[i];
	chain[i]=j;
}

int Hash::search(int data[],int flag[],int chain[],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 Hash::print(int data[],int flag[],int chain[]){
	int i;
	for(i=0;i<size;i++){
		if(flag[i]){
			cout<<"\n("<<i<<")\t"<<data[i]<<"\t"<<chain[i];
			}
		else{
			cout<<"\n("<<i<<")\t"<<"---"<<"\t"<<chain[i];
		}
	}
}

int main(){
	Hash h;
	int  data[size], flag[size], chain[size], x, op, loc, k;
	
	for(int i=0;i<size;i++){
		flag[i]=FALSE;
		chain[i]=-1;
	}
	
	do{
		cout<<"\n1.Insert\n2.Print\n3.Search\n0.Exit\n";
		cout<<"Enter choice : "<<endl;
		cin>>op;
		
		switch(op){
			case 1:
				cout<<"Enter element to be inserted : ";
				cin>>x;
				h.insert(data,flag,chain,x);
				break;
				
			case 2:
				h.print(data,flag,chain);
				break;
				
			case 3:
				cout<<"Enter element to search : ";
				cin>>k;
				loc=h.search(data,flag,chain,k);
				if(loc==-1)
					cout<<"Not Found\n";
				else
					cout<<"Found at location "<<loc<<endl;
				
		}
		
	}while(op!=0);
}