Natchatran

NATCHATRAN

Natchatran Blogs includes Technical Tutorials, E-books, Notes, Lab Manual, Question Banks, Viva questions and Interview questions for engineering students, provides all study material for cse students.

-Natchatran(Prem Anandh.J)

Tuesday, August 20, 2013

CS 2063 Grid Computing -Syllabus

CS 2063 GRID COMPUTING

SEMESTER VIII – Elective VI

UNIT I           CONCEPTS AND ARCHITECTURE     9
Introduction-Parallel and Distributed Computing-Cluster Computing-Grid Computing-
Anatomy and Physiology of Grid-Review of Web Services-OGSA-WSRF.
UNIT II          GRID MONITORING         9
Grid Monitoring Architecture (GMA) - An Overview of Grid Monitoring Systems- Grid
ICE – JAMM -MDS-Network Weather Service-R-GMA-Other Monitoring Systems-
Ganglia and GridMon
UNIT III        GRID SECURITY AND RESOURCE MANAGEMENT         
Grid Security-A Brief Security Primer-PKI-X509 Certificates-Grid Security-Grid
Scheduling and Resource Management-Scheduling Paradigms- Working principles of
Scheduling -A Review of Condor, SGE, PBS and LSF-Grid Scheduling with QoS.
UNIT IV        DATA MANAGEMENT AND GRID PORTALS           9
Data Management-Categories and Origins of Structured Data-Data Management
Challenges-Architectural Approaches-Collective Data Management Services-Federation
Services-Grid Portals-First-Generation Grid Portals-Second-Generation Grid Portals.
UNIT V          GRID MIDDLEWARE       9
List of globally available Middlewares - Case Studies-Recent version of Globus Toolkit
and gLite - Architecture, Components and Features.

TOTAL: 45 PERIODS

TEXT BOOK:
1. Maozhen Li, Mark Baker, The Grid Core Technologies, John Wiley & Sons ,2005.

REFERENCES:
1. Ian Foster & Carl Kesselman, The Grid 2 – Blueprint for a New Computing
Infrascture , Morgan Kaufman – 2004
2. Joshy Joseph & Craig Fellenstein, “Grid Computing”, Pearson Education 2004.
3. Fran Berman,Geoffrey Fox, Anthony J.G.Hey, “Grid Computing: Making the Global

Infrastructure a reality”, John Wiley and sons, 2003.

Monday, August 5, 2013

CS2208 - Data Structures Lab

CS2208 - Data Structures Lab - Manual

EX.NO:1
Implementation of singly linked list
Aim:
To write a program for implement singly linked list.
Algorithm:
Step 1:             Create linked list by given elements one by one.
Step 2:             Perform the operation on insert, delete and display the elements in the list.
Step 3:             Insert an element at given position and check whether the list is full or not.
Step 4:             Delete an element at given position.
Step 5:             Before deletion to check whether the list is empty or not.
Step 6:             Display all the elements in the list.
           
Source Code:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
struct node *find(int);
struct node *findprevious(int);
struct node
{
int element;
struct node *next;
}*List=NULL,*p;
void insert(int X);
void deletion(int X);
void display();
void insert(int X)
{
struct node *newnode;
int pos;
newnode=(struct node *)malloc(sizeof(struct node));
newnode->element=X;
if(List->next==NULL)
{
List->next=newnode;
newnode->next=NULL;
}
else
{
printf("\n\nenter the value after which the element to be inserted\t:");
scanf("%d",&pos);
p=find(pos);
newnode->next=p->next;
p->next=newnode;
}
}
struct node *find(int s)
{
p=List->next;
while(p!=NULL && p->element!=s)
p=p->next;
return p;
}
void deletion(int X)
{
struct node *temp;

temp=(struct node *)malloc(sizeof(struct node));
p=findprevious(X);
if(p->next!=NULL)
{
temp=p->next;
p->next=temp->next;
printf("\n\nthe deleted element is\t %d",temp->element);
free(temp);
}
else
{
printf("\n\nelement not found");
}
}
struct node *findprevious(int s)
{
p=List;
while(p->next!=NULL&&p->next->element!=s)
p=p->next;
return p;
}
void display()
{
if(List->next==NULL)
printf("\n\nlist is empty");
else
{
p=List->next;
printf("\n\n the contents of the list are\t:\n\n");
while(p!=NULL)
{
printf("%d-->",p->element);
p=p->next;
}
printf("NULL");
}
}
void main()
{
int data,ch;
clrscr();
printf("\t\t\tSingle linked list\n");
printf("\t\t\t******************\n");
printf("1.insert\n2.delete\n3.display\n4.exit\n");
do
{
printf("\n\nenter ur choice\t:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf(" \n\nenter the element to insert\t:");
scanf("%d",&data);
insert(data);
break;
case 2:
printf(" \n\nenter the element to delete\t:");
scanf("%d",&data);
deletion(data);
break;
case 3:
display();
break;
case 4:
exit(0);
}
}
while(ch<4);
getch();
}


Sample Output:
 Single linked list                       
1.insert
2.delete
3.display
4.exit
enter ur choice :1
enter the element to insert     :7
enter ur choice :1
enter the element to insert     :9
enter the value after which the element to be inserted  :7
enter ur choice :1
enter the element to insert     :11
enter the value after which the element to be inserted  :9
enter ur choice :1
enter the element to insert     :31
enter the value after which the element to be inserted  :11
enter ur choice :1
enter the element to insert     :33
enter the value after which the element to be inserted  :31
enter ur choice :3
 the contents of the list are   :
7-->9-->11-->31-->33-->NULL
enter ur choice :2
enter the element to delete     :11
the deleted element is   11
enter ur choice :3
 the contents of the list are   :
7-->9-->31-->33-->NULL
enter ur choice :2
enter the element to delete     :31
the deleted element is   31
enter ur choice :3
 the contents of the list are   :
7-->9-->33-->NULL
enter ur choice :4

EX.NO:2
Implementation of doubly linked list
Aim:

To write a program for implement doubly linked list.
Algorithm:

Step 1:             Create linked list by given elements one by one.
Step 2:             Perform the operation on insert, delete and display the elements in the list.
Step 3:             Insert an element at given position and check whether the list is full or not.
Step 4:             Delete an element at given position.
Step 5:             Before deletion to check whether the list is empty or not.
Step 6:             Display all the elements in the list.



