// Separate Chaining

#include<stdio.h>
#include<stdlib.h>
#define size 7
struct node
{
int ele;
struct node *next;
};
struct node *head[size]={NULL};
int hash(int e)
{
return(e%size);
}
void insert(int ele)
{
struct node *bucket,*ptr;
int key;
bucket=(struct node *)malloc(sizeof(struct node *));
bucket->ele=ele;
key=hash(ele);
if(head[key]==NULL)
{
head[key]=bucket;
head[key]->next=NULL;
}
else
{
ptr=head[key];
while(ptr->next!=NULL)
ptr=ptr->next;
ptr->next=bucket;
bucket->next=NULL;
}
}
void display()
{
int i;
struct node *ptr;
printf("\n Hash Table is:\n");
printf("KEY\tData\n");
for(i=0;i<size;i++)
{
printf("%d\t",i);
if(head[i]==NULL)
1
 {
printf("\n");
continue;
}
else
{
ptr=head[i];
while(ptr!=NULL)
{
printf("%d->",ptr->ele);
ptr=ptr->next;
}
}
printf("\n");
}
}
void search()
{
int key,x,f=0;
struct node *ptr;
printf("\n Enter an element to search in hash table");
scanf("%d",&x);
key=hash(x);
if(head[key]==NULL)
{
printf("\n Element not in hash table");
return;
}
else
{
ptr=head[key];
while(ptr!=NULL)
{
if(ptr->ele==x)
{
f=1;
break;
}
ptr=ptr->next;
}
if(f==1)

printf("\n Element found");

else
printf("\n Element not in hash table");
2
 }
}
int main()
{
int c,ele;
do
{
printf("1.INSERT \n2.DISPLAY\n3.SEARCH\n");
printf("\n Enter Your Choice:");
scanf("%d",&c);
if(c==1)
{
printf("\n Enter a number to insert into hash table:");
scanf("%d",&ele);
insert(ele);
}
if(c==2)
display();
if(c==3)
search();
}while(c!=0);
return 0;
}

3
//Linear Probing
#include<stdio.h>
#include<stdlib.h>
#define size 10
struct hash{
int key,hkey;
}ht[size];
void insert(int v){
int index=v%size;
if(ht[index].key==-1)
ht[index].key=v;
else{
for(int i=1;i<size;i++){
index=((v%size)+i)%size;
if(ht[index].key==-1){
ht[index].key=v;
break;
}
}
}
}
void search(int v){
int flag=0;
int index=v%size;
for(int i=0;i<size;i++){
index=((v%size)+i)%size;
if(ht[index].key==v){
flag=1;
break;
}

4
 }
if(flag==1)
printf("found");
else
printf("not found");
}
void display(){
printf("hkey\tkey\n");
for(int i=0;i<size;i++){
printf("%d\t%d\n",ht[i].hkey,ht[i].key);
}
}
int main(){
for(int i=0;i<size;i++){
ht[i].hkey=i;
ht[i].key=-1;
}
while(1){
int ch,v;
printf("1.insert\t2.search\t3.display\t4.exit\n");
printf("enter choice:");
scanf("%d",&ch);
switch(ch){
case 1:printf("enter value:");
scanf("%d",&v);
insert(v);
printf("\n");
break;
case 2:printf("enter value:");
scanf("%d",&v);

5
 search(v);
printf("\n");
break;
case 3:display();
printf("\n");
break;
case 4:exit(0);
}
}
return 0;
}

6
//Quadratic Probing
#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

