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.
No comments:
Post a Comment