Source Code:
#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *ptr1,*ptr2;
}*head;
struct node *ins_beg(int x,struct node *first);
struct node *ins_end(int x,struct node *first);
struct node *dele(struct node *first,int del);
void display(struct node *first);
void main()
{
int x,del,ch;
head=NULL;
clrscr();
printf("\t\t\tDoubly linked list\n");
printf("\t\t\t******************\n");
printf("1.insert_beg\n2.insert_end \n3.delete\n4.display\n5.exit\n");
while(1)
{
printf("\n\nenter ur choice\t:");
scanf("%d",&ch);
switch(ch)
{
case 1:
            printf(" \n\nenter the element to insert\t:");
            scanf("%d",&x);
            head=ins_beg(x,head);
            break;

case 2:
            printf(" \n\nenter the element to insert\t:");
            scanf("%d",&x);
            head=ins_end(x,head);
            break;

case 3:
            printf(" \n\nenter the element to delete\t:");
            scanf("%d",&del);
            head=dele(head,del);
            break;
case 4:
            display(head);
            break;
case 5:
            exit(0);
default:
            printf("\n\nInvalid entry.....!!!!!");
            getch();
}
}
getch();
}
struct node *ins_beg(int x,struct node *first)
{
struct node *new,*cur,*prev;
new=(struct node *)malloc(sizeof(struct node));
if(first==NULL)
{
new->data=x;
new->ptr1=NULL;
new->ptr2=NULL;
return new;
}
else
{
new->data=x;
new->ptr1=NULL;
new->ptr2=first;
return new;
}
}
struct node *ins_end(int x,struct node *first)
{
struct node *new,*cur,*prev;
new=(struct node *)malloc(sizeof(struct node));
if(first==NULL)
{
new->data=x;
new->ptr1=NULL;
new->ptr2=NULL;
return new;
}
else
{
cur=first;
while(cur->ptr2!=NULL)
{
prev=cur;
cur=cur->ptr2;
}
cur->ptr2=new;
new->data=x;
new->ptr1=cur;
new->ptr2=NULL;
return first;
}
}
void display(struct node *first)
{
struct node *temp;
temp=first;
if(temp==NULL)
printf("\n\nlist is empty");
while(temp!=NULL)
{
printf("%d-->",temp->data);
temp=temp->ptr2;
}
getch();
}
struct node *dele(struct node *first,int del)
{
struct node *prev,*cur;
cur=first;
if(first==NULL)
{
printf("\n\n No Data Present!!!");
getch();
}
else if(first->data==del)
{
printf("\n\n data %d is deleted",first->data);
first=first->ptr2;
getch();
return first;
}
else
{
while(cur->ptr2!=NULL&&cur->data!=del)
{
prev=cur;
cur=cur->ptr2;
}
if(cur->ptr2==NULL&&cur->data!=del)
printf("\n\ndata not presented!");
if(cur->ptr2!=NULL&&cur->data==del)
{
prev->ptr2=cur->ptr2;
(cur->ptr2)->ptr1=prev;
printf("\n\ndata %d is deleted",cur->data);
}
else if(cur->ptr2==NULL&&cur->data==del)
{
prev->ptr2=NULL;
printf("data %d is deleted",cur->data);
}
getch();
return first;
}
}

Sample Output:

                         Doubly linked list
1. insert_beg
2. insert_end
3. delete
4. display
5. exit

Enter ur choice :1
enter the element to insert     :10
enter ur choice :1
enter the element to insert     :20
enter ur choice :1
enter the element to insert     :30
enter ur choice :4
30-->20-->10-->
enter ur choice :2
enter the element to insert     :5
enter ur choice :4
30-->20-->10-->5-->
enter ur choice :3
enter the element to delete     :20
data 20 is deleted
enter ur choice :4
30-->10-->5-->
enter ur choice :5




EX.NO:3
Polynomial addition using linked list
Aim:

Write a program to implement polynomial addition using linked list.
Algorithm:

Step 1:             Build a polynomial by entering it term by term.
Step 2:             The function must first check to see if there is a term with that exponent in the polynomial (find).
Step 3:             If there is not the function will insert the term. If there is, the function will first remove the existing term and then insert the new term.
Step 4:             Add the two polynomials to produce a new polynomial and return their sum.
Step 5:             Print out the three polynomials in the form.
                        Term1+term2+……..+term N
                        +term 1+term 2+……+term N
                        Term 1+term 2+……..+term N
Step 6:             Evaluate the polynomial that was the result of 2 given a value form the user.
Step 7:             Clear the polynomials and start again.

SourceCode:             

#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<alloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct pnode
{
float coef;
int exp;
struct pnode *next;
}p;
void main()
{
p *p1,*p2,*p3;
p *get_poly(),*add(p*,p*);
void display(p*);
clrscr();
printf("POLYNOMIAL ADDITION\n");
printf("^^^^^^^^^^^^^^^^^^^\n\n");
printf("\n\nEnter the first polynomial");
printf("\n**************************");
p1=get_poly();
printf("\n\nEnter the second polynomial");
printf("\n***************************");
p2=get_poly();


printf("\n\n\nThe first polynomial is\t:\n\n");
display(p1);
printf("\n\n\nThe second polynomial is\t:\n\n");
display(p2);
p3=add(p1,p2);
printf("\n\nThe addition of the polynomial is....\n\n");
printf("\n----------------------------------------\n\n");
display(p3);
exit(0);
}
p *get_poly()
{
p *temp,*New,*last;
int exp,flag;
float coef;
p *get_node();
char ans='y';
temp=NULL;
flag=TRUE;
printf("\n\nEnter the polynomial is desending order of exponent......");
do
{
printf("\n\nEnter the coefficient and exponent of a term:\n\n");
scanf("%f\t%d",&coef,&exp);
New=get_node();
if(New==NULL)
printf("\n\nmemory cannot be allocated");
New->coef=coef;
New->exp=exp;

if(flag==1)
{
temp=New;
last=temp;
flag=FALSE;
}
else
{
last->next=New;
last=New;
}
printf("\n\n......Do you want to add more terms(y/n)?......\n");
ans=getch();
}
while(ans=='y');
return(temp);
}
p *get_node()
{
p *temp;
temp=(p*)malloc(sizeof(p));
temp->next=NULL;
return(temp);
}
void display(p *head)
{
p *temp;
temp=head;
if(temp==NULL)
{
printf("\n\nthe polynomial is empty\n");
getch();
return;
}
printf("\n");
while(temp->next!=NULL)
{
printf("%0.1fx^%d+",temp->coef,temp->exp);
temp=temp->next;
}
printf("%0.1fx^%d+",temp->coef,temp->exp);
getch();
}
p *add(p* first,p* second)
{
p *p1,*p2,*temp,*dummy;
char ch;
float coef;
p *append(int,float,p*);
p1=first;
p2=second;
temp=(p*)malloc(sizeof(p));
if(temp==NULL)
printf("\n\nMemory cannot be allocated");
dummy=temp;
while(p1!=NULL && p2!=NULL)
{
if(p1->exp==p2->exp)
{
coef=p1->coef+p2->coef;
temp=append(p1->exp,coef,temp);
p1=p1->next;
p2=p2->next;
}
else if(p1->exp<p2->exp)
{
coef=p2->coef;
temp=append(p2->exp,coef,temp);
p2=p2->next;
}
else if(p1->exp>p2->exp)
{
coef=p1->coef;
temp=append(p1->exp,coef,temp);
p1=p1->next;
}
}
while(p1!=NULL)
{
temp=append(p1->exp,p1->coef,temp);
p1=p1->next;
}
while(p2!=NULL)
{
temp=append(p2->exp,p2->coef,temp);
p2=p2->next;
}
temp->next=NULL;
temp=dummy->next;
free(dummy);
return(temp);
}

