VI INSTITUTE OF TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE

AND ENGINEERING

LAB MANUAL

EC2209 DATA STRUCTURES AND

OBJECT ORIENTED PROGRAMMING
LAB
(III SEMESTER ECE)

Prepared by:

MS. K.SATHIYAPRIYA
AP / CSE
Ex. No: 1a DEFAULT ARGUMENTS

Aim:

To implement function with default arguments.

Algorithm:
1.              Declare the default function.
2.              Invoke the default function.
3.              Display the result
             
Program:

#include<iostream.h>
void printLine(char =’_’,int =70);
void main()
{
printLine();
printLine(‘/’);
printLine(‘*’,40);
printLine(‘R’,55);
}
void printLine(char ch, int Repeatcount)
{
int i;
cout<<endl;
for(i=0;i<Repeatcount;i++)
cout<<ch;
}
 
Output:
 
- - - - - - - -  - - - - - - - - - - - - - - - - - - - - - - - - - - -
///////////////////////////////////////
****************************
RRRRRRRRRRRRRRRRRRRRRRR
 

Result:

EC 2209 Data Structures and Object Oriented Programming Lab 2

 Thus the Given Program function with Default Arguments was implemented
successfully.
 
Ex. No: 1b  CLASS WITH STATIC DATA MEMBER

Aim:

          To implement static data member in class.

 
Algorithm:
1.              Create class ITEM with static data member as count.
2.              Create a member function to increment the count.
3.              Declare the static datamember using scope resolution operator.
4.              Display the count value.

Program:

#include<iostream.h>
class item
{
static int count;
int num;
public:
void getdata(int a)
{
num=a;
count++;
cout<<”Number”<<num;
}
void showcount()
{
cout<<”count”;
cout<<count<<”\n”;
}
};
int item::count;
int main()
{
item a,b,c;
a.showcount();
b.showcount();
c.showcount();
a.getdata(20);
b.getdata(30);
c.getdata(40);
a.showcount();

EC 2209 Data Structures and Object Oriented Programming Lab 3

 b.showcount();
c.showcount();
}
Output:

count                            0
count                            0
count                            0
Number              20
Number              30
Number              40
count                            3
count                            3
count                            3
                             
 
 
 
 
 
 
 
 
 
 
 

 
 
 Result:

EC 2209 Data Structures and Object Oriented Programming Lab 4

 Thus the Given Program static data member in class was implemented
successfully.
 
Ex. No: 1c CLASS WITH STATIC MEMBER FUNCTION

Aim:
To implement static member function in class.

Algorithm:
1.              Create class ITEM with static data member as count.
2.              Create a member function to increment the count.
3.              Declare the static data member using scope resolution operator.
4.              Display the count value.
Program:

#include<iostream.h>
class test
{
int code;
static int count;
public:
void setcode()
{
cout<<”Object Number:”<<code<<”\n”;
}};
int test::count;
int main()
{
test t1,t2;
t1.setcount();
t2.setcount();
test::showcount();
test t3;
t1.showcode();
t2.showcode();
t3.showcode();
return(0);
}

Output:
  count                               2
count                               3
Object Number               1
Object Number               2
Object Number               3
 

EC 2209 Data Structures and Object Oriented Programming Lab 5

 Result:
Thus the Given Program static member function in class was implemented
successfully.
Ex. No: 1d OBJECT AS ARGUMENT AND RETURNING AN
OBJECT

Aim:

To write a program for object as argument and returning an object using complex
number addition.
 
Algorithm:

1. The class complex contains two member variables real and imaginary.
2. Assign the value for real and imaginary part.
3. Declare a temporary variable temp.
4. Add real part with real of other object and store it in temp’s real.
5. Add imaginary part with imaginary of other object and store it in temp’s
imaginary.
6. Display temp.

 Program:

#include<iostream.h>
template<class T>
class complex
{
private:
              T real;
T imag;
Public:
complex()
{
real=imag=0;
}
void getdata()
{
cout<<”real part?”;
cin>>real;
cout<<”imag part?”;
cin>>imag;
}
complex operator +(complex c2);
void outdata(char *msg)
{

EC 2209 Data Structures and Object Oriented Programming Lab 6

cout<<msg<<”(“<<real;
cout<<”,”<<img<<”)”<<endl;
}
};

Template<class T>
complex<T> complex<T>::operator +(complex<T>c2)
{
Complex<T>temp;
temp.real=real+c2.real;
temp.img=imag+c2.imag;
return(temp);
}
void main()
{
complex<int>c1,c2,c3;
cout<<”Addition of integercomplexobjects….”<<endl;
cout<<”Enter complex number c1..”<<endl;
c1.getdata();
cout<<”Enterthecomplexnumberc2”<<endl;
c2.getdata();
c3=c1+c2;
c3.outdata(“c3=c1+c2:”);
 
complex<float>c4,c5,c6;
cout<<”Additionof float complexobjects….”<<endl;
cout<<”Enter complex number c4..”<<endl;
c4.getdata();
cout<<”Enterthecomplexnumberc5”<<endl;
c5.getdata();
c6=c4+c5;
c6.outdata(“c6=c4+c5:”);
 
}
 

EC 2209 Data Structures and Object Oriented Programming Lab 7

 Output:

Addition of integer complexobjects…

Enter complex number c1..
Real part?1
Imag part?2
Enter complex number c2..
Real part?3
Imag part?4
C3=c1+c2:(4,6)
 
Addition of float complexobjects…
Enter complex number c4..
Real part?1.5
Imag part?2.5
Enter complex number c5..
Real part?2.4
Imag part?3.7
C6=c4+c5:(3.9,6.2)

 
Result:

EC 2209 Data Structures and Object Oriented Programming Lab 8

 Thus the Given Program Object as a argument and returning an object was
implemented successfully.
 
Ex. No:1e FRIEND FUNCTION

Aim:
              To write a c++ program for friend function.
 
Algorithm:

1.        Create the class and declare the data member as private.

2.        Declare the friend function using the keyword friend.
3. Perform the operation of adding two private variables in the friend function.
4.        Display the result.

Program:
 
#include <iostream.h>
using namespace std;
class myclass {
int a, b;
public:
friend int sum(myclass x);
void set_ab(int i, int j);
};
void myclass::set_ab(int i, int j)
{
a = i;
b = j;
}
// Note: sum() is not a member function of any class.
int sum(myclass x)
{
/* Because sum() is a friend of myclass, it can
directly access a and b. */
return x.a + x.b;
}
int main()
{
myclass n;
n.set_ab(3, 4);
cout << sum(n);
return 0;
}
Output:

EC 2209 Data Structures and Object Oriented Programming Lab 9

 7
Result:

Thus the Given Program friend function was implemented successfully.

Ex. No: 1f CLASS AND OBJECTS

Aim:
              To write a c++ program for employee wages calculation using class and objects.
 
Algorithm:
 
1. Employee class contains name and wage variable and member function a
putname(), putwage(),getwage() and getname().
2. Putname: Assign the valve for the character array name.
3. Getname: Retrieves the value of Variable name.
4. Putwage: Assign the valve for wage variable.
5. Getwage: Retrieves the value of wage variable.
6. Im main() Put and display both name and wages.
 
  
 Program:

#include <iostream.h>
using namespace std;
class employee {
char name[80]; // private by default
public:
void putname(char *n); // these are public
void getname(char *n);
private:
double wage; // now, private again
public:
void putwage(double w); // back to public
double getwage();
};
void employee::putname(char *n)
{
strcpy(name, n);
}
void employee::getname(char *n)
{
strcpy(n, name);
}
void employee::putwage(double w)
{

EC 2209 Data Structures and Object Oriented Programming Lab

10
 wage = w;
}
double employee::getwage()
{
return wage;
}
int main()
{
employee ted;
char name[80];
ted.putname("Ted Jones");
ted.putwage(75000);
ted.getname(name);
cout << name << " makes $";
cout << ted.getwage() << " per year.";
return 0;
}
 
 
Output:
 
Ted Jones makes $75000 per year.
 
 

Result:

Thus the Given Program for employee wages calculation using class and objects was
implemented successfully.

EC 2209 Data Structures and Object Oriented Programming Lab

11
  

Ex. No: 1g COPY CONSTRUCTOR

Aim:
To write a c++ program for demonstrating the copy constructor.

Algorithm:
1. Define the class
2. Declare the variables.
3. Define the function as constructor.
4. Define the main function and declare the variables.
5. Call the copy constructor.
Program:

#include<iostream.h>
class test
{
int x;
public:
//default constructor
test();
//parameterized constructor
test(int val)
{
x=val;
}
//copy constructor
test(test &obj)
{
x.obj.x;// entered is in value in obj.x
}
void show()
{
cout<<x;
}
};
void main()
{
int val;
cout<<”enter some number”<<endl;
cin>>val;
test old(val);
//call for copy constructor

EC 2209 Data Structures and Object Oriented Programming Lab

12
test new(old);
cout<<”\n the original value is”;
old.show();
cout<<”\n the new copied value is:”;
new.show();
cout<<endl;
getch();
}

Output:
enter value is 500
the original value is 500
the new copied value is 500

Result:
Thus the given program copy constructor was executed successfully.

EC 2209 Data Structures and Object Oriented Programming Lab

13
Ex.No:1h INHERITANCE

Aim:
To Write a C++ program for implementing the inheritance.

Algorithm:
1. Define the base class with variables and functions.
2. Define the derived class with variables and functions.
3. Define main function
4. Declare the variables.
5. Inherits base class.
6. Access member of derived class.
Program:
#include<iostream.h>
class base
{
public:
int x;
void set_x(int n)
{x=n;
}
void show_x()
{
cout<<”\n\t Base class….”;
cout<<”\n\tx=”<<x;
}
};
class derived:public base
{
int y;
public:
void set_y(int n)
{
y=n;
}
void show_xy()
{
cout<<”\n\n\t derived class…”;
cout<<”\n\tx=”<<x;
cout<<”\n\ty=”<<y;
}
};