int key,index,i,flag=0,hkey;
printf("\nenter a value to insert into hash table\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE;i++)
{

index=(hkey+i*i)%TABLE_SIZE;

if(h[index] == NULL)
{
h[index]=key;
break;
}
}
if(i == TABLE_SIZE)
printf("\nelement cannot be inserted\n");
}
void search()
{

int key,index,i,flag=0,hkey;
printf("\nenter search element\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE; i++)
{
index=(hkey+i*i)%TABLE_SIZE;
if(h[index]==key)
{
printf("value is found at index %d",index);
break;
}
}
if(i == TABLE_SIZE)
7
 printf("\n value is not found\n");
}
void display()
{
int i;

printf("\nelements in the hash table are \n");

for(i=0;i< TABLE_SIZE; i++)

printf("\nat index %d \t value = %d",i,h[i]);

}
main()
{
int opt,i;
while(1)
{
printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
scanf("%d",&opt);
switch(opt)
{
case 1:
insert();
break;
case 2:
display();
break;
case 3:
search();
break;
case 4:exit(0);
}
}
}

8
//DOUBLE HASHING
#include <stdio.h>
#define size 10
#define prime 7
struct hash
{
int hkey,key;
}ht[size];
void insert()
{
int ele,h1,h2,index,i;
printf("Enter the key");
scanf("%d",&ele);
h1=ele%size;
h2=prime-(ele%prime);

for( i=0;i<size;i++)
{ index=(h1+i*h2)%size;
if(ht[index].key == -1)
{
ht[index].key=ele;
break;
}

}
if(i==size)
printf("element can't be inserted");
}

void initially()
{
int i;
for(i=0;i<size;i++)
{
ht[i].key=-1;
ht[i].hkey=i;
}
}
void search()
{

int ele,h1,h2,index,i;
printf("eneter the key");
scanf("%d",&ele);
h1=ele%size;
h2=prime-(ele%prime);
9
 for( i=0;i<size;i++)
{
index=(h1+i*h2)%size;
if(ht[index].key == ele)
{
printf("value is found at index %d",index);
break;
}

}
if(i==size)
printf("\n value is not found\n");
}

void display()
{int i;
for(i=0;i<size;i++)
printf("hash_table[%d]=%d\n",ht[i].hkey,ht[i].key);
}
int main() {

initially();
insert();
insert();
insert();
insert();
display();
search();
return 0;
}

10
//BST

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *lchild;
struct node *rchild;
};
typedef struct node * tree;

tree findmin(tree root);

tree insert(tree,int);
void inorder(tree);
void preorder(tree);
void postorder(tree);
tree find(tree,int);
tree del(tree,int);

void main()
{
int ch,data;
char res;
tree root=NULL,p;
clrscr();
do
{
printf("\n****MENU****\n");
printf("\n1.INSERT\n2.PREORDER TRAVERSAL\n3.INORDER
TRAVERSAL\n4.POSTORDER TRAVERSAL\n7.SEARCH\n8.DELETE\n");
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\nEnter the data to be inserted:");
scanf("%d",&data);
root=insert(root,data);
break;
case 2:preorder(root);
break;
case 3:inorder(root);
break;
11
 case 4:postorder(root);
break;

case 5:printf("\nEnter the data to be searched:");

scanf("%d",&data);
p=find(root,data);
printf("\nThe element %d is found.",p->data);
break;
case 6: printf("\nEnter the data to be deleted:");
scanf("%d",&data);
root=del(root,data);
break;

case 7:exit(0);
}
}while(1);
}

tree insert(tree root,int data)

{
if(root==NULL)
{
root=(tree)malloc(sizeof(struct node));
root->data=data;
root->lchild=NULL;
root->rchild=NULL;
}
else if(data < root->data)
root->lchild=insert(root->lchild,data);
else
root->rchild=insert(root->rchild,data);
return root;
}

void inorder(tree root)

{
if(root!=NULL)
{
inorder(root->lchild);
printf("%d\t",root->data);
inorder(root->rchild);
}
}

void preorder(tree root)