p *append(int exp,float coef,p *temp)
{
p *New,*dummy;
New=(p*)malloc(sizeof(p));
if(New==NULL)
printf("\n\nMemory cannot be allocated\n");
New->exp=exp;
New->coef=coef;
New->next=NULL;
dummy=temp;
dummy->next=New;
dummy=New;
return(dummy);
}

Sample Output:
POLYNOMIAL ADDITION
^^^^^^^^^^^^^^^^^^^
Enter the first polynomial
**************************
Enter the polynomial is descending order of exponent......
Enter the coefficient and exponent of a term:

7
4

......Do you want to add more terms(y/n)?......
Enter the coefficient and exponent of a term:

3
3
......Do you want to add more terms(y/n)?......
Enter the coefficient and exponent of a term:

5
2
......Do you want to add more terms(y/n)?......


Enter the coefficient and exponent of a term:
2
1
......Do you want to add more terms(y/n)?......
2
1
......Do you want to add more terms(y/n)?......


Enter the second polynomial
***************************
Enter the polynomial is desending order of exponent......
Enter the coefficient and exponent of a term:
4
3
......Do you want to add more terms(y/n)?......
Enter the coefficient and exponent of a term:

7
1
......Do you want to add more terms(y/n)?......
The first polynomial is :
7.0x^4+3.0x^3+5.0x^2+2.0x^1+
The second polynomial is        :
4.0x^3+7.0x^1+
The addition of the polynomial is....
________________________________________
7.0x^4+7.0x^3+5.0x^2+9.0x^1+

EX.NO:4
Array Implementation of stack
Aim:

Write a program to implement stack ADT using Array.
Algorithm:

Step 1:             Get the elements.
Step 2:             Push the elements in to the stack by adding new element in the stack.
Step 3:             Check whether stack is full or empty.
Step 4:             Pop elements from the stack by deleting element in the top.
Step 5:             Check whether stack is empty or not.
Step 6:             Display the top of the element in the stack using Top.
Step 7:             Display all the elements in the list.

Source Code:
                                    //ARRAY IMPLEMENTATION OF STACK//
#include<stdio.h>
#include<conio.h>
#define size 3
int stack[size],top=-1,b,cn;
int c,res;
void push();
void pop();
void display();
void push()
{
if(top>=size)
{
printf("\n\n stack overflow");
return;
}
else
{
printf("\n\nenter num to push\t:");
scanf("%d",&b);
top++;
stack[top]=b;
printf("\n\nnum %d is pushed",stack[top]);
return;
}
}

void pop()
{
if(top==-1)
{
printf("\n\nstack underflow");
return;
}
else
{
res=stack[top];
top--;
printf("\n\nNum %d is deleted",res);
return;
}
}
void display()
{
int i;
if(top==-1)
{
printf("\n\nstack underflow");
return;
}
for(i=0;i<=top;i++)
{
printf("%d\t",stack[i]);
}
}