EC 2209 Data Structures and Object Oriented Programming Lab

14
void main()
{
derived obj;
int x,y;
cout<<”\n enter the value of x”;
cin>>x;
cout<<”\n enter the value of y”;
cin>>y;
obj.set_x(x);//inherits base class
obj.set_y(y);//acess member of derived class
obj.show_x();//inherits base class
obj.show_xy();//acess member of derived class
}

Output:
enter the value of x 10
enter the value of y 20
base class….
x=10

derived class…..
x=10
y=20

Result:
Thus the given Program inheritance was implemented successfully.

EC 2209 Data Structures and Object Oriented Programming Lab

15
Ex.No:1i FUNCTION OVERLOADING

Aim:
To Write a C++ program for implementing the function overloading.

Algorithm:
1. Define class.
2. Define the functions with different arguments.
3. Define main function
4. Declare the variables.
5. Call the Different task of function.
6. Print the output.
Program:
#include<iostream.h>
class test
{
public:
int sum(int,int);
float sum(float,float);
double sum(double,double);
};
int test::sum(int a.int b)
{
return(a+b);
}
float test::sum(float a ,float b)
{
return(a+b);
}
double test::sum(double a,double b)
{
return(a+b);
}
void main()
{
test obj;
int choice;
int a,b;
float x,y;
double m,n;
double result=0;
cout<<”\n\t\t main menu”;

EC 2209 Data Structures and Object Oriented Programming Lab

16
cout<<”\n\t1. Addition of two integer numbers”;
cout<<”\n\t2. Addition of two float numbers”;
cout<<”\n\t3. Addition of two double numbers”<<endl;
cout<<\n enter your choice:”;
cin>>choice;
switch(choice)
{
case 1: cout<<”\n enter 2 numbers”;
cin>>a>>b;
result=obj.sum(a,b);
break;
case 2:
cout<<”\n enter 2 number”;
cin>>x>>y;
result=obj.sum(x,y);
break;
case 3:
cout<<”\n enter 2 number”;
cin>>m>>n;
result=obj.sum(m,n);
break;
default:
cout<<”wrong choice”;
break;
}
cout<<”\n\n result”<<result<<endl;
getch();
}

Output:
Main menu
1.Addition of two integer numbers
2.Addition of two float numbers
3.Addition of two double numbers
enter your choice 2

enter 2 number 1.13 5.6

result 6.73

EC 2209 Data Structures and Object Oriented Programming Lab

17
Result:
Thus the Given program function overloading was executed successfully.

Ex. No: 2 IMPLEMENTATION OF VARIOUS LIST OPERATIONS

USING ARRAYS

Program
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
class arr_list
{
/*data structure for list using array*/
private:
struct node
{
int data;
int next;
}a[10];
public:
int head;
arr_list();
int create();
void display(int);
void insert();
void delete();
void search();
};
arr_list::arr_list()
{
for(int i-0;i<10;i++)
{
a[i].data=-1;
}}
int arr_list::create()
{
int head,I;
cout<<”\n enter the index for first node”;
cin>>I;
head=i;
while(i!=-1)
{
cout<<”\n enter the data and index of the first element”;

EC 2209 Data Structures and Object Oriented Programming Lab

18
cin>>a[i].data;
cout<<””;
cin>>a[i].next;
i=a[i].next;
}
return head;
}
void arr_list::display(int i)
{
while(i!=-1)
{
if(a[i].data==-1)
cout<<””;
else
{
cout<<a[i].data<<”->”;
}
i=a[i].next;
}
cout<<”NULL”;
}
void arr_list::insert()
{
int I,new_data,temp;
cout<<”\n enter the new data which is to be inserted”;
cin>>new_data;
cout<<”\nenter the data after which you want to insert”;
cin>>temp;
for(i=0;i<10;i++)
{
if(a[i].data==temp)
break;
}
if(a[i+1].data==-1) /* next location is empty*/
{
a[i+1].next=a[i].next;
a[i].next=i+1;
a[i+1].data=new_data;
}}
void arr_list::delete()
{
int I,temp,current,new_next;
cout<<”\n enter the node to be dleted”;
cin>>temp;
for(i=0;i<10;i++)
{

EC 2209 Data Structures and Object Oriented Programming Lab

19
if(a[i].data==temp)
{
if(a[i].next==-1)
{
a[i].data=-1; /* writing -1 means deleting the element*/
}
current=I;/* marking the index of an array at which record is placed*/
new_next=a[i].next; /*storing the next pointer at that index*/
}
}
for(i=0;i<10;i++)
{
if(a[i].next==current)
{
a[i].next=new_next;
a[current].data=-1;
}
}
}
void arr_list::search
()
{
int i ,temp ,flag=0;
cout<<”\n enter the node to be searched”;
cin>>temp;
for(i=0;i<10;i++)
{
if(a[1].data==temp)
{
flag=1; /* flag 1 means the element is present*/
break;
}
}
if (flag==1)
cout<<”\n the “<<temp<<” node is present is the list”;
else
cout<<”\n the node is not present”;
}
void main()
{
char ans;
int choice;
arr_list obj;
do
{
clrscr();

EC 2209 Data Structures and Object Oriented Programming Lab

20
cout<<”\t\t program for implementing list using array”;
cout<<”\n main menu”;
cout<<”\n 1. creation”;
cout<<”\n 2. display”;
cout<<”\n 3.insertion of element in the list”;
cout<<”\n 4. deletion of element from the list”;
cout<<”\n5. Searching of element from the list”;
cout<<”\n 6.exit”;
cout<<”\n enter your choice”;
switch(choice)
{
case 1:
obj.head=obj.create();
break;
case 2:
obj.display(obj.head);
break;
case 3:
obj.insert();
break;
case 4:
obj.delete();
break;
case 5:
obj.search();
break;
case 6:
exit(0);
}
cout<<”\n do you wish to go to main menu?”;
ans=getch();
}
while(ans==’Y’||ans==’y’);
getch();
}
Output
program for implementing list using array
main menu
1. creation
2. display
3. insertion of element in the list
4. deletion of element from the list
5. Searching of element from the list
6. exit

enter your choice 1

EC 2209 Data Structures and Object Oriented Programming Lab

21
enter the index for first node 4
enter the data and index of the first element 10 1
enter the data and index of the first element 20 6
enter the data and index of the first element 30 7
enter the data and index of the first element 40 -1

do you wish to go to main menu?

program for implementing list using array

main menu
1. creation
2. display
3. insertion of element in the list
4. deletion of element from the list
5. Searching of element from the list
6. exit

enter your choice 2

10->20->30->40->null

do you wish to go to main menu?

program for implementing list using array

main menu
1. creation
2. display
3. insertion of element in the list
4. deletion of element from the list
5. Searching of element from the list
6. exit

enter your choice 3

enter the new data which is to be inserted 21
enter the data after which you want to insert 20
do you wish to go to main menu?

program for implementing list using array

main menu
1. creation
2. display
3. insertion of element in the list
4. deletion of element from the list
5. Searching of element from the list
6. exit

enter your choice 2

EC 2209 Data Structures and Object Oriented Programming Lab

22
10->20->21->30->40->Null
do you wish to go to main menu?

program for implementing list using array

main menu
1. creation
2. display
3. insertion of element in the list
4. deletion of element from the list
5. Searching of element from the list
6. exit

enter your choice 4

enter the node to be deleted 30

do you wish to go to main menu?

program for implementing list using array

main menu
1. creation
2. display
3. insertion of element in the list
4. deletion of element from the list
5. Searching of element from the list
6. exit

enter your choice 2

10->20->21->40->null

do you wish to go to main menu?

program for implementing list using array

main menu
1. creation
2. display
3. insertion of element in the list
4. deletion of element from the list
5. Searching of element from the list
6. exit

enter your choice 5

enter the node to be searched 20
the 20 node is present in the list
do you wish to go to main menu?

program for implementing list using array

EC 2209 Data Structures and Object Oriented Programming Lab

23
main menu
1. creation
2. display
3. insertion of element in the list
4. deletion of element from the list
5. Searching of element from the list
6. exit

enter your choice 5

enter the node to be searched 30
the node is not present
do you wish to go to main menu?

program for implementing list using array

main menu
1. creation
2. display
3. insertion of element in the list
4. deletion of element from the list
5. Searching of element from the list
6. exit

enter your choice 6

Result:

EC 2209 Data Structures and Object Oriented Programming Lab

24
Thus the Array implantation of List ADT program was executed successfully.

Ex. No: 3 LINKED LIST IMPLEMENTATION USING LISTADT

 
Aim
 
To implement a linked list and do all operations on it.
 
Algorithm:
 
Step 1 : Start the process.
 
Step 2: Initialize and declare variables.
 
Step 3: Enter the choice.
 
Step 4: If choice is INSERT then
a. Enter the element to be inserted.
 
b. Get a new node and set DATA[NEWNODE] = ITEM.
 
c. Find the node after which the new node is to be inserted.
 
d. Adjust the link fields.
 
e. Print the linked list after insertion.
 
Step 5: If choice is DELETE then
 
a. Enter the element to be deleted.
 
b. Find the node containing the element (LOC) and its preceding node (PAR).
 
c. Set  ITEM = DATA[LOC] and delete the node LOC.
 
d. Adjust the link fields so that PAR points to the next element. ie
LINK[PAR] = LINK [ LOC].
 
e. Print the linked list after deletion.
 
Step 6: Stop the process.
 

EC 2209 Data Structures and Object Oriented Programming Lab

25
 
 
 program:

/**************************************************************
Demonstration program to perform various operations on singly link list.
*************************************************************/
// List of include files
# include<iostream.h>
#include<conio.h>
#define TRUE 1
#define FALSE 0
//class definition
{
class sll
{
private:
struct node
{
int data;
struct node *next;
}*head;
public:
sll();
void create();
void display();
void search(int key);
void insert _head();
void insert_after();
void insert_last();
void dele();
~sll();
};
/*………………………………..
the constructor defined
………………………………….*/

sll::sll()
{
head=NULL;//initialize head to NULL
}
/*…………………………………

EC 2209 Data Structures and Object Oriented Programming Lab

26
destructor defined
…………………………………..*/

sll::~sll()
{
node *temp,*temp1;
temp=head->next;
delete head;
while(temp!=NULL)//freethe memory allocated
{
temp1=temp->next;
delete temp;
temp=temp1;
}
}
/*……………………………………..
the create function
………………………………………
*/
void sll::create()
{
node *temp,*new;
int val,flag;
char ans=’y’;
flag=TRUE;
do
{
cout<<”\n enter the data:”;
cin>>val;
??allocate memory to new node
new=new node;
if(new==NULL)
cout<<”unable to allocate memory\n”;
new->data=val;
new->next=NULL;
if(flag==true)//executed only for the first time
{
head=new;
temp=new;
flag=FALSE;
}
else
{
/*temp last keeps track of the most recently created node*/
temp->next=new;
temp=new;

EC 2209 Data Structures and Object Oriented Programming Lab

27
}
cout<<”\n do you want to enter more elements?(y/n)”;
ans=getche();
}
while(ans==’y’||ans==’Y’);
cout<<”\n the singly linked list is created\n”;
getch();
clrscr();
}
/*…………………………………………..
the display function
………………………………………………
*/
void sll::display()
{
node *temp;
temp=head;
if(temp==NULL)
{
cout<<”\n the list is empty\n”;
getch();
clrscr();
return;
}
while(temp!=NULL)
{
cout<<temp->data<<””;
temp=temp->next;
}
getch();
}
void sll::search(int key)
{
node *temp;
int found;
temp=head;
if(temp==NULL)
{
cout<<”linked list is empty\n”;
getch();
clrscr();
}
found=FALse;
while(temp!=NULL&&found==FALSE)
{
if(temp->data!=key)

EC 2209 Data Structures and Object Oriented Programming Lab

28
temp=temp->next;
else
found=TRUE;
}
if(found==TRUE)
{
cout<<”\n the element is present in the list\n”;
getch();
}
else
{
cout<<”the element is not present in the list\n”;
getch();
}
}

/*
……………………………………………
the dele function
……………………………………………
*/
void sll::dele()
{
node *temp,*prev;
int key;
temp=head;
clrscr();
cout<<”\n enter the data of the node you want to delete:”;
cin>>key;
while(temp!=NULL)
{
if (temp->data==key)//traverse till required node to delete
break; //is found
prev=temp;
temp=temp->next;
}
if(temp==NULL)
cout<<”\n node not found”;
else
{
if(temp==head)//first node
head=temp->next;
else
prev->next=temp->next; //intermediate or end node

EC 2209 Data Structures and Object Oriented Programming Lab

29
delete temp;
cout<<”\n the element is deleted\n”;
}
getch();
}
/*
…………………………………….
function to insert at end
………………………………………
void sll::insert_last()
{
node *new,*temp;
cout<<”\n enter the element which you want to insert”;
cin>>new->data;
if(head==NULL)
head=new;
else
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=new;
new->next=NULL;
}
}
/*
………………………………………..
function to insert after a node
………………………………………….
*/
void sll::insert_after()
{
int key;
node *temp,*new;
node=new node;
cout<<”\n enter the element which you want to insert”;
cin>>new->data;
if(head==NULL)
{
head=New;
}
else
{
cout<<”\n enter the element after which you want to insert the node”;
cin>>key;
temp=head;

EC 2209 Data Structures and Object Oriented Programming Lab

30
do
{
if(temp->data==key)
{
New->next=temp->next;
temp->next=New;
break;
}
else
temp=temp->next;
}
while(temp!=NULL);
}
}
/*……………………………………..
function to insert at the beginning
……………………………………….*/
void sll::insert_head()
{
node *New,*temp;
New=new node;
cout<<”\n enter the element which you want to insert”;
cin>>New->data;
if(head==NULL)
head=New;
else
{
temp=head;
New->next=temp;
head=New;
}
}
/*
……………………………………………
the main function
Input:None
Output:None
parameter passing method:None
…………………………………………………...
*/
void main()
{
sll s;
int choice,val ch1;
char ans=’y’;
do {

EC 2209 Data Structures and Object Oriented Programming Lab

31
clrscr();
cout<<”\n program to perform various operations on linked list”;
cout<<”\n 1.create”;
cout<<”\n2. display”;
cout<<”\n3.search”;
cout<<”\n4.insert an element in a list”;
cout<<”\n5.delete an element from list”;
cout<<”\n6.quit”;
cout<<\n enter your choice(1-6)”;
cin>>choice;
switch(choice)
{
case1: s.create();
break;
case 2:s.display();
break;
case 3:cout<<”enter the element you want to search”;
cin>>val;
s.search(val);
break;
case4:
clrscr();
cout<<”\n the list is:\n”;
s.display();
cout<<”\n menu”;
cout<<”\n1.insert at beginning \n2. insert after”;
cout<<”\n3.insert at end”;
cout<<”\n enter your choice”;
cin>>ch1;
switch(ch1)
{
case 1:s.insert_head();
break;
case 2: s.insert_after();
break;
case 3:s.insert_last();
break;
default:cout<<”\n invalid choice”;
}
break;
case 5:
s.dele();
break;
default:cout<<”\n invalid choice”;
}
cout<<”\n continue?”;

EC 2209 Data Structures and Object Oriented Programming Lab

32
cin>>ans;
}
while(ans==’y’||ans==’Y’)
getch();
return;
}

output

program to perform various operations on linked list

1.create
2. display
3.search
4.insert an element in a list
5.delete an element from list
6.quit
enter your choice(1-6) 1

enter the data: 10

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

enter the data 20

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

enter the data 30

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

enter the data 40

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

enter the data 50

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

the singly linked list is created

continue?

program to perform various operations on linked list

1.create
2. display
3.search
4.insert an element in a list
5.delete an element from list
6.quit
enter your choice(1-6) 2

EC 2209 Data Structures and Object Oriented Programming Lab

33
10 20 30 40 50
continue?

program to perform various operations on linked list

1.create
2. display
3.search
4.insert an element in a list
5.delete an element from list
6.quit
enter your choice(1-6) 3
enter the element you want to search 30

the element is present in the list

continue?
program to perform various operations on linked list
1.create
2. display
3.search
4.insert an element in a list
5.delete an element from list
6.quit
enter your choice(1-6) 4

the list is:

10 20 30 40 50
menu
1.inset at beginning
2.insert after
3.insert at end
enter your choice 1

enter the element which you want to insert 9

continue?
program to perform various operations on linked list
1.create
2. display
3.search
4.insert an element in a list
5.delete an element from list
6.quit
enter your choice(1-6) 4

the list is:

9 10 20 30 40 50

EC 2209 Data Structures and Object Oriented Programming Lab

34
menu
1.inset at beginning
2.insert after
3.insert at end
enter your choice 2

enter the element which you want to insert 31

enter the element after which you want to insert the node 30

continue?
program to perform various operations on linked list
1.create
2. display
3.search
4.insert an element in a list
5.delete an element from list
6.quit
enter your choice(1-6) 4

the list is:

9 10 20 30 31 40 50
menu
1.inset at beginning
2.insert after
3.insert at end
enter your choice 3

enter the element which you want to insert 60

continue?

program to perform various operations on linked list

1.create
2. display
3.search
4.insert an element in a list
5.delete an element from list
6.quit
enter your choice(1-6) 2
9 10 20 30 31 40 50 60

continue?

program to perform various operations on linked list

1.create
2. display
3.search

EC 2209 Data Structures and Object Oriented Programming Lab

35
4.insert an element in a list
5.delete an element from list
6.quit
enter your choice(1-6) 5
enter the data of the node you want to delete :10
the element is deleted

continue?

program to perform various operations on linked list

1.create
2. display
3.search
4.insert an element in a list
5.delete an element from list
6.quit
enter your choice(1-6) 2
9 20 30 31 40 50 60

Result

Thus the given program Linked List implementation of the list ADT was executed
successfully.

EC 2209 Data Structures and Object Oriented Programming Lab

36
Ex.No:4 CURSOR IMPLEMENTATION – LIST ADT

Aim:
              To write a C++ program for cursor implementation of list ADT.
 
Algorithm:
 
1. Start the program.
2. Create a node with two fields data and link field.
o Allocate space for the node dynamically.
o Create link between the created nodes and let the last node be with NULL
Link
o Insert the input data in the data field and press –1 to stop the same.
3. Get the choice of operations either insertion or deletion.
4. For insertion get the position in which insertion is to be done and the element to be
inserted. Check for the start, middle or end position of insertion. Insert the node and
change its link accordingly.
5. For deletion get the position in which deletion is to be done. Delete the node and
then link it to the next node. Before deletion check whether there is data in the list
to be deleted.
6. Using display option list the elements of the list.
7. Stop the program.

Program:
 
/* ***************************************
Program To implement cursor of List ADT
*****************************************/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 20
class LIST
{
private:
int list[MAX];
public:
int create();
void display(int);
void reverse(int);
int search(int);
void delet(int);

EC 2209 Data Structures and Object Oriented Programming Lab

37
};

/*
*************************************
Function: create
Input: None
Output: creates the list
Calls: None
**************************************
*/
int LIST::create()
{int n,I;
clrscr();
cout<<”\n how many elements you want in the list:”;
cin>>n;
if(n>MAX)
cout<<”\n Error:Number of elements exceeds the limit”;
for(i=0;i<n;i++)
{
cout<<”\nEnter the element number”<<i+1<<”:”;
cin>>List[i];
}
cout<<”\n The List is successfully created\n”;
getch();
return(n);
}
/*
*************************************
Function: Display
Input: Length of the list
Output: prints the list
Calls: None
**************************************
*/
void LIST::display(int n)
{
int I;
clrscr();
cout<<”\n the list is…\n”;
for(i=0;i<n;i++)
cout<<”\n”<<List[i];
cout<<|n press any key to continue…\n”;
getch();
}
/*

EC 2209 Data Structures and Object Oriented Programming Lab

38
*************************************
Function: reverse
Input: Length of the list
Output: prints the list in reverse manner
Calls: None
**************************************
*/
void LIST::reverse(int n)
{
int I;
clrscr();
cout<<”\n the reversed list is….\n”;
for(i=n-1;i>=0;i--)
cout<<”\n”<<List[i];
cout<<”\n press ant key to continue…\n”;
getch();
}
/*
*************************************************
Function: Search
Input: Length of the list
Output: Reads a number & searches the list for a number
Calls: None
**************************************************
*/
int LIST::search(int n)
{
int I,key;
clrscr();
cout<<”\n enter the number you want to search?”;
cin>>key;
/* Now search in the list*/
for (i-0;i<n;i++)
{
if(List[i]==key)
{
cout<<”\n the given number is at postion:”<<i<<”\n”;
getch();
return I;
}
}
cout<<”\n the given number is at postion:”<<i<<|n”;
getch();
return I;
}
}

