Ex no –1(A) IMPLEMENTATION OF SINGLY

04-9-2008 LINKED LIST

AIM:
To write a c++ program to implement singly linked list.

ALGORITHM:
Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Create a structure named node and declare variables to denote a node for

singly linked list.

Step4: In the create () method, check whether the head is NULL or not. If it is

NULL, then get the number of nodes from user and get data for each

node that are created.

Step5: In the insert () method, check whether the head is NULL or not. If it is

NOT NULL, then get the position from the user and then insert into list.

Step6: In the delete () method, check whether the head is NULL or not. If it is

NOT NULL, then get the position to be deleted from the user.

Step7: Insert and delete according to the position.

Step8: In display () method, print the elements of singly linked list.

Step9: In main () method, use switch case statement to invoke the methods

according to the user choice entered.

Step10: End of the program.

INPUT & OUTPUT:

SINGLY LINKED LIST MENU

1.create
2.insert
3.delete
4.display
5.exit

enter the choce:1

enter the no of nodes:3
enter the data1:10
enter the data2:20
enter the data3:30
list created...

enter the choce:4

SINGLY LINKED LIST->10->20->30

enter the choce:2

enter the position:2
enter the data:40
data has been inserted...

enter the choce:4

SINGLY LINKED LIST->10->40->20->30

enter the choce:3

enter the position:1
data has been deleted...

enter the choce:4

SINGLY LINKED LIST->40->20->30

enter the choce:5

press y(or)Y to exit
y <exiting…>

RESULT:

Thus the implementation of singly linked list has been completed successfully and
output verified.
CODING:

#include<iostream.h>
#include<conio.h>
#include<process.h>
#include<stdio.h>
struct node
{
char data[20];
node *link;
}*p,*pre;
node *head=NULL;
int pos,i;
void create()
{
if(head!=0)
cout<<"* cannot create newlist * ";
else
{
int no;
cout<<"enter the no of nodes:";
cin>>no;
p=new node;
cout<<"enter the data1:";
gets(p->data);
head=p;
for(i=1;i<no;i++)
{
pre=p;
p=new node;
pre->link=p;
cout<<"enter the data"<<i+1<<":";
gets(p->data);
}
p->link=NULL;
cout<<"list created...";
}
}
void insert()
{
if(head==0)
{
cout<<"* cannot insert *";
}
else
{
 cout<<"enter the position:";
cin>>pos;
pre=head;
for(i=1;i<pos-1;i++)
{
pre=pre->link;
if(pre->link==NULL)
break;
}
if(pos>i+2||pos<1)
{
cout<<"* position out of range *";
}
else
{
p=new node;
cout<<"enter the data:";
gets(p->data);
if(pos==1)
{
p->link=head;
head=p;
}
else
{
p->link=pre->link;
pre->link=p;
}
cout<<"data has been inserted...";
}
}
}
void del()
{
if(head==0)
{
cout<<"* cannot delete * list is empty *";
}
else
{
cout<<"enter the position:";
cin>>pos;
pre=head;
for(i=1;i<pos-1;i++)
{
pre=pre->link;
 if(pre->link==NULL)
break;
}
p=pre->link;
if(pos>i+1||pos<1)
{
cout<<"\nposition out of range";
}
else
{
if(pos==1)
{
head=head->link;
cout<<"data has been deleted...";
}
else
{
pre->link=p->link;
cout<<"data has been deleted...";
}
}
}
}
void display()
{
cout<<"SINGLY LINKED LIST->";
p=head;
cout<<p->data;
while((p->link!=NULL) &&(head!=NULL))
{
cout<<"->";
p=p->link;
cout<<p->data;
}
}
void main()
{
char ch,x;
clrscr();
while(1)
{
cout<<"\n\tSINGLY LINKED LIST MENU";
cout<<"\n1.create\n2.insert\n3.delete\n4.display\n5.exit";
cout<<"\nenter the choce:";
cin>>ch;
switch(ch)
 {
case '1':
create();
break;
case '2':
insert();
break;
case '3':
del();
break;
case '4':
display();
break;
case '5':
cout<<"press y(or)Y to exit";
x=getch();
if(x=='y' ||x=='Y')
exit(0);
break;
default:
cout<<"* wrong choice *";
}
getch();
}
}
Ex no –1(B) IMPLEMENTATION OF DOUBLY
04-09-2008 LINKED LIST
AIM:
To write a c++ program to implement doubly linked list.

ALGORITHM:
Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Create a structure named node and declare variables to denote a node for

doubly linked list.

Step4: In the create () method, get the number of nodes and iterate the loop to

get data for each node that are created.

Step5: In the insert () method, get the position from the user. If it is valid

position, get the data for a node and give forward link and backward link.

Step6: In the delete () method, get the position to be deleted. If it is valid

position, by rearranging forward link and backward link to delete the

node from the list.

Step7: Insert and delete according to the valid position.

Step8: In display () method, print the elements of doubly linked list.

Step9: In main () method, use switch case statement to invoke the methods

according to the user choice entered.

Step10: End of the program.

INPUT & OUTPUT:

DOUBLY LINKED LIST MENU

1.create
2.insert
3.delete
4.display
5.exit
enter the choice:1
enter the number of nodes:3
enter the data:1
enter the data:2
enter the data:3

enter the choice:4

nodes in list are: 3
DOUBLY LINKED LIST<=>1<=>2<=>3

enter the choice:2

enter the position to insert:4
enter the data:4
data has been inserted...

enter the choice:4

nodes in list are: 4
DOUBLY LINKED LIST<=>1<=>2<=>3<=>4

enter the choice:3

enter the position to delete:2
data has been deleted...

enter the choice:4

nodes in list are: 3
DOUBLY LINKED LIST<=>1<=>3<=>4

enter the choice:5 <exiting…>

RESULT:

Thus the implementation of doubly linked list has been completed successfully
and output verified.
CODING:

#include<iostream.h>
#include<conio.h>
#include<process.h>
struct node
{
node *blink;
node *flink;
int no;
}*head,*pt1,*pt2,*p;
class d_link
{
private:
int x,pos;
public:
d_link()
{
p=new node;
p->flink=0;
p->blink=0;
p->no=0;
head=p;
pt1=p;
}
void create();
void display();
void insert();
void del();
};
void d_link::create()
{
int n;
cout<<"enter the number of nodes:";
cin>>n;
head->no=n;
for(int i=0;i<n;i++)
{
p=new node;
cout<<"enter the data:";
cin>>p->no;
p->blink=pt1;
pt1->flink=p;
pt1=p;
}
p->flink=0;
}
void d_link::display()
{
p=head->flink;
cout<<"nodes in list are: "<<head->no<<"\n";
cout<<"DOUBLY LINKED LIST";
for(int i=0;i<head->no;i++)
{
cout<<"<=>"<<p->no;
p=p->flink;
}
cout<<"\n";
}
void d_link::insert()
{
cout<<"enter the position to insert:";
cin>>pos;
if(pos>head->no+1)
cout<<"* invalid position *";
else
{
head->no+=1;
p=new node;
cout<<"enter the data:";
cin>>p->no;
pt1=head;
for(int i=1;i<pos;i++)
pt1=pt1->flink;
if(pt1->flink!=0)
{
pt2=pt1->flink;
p->flink=pt2;
p->blink=pt1;
pt1->flink=p;
pt2->blink=p;
cout<<"\ndata has been inserted...";
}
else
{
pt1->flink=p;
p->blink=pt1;
p->flink=0;
cout<<"\ndata has been inserted...";
}
}
}
void d_link::del()
{
cout<<"enter the position to delete:";
cin>>pos;
if(pos>head->no)
cout<<"* invalid position *";
else
{
head->no-=1;
pt1=head;
for(int i=1;i<pos;i++)
pt1=pt1->flink;
p=pt1->flink;
pt2=p->flink;
if(pt2==0)
{
pt1->flink=0;
cout<<"\ndata has been deleted...";
}
else
{
pt1->flink=pt2;
pt2->flink=pt1;
cout<<"\ndata has been deleted...";
}
}
}
void main()
{
d_link d1;
char ch;
int no=0;
clrscr();
while(no!=1)
{
cout<<"\n\tDOUBLY LINKED LIST MENU";
cout<<"\n1.create\n2.insert\n3.delete\n4.display\n5.exit";
cout<<"\nenter the choice:";
cin>>ch;
switch(ch)
{
case '1':
d1.create();
break;
case '2':
d1.insert();
 break;
case '3':
d1.del();
break;
case '4':
d1.display();
break;
case '5':
exit(0);
default:
cout<<"* enter correctly *";
}
}
getch();
}
Ex no –1(C) IMPLEMENTATION OF CIRCULAR
04-09-2008 LINKED LIST
AIM:
To write a c++ program to implement circular linked list.

ALGORITHM:
Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Create a structure named node and declare needed variables to denote a

node for circular linked list.

Step4: In the create () method, check whether the head is NULL or not. If it is

NULL, then get the number of nodes from user and get data for each

node that are created. Last node should not be NULL. Give the last node

pointer to head.

Step5: In the insert () method, check whether the head is NULL or not. If it is

NOT NULL, then get the valid position from the user and then insert

into list.

Step6: In the delete () method, check whether the head is NULL or not. If it is

NOT NULL, then get the valid position to be deleted from the user.

Step7: In display () method, print the elements of circular linked list.

Step8: In main () method, use switch case statement to invoke the methods

according to the user choice entered.

Step9: End of the program.

INPUT & OUTPUT:

CIRCULAR LINKED LIST MENU

1.create 2.insert 3.delete 4.display 5.exit
enter the choce:1
enter the no of nodes:3
enter the data1:10
enter the data2:20
enter the data3:30
list created..

enter the choce:4

CIRCULAR LINKED LIST->10->20->30->10

enter the choce:2

enter the position:1
enter the data:99
data has been inserted...

enter the choce:4

CIRCULAR LINKED LIST->99->10->20->30->99

enter the choce:3

enter the position:3
data has been deleted...

enter the choce:4

CIRCULAR LINKED LIST->99->10->30->99

enter the choce:5

press y(or)Y to exit Y <exiting…>

RESULT:

Thus the implementation of circular linked list has been completed successfully
and output verified.
CODING:

#include<iostream.h>
#include<conio.h>
#include<process.h>
#include<stdio.h>
struct node
{
char data[20];
node *link;
}*p,*pre,*end;
node *head=NULL;
int pos,i;
int list;
void create()
{
if(head!=0)
cout<<"cannot create";
else
{
int no;
list=0;
cout<<"enter the no of nodes:";
cin>>no;
list=no;
p=new node;
cout<<"enter the data1:";
gets(p->data);
head=p;
for(i=1;i<no;i++)
{
pre=p;
p=new node;
pre->link=p;
cout<<"enter the data"<<i+1<<":";
gets(p->data);
}
p->link=head;
end=p;
cout<<"list created..";
}
}
void insert()
{
if(head==0)
{
 cout<<"* list not available *";
}
else
{
cout<<"enter the position:";
cin>>pos;
pre=head;
for(i=1;i<pos-1;i++)
{
pre=pre->link;
if(pre->link==head)
break;
}
if(pos>i+2||pos<1)
{
cout<<"* position out of range *";
}
else
{
p=new node;
cout<<"enter the data:";
gets(p->data);
if(pos==1)
{
p->link=head;
head=p;
end->link=head;
}
else
{
p->link=pre->link;
pre->link=p;
}
list+=1;
cout<<"data has been inserted...";
}
}
}
void del()
{
if(head==0)
{
cout<<"* list not available *";
}
else
{
 cout<<"enter the position:";
cin>>pos;
pre=head;
for(i=1;i<pos-1;i++)
{
pre=pre->link;
if(pre->link==head)
break;
}
p=pre->link;
if(pos>i+1||pos<1)
{
cout<<"\n* position out of range *";
}
else
{
if(pos==1)
{
head=head->link;
end->link=head;
}
else
{
pre->link=p->link;
}
list-=1;
cout<<"\ndata has been deleted...";
}
}
}
void display()
{
cout<<"CIRCULAR LINKED LIST->";
p=head;
cout<<p->data;
for(int c=0;c<=list-1;c++)
{
cout<<"->";
p=p->link;
cout<<p->data;
}
}
void main()
{
char ch,x;
clrscr();
 while(1)
{
cout<<"\n\tCIRCULAR LINKED LIST MENU";
cout<<"\n1.create 2.insert 3.delete 4.display 5.exit";
cout<<"\nenter the choce:";
cin>>ch;
switch(ch)
{
case '1':
create();
break;
case '2':
insert();
break;
case '3':
del();
break;
case '4':
display();
break;
case '5':
cout<<"press y(or)Y to exit";
x=getch();
if(x=='y'||x=='Y')
exit(0);
break;
default:
cout<<"* wrong choice *";
}
getch();
}
}
Ex no – 2 IMPLEMENTATION OF STACK
11-09-2008

AIM:
To write a c++ program to implement stack operations.

ALGORITHM:
Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Define a class named stack and declare the needed variables and initialize

them.

Step4: In push () operation, check whether the stack is full or not. If the stack is

not full, insert the element into the stack by incrementing top value.

Step5: In pop () operation, check whether the stack is empty or not. If the stack

is not empty, delete the element from the stack by decrementing top

value.

Step6: In peep () operation, get the position to be searched. If it is valid

position, bring the value from stack and print.

Step7: In change () operation, get the position user wish to change. If it is

valid position, get the new element and insert it into stack.

Step8: In display () method, print the stack elements using for loop.

Step9: In main () method, using switch case statement to invoke the methods

according to the user choice entered.

Step10: End of the program.

INPUT & OUTPUT:

*** STACK OPERATIONS ***

1.push
2.pop
3.peep
4.change
5.diaplay
6.exit
enter the choice:1
enter the element to push: 1
enter the choice:1
enter the element to push: 2
enter the choice:1
enter the element to push: 3
enter the choice:5
STACK
3
2
1
enter the choice:2
deleted element is 3
enter the choice:5
STACK
2
1
enter the choice:3
enter the position to search:1
element in position 1 is 2
enter the choice:4
enter the position:1
enter the element:9
enter the choice:5
STACK
9
1
enter the choice:6 <exiting…>