void main()
{
int ch;
clrscr();
printf(" ARRAY IMPLEMENTAION OF STACK\n");
printf("  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
printf("\n1.Push\n2.Pop\n3.Display\n");

do
{
printf("\n\n enter ur choice\t:");
scanf("%d",&ch);
switch(ch)
{
case 1:
            push();
            break;
case 2:
            pop();
            break;

case 3:
            printf("\n\n contents of the stack are\t:\n");
            display();
            break;

default:
printf("\n\nInvalid Choice!!!!!!!");
exit(0);
}
}
while(ch<4);
getch();
}


Sample Output:
ARRAY IMPLEMENTAION OF STACK
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

1.Push
2.Pop
3.Display


 enter ur choice        :1

enter num to push       :10

num 10 is pushed

 enter ur choice        :1

enter num to push       :20

num 20 is pushed

 enter ur choice        :1

num 40 is pushed

 enter ur choice        :1

 stack overflow

 enter ur choice        :3

 contents of the stack are      :

10      20      30      40

 enter ur choice        :2

Num 40 is deleted

 enter ur choice        :3

 contents of the stack are      :

10      20      30

 enter ur choice        :2

Num 30 is deleted

 enter ur choice        :3

 contents of the stack are      :

10      20

enter ur choice        :1

enter num to push       :50

num 50 is pushed

enter ur choice        :3

 contents of the stack are      :

10      20      50

 enter ur choice        :4


EX.NO:5
Implementation of stack using linked list
Aim:

Write a program to implement stack ADT using linked list.
Algorithm:

Step 1:             Get the elements.
Step 2:             Push the elements in to the stack by adding new element in the stack.
Step 3:             Check whether stack is full or not.
Step 4:             Pop elements from the stack by deleting element in the top.
Step 5:             Check whether stack is empty or not.
Step 6:             Display the top of the element in the stack using Top.
Step 7:             Display all the elements in the list.

Source Code:
                                    //LINKEDLIST IMPLEMENTATION OF STACK//
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
int count;
void push();
void pop();
void display();
struct node
{
int data;
struct node *next;
}*top=NULL;
void push()
{
int x;
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node));
printf("\nenter the number\t:");
scanf("%d",&x);
newnode->data=x;
if(top==NULL)
{
newnode->next=NULL;
top=newnode;
}
else
{
newnode->next=top;
top=newnode;
}
printf("\nThe element %d is inserted",x);
return;
}
void pop()
{
struct node *temp;
if(top==NULL)
printf("\n the stack is underflow");
else
{
temp=top;
top=top->next;
printf("\nthe element %d is deleted",temp->data);
free(temp);
}
return;
}
void display()
{
struct node *i;
printf("\n the element of stack is\t:");
for(i=top;i!=NULL;i=i->next)
printf("\t%d",i->data);
if(top==NULL)
printf("\n stack is empty");
return;
}
void main()
{
int ch;
clrscr();
printf(" LINKEDLIST IMPLEMENTAION OF STACK\n");
printf(" ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
printf("\n1.Push\n2.Pop\n3.Display\n");

do
{
printf("\n\n enter ur choice\t:");
scanf("%d",&ch);
switch(ch)
{
case 1:
            push();
            break;
case 2:
            pop();
            break;

case 3:

            display();
            break;

default:
printf("\n\nInvalid Choice!!!!!!!");
exit(0);
}
}
while(ch<4);
getch();
}
Sample Output:
LINKEDLIST IMPLEMENTAION OF STACK
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

1.Push
2.Pop
3.Display

enter ur choice        :1

enter the number        :10

The element 10 is inserted

 enter ur choice        :1

enter the number        :20

The element 20 is inserted

 enter ur choice        :1

enter the number        :30

The element 30 is inserted

 enter ur choice        :1

enter the number        :40

The element 40 is inserted

 enter ur choice        :3

 the element of stack is        :       40      30      20      10

 enter ur choice        :2

the element 40 is deleted

 enter ur choice        :3

 the element of stack is        :       30      20      10

 enter ur choice        :4

EX.NO:6
Conversion of infix to postfix expression using linked list
Aim:

Write a program to Conversion of infix to postfix expression using linked list.

Algorithm:

Step 1:             Get the expression as input.
Step 2:             Check whether the input is an alphabet means, get the value for the alphabet.
Step 3:             if it is alphabet means get the value for the alphabet.
Step 4:             Now push that value into the stack.
Step 5:             if it is operator means get the value for the operator.
Step 6:             Now pop two values from the stack.
Step 7:             perform that respective operation.
Step 8:             push the result in the stack again.
Step 9:             Repeat the steps until all the characters in the string is read.
Step 10:           pop the result from the stack and display it.

Source Code:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>

char inf[40],post[40];
int top=0,st[20];
void postfix();
void push(int);
char pop();

void main(void)
{
clrscr();
printf("\t\tINFIX TO POSTFIX CONVERSION\n");
printf("\t\t***************************\n");
printf("\n\nEnter the infix expression\t:\t");
scanf("%s",inf);
postfix();
getch();
}

void postfix()
{
int i,j=0;
for(i=0;inf[i]!='\0';i++)
{
switch(inf[i])
{
case '+':
while(st[top]>=1)
post[j++]=pop();
push(1);
break;

case '-':
while(st[top]>=1)
post[j++]=pop();
push(2);
break;

case '*':
while(st[top]>=3)
post[j++]=pop();
push(3);
break;

case '/':
while(st[top]>=3)
post[j++]=pop();
push(4);
break;

case '^':
while(st[top]>=4)
post[j++]=pop();
push(5);
break;

case '(':
push(0);
break;
case ')':
while(st[top]!=0)
post[j++]=pop();
top--;
break;

default:
post[j++]=inf[i];
}
}
while(top>0)
post[j++]=pop();
printf("\n\nPostfix expression is \t\t:\t%s",post);
}
void push(int ele)
{
top++;
st[top]=ele;
}
char pop()
{
int el;
char e;
el=st[top];
top--;
switch(el)
{
case 1:
e='+';
break;
case 2:
e='-';
break;
case 3:
e='*';
break;
case 4:
e='/';
break;

case 5:
e='^';
break;

}
return(e);
}


Sample Output:

INFIX TO POSTFIX CONVERSION
Enter the infix expression      :       (a+b)*(a-d/e)
Postfix expression is           :       ab+ade/-*


EX.NO:7
Implementation of Dequeue
Aim:

Write a program to Implementation of Dequeue where insertion and deletion is possible at both the ends.

Algorithm:

Step 1:             Get the elements
Step 2:             Insert the elements either at front end or rear end.
Step 3:             Before inserting the elements, check whether the dequeue is full.
Step 4:             If dequeue is full, display error message.
Step 5:             After insertion, the front end/rear end position is changed.
Step 6:             Delete the elements either at the front end /rear end.
Step 7:             Before deletion, check whether the dequeue is empty.
Step 8:             If dequeue is empty, display the error message.
Step 9:             After deletion, the front end/rear end position is changed.
Step 10:           display the elements in the dequeue.

Source Code:

#include<stdio.h>
#include<conio.h>
#define MAX 20

void display();
int a[25],x,y,l,r,i,j,ch;


void show()
{
printf("\nLeft Queue\t:");

for(x=l-1;x>=0;x--)
{
if(a[x]==0)
continue;
printf("%d\t",a[x]);
}

printf("\nRight queue\t:");
for(x=r+1;x<MAX;x++)
printf("%d\t",a[x]);
}

void insleft(int v)
{
i=l-1;
while(i>=0)
a[i+1]=a[i--];
a[0]=v;
l++;
}

void rmvleft()
{
int p;
i=0;
p=l-2;
while(p>=0)
a[p+1]=a[p--];
a[0]=0;
}

void insright(int v)
{
j=r+1;
while(j>v && j<MAX)
a[j-1]=a[j++];
a[MAX-1]=v;
r--;
}

void rmvright()
{
j=MAX-1;
while(j>r)
a[j]=a[j--];
a[j]=0;
r++;
}

void main()
{
char con='y';
l=0;
r=MAX-1;

while(con=='y')
{
display();
switch(ch)
{
case 1:
printf("\nEnter the value\t:");
scanf("%d",&y);
insleft(y);
break;

case 2:
printf("\nEnter the value\t:");
scanf("%d",&y);
insright(y);
break;

case 3:
if(l==0)
printf("\nno value are entered from left\n");
rmvleft();
break;

case 4:
if(r==MAX-1)
printf("\nno value are entered from right\n");
rmvright();
break;

case 5:
if(r==MAX-1&&l==0)
printf("\nDequeue underflow");
else if(r-1>=0)
show();
else
printf("\n Dequeue overflow");
break;
default:
break;
}
printf("\n Do you want to continue(y/n)?");
con=getch();
}
}
void display()
{
clrscr();
printf("DOUBLE ENDED QUEUE\n");
printf("^^^^^^^^^^^^^^^^^^\n");
printf("\n1.Insert Left\n2.Insert Right\n3.Remove left\n4.Remove Right\n5.Display\n6.Exit\n");
printf("\nEnter ur choice\t:");
scanf("%d",&ch);
getch();
}
Sample Output:

DOUBLE ENDED QUEUE
^^^^^^^^^^^^^^^^^^
1.Insert Left
2.Insert Right
3.Remove left
4.Remove Right
5.Display
6.Exit

Enter ur choice :1

Enter the value :23

Enter ur choice :1

Enter the value :34

Enter ur choice :1

Enter the value :45

Enter ur choice :1

Enter the value :56

Enter ur choice :2

Enter the value :11

Enter ur choice :2

Enter the value :22

Enter ur choice :2

Enter the value :33

Enter ur choice :5

Left Queue      :23     34      45      56

Right queue     :11     22      33

Enter ur choice :3

Enter ur choice :5

Left Queue      :34     45      56
Right queue     :11     22      33
 Do you want to continue(y/n)?
Enter ur choice :4

Enter ur choice :5

Left Queue      :34     45      56

right queue     :22     33
 Do you want to continue(y/n)?

Enter ur choice :6
EX.NO:8

Implementation of pre order, in order and post order traversals using
expression tree
Aim:

Write a program to Implementation of pre order, in order and post order traversals using expression tree.
Algorithm:

Step 1:             Get the expression as input.
Step 2:             perform the in-order traversal
a) Process the left sub tree.
b) Process root.
c)  Process right sub tree.
Step 3:             perform the pre-order traversal
a) Process root.
b) Process the left sub tree.
c)  Process right sub tree.