EC 2209 Data Structures and Object Oriented Programming Lab

39
cout<<”\n the given number is not in the list\n”;
getch();
return -1;}
/*
*************************************
Function: delet
Input: Length of the list
Output: deletes the number from the list
Calls: search
called by:main
**************************************
*/
void LIST::delet(int n)
{
int I;
i=search(n);
List[i]=-1;
cout<<”\n the element is now deleted!”;
cout<<”\n we put -1 to indicate empty location”;
getch();
}
void main()
{
LIST obj;
int choice,len,position;
char ans;
do
{
clrscr();
cout<<”\n\t program to perform operations on ordered list”;
cout<<”\n 1.create;
cout<<”\n 2.display;
cout<<”\n 3.search for a number”;
cout<<”\n 4.reverse”;
cout<<”\n 5.delete”;
cout<<”\n 6.Quit”;
cout<<”\n enter your choice(1-6)”;
cin>>choice;
switch(choice)
{
case 1:
len=obj.create();
break;
case 2:
obj.display(len)
break;

EC 2209 Data Structures and Object Oriented Programming Lab

40
case 3:
position=obj.serch(len);
break;
case 4:
obj.reverse(len)
break;
case 5:
obj.delet(len)
break;
case 6:
cout<<”\n do you want to exit(y/n)?”;
ans=getche();
if(ans==’y’)
exit(0);
else
break;
default;
clrscr();
cout<<”\n invalid choice,try again”;
getch\();
}
}while(choice!=6)
}

Output

program to perform operations on ordered list

1.create
2.display
3.search for a number
4.reverse
5.delete
6.Quit

enter your choice(1-6) 1

how many elements you want in the list:5
Enter the element number 1 :10
Enter the element number 2 :20
Enter the element number 3 :30
Enter the element number 4 :40
Enter the element number 5 :50
The List is successfully created
program to perform operations on ordered list
1.create
2.display

EC 2209 Data Structures and Object Oriented Programming Lab

41
3.search for a number
4.reverse
5.delete
6.Quit

enter your choice(1-6)2

the lis is…
10
20
30
40
50
press the key to continue…
program to perform operations on ordered list
1.create
2.display
3.search for a number
4.reverse
5.delete
6.Quit

enter your choice(1-6) 3

enter the number you want to search? 20
the given number is at position 1
program to perform operations on ordered list
1.create
2.display
3.search for a number
4.reverse
5.delete
6.Quit

enter your choice(1-6) 4

the reversed list is …..
50
40
30
20
10
press the key to continue…
program to perform operations on ordered list
1.create
2.display
3.search for a number
4.reverse
5.delete

EC 2209 Data Structures and Object Oriented Programming Lab

42
6.Quit

enter your choice(1-6) 5

enter the number you want to search? 20
the given number is at position 1

the element is now deleted!

we put -1 to indicate empty location
program to perform operations on ordered list
1.create
2.display
3.search for a number
4.reverse
5.delete
6.Quit

enter your choice(1-6) 2

the list is…
10
-1
30
40
50
press the key to continue…
program to perform operations on ordered list
1.create
2.display
3.search for a number
4.reverse
5.delete
6.Quit

enter your choice(1-6) 6

do you want to exit(y/n)?n

 Result:

Thus the Given Program Cursor implementation of list was executed successfully.
 

EC 2209 Data Structures and Object Oriented Programming Lab

43
Ex. No:5a STACK ADT USING ARRAY IMPLEMENTATION

Aim:
              To write a program for stack using array implementation.
 
Algorithm:

           Step1:Define a array which stores stack elements..

          Step 2: The operations on the stack are

a)PUSH data into the stack
         b)POP data out of stack
 
Step  3:  PUSH DATA INTO STACK
                   3a.Enter the data to be inserted into stack.
                   3b.If TOP is NULL
                         the input data is the first node in stack.
                         the link of the node is NULL.
                        TOP points to that node.
                   3c.If TOP is NOT NULL
                        the link of TOP points to the new node.
                        TOP points to that node.

           Step 4:   POP DATA FROM STACK

                   4a.If TOP is NULL
                        the stack is empty
                   4b.If TOP is NOT NULL
                        the link of TOP is the current TOP.
                        the pervious TOP is popped from stack.

            Step 5.  The stack represented by linked list is traversed to display its content.
 
 Program:

/*
************************************************************************
Program for implementing a stack using arrays. it involves various operations such as
push ,pop, stack empty, stack full and display.
*************************************************************************
*/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

EC 2209 Data Structures and Object Oriented Programming Lab

44
#define size 5
/* stack structure*/
class stack_class
{
private:
struct stack
{
int s[size];
int top;
}st;
public:
stack_class();
int stfull();
void push(int item);
int stempty();
int pop();
void display();
};
//constructor is used to intialise stack
stack_class::stack_class()
{
st.top=-1;
for(int i=0;i<size;i++)
st.s[i]=0;
}
/*
the stfull function
input:none
output:returns 1 or 0 for stack full or not
called by :main
calls:none
*/
int stack_class::stfull()
{
if(st.top>=size-1)
return 1;
else
return 0;
}
/*
push function
input:item which is to be pushed
output:none –simply pushes the item onto the stack
called by: main
calls:none
*/

EC 2209 Data Structures and Object Oriented Programming Lab

45
void stack_class::push(int item)
{
st.top++;
st.s[st.top]=item;
}
/*
the stempty function
input:none
output: returns 1 or 0 for stack empty or not
called by :main
calls :none
*/
int stack_class::stempty()
{
if(st.top==-1)
return 1;
else
return 0;
}
/*
pop function
input:none
output:returns the item which is poped from the stack
calledby:main
calls:none
*/
int stack_class::pop()
{
in item;
item=st.s[st.top];
st.top--;
return(item);
}
/*
display function
input:none
output:none –displays the contents of the stack
calledby:main
calls:none
*/
void stack_class::display()
{
int i;
if(stempty())
cout<<”\n stack is empty!”;
else

EC 2209 Data Structures and Object Oriented Programming Lab

46
{
for(i=st.top;i>=0;i--)
cout<<”\n”<<st.s[i];
}
}
/*
the main function
input:none
output:none
calledby:o.s
calls:push,pop,stempty,stfull,display
*/
void main(void)
{
int item,choice;
char ans;
stack_class obj;
clrscr();
cout<<”\n\t\t implementation of stack”;
do
{
cout<<”\n main menu”;
cout<<”\n1.push\n2.pop\n3.display\n 4.exit”;
cout<<”\nenter your choice”;
cin>>choice;
switch(choice)
{
case 1:
cout<<”\n enter the item to be pushed”;
cin>>item;
if(obj.stfull())
cout<<”\n stack is full”;
else
obj.push(item);
break;
case 2:if(obj.stempty())
cout<<”\n empty stack!underflow !!”;
else
{
item=obj.pop();
cout<<”\n the poped element is”<<item;
}
break;
case 3:
obj.display();
break;

EC 2209 Data Structures and Object Oriented Programming Lab

47
case 4:exit(0);
}
cout<<”\n do you want to continue?”;
ans=getche();
}
while(ans==’Y’||ans’y’)
getch();
}

Output:

implementation of stack
main menu
1.push
2.pop
3.display
4.exit

enter your choice 1

enter the item to be pushed 10
do you want to continue? y

main menu
1.push
2.pop
3.display
4.exit

enter your choice 1

enter the item to be pushed 20
do you want to continue? y
main menu
1.push
2.pop
3.display
4.exit

enter your choice 2

the popped element is 30
do you want to continue? y

main menu
1.push
2.pop
3.display
4.exit

EC 2209 Data Structures and Object Oriented Programming Lab

48
enter your choice 3
20
10
do you want to continue? y
main menu
1.push
2.pop
3.display
4.exit

enter your choice 2

the popped element is 20

do you want to continue? y

main menu
1.push
2.pop
3.display
4.exit

enter your choice 2

the popped element is 10
do you want to continue? y
main menu
1.push
2.pop
3.display
4.exit

enter your choice 2

empty stack! Underflow !!
do you want to continue

Result:
Thus the given program stack ADT using array implemented successfully.

EC 2209 Data Structures and Object Oriented Programming Lab

49
Ex. No:5b STACK ADT USING LINKED LIST IMPLEMENTATION