{
12
 if(root!=NULL)
{
printf("%d\t",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}

void postorder(tree root)

{
if(root!=NULL)
{
postorder(root->lchild);
postorder(root->rchild);
printf("%d\t",root->data);
}
}

tree find(tree root,int data)

{
if(root==NULL)
return NULL;
if(data < root->data)
return find(root->lchild,data);
else if(data > root->data)
return find(root->rchild,data);
else
return root;
}

tree del(tree root, int data)

{
if(root==NULL)
printf("\nElement not found");
else if(data < root->data)
root->lchild=del(root->lchild,data);
else if(data > root->data)
root->rchild=del(root->rchild,data);
else
{
if(root->lchild==NULL && root->rchild==NULL)
13
 {
root=NULL;
}
else if(root->lchild==NULL)
{
root=root->rchild;
}

else if(root->rchild==NULL)
{
root=root->lchild;
}
else
{
tree temp=findmin(root->rchild);
root->data=temp->data;
root->rchild=del(root->rchild,temp->data);
}
}
return root;
}

tree findmin(tree root)

{
int r;
if(root==NULL)
return NULL;
else if(root->lchild==NULL)
return root;
else
return findmin(root->lchild);
}

14
// AVL Tree

#include<stdio.h>
#include<stdlib.h>

typedef struct node

{
int data;
struct node *left,*right;
int ht;
}node;

node *insert(node *,int);

node *Delete(node *,int);
void preorder(node *);
void inorder(node *);
int height( node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);

int main()
{
node *root=NULL;
int x,n,i,op;
do
{
printf("\n1)Create:");
printf("\n2)Insert:");
printf("\n3)Delete:");
printf("\n4)Print:");
printf("\n5)Quit:");
printf("\n\nEnterYour Choice:");
scanf("%d",&op);
switch(op)
{
case 1:printf("\nEnter no. of elements:");
scanf("%d",&n);
printf("\nEnter tree data:");
root=NULL;
15
 for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
break;
case 2:

printf("\nEnter a data:");
scanf("%d",&x);
root=insert(root,x);
break;
case 3:

printf("\nEnter a data:");
scanf("%d",&x);
root=Delete(root,x);
break;
case 4: printf("\nPreordersequence:\n");
preorder(root);
printf("\nnInordersequence:\n");
inorder(root);
printf("\n");
break;
}
}while(op!=5);
return 0;
}
node * insert(node *T,int x)
{
if(T==NULL)
{
T=(node*)malloc(sizeof(node));
T->data=x;
T->left=NULL;
T->right=NULL;
}

else if(x> T->data) /* insertion right subtree*/

{
T->right=insert(T->right,x);
if(BF(T)==-2)
if(x>T->right->data)
T=RR(T);
16
 else
T=RL(T);
}
else if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
if(x< T->left->data)
T=LL(T);
else
T=LR(T);
}
T->ht=height(T);
return(T);
}

node * Delete(node *T,int x)

{
node *p;
if(T==NULL)
{
return NULL;
}
else if(x> T->data)/* insertin right subtree*/
{
T->right=Delete(T->right,x);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else if(x<T->data)
{
T->left=Delete(T->left,x);
if(BF(T)==-2)/*Rebalanceduring windup*/
if(BF(T->right)<=0)
T=RR(T);
else
T=RL(T);
}
else
{
/*data to be deleted is found*/
if(T->right!=NULL)
17
 { /*delete its inordersuccesor*/
p=T->right;
while(p->left!= NULL)
p=p->left;
T->data=p->data;
T->right=Delete(T->right,p->data);

if(BF(T)==2)/*Rebalanceduring windup*/
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
return(T->left);
}
T->ht=height(T);
return(T);
}

int height(node *T)

{
int lh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;

if(lh>rh)
return(lh);
return(rh);
}

node * rotateright(node *x)

{
node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
18
 y->ht=height(y);
return(y);
}

node * rotateleft(node *x)

{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * RR(node *T)
{
T=rotateleft(T);
return(T);
}
node * LL(node *T)
{
T=rotateright(T);
return(T);
}
node * LR(node *T)
{
T->left=rotateleft(T->left);
T=rotateright(T);
return(T);
}
node * RL(node *T)
{
T->right=rotateright(T->right);
T=rotateleft(T);
return(T);
}
int BF(node *T)
{
int lh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
19
 if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
return(lh-rh);
}

void preorder(node *T)

{
if(T!=NULL)
{
printf("%d(Bf=%d)",T->data,BF(T));
preorder(T->left);
preorder(T->right);
}
}
void inorder(node *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%d(Bf=%d)",T->data,BF(T));
inorder(T->right);
}
}

20
//HeapSort
#include<stdio.h>
void max_heapify(int arr[], int n, int i)
{
int t;
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
t=arr[i];
arr[i]=arr[largest];
arr[largest]=t;
max_heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n)

{
int i,t;
for ( i = n / 2 - 1; i >= 0; i--)
max_heapify(arr, n, i);
for (i=n-1; i>=0; i--)
{
t=arr[i];
arr[i]=arr[0];
arr[0]=t;
max_heapify(arr, i, 0);
}
}

int main()
{
int arr[100],n,i;
printf("Enter number of nodes:\n");
scanf("%d",&n);
printf("Enter array elemets:");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
21
 heapSort(arr, n);
printf("Sorted list:\n");
for (i=0; i<n; ++i)
printf("%3d",arr[i]);

22