Step 4:             perform the post-order traversal
a) Process the left sub tree.
b)  Process right sub tree.
c) Process root.







Source Code:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<ctype.h>
#define size 20
typedef struct node
{
char data;
struct node *left;
struct node *right;
}btree;
btree *stack[size];
int top;
void main()
{
btree *root;
char exp[80];
btree *create(char exp[80]);
void inorder(btree *root);
void preorder(btree *root);
void postorder(btree *root);
clrscr();
printf("EXPRESSION TREE\n");
printf("^^^^^^^^^^^^^^^^\n");
printf("\n\nEnter the postfix expression\t:");
scanf("%s",exp);
top=-1;
root=create(exp);
printf("\n\nThe tree is created........\n");
printf("\n\nThe in order traversel is\t: ");
inorder(root);
printf("\n\nThe preorder traversal is\t: ");
preorder(root);
printf("\n\nThe post order traversal is\t: ");
postorder(root);
getch();
}
btree *create(char exp[])
{
btree *temp;
int pos;
char ch;
void push(btree *);
btree *pop();
pos=0;
ch=exp[pos];
while(ch!='\0')
{
temp=(btree *)malloc(sizeof(btree));
temp->left=temp->right=NULL;
temp->data=ch;
if(isalpha(ch))
push(temp);
else if(ch=='+'|| ch=='-'|| ch=='*' ||ch=='/')
{
temp->right=pop();
temp->left=pop();
push(temp);
}
else
printf("\nInvalid character in expression\n");
pos++;
ch=exp[pos];
}
temp=pop();
return(temp);
}
void push(btree *node)
{
if(top+1>=size)
printf("\nERROR: Stack is full\n");
top++;
stack[top]=node;
}
btree* pop()
{
btree *node;
if(top==-1)
printf("\nError:stack is empty\n");
node=stack[top];
top--;
return(node);
}
void inorder(btree *root)
{
btree *temp;
temp=root;
if(temp!=NULL)
{
inorder(temp->left);
printf("%c",temp->data);
inorder(temp->right);
}
}
void preorder(btree *root)
{
btree *temp;
temp=root;
if(temp!=NULL)
{
printf("%c",temp->data);
preorder(temp->left);
preorder(temp->right);
}
}
void postorder(btree *root)
{
btree *temp;
temp=root;
if(temp!=NULL)
{
postorder(temp->left);

postorder(temp->right);
printf("%c",temp->data);
}
}

Sample Output:

EXPRESSION TREE
^^^^^^^^^^^^^^^^

Enter the postfix expression    :ab+cde/-*

The tree is created........

The in order traversel is       : a+b*c-d/e

The preorder traversal is       : *+ab-c/de

The post order traversal is     : ab+cde/-*

EX.NO:9
Implementation of binary search tree
Aim:
           
Write a program to Implementation binary search tree.


Algorithm:

Step 1:             Get the elements.
Step 2:             construct the binary tree for the given elements.
Step 3:             perform the operation search, insert, delete.
Step 4:             To search a node in the binary tree
a) First compare the data with that of the root.
b) If it is equal means the search is successful
c) If it is greater means the searching process proceeds in the right sub tree otherwise process left sub tree
Step 5:             To insert a node in the binary tree
a)      First compare the data with that of the root node.
b)      If it is greater means he insert the data in right sub tree otherwise insert the data in left sub tree.
c)      Continue this process until insert the data in right position.
Step 6:             To delete a node in the binary tree to check the condition
a)      No node in the tree contains the specified data.
b)      The node containing the data has no children
c)      The node containing the data has exactly one child.
d)     The node containing the data has two children




Source Code:
//BINARY SEARCH TREE//
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct bst
{
int data;
struct bst *left,*right;
}node;
void insert(node *,node *);
void inorder(node *);
node *search(node *,int,node **);
void del(node *,int);
void main()
{
int choice;
char ans='N';
int key;
node *New,*root,*tmp,*parent;
node *getnode();
root=NULL;
clrscr();
printf("\t\t Binary search tree\n");
printf("\t\t *******************\n");
do
{
printf("\n1.Create\n2.Search\n3.Delete\n4.Display");
printf("\n\nEnter ur choice\t:");
scanf("%d",&choice);
switch(choice)
{
case 1:
do
{
New=getnode();
printf("\n\nEnter the element\t:");
scanf("%d",&New->data);
if(root==NULL)
root=New;
else
insert(root,New);
printf("\n\ndo you want to enter more elements?(y/n)");
ans=getch();
}
while(ans=='y');
break;
case 2:
printf("\n\nenter the element u want to search\t:");
scanf("%d",&key);
tmp=search(root,key,&parent);
printf("\n\nparent of node %d is %d",tmp->data,parent->data);
break;
case 3:
printf("\n\nEnter the element you wish to delete\t:");
scanf("%d",&key);
del(root,key);
break;
case 4:
if(root==NULL)
printf("tree is not created");
else
{
printf("\n\nThe tree is\t:");
inorder(root);
}
break;
}
}
while(choice!=5);
}
node *getnode()
{
node *temp;
temp=(node *)malloc(sizeof(node));
temp->left=NULL;
temp->right=NULL;
return temp;
}

void insert(node *root,node *New)
{
if(New->data<root->data)
{
if(root->left==NULL)
root->left=New;
else
insert(root->left,New);
}

if(New->data>root->data)
{
if(root->right==NULL)
root->right=New;
else
insert(root->right,New);
}
}