Aim:
              To write a program for stack ADT using linked list implementation.
 
Algorithm:

           Step1:Define a struct for each node in the stack. Each node in the stack
                     contains data and link to the next node. TOP pointer points to last
                    node inserted in the stack.

          Step 2: The operations on the stack are

         a)PUSH data into the stack
         b)POP data out of stack
 
         Step  3:  PUSH DATA INTO STACK
                   3a.Enter the data to be inserted into stack.
                   3b.If TOP is NULL
                         the input data is the first node in stack.
                         the link of the node is NULL.
                        TOP points to that node.
                   3c.If TOP is NOT NULL
                        the link of TOP points to the new node.
                        TOP points to that node.

           Step 4:   POP DATA FROM STACK

                   4a.If TOP is NULL
                        the stack is empty
                   4b.If TOP is NOT NULL
                        the link of TOP is the current TOP.
                        the pervious TOP is popped from stack.

            Step 5.  The stack represented by linked list is traversed to display its content.
 
 Program:

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
// Declaration for data structure of linked stack
class lstack
{
private:

EC 2209 Data Structures and Object Oriented Programming Lab

50
 typedef struct stack
{
int data;
struct stack *next;
}node;
node *top;
public:
lstack();
~lstack();
void creat(),remove(),show();
void push(int,node**);
void display(node **);
int pop(node **);
int sempty(node **);
};
/*
…………………………………..
the constructor defined
……………………………………….
*/
lstack::lstack()
{
top=NULL;
}
/*
……………………………………
the destructor defined
…………………………………….
*/
lstack::~lstack()
{
node *temp;
temp=top;
if(temp==NULL)
delete temp;
else
{
while(temp!=NULL)
{
temp=temp->next;
top=NULL;
top=temp;
}
delete temp;//de allocating memory
}
}

EC 2209 Data Structures and Object Oriented Programming Lab

51
/*
……………………………………
the create function
………………………………………
*/
void lstack::create()
{
int data;
cout<<”\n enter the data”;
cin>>data;
push(data,&top);
}
/*
………………………………………….
remove function
………………………………………….
*/
void lstack::remove()
{
int item;
if(sempty(top))
cout<<”\n stack underflow!”;
else
{
item=pop(&top);
cout<<”\n the popped node is”<<item;
}
}
/*
…………………………………..
the show function
……………………………………*/
void lstack::show()
{
display(&top);
}
/*………………………………………
the push function
………………………………………….*/
void lstack::push(int item,node **top)
{
node * New;
New=new node;
New->next=NULL;
New->data=item;
New->next=*top;

EC 2209 Data Structures and Object Oriented Programming Lab

52
*top=New;
}

/*
……………………………………..
the sempty function
………………………………………
*/
int lstack::sempty(node *temp)
{
if(temp==NULL)
return 1;
else
return 0;
}
/*
………………………………………..
the pop function
…………………………………………*/
int lstack::pop(node **top)
{
int item;
node *temp;
item=(*top)->data;
temp=*top;
*top=(*top)->next;
delete temp;
return(item);
}
/*
………………………………….
the display function
………………………………….
*/
void lstack::display(node **head)
{
node *temp;
temp=*head;
if(sempty(temp))
cout<<”\n the stack is empty!”;
else
{
while(temp!=NULL)
{
cout<<””<<temp->data;

EC 2209 Data Structures and Object Oriented Programming Lab

53
temp=temp->next;
}
}
getch();
}
/*
………………………………..
the main function
…………………………………….
*/
void main()
{
int choice;
char ans,ch;
lstack st;
clrscr();
cout<,”\n\t\t stack using linked list”;
do
{
cout<<”\n\n the main menu”;
cout<<”\n 1.push\n2.pop\n3.display\n4.exit”;
cout<<”\n enter your choice”;
cin>>choice;
switch(choice)
{
case 1:st.create();
break;
case 2:
st.remove();
case 3:
st.show()’
break;
case 4:
exit(0);
}
cout<<”\n do you want to continue>”;
ans=getche();
getch();
clrscr();
}
while(ans==’y’||ans==’Y’);
getch();
}

EC 2209 Data Structures and Object Oriented Programming Lab

54
Output:

stack using linked list

the main menu

1.push
2.pop
3.display
4.exit
enter your choice 1
enter the data 10

do you want to continue?

the main menu

1.push
2.pop
3.display
4.exit
enter your choice 1
enter the data 20
do you want to continue? y

the main menu

1.push
2.pop
3.display
4.exit
enter your choice 1
enter the data 30
do you want to continue? y

the main menu

1.push
2.pop
3.display
4.exit
enter your choice 1
enter the data 40

do you want to continue? y

EC 2209 Data Structures and Object Oriented Programming Lab

55
the main menu
1.push
2.pop
3.display
4.exit
enter your choice 1
enter the data 50

do you want to continue? y

the main menu

1.push
2.pop
3.display
4.exit
enter your choice 3
50 40 30 20 10
do you want to continue? y
the main menu
1.push
2.pop
3.display
4.exit
enter your choice 2
the poped node is 50

do you want to continue? y

the main menu
1.push
2.pop
3.display
4.exit
enter your choice 4

 Result:

Thus the Given Program for stack ADT using linked list implementation was
executed successfully.

EC 2209 Data Structures and Object Oriented Programming Lab

56
  

Ex. No: 6 PROGRAM SOURCE FILES FOR STACK APPLICATION1 

Application 1: checking well formedness of parenthesis.

A) STACK IMPLEMENTED AS ARRAYS(USING THE HEADER FILE OF

STACK OPERATIONS)

Step 1: Crate a header file named stack.h . in this frile we will declare the class and all the
stack operations. the implementation of stack is using arrays.

stack.h
#define size 10
class stk_class
{
private:
/*stack structure*/
struct stack{
char s[size];
int top;
}st;
public:
stk_class();
void push(char item);
int stempty();
char pop();
};
stk_class::stk_class()
{
st.top=-1;
}
/* the push function
input:item which is to be pished
output:none –simply pushes the item onto the stack
called by: main
calls: one
*/
void stk_class::push(char item)
{
st.top++;
st.s[st.top]=item;
EC 2209 Data Structures and Object Oriented Programming Lab
57
}
/*
the stempty function
input:none
output:returns 1 or 0 for stack empty or not
called by:none
*/
int stk_class::stempty()
{
inr(st.top==-1)
return 1;
else
return 0;
}
/*
the stfull function
input:none
coutput:returns 1 or 0 for stack full or not
called by :main
calls:none
*/
int stk_class::stfull()
{
if(st.top==size)
return 1;
else
return 0;
}
/*
the pop function
input:none
output:returns the item which is poped from the stack
called by: main
calls:none
*/
char stk_class::pop()
{
char item;
item=st.s[st.top];
st.top--;
return(item);
}

EC 2209 Data Structures and Object Oriented Programming Lab

58
Step 2: Now we will create a stack application program. We have chosen an application as
“checking well formedness of parenthesis” for this application we will use stack operations.
These operations are used from the external file stack.h. Hence we will include this file in
the include file section. Here is an application program.

/************************************************************************
program for checking the well formedness of the parenthesis using stack as arrays.
************************************************************************/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include “d:\stack.h”
#define size 10
/*
the main function
input:none
ouput:none
called by:O.S
calls:push,pop,stempty
*/
void main(void)
{
char item;
char ans,bracket[10];
stk_class obj;
int I;
clrscr();
cout<,”\n\t\t program for stack application using separate header file”;
cout<<”\n enter the expression and put $at end “;
cin>>bracket;
i=0;
if(bracket[i]==’)’)
cout<<”\n the expressin is invalid”;
else
{
do
{
while(brackt[i]==’(‘)
{
obj.push(bracket[i]);
i++;
}
while(bracket[i]==’)’)

EC 2209 Data Structures and Object Oriented Programming Lab

59
{
item=obj.pop();
i++;
}
}
while(brackt[i]!=’$’)
if(!obj.stempty())
cout<<”\n the expression is invalid”;
else
cout<<”\n the expression has well formed parenthesis”;
}
getch();
}

Step 3: Execute above program and following output can be obtained.

Output(run 1)
program for stack application using separate header file
enter the expression and put $ at the end (()(()))$
the expression has well formed parenthesis
Output(run 2)

program for stack application using separate header file

enter the expression and put $ at the end (()()$

the expression in invalid.

Result:

EC 2209 Data Structures and Object Oriented Programming Lab

60
Thus the given program checking well formedness of parenthesis stack implemented as
arrays was executed successfully.

B) STACK IMPLEMENTED AS LINKED LIST(USING THE HEADER FILE OF STACK

OPERATION)

step 1:
create a header file named stack. In this file we declare the class and all the stack
operations. The implementation of stack using linked list.

/**********************************
the stack.h file
***********************************/
class stk_class
{
private:
/*data structure for the linked stack*/
typedef struct stack
{
char data;
struct stack * next;
}node;
node *top;
public:
stk_class();
void push(char item);
int sempty();
void pop();
};
stk_class ::stk_class()
{
top=NULL;
}
/* functionality performed on linked stack*/
void stk_class::push(char item)
{
node * New;
New=new node;
if(New==NULL)
cout<<”\n memory cannot be allocated \n”;
else
{
New->data=item;
new->next=top;

EC 2209 Data Structures and Object Oriented Programming Lab

61
top=New;
}
}
/* the sempty function
input: any node for checking the empty condition
output:1 or 0 for empty or not condition
called by: main
calls: none
*/
int stk_class::sempty()
{
if(top==NULL)
return 1;
else
return 0;
}
/*
………………………………………
the pop function
input: the top of the stack
called by: main
calls:none
……………………………………………*/
void stk_class::pop()
{
node *temp;
temp=top;
top=top->next;
delete temp;}

