#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#define INTCAPACITY 10
struct hashtable
{
int size;
int nelements;
struct listnode **array;
};
struct listnode
{
int data;
struct node *next;
};
//creating hashtable
struct hashtable * createhashtbl()
{
int i,position;
struct hashtable *htbl;
struct listnode *tmp;
htbl=malloc(sizeof(struct hashtable));
htbl->nelements=0;
htbl->size=INTCAPACITY;
htbl->array=malloc(INTCAPACITY*sizeof(struct listnode*));
for(i=0;i<INTCAPACITY;++i)
{
tmp=malloc(sizeof(struct listnode));
tmp->next=NULL;
htbl->array[i]=tmp;
}
printf("\n hash table created successfully");
return htbl;
}
//hash function u can use other hashfuntions
int hash(int key,int k)
{
return key%k;
}
//for each index in hash table im maintaing linked list with sorted order
int listinsert(struct listnode *head,int i)
{
struct listnode *temp,*q,*t;
if(head->next==NULL)
{
temp=(struct listnode *)malloc(sizeof(struct listnode));
temp->data=i;
temp->next=NULL;
head->next=temp;
}
else
{
temp=(struct listnode *)malloc(sizeof(struct listnode));
temp->data=i;
temp->next=NULL;
t=head;
q=head->next;
while(i>q->data&&q->next!=NULL)
{
t=q;
q=q->next;
}
if(i<q->data)
{
t->next=temp;
temp->next=q;
}
else if(q->next==NULL)
{
q->next=temp;
}
}
return 1;
}
//insert in to hashtable
int add(struct hashtable *htbl,int key)
{
int lf=1,position;
if(htbl->nelements/htbl->size>lf)
{
rehash(htbl);
}
position=hash(key,htbl->size);
if(listinsert(htbl->array[position],key))
{
htbl->nelements++;
return 1;
}
else
return 0;
}
//rehash when number of elements pointed to index crosses loadfactor we will do rehash
int rehash(struct hashtable *htbl)
{
int newsize,i,position;
struct listnode **newarray;
struct listnode *tmp,*current;
newsize=2*htbl->size;
newarray=malloc(newsize*sizeof(struct listnode *));
printf("entered to rehash");
for(i=0;i<newsize;i++)
{
tmp=malloc(sizeof(struct listnode));
tmp->next=NULL;
newarray[i]=tmp;
}
for(i=0;i<htbl->size;i++)
{
for(current=htbl->array[i];current->next!=NULL;)
{
tmp=current->next;
position=hash(tmp->data,newsize);
listinsert(newarray[position],tmp);
current->next=tmp->next;
}
}
htbl->size=newsize;
htbl->array=newarray;
return 1;
}
//find in likned list this will be used when searching a key in table
int findlink(struct listnode *root,int j)
{
struct listnode *temp=root->next;
if(temp==NULL) return 0;
while(temp->data<j&&temp->next!=NULL)
{
temp=temp->next;
}
if(temp->data==j)
return 1;
else return 0;
}
int find(struct hashtable *htbl,int j)
{
int k;
k=hash(j,htbl->size);
return findlink(htbl->array[k],j);
}
//remove node
int removenode(struct listnode *root,int j)
{
struct listnode *temp1,*temp2;
if(root->next==NULL) return 0;
temp1=root->next;
temp2=root;
while(temp1->next!=NULL&&temp1->data!=j)
{
temp2=temp1;
temp1=temp1->next;
}
if(temp1->data==j)
{
temp2->next=temp1->next;
free(temp1);
return 1;
}
else if(temp1->next==NULL)
return 0;
}
//remove1 function
void remove1(struct hashtable *htbl,int j)
{
int k,l;
k=hash(j,htbl->size);
l=removenode(htbl->array[k],j);
if(l==1)
{
htbl->nelements--;
printf("\n deleted successfully");
}
else printf("\n deletion not successfull given data not present in table");
}
void main()
{
struct hashtable *htbl;
int i,j;
while(1)
{
printf("\n ");
printf("\n enter 1 to initialize hashtable");
printf("\n enter 2 to add elements to hashtable");
printf("\n enter 3 to find whether elemnt is exist or not");
printf("\n enter 4 to delete elment");
scanf("%d",&i);
switch(i)
{
case 1:
htbl=createhashtbl();
break;
case 2:
printf("\n enter value");
scanf("%d",&j);
i=add(htbl,j);
if(i==1)
printf("\n entered successfully");
else printf("\n not success");
break;
case 3:
printf("\n enter element to find");
scanf("%d",&j);
j=find(htbl,j);
if(j) printf("\n element present in hashtable");
else printf("\n element not present in hashtable");
break;
case 4:
printf("\n enter elemnt to delete");
scanf("%d",&j);
remove1(htbl,j);
break;
}
}
}
comment here if this is usefull for anyone
#include<malloc.h>
#include<conio.h>
#define INTCAPACITY 10
struct hashtable
{
int size;
int nelements;
struct listnode **array;
};
struct listnode
{
int data;
struct node *next;
};
//creating hashtable
struct hashtable * createhashtbl()
{
int i,position;
struct hashtable *htbl;
struct listnode *tmp;
htbl=malloc(sizeof(struct hashtable));
htbl->nelements=0;
htbl->size=INTCAPACITY;
htbl->array=malloc(INTCAPACITY*sizeof(struct listnode*));
for(i=0;i<INTCAPACITY;++i)
{
tmp=malloc(sizeof(struct listnode));
tmp->next=NULL;
htbl->array[i]=tmp;
}
printf("\n hash table created successfully");
return htbl;
}
//hash function u can use other hashfuntions
int hash(int key,int k)
{
return key%k;
}
//for each index in hash table im maintaing linked list with sorted order
int listinsert(struct listnode *head,int i)
{
struct listnode *temp,*q,*t;
if(head->next==NULL)
{
temp=(struct listnode *)malloc(sizeof(struct listnode));
temp->data=i;
temp->next=NULL;
head->next=temp;
}
else
{
temp=(struct listnode *)malloc(sizeof(struct listnode));
temp->data=i;
temp->next=NULL;
t=head;
q=head->next;
while(i>q->data&&q->next!=NULL)
{
t=q;
q=q->next;
}
if(i<q->data)
{
t->next=temp;
temp->next=q;
}
else if(q->next==NULL)
{
q->next=temp;
}
}
return 1;
}
//insert in to hashtable
int add(struct hashtable *htbl,int key)
{
int lf=1,position;
if(htbl->nelements/htbl->size>lf)
{
rehash(htbl);
}
position=hash(key,htbl->size);
if(listinsert(htbl->array[position],key))
{
htbl->nelements++;
return 1;
}
else
return 0;
}
//rehash when number of elements pointed to index crosses loadfactor we will do rehash
int rehash(struct hashtable *htbl)
{
int newsize,i,position;
struct listnode **newarray;
struct listnode *tmp,*current;
newsize=2*htbl->size;
newarray=malloc(newsize*sizeof(struct listnode *));
printf("entered to rehash");
for(i=0;i<newsize;i++)
{
tmp=malloc(sizeof(struct listnode));
tmp->next=NULL;
newarray[i]=tmp;
}
for(i=0;i<htbl->size;i++)
{
for(current=htbl->array[i];current->next!=NULL;)
{
tmp=current->next;
position=hash(tmp->data,newsize);
listinsert(newarray[position],tmp);
current->next=tmp->next;
}
}
htbl->size=newsize;
htbl->array=newarray;
return 1;
}
//find in likned list this will be used when searching a key in table
int findlink(struct listnode *root,int j)
{
struct listnode *temp=root->next;
if(temp==NULL) return 0;
while(temp->data<j&&temp->next!=NULL)
{
temp=temp->next;
}
if(temp->data==j)
return 1;
else return 0;
}
int find(struct hashtable *htbl,int j)
{
int k;
k=hash(j,htbl->size);
return findlink(htbl->array[k],j);
}
//remove node
int removenode(struct listnode *root,int j)
{
struct listnode *temp1,*temp2;
if(root->next==NULL) return 0;
temp1=root->next;
temp2=root;
while(temp1->next!=NULL&&temp1->data!=j)
{
temp2=temp1;
temp1=temp1->next;
}
if(temp1->data==j)
{
temp2->next=temp1->next;
free(temp1);
return 1;
}
else if(temp1->next==NULL)
return 0;
}
//remove1 function
void remove1(struct hashtable *htbl,int j)
{
int k,l;
k=hash(j,htbl->size);
l=removenode(htbl->array[k],j);
if(l==1)
{
htbl->nelements--;
printf("\n deleted successfully");
}
else printf("\n deletion not successfull given data not present in table");
}
void main()
{
struct hashtable *htbl;
int i,j;
while(1)
{
printf("\n ");
printf("\n enter 1 to initialize hashtable");
printf("\n enter 2 to add elements to hashtable");
printf("\n enter 3 to find whether elemnt is exist or not");
printf("\n enter 4 to delete elment");
scanf("%d",&i);
switch(i)
{
case 1:
htbl=createhashtbl();
break;
case 2:
printf("\n enter value");
scanf("%d",&j);
i=add(htbl,j);
if(i==1)
printf("\n entered successfully");
else printf("\n not success");
break;
case 3:
printf("\n enter element to find");
scanf("%d",&j);
j=find(htbl,j);
if(j) printf("\n element present in hashtable");
else printf("\n element not present in hashtable");
break;
case 4:
printf("\n enter elemnt to delete");
scanf("%d",&j);
remove1(htbl,j);
break;
}
}
}
comment here if this is usefull for anyone
No comments:
Post a Comment