node *search(node *root,int key,node **parent)
{
node *temp;
temp=root;
while(temp!=NULL)
{
if(temp->data==key)
{
printf("\n\nThe %d element is present ",temp->data);
return temp;
}
*parent=temp;
if(temp->data>key)
temp=temp->left;
else
temp=temp->right;
}
return NULL;
}
void del(node *root,int key)
{
node *temp,*parent,*temp_succ;
temp=search(root,key,&parent);


if(temp->left!=NULL&&temp->right!=NULL)
{
parent=temp;
temp_succ=temp->right;
while(temp_succ->left!=NULL)
{
parent=temp_succ;
temp_succ=temp_succ->left;
}
temp->data=temp_succ->data;
parent->right=NULL;
printf("Now delete it!");
return;
}

if(temp->left!=NULL && temp->right==NULL)
{
if(parent->left==temp)
parent->left=temp->left;
else
parent->right=temp->left;
temp=NULL;
free(temp);
printf("Now delete it");
return;
}

if(temp->left==NULL && temp->right!=NULL)
{
if(parent->left==temp)
parent->left=temp->right;
else
parent->right=temp->right;
temp=NULL;
free(temp);
printf("Now delete it");
return;
}


if(temp->left==NULL && temp->right==NULL)
{
if(parent->left==temp)
parent->left=NULL;
else
parent->right=NULL;
printf("Now delete it");
return;
}}
void inorder(node *temp)
{
if (temp!=NULL)
{
inorder(temp->left);
printf("%d\t",temp->data);
inorder(temp->right);
}
}




Sample Output:

                             Binary search tree
                             ***************
1.Create
2.Search
3.Delete
4.Display

Enter ur choice :1

Enter the element       :12

do you want to enter more elements?(y/n)

Enter the element       :13


do you want to enter more elements?(y/n)

Enter the element       :14

do you want to enter more elements?(y/n)

Enter the element       :15

do you want to enter more elements?(y/n)

Enter the element       :16

do you want to enter more elements?(y/n)

Enter the element       :17

do you want to enter more elements?(y/n)

Enter ur choice :4

The tree is     :12     13      14      15      16      17

Enter ur choice :2

enter the element u want to search      :16

The 16 element is present

parent of node 16 is 15




Enter ur choice :3

Enter the element you wish to delete    :14

The 14 element is present Now delete it

Enter ur choice :4

The tree is     :12     13      15      16      17



EX.NO:10
Implementation of insertion in AVL tree
Aim:

Write a program for insertion in AVL tree.

Algorithm:

Step 1:             Get the elements
Step 2:             To insert a new node in an AVL tree, first find the appropriate position.
Step 3:             If new node is inserted as a child of any non leaf node, the balance factor doesn’t change.
Step 4:             If new node is inserted as a child of a leaf node, the balance factor may be changed..
Step 5:             If new node is inserted as a child of a leaf node of sub tree (left/right), the balance factor is changed according to the height of the sub tree.


Source Code:

//INSERTION IN AVL TREE//

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define TRUE 1
#define FALSE 0

struct avl
{
int data;
int balfact;
struct avl *left;
struct avl *right;
};

struct avl *insert(struct avl *,int,int *);
struct avl *balr(struct avl *,int *);
struct avl *ball(struct avl *,int *);
void display(struct avl *);
void main()
{
struct avl *avl=NULL;
int h,item,ch;
clrscr();
printf("\t\t AVL tree\n");
printf("\t\t ********\n");
printf("\n1.Insertion\n2.Dispaly\n3.Exit\n");
do
{

printf("\n\nEnter ur choice\t\t:");
scanf("%d",&ch);
switch(ch)
{
case 1:

printf("\n\nenter the item to be inserted\t:");
scanf("%d",&item);
avl=insert(avl,item,&h);
break;

case 2:
display(avl);
break;
}
}
while(ch!=3);
getch();
}
struct avl *insert(struct avl *root,int data,int *h)
{
struct avl *node1,*node2;
if(!root)
{
root=(struct avl *)malloc(sizeof(struct avl));
root->data=data;
root->left=NULL;
root->right=NULL;
root->balfact=0;
*h=TRUE;
return(root);
}
if(data<root->data)
{
root->left=insert(root->left,data,h);
if(*h)
{
switch(root->balfact)
{
case 1:

node1=root->left;
if(node1->balfact==1)
{
printf("\n Right rotation along %d",root->data);
root->left=node1->right;
node1->right=root;
root->balfact=0;
root=node1;
}
else
{
printf("\n Double rotation,left along %d",node1->data);
node2=node1->right;
node1->right=node2->left;
printf("then right along %d.\n",root->data);
node2->left=node1;
root->left=node2->right;
node2->right=root;
if(node2->balfact==1)
root->balfact=-1;
else
root->balfact=0;
if(node2->balfact==-1)
node1->balfact=1;
else
node1->balfact=0;
root=node2;
}
root->balfact=0;
*h=FALSE;
break;
case 0:

root->balfact=1;
break;
case -1:
root->balfact=0;
*h=FALSE;
}
}
}

if(data>root->data)
{
root->right=insert(root->right,data,h);
if(*h)
{
switch(root->balfact)
{
case 1:
root->balfact=0;
*h=FALSE;
break;

case 0:
root->balfact=-1;
break;

case -1:
node1=root->right;
if(node1->balfact==-1)
{
printf("\n Left rotation along %d.",root->data);
root->right=node1->left;
node1->left=root;
root->balfact=0;
root=node1;
}
else
{
printf("\n Double rotation,right along %d",node1->data);
node2=node1->left;
node1->left=node2->right;

node2->right=node1;
printf("then left along %d.\n",root->data);
root->right=node2->left;
node2->left=root;
if(node2->balfact==-1)
root->balfact=1;
else
root->balfact=1;
if(node2->balfact==1)
node1->balfact=-1;
else
node1->balfact=0;
root=node2;
}
root->balfact=0;
*h=FALSE;
}
}
}
return(root);
}

struct avl *ball(struct avl *root,int *h)
{
struct avl *node1,*node2;
switch(root->balfact)
{
case -1:

root->balfact=0;
break;
case 0:
root->balfact=1;
*h=FALSE;
break;

case 1:
node1=root->left;
if(node1->balfact>=0)
{
printf("\n Right rotation along %d",root->data);
root->left=node1->right;
node1->right=root;
if(node1->balfact==0)
{

root->balfact=1;
node1->balfact=-1;
*h=FALSE;
}
else
{
root->balfact=node1->balfact=0;
}
root=node1;
}

else
{
printf("\n Double rotation,left along %d",node1->data);
node2=node1->right;
node1->right=node2->left;

node2->left=node1;
printf("then right along %d.\n",root->data);
root->left=node2->right;
node2->right=root;
if(node2->balfact==1)
root->balfact=-1;
else

root->balfact=0;
root=node2;
node2->balfact=0;
}
}
return(root);
}
void display(struct avl *root)
{
if(root!=NULL)
{
display(root->left);
printf("%d\t",root->data);
display(root->right);
}
}



Sample Output:

AVL tree
********

1.Insertion
2.Dispaly
3.Exit


Enter ur choice            :1

enter the item to be inserted   :1

Enter ur choice                        :1

enter the item to be inserted   :2

Enter ur choice                        :1

enter the item to be inserted   :3

 Left rotation along 1.

Enter ur choice                    :1

enter the item to be inserted   :4