Step 2:
Now we will create a stack application program. We have chosen an application as
“checking well formedness of parenthesis” for this application we will use stack operations.
These operations are used from the external file stack.h. Hence we will include this file in
the include file section. Here is an application program.

/*…………………………………………………………………………………………
Program for checking the well – formedness of the parenthesis using linked stack.
……………………….…………………………………………………………………..*/

/*include file section*/

#include<iostream.h>
#include<conio.h>
#include<process.h>
#include<stdlib.h>
/* Included linked stack as a header file*/

EC 2209 Data Structures and Object Oriented Programming Lab

62
#include<”d:\stack.h”
/*
the main function
input:none
output:none
called by:O.S
calls:push ,pop,sempty
*/
void main(void)
{
char ans,bracket[10];
Char data ,item;
stk_class obj;
int choice;
int I;
clrscr();
cout<<”\n\t\t enter the expression and put $ at the end “;
cin>>bracket;
i=0;
if(bracket[i]==’)’)
cout<<”\n the expression is invalid”;
else
{
do
{
if(bracket[i]==’(‘)
{
obj.push(bracket[i]);
}
else if(bracket[i]==’)’)
{
if(obj.sempty())
{
cout<<”\n the expression is invalid”;
getch();
exit(0);
}
obj.pop();
}
i++;
}
while(bracket[i]!=’$’);
if(obj.sempty())
cout<<”\n the expression is invalid”;
else
cout<<”\n the expression has well formed parenthesis”;

EC 2209 Data Structures and Object Oriented Programming Lab

63
}
getch();
}
Step 3:

The above program will be executed to get output as follows

output(run1)
enter the expression and put $ at the end ()()$
the expression has well formed parenthesis

output(run 2)
enter the expression and put $ at the end (()()$
the expression is invalid.

Result:

Thus the given program checking well formedness of parenthesis stack implemented as
Linked List was executed successfully.

EC 2209 Data Structures and Object Oriented Programming Lab

64
Ex. No: 6 PROGRAM SOURCE FILES FOR STACK APPLICATION2

application 2: Evaluation of postfix expression.

A.USING STACK(IMPLEMENTATION AS ARRAYS)

STEP 1:

/********************************************
stack.h
*********************************************/
#define Max 10
class stk_class
{
/*declaration of stack data structure*/
struct stack
{
double s[MAX];
int top;
}st;
public:
stk_class();
void push(double val);
double pop();
};
stk_class::stk_class()
{
st.top=0;
}
void stk_class::push(double val)
{
if(st.top+1>=MAX)
cout<<”\n stack is full”;
st.top++;
st.s[st.top]=val;
}

double stk_class::pop()
{
double val;

EC 2209 Data Structures and Object Oriented Programming Lab

65
if(st.top==-1)
cout<<”\n stack is empty\n”;
st.top--;
return(val);l
}

STEP 2:

/************************************************************************
program to evaluate a given postfix expression .her the stack using arrays is implemented
in separate file named stack.h
************************************************************************/

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
/*included the header file as stack using array*/
#define size 80
void main()
{
char exp[size];
int len;
double result;
double post(char exp[]);
clrscr();
cout<<”enter the postfix expression\n”;
cin>>exp;
len=strlen(exp);
exp[len]=’$’;/*append $ at the end a end marker*/
result=post(exp);
cout<<”the value of the expression is”<<result;
getch();
exit(0);
}

double post(char exp[])

{
stk_class obj;
char ch,*type;
double result ,val,op1,op2;
int i;
i=0;
ch=exp[i];

EC 2209 Data Structures and Object Oriented Programming Lab

66
while(ch!=’$’)
{
if(ch>=’0’&&ch<=’9’)
type=””operand”:
else if(ch==’+’||ch==’-‘||ch==’^’)
type=”operator”;
if(strcmp(type,”operand”)==0)/* if the character is operator*/
{
val=ch-48;
obj.push(val);
}
else
if(strcmp(type,”operator”)==0)/* if it is operator*/
{
op2=obj.pop();
op1=obj.pop();
switch(ch)
{
case ‘+’:result=op1+op2;
break;
case ‘-‘:result=op1-op2;
break;
case ‘*;:result=op1*op2;
break;
case ‘/’: result=op1/op2;
break;
case ‘^’:result=pow(op1,op2)
break;
}
/*switch*/
obj.push(result);
}
i++;
ch=exp[i];
}/*while*/
result-obj.pop();/*pop the result*/
return(result);
}

Output:

Enter the postfix expression

12+3*
The value of the expression is 9

EC 2209 Data Structures and Object Oriented Programming Lab

67
Result:

Thus the given program Evaluation of postfix expression stack implemented as arrays was
executed successfully.

B. STACK IMPLANTED AS LINKED LIST(USE OF SEPARATE HEADER FILE FOR STACK

OPERATIONS)

STEP 1:
/********************************************************************
the stack.h file
**********************************************************************/
class stk_class
{
/* data structure for the linked stack*/
typedef struct stack
{
char data;
struct stack *next;
}node;
public:
node *top;
stk_class();
void push(char item);
char pop();
};
stk_class::stk_class()
{
top=NULL:
}
/* functionality performed on linked linked stack*/
void stk_class::push(char item)
{
node *New;
New=new node;
New->data =Item;
New->next=top;
top=New;
}
char stk_class::pop()
{
char item;
node *temp;
item=top->data;

EC 2209 Data Structures and Object Oriented Programming Lab

68
temp=top;
top=top->next;
delete temp;
return item;
}

STEP 2:

/*********************************************************************
program to evaluate a given postfix expression using linked stack.
here stack.h is a user defined header file created for linked stack
**********************************************************************/
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<conio.h>
/* included the stack.h file (given below) for linked stack*/
#include”d:\stack.h”
#define size 80
void main()
{
char exp[size];
int len;
double result;
double post(char exp[])
clrscr();
cout<<”enter the postfix expression\n”;
cin>>exp;
len=strlen(exp);
cin>>exp;
len=strlen(exp);
exp[len]=’$’;/*append $at the end as a endmarker*/
result=post(exp);
cout<<”the value of the expression is”<<result;
getch();
exit(0);
}

double post(char exp[])

{
char ch,*type;
double result ,val,oip1,op2;
int I;
stk_class obj;

EC 2209 Data Structures and Object Oriented Programming Lab

69
i=0;
ch=exp[i];
while(ch!=’$’)
{
if(ch>=’0’&&ch<=’9’)
type=”operand”;
else if(ch==’+’||ch==’-‘||ch==’*’||ch==’/’||ch==’^’)
type=”operator”;
if(strcmp(type,”operator”)==0) /* if the character is operand*/
{
val=ch-48;
obj.push(val);
}
else
if(strcmp(type,”operator”)==0)/*if it is operator*/
{
op2=obj.pop();
op1=obj.pop();
switch(ch)
{
case ‘+’:result=op1+op2;
break;
case ‘-‘:result=op1-op2;
break;
case ‘*;:result=op1*op2;
break;
case ‘/’: result=op1/op2;
break;
case ‘^’:result=pow(op1,op2)
break;
}
/*switch*/
obj.push(result);
}
i++;
ch=exp[i];
}/*while*/
result-obj.pop();/*pop the result*/
return(result);
}

Output:

enter the expression

12+3*
the value of the expression is 9

EC 2209 Data Structures and Object Oriented Programming Lab

70
Result:

Thus the given program Evaluation of postfix expression stack implemented as Linked List
was executed successfully.
Ex. No:7a QUEUE ADT USING ARRAY IMPLEMENTATION

Aim:
              To write a program for Queue using array implementation.
 
Algorithm:

           Step1:Define a array which stores queue elements..

          Step 2: The operations on the queue are

         a)INSERT data into the queue
         b)DELETE data out of queue
 
         Step  3:  INSERT DATA INTO queue
                   3a.Enter the data to be inserted into queue.
                   3b.If TOP is NULL
                         the input data is the first node in queue.
                         the link of the node is NULL.
                        TOP points to that node.
                   3c.If TOP is NOT NULL
                        the link of TOP points to the new node.
                        TOP points to that node.

           Step 4:   DELETE DATA FROM queue

                   4a.If TOP is NULL
                        the queue is empty
                   4b.If TOP is NOT NULL
                        the link of TOP is the current TOP.
                        the pervious TOP is popped from queue.

            Step 5.  The queue represented by linked list is traversed to display its content.
 
  Program:
/******************************************************
Program for implementing the queue using arrays
*******************************************************/

#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
#define size 5
class myq

EC 2209 Data Structures and Object Oriented Programming Lab

71
{
private:
struct queue
{
int que[size];
int front ,rear;
}q;
public:
myq();
int qfull();
int insert(int);
int qempty();
int delet();
void display();
};
myq::myq()
{
q.front=-1;
q.rear=-1;
}
/*
the qfull function
input:none
output:1 or 0 for q full or not
called by:main
*/
int myq::qfull()
{
if(q.rear>=size-1)
return 1;
else return 0;
}
/*
the insert function
input: item which is to be insered in the q
output:rear value
called by :main
calls :none
*/
int myq::insert(int item)
{
if(q.front==-1)
q.front++;
q.que[++q.rear]=item;
return q.rear;
}

EC 2209 Data Structures and Object Oriented Programming Lab