RESULT:

Thus the implementation of stack has been completed successfully and output
verified.
CODING:

#include<iostream.h>
#include<conio.h>
#include<process.h>
class stack
{
int st[10],top,i;
public:
stack()
{
top=0;
}
void push(int e1)
{
if(top>10)
{
cout<<"\nstack full";
}
else
{
st[top]=e1;
top++;
}
}
void pop()
{
if(top==0)
{
cout<<"\n*stack empty*";
}
else
{
top--;
cout<<"\ndeleted element is "<<st[top];
}
}
void display()
{
cout<<"\t\tSTACK\n";
for(i=top-1;i>=0;i--)
cout<<"\t\t"<<st[i]<<"\n";
}
void peep(int p1)
{
if(top-p1<=0)
 cout<<"\ninvalid position";
else
cout<<"\nelement in position "<<p1 <<"is "<<st[top-p1];
}
void change(int e2,int p2)
{
if(top-p2<=0)
cout<<"\ninvalid position";
else
st[top-p2]=e2;
}
};
void main()
{
int c,e,p,pp,ee;
stack s;
clrscr();
do
{
cout<<"\n\n*** STACK OPERATIONS ***\n";
cout<<"\n1.push\n2.pop\n3.peep\n4.change\n5.diaplay\n6.exit";
cout<<"\nenter the choice:"; cin>>c;
switch(c)
{
case 1:
cout<<"\nenter the element to push:"; cin>>e;
s.push(e); break;
case 2:
s.pop(); break;
case 3:
cout<<"\nenter the position to search:"; cin>>p;
s.peep(p); break;
case 4:
cout<<"\nenter the position:"; cin>>pp;
cout<<"\nenter the element:"; cin>>ee;
s.change(ee,pp); break;
case 5:
s.display(); break;
case 6:
exit; break;
default:
break;
}
}while(c<=5);
}
Ex no – 3 IMPLEMENTATION OF QUEUE
11-09-2008

AIM:
To write a c++ program to implement queue operations.

ALGORITHM:
Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Define a class named queue and declare the needed variables and

Initialize them.

Step4: In insert () operation, check whether the queue is full or not. If the queue

is not full, insert the element into the queue by incrementing rear value.

Step5: In delete () operation, check whether the queue is empty or not. If the

queue is not empty, delete the element from the queue by incrementing

front value.

Step6: In display () method, print the queue elements using for loop.

Step7: In main () method, using switch case statement to invoke the methods

according to the user choice entered.

Step8: End of the program.

INPUT & OUTPUT:

*** QUEUE OPERATIONS ***

1.insert
2.delete
3.display
4.exit

enter the option:1

enter the element:1
enter the option:1
enter the element:2
enter the option:1
enter the element:3

enter the option:3

QUEUE :1 2 3

enter the option:2

deleted element is: 1
enter the option:2
deleted element is: 2
enter the option:2
deleted element is: 3

enter the option:2

* queue empty *

enter the option:3

QUEUE :

enter the option:4 <exiting…>

RESULT:

Thus the implementation of queue has been completed successfully and output
verified.
CODING:

#include<iostream.h>
#include<conio.h>
#include<process.h>
class queue
{
int e1;
int q[10];
int front,rear;
public:
queue()
{
front=-1;
rear=-1;
q[10]=NULL;
}
void insert(int e1)
{
if(rear>10)
{cout<<"\n* queue full *";}
else
{
rear++;
q[rear]=e1;
}
if(front==-1)
front=0;
}
void del()
{
if(front==-1)
cout<<"\n* queue empty *";
else
{
if(front==rear)
{
cout<<"\ndeleted element is: "<<q[front];
front=-1;
rear=-1;
}
else
{
cout<<"\ndeleted element is: "<<q[front];
front++;
}
 }
}
void display()
{
int i;
cout<<"\n\tQUEUE :";
for(i=front;i<=rear;i++)
{
cout<<q[i]<<"\t";
}
}
};
void main()
{
int o,e;
queue q;
clrscr();
do
{
cout<<"\n\t*** QUEUE OPERATIONS ***";
cout<<"\n1.insert\n2.delete\n3.display\n4.exit";
cout<<"\nenter the option:";
cin>>o;
switch(o)
{
case 1:
cout<<"\nenter the element:";
cin>>e;
q.insert(e);
break;
case 2:
q.del();
break;
case 3:
q.display();
break;
case 4:
exit(0);
break;
}
}while(o<=3);
getch();
}
Ex no – 4 IMPLEMENTATION OF SEARCHING
18-9-2008 TECHNIQUES

AIM:
To write a c++ program to implement searching techniques.

ALGORITHM:

i) LINEAR SEARCH (SEQUENTIAL SEARCH):

 Start from the beginning.

 Access the first record and check if this is what you are looking for.
o If yes then return the element.
o If no then continue with next record until done or no more records.

ii) INDEXED SEQUENTIAL SEARCH:

 Instead of checks every element of a list, checks every index associated with an
element.
 Repeat the check until a match is found.

iii) BINARY SEARCH:

 Have to start with an ordered list.

 Start with the middle number
o If it matches, then return the element.
o If middle number is less than entered number, then continue in the same
way with the first half of the remaining list.
o If middle number is greater than number, then continue in the same way
with the second half of the remaining list.
o Repeat the steps until the data element is found.
INPUT & OUTPUT:

*** LINEAR SEARCH ***

enter the no of elements in the array:4

enter the array elements:

location0 3445
location1 32
location2 87
location3 1

enter the element to be searched:32

element is present at location1

*** INDEXED SEQUENTIAL SEARCH ***

enter the no of elements:4

enter the key and data for element1:1 654

enter the key and data for element2:2 134
enter the key and data for element3:3 98
enter the key and data for element4:4 34

enter the key to search:3

* ITEM FOUND *
the item is:98

*** BINARY SEARCH ***

enter the no of elements:5

enter the key and data for element1:1 78

enter the key and data for element2:2 456
enter the key and data for element3:3 876
enter the key and data for element4:4 987
enter the key and data for element5:5 2

enter the key to search:4

* ITEM FOUND *
the item is:987

RESULT:
 Thus the implementation of searching techniques has been completed successfully
and output verified.
CODING:

LINEAR SEARCH (SEQUENTIAL SEARCH):

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int *a,n,i,elt,loc;
template<class T>
class linear
{
public:
void linearsearch();
};
template<class T>
void linear<T>::linearsearch()
{
for(i=0;i<n;i++)
{
if(a[i]==elt)
{
cout<<"\n element is present at location"<<loc;
break;
}
loc++;
}
if(i>=n)
cout<<"\n element not found";
}
void main()
{
clrscr();
linear<float> l1;
cout<<"\n\t\t*** LINEAR SEARCH ***";
cout<<"\n enter the no of elements in the array:";
cin>>n;
a=new int(n);
cout<<"\n enter the array elements:";
for(i=0;i<n;i++)
{
cout<<"\n location"<<i<<" ";
cin>>a[i];
}
 cout<<"\n enter the element to be searched:";
cin>>elt;
loc=0;
l1.linearsearch();
getch();
}