Enter ur choice                    :1

enter the item to be inserted   :5

 Left rotation along 3.

enter the item to be inserted   :6

 Left rotation along 2.

Enter ur choice                    :1

enter the item to be inserted   :7

 Left rotation along 5.

Enter ur choice                    :1

enter the item to be inserted   :8

Enter ur choice                    :1

enter the item to be inserted   :9

 Left rotation along 7.

Enter ur choice                    :1

enter the item to be inserted   :10

 Left rotation along 6.

Enter ur choice                    :1

enter the item to be inserted   :11

 Left rotation along 9.

Enter ur choice                    :2

1       2       3       4       5       6       7       8       9       10
11

Sample Output:

                AVL tree
                 ********

1.Insertion
2.Dispaly
3.Exit


Enter ur choice         :1


enter the item to be inserted   :10


Enter ur choice         :1


enter the item to be inserted   :9


Enter ur choice         :1


enter the item to be inserted   :8

 Right rotation along 10

Enter ur choice         :1


enter the item to be inserted   :7


Enter ur choice         :1


enter the item to be inserted   :6

 Right rotation along 8

Enter ur choice         :1


enter the item to be inserted   :5

 Right rotation along 9

Enter ur choice         :1


enter the item to be inserted   :4

 Right rotation along 6

Enter ur choice         :1


enter the item to be inserted   :3


Enter ur choice         :1


enter the item to be inserted   :2

 Right rotation along 4

Enter ur choice         :1


enter the item to be inserted   :1

 Right rotation along 5

Enter ur choice         :2
1       2       3       4       5       6       7       8       9       10






EX.NO:11
Implementation of priority queue using binary heaps
Aim:

Write a program to Implementation of priority queue using binary heaps.

Algorithm:

Step 1:             Get the elements.
Step 2:             To insert a node in the heap
a)      Node is inserted after the last element and parent is present at (i/2) th position.
b)      If it is greater than parent then exchange the position
c)      This procedure is repeated till the element is paced at its appropriate position.
Step 3:             To delete a node in the heap
a)      The node to be deleted is always of the highest priority.
b)      The element presented at the index n in the array is stored at the position in the array and maximum. Index value of the array is decremented by one.
c)      The heap is restored as in the case of replace operation.
Step 4:             Display the elements.


Source Code:

#include<stdio.h>
#include<conio.h>

void restoreup(int,int *);
void restoredown(int,int*,int);
void makeheap(int*,int);
void add(int,int*,int*);

int replace(int,int*,int);
int del(int*,int*);
void main()
{
int a[20];
int i,n,ch;
clrscr();
printf("PRIORITY QUEUE USING BINARY HEAPS\n");
printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
printf("\n1.MakeHeap\n2.Insertion\n3.Deletion\n4.Replace\n5.Exit\n");
do
{

printf("\nEnter ur choice\t\t:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\nEnter the total no of numbers\t:");
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
makeheap(a,n);
printf("\n\nHeap:\n");
for(i=1;i<=n;i++)
printf("%d\t",a[i]);
break;

case 2:
printf("\n\nenter the element to be inserted\t:");
scanf("%d",&i);
add(i,a,&n);
printf("\nElement added:  %d\n",i);
printf("\n\nHeap after addition of an element:\n");

for(i=1;i<=n;i++)
printf("%d\t",a[i]);
break;

case 3:
printf("\n\nthe root node is deleted:");
i=del(a,&n);
printf("\n\nelement deleted%d\n",i);
for(i=1;i<=n;i++)
printf("%d\t",a[i]);
break;

case 4:
printf("\n\nThe root node is replaced");
printf("\n\nenter the value to be placed in the root node");
scanf("%d",&i);
i=replace(i,a,n);
printf("\n\nelement replaced %d\n",i);

for(i=1;i<=n;i++)
printf("%d\t",a[i]);
break;
}
getch();
}
while(ch!=5);
}

void restoreup(int i,int *a)
{
int v;
v=a[i];
while(a[i/2]>=v)
{
a[i]=a[i/2];
i=i/2;
}
a[i]=v;
}

void restoredown(int p,int *a,int n)
{
int i,v;
v=a[p];
while(p<=n/2)
{
i=2*p;
if((i<n)&&(a[i]<a[i+1]))
i++;
if(v<=a[i])
break;
a[p]=a[i];
p=i;
}
a[p]=v;
}


void makeheap(int *a,int n)
{
int i;
for(i=n/2;i>=1;i++)
restoredown(i,a,n);
}


void add(int v,int *a,int *n)
{
(*n)++;
a[*n]=v;
restoreup(*n,a);
}

int replace(int i,int *a,int n)
{
int r=a[1];
a[1]=i;
for(i=n/2;i>=1;i--)
restoredown(i,a,n);
return r;
}
int del(int *a,int *n)
{int v;
v=a[1];
a[1]=a[*n];
(*n)--;
restoredown(1,a,*n);
return v;
}


Sample Output:
PRIORITY QUEUE USING BINARY HEAPS
1.MakeHeap
2.Insertion
3.Deletion
4.Replace
5.Exit
Enter ur choice         :1
Enter the total no of numbers   :5
1
2
3
4
5
Heap:
1       2       3       4       5
Enter ur choice         :2
enter the element to be inserted        :9
Element added:  9
Heap after addition of an element:
1       2       3       4       5       9
Enter ur choice         :3
the root node is deleted:
element deleted1
3       2       9       4       5
Enter ur choice         :4
The root node is replaced
enter the value to be placed in the root node
10
element replaced 3
9       2       10      4       5
EX.NO:12
Implementation of open addressing with hash table
Aim:

Write a program to Implementation of open addressing with hash table.

Algorithm:

Step 1:             Get the values.
Step 2:             The algorithm for inserting a value into the table is:
1.      Compute the position at which V ought to be stored, P=H (key (V)).
2.      If position P is not OCCUPIED, store V there.
3.      If position P is OCCUPIED, Compute another position in the table; set P to this value and repeat (2)-(3).

Step 3:             The algorithm for retrieving a value into the table with the key K is:
1.      P=H (k), the position where the key would be found if no collision occurred when it was inserted.
2.      If position P is EMPTY, then no value with the key K occurs in the table.
3.      If position P is OCCUPIED by a value whose key K, return the value in position p.
4.      Otherwise compute another position in the table, set P to this value and repeat (2)-(4).

Step 4:             The algorithm for deleting a value into the table with the key K is:
1.      P=H (k), the position where the key would be found if no collision occurred when it was inserted.
2.      If position P is EMPTY, then no value with the key K occurs in the table.
3.      If position P is DELETED by a value whose key K, return the value in position p.
4.      Otherwise compute another position in the table, set P to this value and repeat (2)-(4).
Step 5:             Display all the elements in the table.