72
int myq::qempty()
{
if(q.front==-1||(q.front>q.rear))
return 1;
else
return 0;
}
/*
the delete function
input:none
output:front value
called by:main
calls:none
*/
int myq::delet()
{
int item;
item=q.que[q.front];
q.front++;
cout<<”\n the deleted item is”<<item;
return q.front;
}
/*
the display function
input: none
output:none
called by:main
calls:none
*/
void myq::display()
{
int I;
for(i=q.front;i<=q.rear;i++)// printing the queue from front to rear
cout<<””<<q.que[i];
}
void main(void)
{
int choice,item;
char ans;
myq obj;
clrscr();
do
{
cout<<”\n main menu”;
cout<<”\n 1.insert\n 2.delete\n 3.display”;
cout<<”\n enter your choice:”;

EC 2209 Data Structures and Object Oriented Programming Lab

73
cin>>choice;
switch(choice)
{
case 1:
if(obj.qfull()) //checking for queue overflow
cout<<?\n cannot insert the element”;
else
{
cout<,”\n enter the number to be insered”;l
cin>.item;
obj.insert(item);
}
break;
case 2:
if(obj.qempty())
cout<<”\n queue underflow!”;
else
obj.delet();
break;
case 3:
if(obj.qempty())
cout<<”\n queue is empty!”;
else
obj.display();
break;
default:cout<<|\n do you want to continue?”;
ans=getche();
}while(ans==’Y’||ans==\y\);
}

Output:

main menu
1.insert
2.delete
3.display

enter your choice 1

enter the number to be inserted 10
do you want to continue?y
main menu
1.insert
2.delete
3.display

enter your choice 1

EC 2209 Data Structures and Object Oriented Programming Lab

74
enter the number to be inserted 20
do you want to continue?y
main menu
1.insert
2.delete
3.display
enter your choice 1
enter the number to be inserted 30
do you want to continue?y
main menu
1.insert
2.delete
3.display
enter your choice 1
enter the number to be inserted 40
do you want to continue?y
main menu
1.insert
2.delete
3.display

enter your choice 3

10 20 30 40
do you want to continue?y
main menu
1.insert
2.delete
3.display

enter your choice 2

the deleted item is 10
do you want to continue?y
main menu
1.insert
2.delete
3.display
enter your choice 2
the deleted item is 20
do you want to continue?y
main menu
1.insert
2.delete
3.display
enter your choice 3
30 40
do you want to continue?

EC 2209 Data Structures and Object Oriented Programming Lab

75
Result:
Thus the Given Program for Queue using array implementation was executed successfully.

Ex. No:7b QUEUE ADT OPERATIONS USING LINKED LIST

Aim:
              To write a C++ program for Queue using Linked implementation.
 
Algorithm:

           Step1: Define a struct for each node in the queue. Each node in the queue
                     contains data and link to the next node. Front and rear pointer points to first
and last
                    node inserted in the queue.

          Step 2: The operations on the queue are

         a)INSERT data into the queue
         b)DELETE data out of queue
 
         Step  3:  INSERT DATA INTO queue
                   3a.Enter the data to be inserted into queue.
                   3b.If TOP is NULL
                         the input data is the first node in queue.
                         the link of the node is NULL.
                        TOP points to that node.
                   3c.If TOP is NOT NULL
                        the link of TOP points to the new node.
                        TOP points to that node.

           Step 4:   DELETE DATA FROM queue

                   4a.If TOP is NULL
                        the queue is empty
                   4b.If TOP is NOT NULL
                        the link of TOP is the current TOP.
                        the pervious TOP is popped from queue.

            Step 5.  The queue represented by linked list is traversed to display its content.
 
 
 Program:
/*
**********************************************
Program for implementing the queue using the linked list.
the queue full condition will never occur in this program.
**********************************************

EC 2209 Data Structures and Object Oriented Programming Lab

76
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
//declaration of linked queue data structure
class lqueue
{
private:
typedef struct node
{
int data;
struct node *next;
}Q;
Q *front,*rear;
public:
lqueue();
~ lqueue();
void create(),remove(),show();
void insert();
Q *delet();
void display(Q *);
};
/*
………………………………………
the constructor defined
………………………………………
*/
lqueue::lqueue()
{
front=NULL;
rear=NULL;
}
/*
………………………………………
the create function
………………………………………..
*/
void lqueue::create()
{
insert();
}
/*
………………………………………
the remove function
………………………………………..
*/
void lqueue::remove()

EC 2209 Data Structures and Object Oriented Programming Lab

77
{
front=delet();
}
/*
………………………………………
the show function
………………………………………..
*/
void lqueue::show()
{
display(front);
}
/*
………………………………………
the insert function
………………………………………..
*/
void lqueue::insert()
{
char ch;
Q *temp;
clrscr();
temp=new Q;//allocate memory for temp node
temp->next=NULL;
cout<<”\n\n\n insert the element in the queue\n”;
cin>>temp->data;

if(front==NULL)//create first node

{
front=temp;
rear=temp;
}
else
{
rear->next=temp;
rear=rear->next;
}
}

/*
………………………………………
the Qempty function
………………………………………..
*/
int qempty(Q *front)
{

EC 2209 Data Structures and Object Oriented Programming Lab

78
if(front==NULL)
return 1;
else
return 0;
}
/*
…………………………………………..
the delete function
…………………………………………..
*/
Q *lqueue::delet()
{
Q *temp;
temp=front;
if(Qempty(front))
{
cout<<”\n\n\t\t sorry ! the queue is empty\n”;
cout<<”\n can not delte the element”;
}
else
{
cout<<”\n\t the deletd element is”<<temp->data;
fron=-front->next;
temp->next=NULL;
delete temp;
}
return front;
}
/*
……………………………………….
the display function
………………………………………..
*/
void lqueue::display(Q *front)
{
if(Qempty(front))
cout<<”\n the queue is empty\n”;
else
{
cout<<”\n\t the display of queue is \n”;
for(;front!=rear->next;front =front ->next)
cout<<”’<<front->data;
}
getch();
}
/*

EC 2209 Data Structures and Object Oriented Programming Lab

79
………………………………………
the destructor defined
………………………………………
*/
lqueue::lqueue()
{
if((front!NULL)&&(rear!=NULL))
{
front=NULL;
rear=NULL;
dlete front;
delete rear;
}
}
/*
…………………………………………
the main function
calls: create,remove,show
called by:O.S
…………………………………………
*/
void main(void)
{
char ans;
int choice;
lqueue que;
do
{
clrscr();
cout<<”\n \t program for queue using linked list\n”;
cout<<”\n main menu”;
cout<<”\n 1.insert\n2. delete\n3.display”;
cout<<”\n enter your choice”;
cin>>choice;
switch(choice)
{
case 1:
que.create();
break;
case 2:
que.remove();
break;
case 3:
que.show();
break;
default:cout<<”\n you have entered wrong choice”<<endl;

EC 2209 Data Structures and Object Oriented Programming Lab

80
break;
}
cout<<”\n do you want main menu?(y/n)”<<endl;
ans=getch();
}
while(ans==’y’||ans=’Y’);
getch();
}

Output

program for queue using linked list

main menu
1.insert
2. delete
3.display

enter your choice 1

insert the element in the queue
10
do you want main menu?(y/n)
y
program for queue using linked list
main menu
1.insert
2. delete
3.display

enter your choice 1

insert the element in the queue
20
do you want main menu?(y/n)
y
program for queue using linked list
main menu
1.insert
2. delete
3.display

enter your choice 1

insert the element in the queue
30
do you want main menu?(y/n)
y

EC 2209 Data Structures and Object Oriented Programming Lab

81
program for queue using linked list
main menu
1.insert
2. delete
3.display

enter your choice 1

insert the element in the queue

40
do you want main menu?(y/n)
y
program for queue using linked list
main menu
1.insert
2. delete
3.display

enter your choice 3

the display of queue is

10 20 30 40
do you want main menu?(y/n)
y
program for queue using linked list
main menu
1.insert
2. delete
3.display

enter your choice 2

the deleted element is 10

do you want main menu?(y/n)

y
program for queue using linked list
main menu
1.insert
2. delete
3.display

enter your choice 2

the deleted element is 20

EC 2209 Data Structures and Object Oriented Programming Lab

82
do you want main menu?(y/n)
y
program for queue using linked list
main menu
1.insert
2. delete
3.display

enter your choice 3

the display of queue is
30 40
do you want to see main menu?(y/n)n

Result:

EC 2209 Data Structures and Object Oriented Programming Lab

83
Thus the given program Queue ADT operations using Linked List was executed
successfully.

Ex. No:8 BINARY SEARCH TREE

 
Aim:
              To write a c program for binary search tree.
 
Algorithm:
 
1. Declare function create(),search(),delete(),Display().
2. Create a structure for  a tree contains left pointer and right pointer.
3. Insert an element is by checking the top node and the leaf node and the operation
will be performed.
4. Deleting an element contains searching the tree and deleting the item.
5. display the Tree elements.
Program:

/*
******************************************************************
Program for implementation of binary search tree and perform insertion
,deletion,searching,display of tree.
******************************************************************
*/
#include<iostream.h>
#include<conio.h>
class bintree
{
typedef struct bst
{
int data;
struct bst,*left,*right;
}
node;
node *root,*new,*temp,*parent;
public:
bintree()
{
root=NULL;
}
void create();
void display();
void delet();
void find();
void insert(node *,node*);

EC 2209 Data Structures and Object Oriented Programming Lab

84
void inorder)node *);
void search(node**,int,node **);
void del(node *,int);
};
void bintree::create()
{
New=new node;
New->left=NULL;
New->right=NULL;
cout<<”\n enter the element”;
cin>>New->data;
if(root==NULL)
root=New;
else
insert(root,New);
}
void bintree::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);
}
}
voi bintree::display()
{
if(root==NULL)
cout<<”tree is not created”;
else
{
cout<<”\n the tree is:”;
inorder(root);
}
}
void bintree::inorder(node *temp)
{
if(temp!NULL)
{

EC 2209 Data Structures and Object Oriented Programming Lab

85
inorder(temp->left);
cout<<””<<temp->data;
inorder(temp->righ);
}
}
void bintree::find()
{
int key;
cout <<”\n enter the element which you want to search”;
cin>>key;
temp=root;
search(&temp,key,&parent);
if(temp==NULL)
cout<<”\n element is not present”;
else
cout<<”\n parent of node “<<temp->data<<”is”<<parent->data;
}
void bintreee::search(node **temp,int key,node ** parent)
{
if(*temp==NULL)
cout<<endL<<”tree is not created”<<endl;
else
{
while(*temp!=NULL)
{
if(*temp)->data==key)
{
cout<<”\n the”<<(*temp)->data<<”element is present”;
break;
}
*parent=*temp;//stores the parent value
if(*temp)->data>key)
*temp=(*temp)->left;
else
*temp=(*temp)->right;
}
}
return;
}
void bintree::delet()
{
int key;
cout<<”\n emter the element you want to delente”;
cin>>key;
if(key==root->data)
{

EC 2209 Data Structures and Object Oriented Programming Lab

86
bintree();// assigning a value NULL to root
}
else
del(root,key);}
/*
************************************************************************
This function is for deleting a node from binary search tree . there exits three possible cases
for deleting of a node
*************************************************************************
*/
void bintree::del(node *root,int key)
{
node *temp_succ;
if(root==NULL)
cout<<”tree is not created”;
else
{
temp=root;
search(&temp,key,&parent);
//temp node is to be deleted
/*deleting a node with two children*/
if(temp->left!=NULL&&temp->right!=NULL)
{
parent=temp;
temp_succ=temp_succ->left;
while(temp_succ->left!=NULL)
{
parent=temp_succ;
temp_succ=temp_succ->left;
}
temp->data=temp_succ->data; //copyng the immediate successor
temp->right-NULL:
cout<<””now deleted it!”;
return;
}
/* deleting a node having only one child*?
/*the node to be deleted has left child*/
if(temp->left!=NULL&&temp->right==NULL)
{
if(parent->left==temp)
parent->left=temp->left;
else
parent->right=temp->left;
temp=NULL;
delte temp;
cout<<”now deleted it!”;

EC 2209 Data Structures and Object Oriented Programming Lab

87
return;
}
/*the node to be deleted has right child*/
if(temp->left==NULL&&temp->right!=NULL)
{
if(parent->left==temp)
parent->left=temp->right;
else
parent->right=temp->right;
temp=NULL;
delete temp;
cout<<”now deleted it!”;
return;
}
/*deleting a node which is having no child*/
if(temp->left==NULL&&temp->right==NULL)
{
if(parent->left==temp)
parent->left=NULL;
else
parent->right=NULL;
cout<<”now deleted it!”;
return;
}
}
}
void main()
{
int choice;
char ans=’N’;
bintree tr;
cout<<”\n\t program for binary search tree”;
do
{
cout<<”\n1.create\n2.search\n3.delete\n4.display”;
cout<<”\n\n wnter your choice:”;
cin>>choice;
switch(choice)
{
case 1:do
{
tr.create();
cout<<”do you want to enter more elements”(y/n)”<<endl;
ans=getche();
}
while(ans==’y’);

EC 2209 Data Structures and Object Oriented Programming Lab

88
break;
case 2:tr.find();
break;
case 3:
tr.delet();
break;
case 4:
tr.display();
break;
}}
while(choice!=5);
}

Output:
program for binary search tree
1.create
2.search
3.delete
4.display

enter your choice 1

enter the element 10

do you want to enter more elements”(y/n)
y
enter the element 8
do you want to enter more elements”(y/n)
y
enter the element 7

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

y
enter the element 9

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

y
enter the element 12

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

y
enter the element 11

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

y
enter the element 13

EC 2209 Data Structures and Object Oriented Programming Lab

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

1.create
2.search
3.delete
4.display

enter your choice 4

the tree is: 7 8 9 10 11 12 13

1.create
2.search
3.delete
4.display

enter your choice 2

enter the element which you want to search 13

the 13 element is present
parent of node 13 is 12
1.create
2.search
3.delete
4.display

enter your choice 3

enter the element you wish to delete 12

the 12 element is present now deleted it!
1.create
2.search
3.delete
4.display

enter your choice 4

the tree is : 7 8 9 10 11 13
1.create
2.search
3.delete
4.display

enter your choice 3

enter the element you wish to delete 11

EC 2209 Data Structures and Object Oriented Programming Lab

90
the 11 element is present now deleted it!
1.create
2.search
3.delete
4.display

enter your choice 4

the tree is : 7 8 9 10 13
1.create
2.search
3.delete
4.display

enter your choice 3

enter the element you wish to delete 7

the 7 element is present now deleted it!
1.create
2.search
3.delete
4.display

enter your choice 4

the tree is : 8 9 10 13
1.create
2.search
3.delete
4.display

enter your choice 5

EC 2209 Data Structures and Object Oriented Programming Lab

91
 Result:

Thus the Given Program Binary Search Tree was executed successfully.

Ex. No:9 HEAP SORT

Aim:
              To  write a c program to perform heap sort.
 
Algorithm:
1. Get the size of the array from the user.
2. Get the elements to be sorted.
3. Sorting is performed when we call the heap sort function.
4. Now the array is contained with sorted elements.
5. Display the sorted elements.

Program:
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
#define MAX 10
class heap
{
private:
int arr[MAX];
int n;
public:
Heap();
void insert(int num);
void makespace();
void heapsort();
void display();
};
heap::heap()
{
n=0;
for(int i=0;i<MAX;i++)
arr[i]=0;
}
void heap::insert(int num)
{
if(n<Max)
{
arr[n]=num;
n++;
}

EC 2209 Data Structures and Object Oriented Programming Lab

92
else
cout<<”\n array is full”;
}
void heap::makeheap()
{
for(int i=1;i<n;i++)
{
int val =arr[i];
int j=I;
int f=(j-1)/2;
while(j>0&&arr[f]<val)//creating a MAX heap
{
arr[j]=arr[f];
j=f;
f=(j-1)/2;
}arr[j]=val;
}}
void heap::heapsprt()
{
for(int i=n-1;i>0;i--)
{
int temp=arr[i];
arr[i]=arr[0];
int k=0;
int j;
if(i==1)
j=-1;
else
j=1;
if(i>2&&arr[2]>arr[1])
j=2;
while(j>=0&&temp<arr[j])
{
arr[k]=arr[j];
k=j;
j=2*k+1;
if(j+1<=i-1&&arr[j]<arr[j+1])
j++;
if(j>i-1)
j=-1;
}
arr[k]=temp;
}
}
void heap::display()
{

EC 2209 Data Structures and Object Oriented Programming Lab

93
for(int i=0;i<n;i++)
cout<<”\n”<<arr[i];
cout<<”\n”;
}
void main()
{
heap obj;
obj.insert(14);
obj.insert(12);
obj.insert(9);
obj.insert(8);
obj.insert(7);
obj.insert(10);
obj.insert(18);
cout<<”\n the elements are …..”<<endl;
obj.display();
odj.makeheap();
cout<<”\n heapified”<<endl;
obj.display();
obj.heapsort();
cout<<”\n elements sorted by heap sort…”<<endl;
obj.display();
getch();
}
Output:
the elements are….
14
12
9
8
7
10
18
heapified
18
12
14
8
7
9
10
Elements sorted by heap sort
7
8
9
10

EC 2209 Data Structures and Object Oriented Programming Lab

94
12
14
18
Result: Thus the Given Program Heap Sort was executed successfully.
 
Ex.No :10 QUICK SORT

Aim:
              To  write a c program to perform quick sort.
 
Algorithm:
1. Get the value of how many no. to be sorted.

2. Get the elements from the user.

3. Two function quicksort() and swap(). Quick sort to perform sorting.

4. Swap() is just to rearrange the values.

5. Quick sort algorithm works by partitioning the array to be sorted, then recursively

sorting each partition.

6. Display the sorted value.

 
 Program:
 
 #include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#define SIZE 10
class quick
{
int arr[SIZE];
public:
int get_data(int);
void quicksort(int ,int);
int partition(int,int);
void swap)int ,int);
void display(int);
};
/*
this function is to input the elements
*/
int quick::get_data(int n)

EC 2209 Data Structures and Object Oriented Programming Lab

95
{
int i
cout<<”\n enter total numbers to sort:”;
cin>>n;
for(i-0;i<n;i++)
{
cout<<”\n enter element”;
cin>>arr[i];
}
return n;
}
/*
this function is to sort the elements in a sublist
*/
void quick::quicksort(int p,int q)
{
int j;
if(p<q)
{
j=partition(p,q+1);// setting pivot element
quicksort(p,j-1);//splitting of list
quicksort(j_1,q);//splitting of list
}}
/*
this function is to partition a list and decide the pivot element
*/
int quick::partition(int m,int p)
{
int pivot=arr[m];
int i=m.j=p;
do
{
do
{
i++;
}
while(arr[i]<pivot);
do
{
j--;
}while(arr[j]>pivot);
if(i<j)
swap(I,j);
}while(i<j);
arr[m]=arr[j];
arr[j]=pivot;

EC 2209 Data Structures and Object Oriented Programming Lab

96
return j;
}
void quick::swap(int I,int j)
{
int p;
p=arr[i];
arr[i]=arr[j];
arr[j]=p;
}
void quick::display(int n)
{
for(int i=0;i<n;i++)
cout<<”’<<arr[i]’
}
void main()
{
quick obj;// for integer elements
int n,I;
clrscr();
cout<,”\n \t\t\quick sort method\n”;
n=obj.get_data(n);
obj.quicksort(0,n-1);
cout<<”\n\\t sorted array is:\n”;
obj.display(n);
getch();
}

Output
quick sort method
enter total numbers to sort: 5
enter element 30
enter element 50
enter element 10
enter element 20
enter element 40
sorted array is
10 20 30 40 50

 Result:

EC 2209 Data Structures and Object Oriented Programming Lab

97
Thus the Given Program quick sort was implemented successfully.
 
 

EC 2209 Data Structures and Object Oriented Programming Lab

98