INDEXED SEQUENTIAL SEARCH:

#include<iostream.h>
#include<conio.h>
#include<process.h>
void main()
{
int data[10],key[10],i,n,z,target;
clrscr();
cout<<"\t*** INDEXED SEQUENTIAL SEARCH ***\nenter the no of
elements:";
cin>>n;
for(z=0;z<n;z++)
{
cout<<"\n enter the key and data for element"<<z+1<<":";
cin>>key[z]>>data[z];
}
while(1)
{
cout<<"\n enter the key to search:";
cin>>target;
for(i=0;i<n;i++)
{
if(key[i]==target)
{
cout<<"\n* ITEM FOUND *";
cout<<"\n the item is:"<<data[i];
getche();
exit(0);
}
}
if(i>=n)
cout<<"\n * ITEM NOT FOUND *";
getch();
}
}
BINARY SEARCH:

#include<iostream.h>
#include<conio.h>
void main()
{
int data[10],key[10],l,h,mid,n,z,target,found;
clrscr();
cout<<"\t*** BINARY SEARCH ***\nenter the no of elements:";
cin>>n;
for(z=0;z<n;z++)
{
cout<<"\n enter the key and data for element"<<z+1<<":";
cin>>key[z]>>data[z];
}
cout<<"\n enter the key to search:";
cin>>target;
found=0;
l=0;
h=n;
do
{
mid=(l+h)/2;
if(target<key[mid])
h=mid-1;
else if(target>key[mid])
l=mid+1;
else
{
found=1;
cout<<"\n* ITEM FOUND *";
cout<<"\nthe item is:"<<data[mid];
}
}while(h<l || found!=1);
getch();
}
Ex no – 5 IMPLEMENTATION OF SORTING
25-9-2008 TECHNIQUES
AIM:
To write a c++ program to implement sorting techniques.

ALGORITHM:
i) BUBBLE SORT

 Comparing each item in the list with the item next to it, and swapping
them if required.
 Repeat this process until it makes a pass all the way through the list
without swapping any items (or) all items are in the correct order.

ii) INSERTION SORT

 Moving the current item past the already sorted items.

 repeatedly swapping it with the preceding item until it is in place.

iii) SELECTION SORT

 The selection sort works by selecting the smallest unsorted item remaining
in the list.
 And then swapping it with the item in the next position to be filled.

iv) SHELL SORT

 The algorithm makes multiple passes through the list, and each time sorts
a number of equally sized sets using the insertion sort.
 The size of the set to be sorted gets larger with each pass through the list,
until the set consists of the entire list.

v) HEAP SORT
  It begins by building a heap out of the dataset, and then removing the
largest item and placing it at the end of the sorted array.
 After removing the largest item, it reconstructs the heap and removes the
largest remaining item and places it in the next open position from the end
of the sorted array. This is repeated until there are no items left in the heap
and the sorted array is full.

vi) MERGE SORT

 The merge sort splits the list to be sorted in to two equal halves, and places
them in separate arrays.
 Each array is recursively sorted using the same algorithm, and then
merged back together to form the final sorted list.

vii) QUICK SORT

 If there is one or less elements in the array to be sorted, return

immediately.
 Pick an element in the array to serve as a ‘pivot’ point. (Usually the left
most element in the array is used.)
 Split the array in to two parts – one with elements larger than the pivot and
the other with elements smaller than the pivot.
 Recursively repeat the algorithm for both halves of the original array.
INPUT & OUTPUT:

*** SORTING MENU ***

1. bubble sort 2.insertion sort 3.selection sort 4.exit
enter the choice:1
*** BUBBLE SORT ***
enter the number of elements:5
enter the element1:78
enter the element2:45
enter the element3:98
enter the element4:23
enter the element5:5
*** SORTED ELEMENTS ***
5 23 45 78 98

enter the choice:2

*** INSERTION SORT ***
enter the number of elements:5
enter the element1:23
enter the element2:1
enter the element3:987
enter the element4:56
enter the element5:76
*** SORTED ELEMENTS ***
1 23 56 76 987

enter the choice:3

*** SELECTION SORT ***
enter the number of elements:5
enter the element1:34
enter the element2:2
enter the element3:1
enter the element4:876
enter the element5:567
*** SORTED ELEMENTS ***
1 2 34 567 876

enter the choice:4 <exiting…>

*** SHELL SORT ***

enter the no of elements:5
enter the element1:34
enter the element2:765
 enter the element3:2
enter the element4:98
enter the element5:67
*** SORTED ELEMENTS ***
2 34 67 98 765

*** HEAP SORT ***

enter the no of elements:5
enter the element1:43
enter the element2:76
enter the element3:23
enter the element4:65
enter the element5:6
*** SORTED ELEMENTS ***
6 23 43 65 76

*** MERGE SORT ***

enter the no of elements:5
enter the element1:43
enter the element2:65
enter the element3:78
enter the element4:23
enter the element5:12
*** SORTED ELEMENTS ***
12 23 43 65 78

*** QUICK SORT ***

enter the no of elements:5
enter the element1:3
enter the element2:6
enter the element3:54
enter the element4:87
enter the element5:1
*** SORTED ELEMENTS ***
1 3 6 54 87

RESULT:

Thus the implementation of sorting techniques has been completed successfully

and output verified.
CODING:

BUBBLE SORT, INSERTION SORT, SELECTION SORT:

#include<iostream.h>
#include<conio.h>
#include<process.h>
void main()
{
int array[100];
int n,temp,ch,j,k,s,i,a;
clrscr();
while(1)
{
cout<<"\n\t\t*** SORTING MENU ***";
cout<<"\n1. bubble sort\n2.insertion sort\n3.selection sort\n4.exit";
cout<<"\nenter the choice:";
cin>>ch;
switch(ch)
{
case 1:
cout<<"\t\t*** BUBBLE SORT ***";
cout<<"\nenter the number of elements:";
cin>>n;
for(i=0;i<n;i++)
{
cout<<"\nenter the element"<<i+1<<":";
cin>>array[i];
}
for(a=1;a<=n-1;a++)
{
for(j=0;j<=n-a-1;j++)
{
if(array[j]>array[j+1])
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
cout<<"\n*** SORTED ELEMENTS ***\n";
for(k=0;k<n;k++)
{
 cout<<array[k]<<" ";
}
break;
case 2:
cout<<"\t\t*** INSERTION SORT ***";
cout<<"\nenter the number of elements:";
cin>>n;
if(n==0 ||n==1)
{
return;
}
else
{
for(a=0;a<n;a++)
{
cout<<"\nenter the element"<<a+1<<":";
cin>>array[a];
}
}
for(i=1;i<n;i++)
{
j=i;
while(j>=1)
{
if(array[j]<array[j-1])
{
temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
j=j-1;
}
}
cout<<"\n*** SORTED ELEMENTS ***\n";
for(k=0;k<n;k++)
{
cout<<array[k]<<" ";
}
break;
case 3:
cout<<"\t\t*** SELECTION SORT ***";
cout<<"\nenter the number of elements:";
cin>>n;
for(a=0;a<n;a++)
{
cout<<"\nenter the element"<<a+1<<":";
 cin>>array[a];
}
for(j=0;j<n;j++)
{
k=j;
s=array[j];
for(i=j+1;i<n;i++)
{
if(array[i]<s)
{
s=array[i];
k=i;
}
}
s=array[j];
array[j]=array[k];
array[k]=s;
}
cout<<"\n*** SORTED ELEMENTS ***\n";
for(k=0;k<n;k++)
{
cout<<array[k]<<" ";
}
break;
case 4:
exit(0);
break;
default:
cout<<"\nenter the choice correctly...";
}
getch();
}
}

SHELL SORT:

#include<iostream.h>
#include<conio.h>
void shell(int a[],int n);
int a[100],i,n,j,k,s,z;
void main()
{
clrscr();
cout<<"\t*** SHELL SORT ***\nenter the no of elements:";
cin>>n;
for(z=0;z<n;z++)
 {
cout<<"\n enter the element"<<z+1<<":";
cin>>a[z];
}
shell(a,n);
cout<<"\n*** SORTED ELEMENTS ***\n";
for(z=0;z<n;z++)
{
cout<<" "<<a[z];
}
getch();
}
void shell(int a[],int n)
{
for(i=(n+1)/2;i>=1;i=i/2)
{
for(j=i;j<n;j++)
{
s=a[j];
k=j-i;
while(k>=0 && s<a[k])
{
a[k+i]=a[k];
k=k-i;
}
a[k+i]=s;
}
}
}

HEAP SORT:

#include<iostream.h>
#include<conio.h>
void heap(int a[],int n);
void createheap(int a[],int n);
void main()
{
int a[100],i,n,z;
clrscr();
cout<<"\t*** HEAP SORT ***\nenter the no of elements:";
cin>>n;
for(z=0;z<n;z++)
{
cout<<"\n enter the element"<<z+1<<":";
cin>>a[z];
 }
heap(a,n);
cout<<"\n*** SORTED ELEMENTS ***\n";
for(z=0;z<n;z++)
{
cout<<" "<<a[z];
}
getch();
}
void createheap(int a[],int n)
{
int i,j,q,key;
for(q=1;q<n;q++)
{
i=q;
key=a[q];
j=(int)(i/2);
while((i>0)&&(key>a[j]))
{
a[i]=a[j];
i=j;
j=(int)(i/2);
if(j<0)
j=0;
}
a[i]=key;
}
}
void heap(int a[],int n)
{
int i,j,q,key,temp;
createheap(a,n);
for (q=n-1;q>=1;q--)
{
temp=a[0];
a[0]=a[q];
a[q]=temp;
i=0;
key=a[0];
j=1;
if((j+1)<q)
if(a[j+1]>a[j])
j=j+1;
while((j<=(q-1)) && (a[j]>key))
{
a[i]=a[j];
 i=j;
j=2*i;
if((j+1)<q)
if(a[j+1]>a[j])
j=j+1;
else if(j>n-1)
j=n-1;
a[i]=key;
}
}
}

MERGE SORT:

#include<iostream.h>
#include<conio.h>
void merge(int a[],int f1,int l1,int f2,int l2);
void split(int a[],int f,int l);
int a[100],b[100];
void main()
{
int n,z;
clrscr();
cout<<"\t*** MERGE SORT ***\nenter the no of elements:";
cin>>n;
for(z=0;z<n;z++)
{
cout<<"\n enter the element"<<z+1<<":";
cin>>a[z];
}
split(a,0,n-1);
cout<<"\n*** SORTED ELEMENTS ***\n";
for(z=0;z<n;z++)
{
cout<<" "<<a[z];
}
getch();
}
void split(int a[],int f,int l)
{
int m;
if(f<l)
{
m=(f+l)/2;
split(a,f,m);
split(a,m+1,l);
 merge(a,f,m,m+1,l);
}
}
void merge(int a[],int f1,int l1,int f2,int l2)
{
int i,j,k=0;
i=f1;
j=f2;
while(i<=l1 && j<=l2)
{
if(a[i]<a[j])
b[k]=a[i++];
else
b[k]=a[j++];
k++;
}
while(i<=l1)
b[k++]=a[i++];
while(j<=l2)
b[k++]=a[j++];
i=f1;
j=0;
while(i<=l2 && j<k)
a[i++]=b[j++];
}

QUICK SORT:

#include<iostream.h>
#include<conio.h>
void quick(int a[],int l,int r);
void swap(int a[],int i,int j);
int a[100],i,j,n,pivot;
void main()
{
int z;
clrscr();
cout<<"\t*** QUICK SORT ***\nenter the no of elements:";
cin>>n;
for(z=0;z<n;z++)
{
cout<<"\n enter the element"<<z+1<<":";
cin>>a[z];
}
quick(a,0,n-1);
cout<<"\n*** SORTED ELEMENTS ***\n";
 for(z=0;z<n;z++)
{
cout<<" "<<a[z];
}
getch();
}
void quick(int a[],int f,int l)
{
if(f<l)
{
pivot=a[f];
i=f;
j=l;
while(i<j)
{
while(a[i]<=pivot && i<l)
{
i++;
}
while(a[j]>=pivot && j>f)
{
j--;
}
if(i<j)
swap(a,i,j);
}
swap(a,f,j);
quick(a,f,j-1);
quick(a,j+1,l);
}
}
void swap(int a[],int i, int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
Ex no – 6 IMPLEMENTATION OF HASH TABLE
23-10-2008

AIM:
To write a c++ program to implement hash table.

ALGORITHM:

Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Declare and initialize needed variables.

Step4: Get the size of the hash table from the user and makes the indices

sequentially based on size.

Step5: Then get the integer number from the user i.e. file. And compute the hash

function for that number using the given formula.

Hash function= (int) e % size of the hash table

Step6: Finally, store the number in corresponding location in the hash table.

Step7: Check whether the hash table is empty or full during insertion and

deletion function.

Step8: Print the contents of hash table whenever the user needs to view.

Step9: End of the program.

INPUT & OUTPUT:

enter the size of the hash table:5

*** HASH TABLE MENU ***

1.insert
2.delete
3.display
4.exit
enter the choice:1
enter the element::456
press any key to continue...
enter the choice:1
enter the element::33
press any key to continue...
enter the choice:3

HASH TABLE
-------------------------
position element
-------------------------
0 -1
1 456
2 -1
3 33
4 -1
-------------------------
press any key to continue...
enter the choice:2
enter the element:33
element has been deleted...
press any key to continue...
enter the choice:4
press any key to continue... <exiting…>

RESULT:
 Thus the implementation of hash table has been completed successfully and
output verified.

CODING:

#include<iostream.h>
#include<conio.h>
enum bool{false,true};
template<class T>
class hash
{
T *tab;
int size;
public:
hash(int s);
~hash();
void insert();
void del();
void display();
bool isfull();
bool isempty();
};
template<class T>
hash<T>::hash(int s)
{
size=s;
tab=new T[size];
for(int i=0;i<size;i++)
tab[i]=-1;//tab[i]=NULL;
}
template<class T>
hash<T>::~hash()
{
delete []tab;
}
template<class T>
bool hash<T>::isfull()
{
for(int i=0;i<size;i++)
if(tab[i]==-1)
return false;
return true;
}
template<class T>
bool hash<T>::isempty()
{
for(int i=0;i<size;i++)
if(tab[i]!=-1)
return false;
return true;
}
template<class T>
void hash<T>::insert()
{
T e;
int p;
cout<<"\n enter the element::";
cin>>e;
if(!isfull())
{
p=(int)e%size;
do
{
if((tab[p]==-1))
{
tab[p]=e;
break;
}
p++;
if(p==size)
p=0;
}while(1);
}
else
{
cout<<"\n* hashtable is full *";
}
}
template<class T>
void hash<T>::del()
{
T e;
int p,cnt,st=0;
cout<<"\n enter the element:";
cin>>e;
if(!isempty())
{
p=(int)e%size;
for(cnt=0;cnt<size;cnt++)
{
if((tab[p]==e))
 {
tab[p]=-1;
cout<<"\n element has been deleted...";
st=1;
break;
}
p++;
if(p==size)
p=0;
}
if(st==0)
cout<<"\n element not found...";
}
else
cout<<"\n* hashtable is empty *";
}
template<class T>
void hash<T>::display()
{
cout<<"\n\tHASH TABLE";
cout<<"\n------------------------";
cout<<"\nposition\telement";
cout<<"\n------------------------";
for(int i=0;i<size;i++)
cout<<"\n"<<i<<"\t\t"<<tab[i];
cout<<"\n------------------------";
}
void main()
{
int ch,s;
int st=1;
clrscr();
cout<<"\nenter the size of the hash table:";
cin>>s;
hash<float>ht(s);
while(st)
{
clrscr();
cout<<"\n*** HASH TABLE MENU ***";
cout<<"\n1.insert\n2.delete\n3.display\n4.exit\n";
cout<<"\n enter the choice:";
cin>>ch;
switch(ch)
{
case 1:
ht.insert();
 break;
case 2:
ht.del();
break;
case 3:
ht.display();
break;
case 4:
st=0;
break;
}
cout<<"\n press any key to continue...";
getch();
}
}
Ex no – 7 IMPLEMENTATION OF HEAP
23-10-2008

AIM:
To write a c++ program to implement heap.

ALGORITHM:

Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Declare the needed variables and initialize them.

Step4: By defining the priority queue, we can perform operations on heap.

Step5: insert an item arbitrarily at any where in the priority queue.

Step6: delete an item that has highest priority i.e. maximum value from the

priority queue. This is called max heap.

Step7: delete an item that has lowest priority i.e. minimum value from the

priority queue. This is called min heap.

Step8: print the contents of heap using for loop.

Step9: End of the program.

INPUT & OUTPUT:

*** HEAP MENU ***

1.insert
2.delete
3.display
4.exit

enter the choice:1

enter the data to be inserted:45
the inserted data is: 45
enter the choice:1
enter the data to be inserted:234
the inserted data is: 234
enter the choice:1
enter the data to be inserted:7
the inserted data is: 7
enter the choice:3

heap contents are: 234 45 7

enter the choice:2

the element deleted is234
enter the choice:2
the element deleted is45
enter the choice:3

heap contents are: 7

enter the choice:4 <exiting…>

RESULT:
 Thus the implementation of heap has been completed successfully and output
verified.

CODING:

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 10
template<class T>
class pqueue
{
public:
T data[MAX];
T last;
pqueue()
{
last=0;
}
void insert();
void display();
T pqdel();
};
template<class T>
void pqueue<T>::insert()
{
T i,x,temp;
if(last==MAX)
cout<<"\npriority queue is full";
else
{
last=last+1;
cout<<"\n enter the data to be inserted:";
cin>>x;
cout<<endl<<"\nthe inserted data is: "<<x;
data[last]=x;
i=last;
while(i>1 && (data[i/2]<data[i]))
{
temp=data[i];
data[i]=data[i/2];
data[i/2]=temp;
i=i/2;
}
 }
}
template<class T>
T pqueue<T>::pqdel()
{
T i,j,temp;
int min;
if(last==0)
cout<<"\n priority queue is empty";
else
{
min=data[1];
data[1]=data[last];
last=last-1;
i=1;
while(i<=last/2)
{
if((data[2*i]>data[(2*1)+1]) || (2*1)==last)
j=2*i;
else
j=2*i+1;
if(data[i]<data[j])
{
temp=data[i];
data[i]=data[j];
data[j]=temp;
i=j;
}
else
{
return(min);
}
}
return(min);
}
return 0;
}
template<class T>
void pqueue<T>::display()
{
T k;
cout<<"\nheap contents are: ";
for(k=1;k<=last;k++)
{
cout<<data[k]<<"\t";
}
}
void main()
{
int ch;
clrscr();
pqueue<int>p;
while(1)
{
cout<<"\n\t*** HEAP MENU ***";
cout<<"\n1.insert\n2.delete\n3.display\n4.exit\n";
cout<<"\nenter the choice:";
cin>>ch;
switch(ch)
{
case 1:
p.insert();
break;
case 2:
cout<<"\n the element deleted is"<<p.pqdel();
break;
case 3:
p.display();
break;
case 4:
exit(0);
break;
}
}
}
Ex no – 8 IMPLEMENTATION OF PRIM’S
13-11-2008 ALGORITHM

AIM:
To write a c++ program to implement prim’s algorithm.

ALGORITHM:

Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Get the number of nodes from the user and get weight for each vertex.

Step4: The general algorithm for this process is as follows,

o select a starting node.

o build the initial fringe from nodes connected to the starting node

o while there are nodes left do

 choose the edge to the fringe of the smallest weight

 add the associated node to the tree

 update the fringe by:

 adding nodes to the fringe connected to the new node

 updating the edges to the fringe so that they are the smallest

o end while

Step5: Print the minimal spanning tree.

Step6: End of the program.

INPUT & OUTPUT:

*** prim's algorithm ***

enter the number of vertices : 4

enter the cost of each vertex(enter 99 -if there is no cost

enter the cost from vertex 1 to 2:9

enter the cost from vertex 1 to 3:3
enter the cost from vertex 1 to 4:2
enter the cost from vertex 2 to 1:9
enter the cost from vertex 2 to 3:99
enter the cost from vertex 2 to 4:1
enter the cost from vertex 3 to 1:3
enter the cost from vertex 3 to 2:99
enter the cost from vertex 3 to 4:6
enter the cost from vertex 4 to 1:2
enter the cost from vertex 4 to 2:1
enter the cost from vertex 4 to 3:6

the output minimal spanning tree will be...

4 to 1 : weight is: 2
2 to 4 : weight is: 1
3 to 1 : weight is: 3
RESULT:

Thus the implementation of prim’s algorithm has been completed successfully

and output verified.

CODING:

#include<iostream.h>
#include<conio.h>

template<class P>
class prim
{
private:
int n,i,j,k,min;
float c[100][100];
float lowcost[100],closest[100];
public:
void getinput();
void output();
};

template<class P>
void prim<P>::getinput()
{
cout<<"\n\t *** prim's algorithm ***";
cout<<"\n enter the number of vertices : ";
cin >>n;
cout<<"\n enter the cost of each vertex(enter 99 -if there is no cost\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i!=j)
{
cout<<"\nenter the cost from vertex "<<i<<" to "<<j<<":";
cin>>c[i][j];
}
else
c[i][j]=0;
}
}
}

template<class P>
void prim<P>::output()
{
cout<<"\n the output minimal spanning tree will be...";
for(i=2;i<=n;i++)
{
lowcost[i]=c[1][i];
closest[i]=1;
}
for(i=2;i<=n;i++)
{
min=lowcost[2];
k=2;
for(j=3;j<=n;j++)
{
if(lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
}
cout<<"\n"<<k<<" to "<<closest[k]<<" : "<<"weight is: "<<lowcost[k];
lowcost[k]=99;
for(j=2;j<=n;j++)
{
if((c[k][j]<lowcost[j]) && (lowcost[j]<99))
{
lowcost[j]=c[k][j];
closest[j]=k;
}
}
}
}
void main()
{
clrscr();
prim<int>p1;
p1.getinput();
p1.output();
getch();
}
Ex no – 9IMPLEMENTATION OF BREADTH FIRST
20-11-2008 SEARCH TECHNIQUE

AIM:
To write a c++ program to implement breadth first search (BFS) technique.

ALGORITHM:

Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Get the number of nodes from the user and get the edges.

Step4: The general algorithm for BFS is as follows,

BreadthFirstTraversal ( G , v )
G is the graph
v is the current node
Visit ( v )
Mark ( v )
Enqueue ( v )
while the queue is not empty do
Dequeue ( x )
for every edge x w in G do
if w is not marked then
Visit (w)
Mark(w)
Enqueue(w)
end if
end for
 end while
Step5: Print the minimal spanning tree.

Step6: End of the program.

INPUT & OUTPUT:

enter the no of nodes : 7

enter the edges:1 3

press 1 to continue 0 to terminate...1

enter the edges:3 2

press 1 to continue 0 to terminate...1

enter the edges:3 4

press 1 to continue 0 to terminate...1

enter the edges:2 5

press 1 to continue 0 to terminate...1

enter the edges:3 5

press 1 to continue 0 to terminate...1

enter the edges:3 6

press 1 to continue 0 to terminate...1

enter the edges:5 6

press 1 to continue 0 to terminate...1

enter the edges:6 7

press 1 to continue 0 to terminate...0

enter the start node:1

output: 1 3 2 4 5 6 7

RESULT:
 Thus the implementation of breadth first search (BFS) technique has been
completed successfully and output verified.

CODING:

#include<iostream.h>
#include<conio.h>
class bfs
{
int g[10][10],num,v[10],q[10];
public:
bfs(int);
int get();
int bfssearch(int);
};
bfs::bfs( int n)
{
num=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=g[j][i]=0;
for(i=1;i<=n;i++)
v[i]=0;
}
int bfs::get()
{
int v1,v2,i,c=1;
while(c)
{
cout<<"\n enter the edges:";
cin>>v1>>v2;
g[v1][v2]=g[v2][v1]=1;
cout<<"\n press 1 to continue 0 to terminate...";
cin>>c;
}
return 0;
}
int bfs::bfssearch(int v1)
{
int v2,front,rear;
v[v1]=1;
front=rear=1;
q[++rear]=v1;
while(front!=rear)
 {
v1=q[++front];
cout<<v1<<" ";
for(v2=1;v2<=num;v2++)
if(g[v1][v2] == 1 && v[v2]==0)
{
q[++rear]=v2;
v[v2]=1;
}
}
return 0;
}
int main()
{
int n;
clrscr();
cout<<"\n enter the no of nodes: ";
cin>>n;
bfs d(n);
d.get();
int s;
cout<<"\n enter the start node:";
cin>>s;
cout<<"\n output: ";
d.bfssearch(s);
getch();
return(0);
}
Ex no – 10 IMPLEMENTATION OF DEPTH FIRST
4-12-2008 SEARCH TECHNIQUE

AIM:
To write a c++ program to implement depth first search (DFS) technique.

ALGORITHM:

Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Get the number of nodes from the user and get the edges.

Step4: The general algorithm for DFS is as follows,

DepthFirstTraversal ( G , v )

G is the graph

v is the current node

Visit ( v )

Mark ( v )

for every edge v w in G do

if w is not marked then

DepthFirstTraversal ( G , w )

end if

end for

Step5: Print the minimal spanning tree.

Step6: End of the program.

INPUT & OUTPUT:

enter the number of nodes:7

enter the adjacency matrix:
enter the value of (1,2) elements:0
enter the value of (1,3) elements:1
enter the value of (1,4) elements:0
enter the value of (1,5) elements:0
enter the value of (1,6) elements:0
enter the value of (1,7) elements:0
enter the value of (2,1) elements:0
enter the value of (2,3) elements:1
enter the value of (2,4) elements:0
enter the value of (2,5) elements:1
enter the value of (2,6) elements:0
enter the value of (2,7) elements:0
enter the value of (3,1) elements:1
enter the value of (3,2) elements:1
enter the value of (3,4) elements:1
enter the value of (3,5) elements:1
enter the value of (3,6) elements:1
enter the value of (3,7) elements:0
enter the value of (4,1) elements:0
enter the value of (4,2) elements:0
enter the value of (4,3) elements:1
enter the value of (4,5) elements:0
enter the value of (4,6) elements:0
enter the value of (4,7) elements:0
enter the value of (5,1) elements:0
enter the value of (5,2) elements:1
enter the value of (5,3) elements:1
enter the value of (5,4) elements:0
enter the value of (5,6) elements:1
enter the value of (5,7) elements:0
enter the value of (6,1) elements:0
enter the value of (6,2) elements:0
enter the value of (6,3) elements:1
enter the value of (6,4) elements:0
enter the value of (6,5) elements:1
enter the value of (6,7) elements:1
enter the value of (7,1) elements:0
enter the value of (7,2) elements:0
enter the value of (7,3) elements:0
enter the value of (7,4) elements:0
enter the value of (7,5) elements:0
enter the value of (7,6) elements:1

nodes are visited in this order ->1->3->2->5->6->7->4

RESULT:
 Thus the implementation of depth first search (DFS) technique has been
completed successfully and output verified.

CODING:

#include<iostream.h>
#include<conio.h>
int a[10][10],visited[10],n;
void search(int);
void main()
{
int i,j;
clrscr();
cout<<"enter the number of nodes:";
cin>>n;
cout<<"\nenter the adjacency matrix:";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
cout<<"\nenter the value of ("<<i<<","<<j<<")
elements:";
cin>>a[i][j];
}
cout<<"\nnodes are visited in this order";
for(i=1;i<=n;i++)
if(visited[i]==0)
search(i);
getche();
}
void search(int k)
{
int i;
cout<<"->"<<k;
visited[k]=1;
for(i=2;i<=n;i++)
if(a[k][i]!=0)
if(visited[i]==0)
search(i);
}
Ex no – 11 IMPLEMENTATION OF DIJKSTRA’S
11-12-2008 ALGORITHM

AIM:
To write a c++ program to implement dijkstra’s algorithm.

ALGORITHM:

Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Get the number of vertices from the user and get cost for each vertex.

Step4: The general algorithm for this process is as follows,

o select a starting node

o build the initial fringe from nodes connected to the starting node
o while we are not at the destination node do
 choose the fringe node with the shortest path to the starting node
 add that node and its edge to the tree
 update the fringe by:
 adding nodes to the fringe connected to the new node
 for each node in the fringe do
update its edge one connected to the tree on the
shortest path to the starting node
 end for
o end while

Step5: Print the shortest path.

Step6: End of the program.

INPUT & OUTPUT:

*** DIJKSTRA’S ALGORITHM ***

enter the no of vertices: 5

cost between1—2: 2
cost between1—3: 1
cost between1—4: 0
cost between1—5: 0
cost between2—1: 2
cost between2—3: 5
cost between2—4: 4
cost between2—5: 0
cost between3—1: 1
cost between3—2: 5
cost between3—4: 3
cost between3—5: 2
cost between4—1: 0
cost between4—2: 4
cost between4—3: 3
cost between4—5: 6
cost between5—1: 0
cost between5—2: 0
cost between5—3: 2
cost between5—4: 6
minimum cost FROM 1 TO 2 is : 2
minimum cost FROM 1 TO 3 is : 1
minimum cost FROM 1 TO 4 is : 4
minimum cost FROM 1 TO 5 is : 3

RESULT:
 Thus the implementation of dijkstra’s algorithm has been completed successfully
and output verified.
CODING:

#include<iostream.h>
#include<conio.h>
#define INFINITY 1000
int a[10][10],b[10][10];
int i,j,k,n;
class dijkstra
{
public:
void input();
void initialize();
void spath();
void display();
};
void dijkstra::input()
{
cout<<"\n\t *** DIJKSTRA’S ALGORITHM ***";
cout<<"\n enter the no of vertices:"<<endl;
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)
{
cout<<"cost between"<<i<<"--"<<j<<endl;
cin>>a[i][j];
}
}
}
void dijkstra::initialize()
{
for(i=1;i<=n;i++)
a[i][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
b[i][j]=a[i][j];
if(!a[i][j] && (i!=j))
{
b[i][j]=INFINITY;
}
}
}
void dijkstra::spath()
{
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if((b[i][k] && b[k][j]) && (b[i][k]+b[k][j]<b[i][j]))
{
b[i][j]=b[i][k]+b[k][j];
}
}
void dijkstra::display()
{
i=1;
if(i<n)
{
for(j=2;j<=n;j++)
cout<<"minimum cost FROM 1 TO "<<j<<" is : "<<b[i][j]<<endl;
}
}
void main()
{
clrscr();
dijkstra d1;
d1.input();
d1.initialize();
d1.spath();
d1.display();
getch();
}
Ex no – 12 IMPLEMENTATION OF KRUSKAL’S
18-12-2008 ALGORITHM

AIM:
To write a c++ program to implement kruskal’s algorithm.

ALGORITHM:

Step1: Start the program.

Step2: Include the required header files at the top of the program.

Step3: Get the number of nodes from the user and get weight for each node.

Step4: The general algorithm for this process is as follows,

sort the edges in nondecreasing order by weight

initialize partition structure
edgeCount = 1
includedCount = 0
while edgeCount <= E and includedCount <= N-1 do
parent1 = FindRoot ( edge[edgeCount].start )
parent2 = FindRoot ( edge[edgeCount].end )
if parent1 != parent2 then
add edge[edgeCount] to spanning tree
includedCount = includedCount + 1
Union ( parent1 , parent2 )
end if
edgeCount = edgeCount + 1
end while

Step5: Print the minimum spanning tree.

Step6: End of the program.

INPUT & OUTPUT:

*** kruskal's algorithm ***

enter the no of nodes in the undirected weighted graph: 5

weight between{1,2}: 2
weight between{1,3}: 1
weight between{1,4}: 0
weight between{1,5}: 0
weight between{2,3}: 5
weight between{2,4}: 4
weight between{2,5}: 0
weight between{3,4}: 3
weight between{3,5}: 2
weight between{4,5}: 6

edges in the given graph are :

weight between {1,2}: 2
weight between {1,3}: 1
weight between {2,3}: 5
weight between {2,4}: 4
weight between {3,4}: 3
weight between {3,5}: 2
weight between {4,5}: 6

sorted edges in the given graph :

weight between {1,3}: 1
weight between {1,2}: 2
weight between {3,5}: 2
weight between {3,4}: 3
weight between {2,4}: 4
weight between {2,3}: 5
weight between {4,5}: 6

the algorithm starts:

the edges included in the graph are: {1,3}
the edges included in the graph are: {1,2}
the edges included in the graph are: {3,5}
the edges included in the graph are: {3,4}
inclusion of the edge{2,4}forms a cycle. hence it is removed...
inclusion of the edge{2,3}forms a cycle. hence it is removed...
inclusion of the edge{4,5}forms a cycle. hence it is removed...

RESULT:
 Thus the implementation of kruskal’s algorithm has been completed successfully
and output verified.

CODING:

#include<iostream.h>
#include<conio.h>
class kruskal
{
private:
int n,noe,graph_edge[100][4],tree[10][10],sets[100][10],top[100];
public:
void read_graph();
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int);
void print_min_span_t();
};
void kruskal::read_graph()
{
cout<<"\n*** kruskal's algorithm ***";
cout<<"\nenter the no of nodes in the undirected weighted graph: ";
cin>>n;
noe=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<"weight between{"<<i<<","<<j<<"}: ";
int w;
cin>>w;
if(w!=0)
{
noe++;
graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}
cout<<"\nedges in the given graph are :\n";
for(i=1;i<=noe;i++)
cout<<"weight between {"<<graph_edge[i][1]<<","<<graph_edge[i][2]
<<"}: "<<graph_edge[i][3]<<endl;
}
void kruskal::sort_edges()
{
for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;
t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;
t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}
cout<<"\n sorted edges in the given graph :\n";
for(i=1;i<=noe;i++)
cout<<"weightbetween {"<<graph_edge[i][1]<<"," <<graph_edge[i][2]
<<"}: " <<graph_edge[i][3]<<endl;
}
void kruskal::algorithm()
{
// make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}
cout<<"\n the algorithm starts:\n";
for(i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);
if(p1!=p2)
{
cout<<"the edges included in the graph are: "<<"{"
<<graph_edge[i][1]<<"," <<graph_edge[i][2] <<"}"<<endl;
tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];
//mix the two sets
 for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
else
{
cout<<"inclusion of the edge"<<"{"<<graph_edge[i][1] <<","
<<graph_edge[i][2]<<"}"<<"forms a cylce. hence it is
removed... \n";
}
}
}
int kruskal::find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
int main()
{
clrscr();
kruskal k1;
k1.read_graph();
k1.sort_edges();
k1.algorithm();
getch();
return 0;
}