Source Code:
#include<stdio.h>
#include<conio.h>
#include<math.h>
int tabsize=10;
int tab[20];
void main()
{
int i,j,ch,res;
int store(int);
void retrieve(int,int*);
void removed(int);
void display();
for(i=0;i<tabsize;i++)
tab[i]=0;
clrscr();
printf("Hashing with open addressing\n");
printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^");
printf("\n1.store\n2.retrieve\n3.remove\n4.display\n5.exit\n");
do
{
printf("\n\nenter your choice\t:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\nenter the item to be placed in a table\t:");
scanf("%d",&i);
res=store(i);
if(res==1)
printf("\n\nItem stored in the table");
else if(res==2)
printf("\n\nthere is no free space in the table!!!");
else if(res==0)
printf("\n\nitem already exists in the table!!!");
getch();
break;
case 2:
printf("\n\nenter the item to be retrived in a table\t:");
scanf("%d",&i);
retrieve(i,&j);
if(j==1)
printf("\n\nItem is in the table");
else
printf("\n\nThere is not exist in the table!!!");
getch();
break;
case 3:
printf("\n\nenter the item to be deleted in a table\t:");
scanf("\n%d",&i);
removed(i);
break;
case 4:
display();
getch();
break;
case 5:
break;
}
}
while(ch!=5);
}

int store(int item)
{
int loc,ploc,k=1;
int flag=0;
loc=item%tabsize;
ploc=loc;
if(loc==tabsize)
loc=0;
while(1)
{
if(tab[loc]==0)
{
tab[loc]=item;
return 1;
}
else if ((tab[loc]!=0)&&(tab[loc]!=item))
{
loc=loc+pow(k,2);
k++;
if(loc>=tabsize)
loc=0;
if(ploc==loc)
return 2;
continue;
}
else if(tab[loc]==item)
{
printf("\n\nItem already exists in the table");
getch();
return 0;
}
else
{
loc=loc+pow(k,2);
k++;
if(loc==tabsize)
loc=0;
if(ploc==loc)
return 2;
continue;
}
}
}
void retrieve(int item,int *j)
{
int loc,ploc,k=1;
loc=item%tabsize;
ploc=loc;
if(tab[loc]==item)
{
*j=1;
return;
}
else
{
loc=loc+pow(k,2);
while(ploc!=loc)
{
if(tab[loc]==item)
{
*j=1;
return;
}
if(loc==tabsize)
loc=0;
else
{
loc=loc+pow(k,2);
k++;
}
}
*j=0;
return;
}
}
void removed(int i)
{
int loc,ploc,k=1;

loc=i%tabsize;
ploc=loc;
if(tab[loc]==i)
{
tab[loc]=0;
printf("\n\nItem removed from the hash table");
getch();
return;
}
else
{
loc=loc+pow(k,2);
while((loc!=ploc)&&(tab[loc]!=i))
{
loc=loc+pow(k,2);
k++;
if(loc==tabsize)
loc=0;
}
if((tab[loc]==i)&&(loc!=ploc))
{
tab[loc]=0;
printf("\n\nItem removed from the hash table");
getch();
return;
}
else if((loc==ploc)&&(tab[loc]!=i))
{
printf("\n\nItem is not found in the table");
getch();
return;
}
}
}

void display()
{
int i;
for(i=0;i<tabsize;i++)
printf("%d\n",tab[i]);
}




Sample Output:
Hashing with open addressing
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1.store
2.retrieve
3.remove
4.display
5.exit
enter your choice       :1
enter the item to be placed in a table  :11
Item stored in the table
enter your choice       :1
enter the item to be placed in a table  :22
Item stored in the table
enter your choice       :1
enter the item to be placed in a table  :33
Item stored in the table
enter your choice       :1
enter the item to be placed in a table  :44
Item stored in the table
enter your choice       :1
enter the item to be placed in a table  :55
Item stored in the table
enter your choice       :1
enter the item to be placed in a table  :66
Item stored in the table
enter your choice       :4
0
11
22
33
44
55
66
0
0
0
enter your choice       :2
enter the item to be retrived in a table        :33
Item is in the table
enter your choice       :3
enter the item to be deleted in a table :55
Item removed from the hash table
enter your choice       :4
0
11
22
33
44
0
66
0
0
0


11. IMPLEMENTATION OF PRIM’S ALGORITHM



Aim:
            To write a C program for implementation of Prim's algorithm.
Algorithm:
1.      Start the program.
2.      Get the number of nodes & edges in the graph.
3.      Get the edges v1 and v2 and then get corresponding weight.
4.      Find the weight of the edge(minimum).
5.      Calculate total path length.
6.      Display the weight and the total path.
7.      Stop the program.

Program:

#include<stdio.h>
#include<conio.h>
#define SIZE 20
#define INFINITY 32767
void prim(int G[][SIZE],int nodes)
{
 int Q[SIZE],i,j,k;
 int min_dist,v1,v2,total=0;
 for(i=0;i<nodes;i++)
  Q[i]=0;
 printf("\n\nThe minimal spanning tree is:\n");
 Q[0]=1;
 for(k=1;k<nodes;k++)
 {
  min_dist=INFINITY;
  for(i=0;i<nodes;i++)
  {
   for(j=0;j<nodes;j++)
   {
    if(G[i][j] && ((Q[i]&&!Q[j]) || (!Q[i] && Q[j])))
    {
     if(G[i][j]<min_dist)
     {
      min_dist=G[i][j];
      v1=i;
      v2=j;
     }
    }
   }
  }
  printf("\n edge(%d,%d) and weight= %d ",v1,v2,min_dist);
  Q[v1]=Q[v2]=1;
  total=total+min_dist;
 }
 printf("\n\n\tTotal path length is = %d ",total);
}
void main()
{
 int G[SIZE][SIZE],nodes;
 int v1,v2,length,i,j,n;
 clrscr();
 printf("\n\t Prim's Algorithm \n");
 printf("Enter the number of nodes in the graph:\t");
 scanf("%d",&nodes);
 printf("\nEnter number of edges in the graph:\t");
 scanf("%d",&n);
 for(i=0;i<nodes;i++)
  for(j=0;j<nodes;j++)
   G[i][j]=0;
 printf("\nEnter edges and weights:\t");
 for(i=1;i<n;i++)
 {
  printf("\nEnter edge by v1 and v2 :\t");
  scanf("%d%d",&v1,&v2);
  printf("\nEnter corresponding weights:\t");
  scanf("%d",&length);
  G[v1][v2]=G[v2][v1]=length;
 }
 getch();
 printf("\n\t");
 clrscr();
 prim(G,nodes);
 getch();
}
























Result:
            Thus the C program for implementation of Prim’s algorithm was written, executed and the output was verified successfully.