NATCHATRAN -PREM ANANDH.J: EC2209 - Data Structures And Object Oriented Programming Lab

Ex No 1)

Date:

TO ADD, SUB, MULTIPLY

AND DIVIDE TWO NUMBERS

AIM:

To write a C++ Program for Adding, Subtracting, Multiplying and Dividing two numbers.

ALGORITHM :

Read the two numbers – n1, n2
If the option is Add, call the member function add with the parameters n1 and n2 and return the Addition of the two numbers.
If the option is Subtract, call the member function sub with the parameters n1 and n2 and return the difference of the two numbers.
If the option is Multiply, call the member function mul with the parameters n1 and n2 and return the product of the two numbers.
If the option is Divide, call the member function div with the parameters n1 and n2 and return the division of n1 by n2.
Display the Result.
If the option is Exit, quit the program.

PROGRAM :

// Program to maintain a calculator

#include <conio.h>

#include <iostream.h>

class calci

{

private :

float num1;

float num2;

float result;

public :

calci() ;

void getdata();

void add () ;

void sub () ;

void mul () ;

void div () ;

void display(char op);

};

// initializes data member

calci::calci()

{

num1 = 0;

num2 = 0;

}

void calci::getdata()

{

cout << "\n\nEnter the number 1 : ";

cin >> num1;

cout << "\n\nEnter the number 2 : ";

cin >> num2;

}

// adds two numbers

void calci::add ()

{

result = num1 + num2;

display('+');

}

// subtracts two numbers

void calci::sub ()

{

result = num1 - num2;

display('-');

}

// Multiplies two numbers

void calci::mul ()

{

result = num1 * num2;

display('*');

}

// divides two numbers

void calci::div ()

{

if(num2 == 0)

{

cout << "\n\nDivide by zero error !";

return;

}

result = num1 / num2;

display('/');

}

void calci::display (char op)

{

cout << "\n\n" << num1 << " " << op << " " << num2 << " = " << result;

}

void main( )

{

calci c ;

int ch;

{

clrscr();

cout << "\n\tCalculator";

cout << "\n\t----------";

cout << "\n\n1. Add";

cout << "\n\n2. Subtract";

cout << "\n\n3. Multiply";

cout << "\n\n4. Divide";

cout << "\n\n5. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

c.getdata();

c.add();

break;

case 2:

c.getdata();

c.sub();

break;

case 3:

c.getdata();

c.mul();

break;

case 4:

c.getdata();

c.div();

break;

default:

break;

}

getch();

}while(ch<5);

}

OUTPUT:

Calculator

-------------

1. Add

2. Subtract

3. Multiply

4. Divide

5. Exit

Enter your choice : 1

Enter the number 1 : 3

Enter the number 2 : 4

3 + 4 = 7

Calculator

-------------

1. Add

2. Subtract

3. Multiply

4. Divide

5. Exit

Enter your choice : 2

Enter the number 1 : 6

Enter the number 2 : 2

6 - 2 = 4

Calculator

-------------

1. Add

2. Subtract

3. Multiply

4. Divide

5. Exit

Enter your choice : 3

Enter the number 1 : 7

Enter the number 2 : 8

7 * 8 = 56

Calculator

-------------

1. Add

2. Subtract

3. Multiply

4. Divide

5. Exit

Enter your choice : 4

Enter the number 1 : 8

Enter the number 2 : 4

8 / 4 = 2

Calculator

-------------

1. Add

2. Subtract

3. Multiply

4. Divide

5. Exit

Enter your choice : 5

RESULT:

Thus the C++ Program for Addition, Subtraction, Multiplication and Division of two numbers was Compiled and Executed Successfully.

Ex No 2)

Date:

TO EVALUATE SIN(X) SERIES

AIM:

To write a C++ Program for evaluating sin(x)..

ALGORITHM :

Read the numbers – x (in radians)
Set i = 3, sum = x, sign = 1, temp = 0
Repeat

begin

psum = sum

factval = factorial of i

pow = power(x, i)

sign = (-1) * sign

temp = sign * pow/factval

sum = sum + temp

i = i + 2

end

until ( abs(sum-psum) > 0.0001)

Display the Result

PROGRAM :

// Program to calculate the value of sin x

// sin x = x - (x^3)/3! + (x^5)/5! - (x^7)/7! ..... (x^n)/n!

#include <conio.h>

#include <iostream.h>

#include <math.h>

const float precision = 0.0001;

class sinx

{

private :

int x;

public :

long int fact (int num);

float power(float x, int n);

float sinx_calculate(int x);

};

long int sinx::fact(int num)

{

long int value = 1;

for(int i = 1; i<=num; i++)

value = value * i;

return value;

}

float sinx::power(float x, int n)

{

float value;

value = 1;

for(int i = 1; i<=n; i++)

value = value * x;

return value;

}

float sinx::sinx_calculate(int x)

{

int sign, i, n;

long int factval;

float sum, psum, temp, pow;

i = 3;

sum = x;

sign = 1;

temp = 0;

{

psum = sum;

factval = fact(i);

pow = power(x, i);

sign = (-1) * sign;

temp = sign * pow/factval;

sum = sum + temp;

i = i + 2;

}while(abs(sum-psum) > precision);

return sum;

}

void main( )

{

sinx s ;

int n;

float result;

char ch;

{

clrscr();

cout << "\nEnter the value of x in radians : ";

cin >> n;

result = s.sinx_calculate(n);

cout << "\n\nsin(" << n << ") = " << result;

cout << "\n\nDo you want to continue ? ";

cin >> ch;

}while(ch == 'y' || ch == 'Y');

}

OUTPUT:

Enter the value of x in radians : 1

sin(1) = 0.833333

Do you want to continue ? y

Enter the value of x in radians : 5

sin(5) = 0.581802

Do you want to continue ? n

RESULT:

Thus the C++ Program for calculating sin(x) was Compiled and Executed Successfully.

Ex No 3)

Date:

COMPLEX NUMBER MANIPULATION

USING OPERATOR OVERLOADING

AIM:

To write a C++ Program for manipulation of complex numbers using operator overloading.

ALGORITHM :

Read the two complex numbers – c1, c2
If the option is Add, call the member function add with the parameter c2 and return the resultant complex number

real = real + b.real

imag = imag + b.imag

If the option is Subtract, call the member function sub with the parameter c2 and return the resultant complex number

real = real - b.real

imag = imag - b.imag

If the option is Multiply, call the member function mul with the parameter c2 and return the resultant complex number

old = c1

real = (old.real * b.real) - (old.imag * b.imag)

imag = (old.real * b.imag) + (old.imag * b.real)

If the option is Divide, call the member function div with the parameter c2 and return the resultant complex number

old = c1

float temp

temp = (b.real * b.real) + (b.imag * b.imag)

real = ((old.real * b.real) + (old.imag * b.imag))/temp

imag = ((old.imag * b.real) - (old.real * b.imag))/temp

Display the Result.
If the option is Exit, quit the program.

PROGRAM :

// complex number operations using operator overloading

#include <conio.h>

#include <iostream.h>

class complex

{

private:

float real;

float imag;

public:

complex();

complex(float r, float i);

void getdata();

void operator += (complex b);

void operator -= (complex b);

void operator *= (complex b);

void operator /= (complex b);

void display(char *msg);

};

complex::complex()

{

real = imag = 0;

}

complex::complex(float r, float i)

{

real = r;

imag = i;

}

void complex::getdata()

{

cout << "\n\nReal part : ";

cin >> real;

cout << "\n\nImaginary part : ";

cin >> imag;

}

void complex::operator += (complex b)

{

real = real + b.real;

imag = imag + b.imag;

}

void complex::operator -= (complex b)

{

real = real - b.real;

imag = imag - b.imag;

}

void complex::operator *= (complex b)

{

complex old = *this;

real = (old.real * b.real) - (old.imag * b.imag);

imag = (old.real * b.imag) + (old.imag * b.real);

}

void complex::operator /= (complex b)

{

complex old = *this;

float temp;

temp = (b.real * b.real) + (b.imag * b.imag);

real = ((old.real * b.real) + (old.imag * b.imag))/temp;

imag = ((old.imag * b.real) - (old.real * b.imag))/temp;

}

void complex::display(char *msg)

{

cout << "\n\n" << msg;

cout << "(" << real;

cout << ", " << imag << ")";

}

void main( )

{

int ch;

complex c1, c2;

{

clrscr();

cout << "\n\tComplex number Arithmetic";

cout << "\n\t-------------------------";

cout << "\n\n1. Add";

cout << "\n\n2. Sub";

cout << "\n\n3. Multiply";

cout << "\n\n4. Divide";

cout << "\n\n5. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

cout << "\n\nEnter Complex number 1 : ";

c1.getdata();

cout << "\n\nEnter Complex number 2 : ";

c2.getdata();;

cout << "\n\nEntered Complex numbers are ...\n";

c1.display("c1 = ");

c2.display("c2 = ");

c1 += c2;

c1.display("c3 = c1 + c2 = ");

break;

case 2:

cout << "\n\nEnter Complex number 1 : ";

c1.getdata();

cout << "\n\nEnter Complex number 2 : ";

c2.getdata();;

cout << "\n\nEntered Complex numbers are ...\n";

c1.display("c1 = ");

c2.display("c2 = ");

c1 -= c2;

c1.display("c3 = c1 - c2 = ");

break;

case 3:

cout << "\n\nEnter Complex number 1 : ";

c1.getdata();

cout << "\n\nEnter Complex number 2 : ";

c2.getdata();;

cout << "\n\nEntered Complex numbers are ...\n";

c1.display("c1 = ");

c2.display("c2 = ");

c1 *= c2;

c1.display("c3 = c1 * c2 = ");

break;

case 4:

cout << "\n\nEnter Complex number 1 : ";

c1.getdata();

cout << "\n\nEnter Complex number 2 : ";

c2.getdata();;

cout << "\n\nEntered Complex numbers are ...\n";

c1.display("c1 = ");

c2.display("c2 = ");

c1 /= c2;

c1.display("c3 = c1 / c2 = ");

break;

default:

break;

}

getch();

}while(ch<5);

}

OUTPUT:

Complex number Arithmetic

-----------------------------------

1. Add

2. Sub

3. Multiply

4. Divide

5. Exit

Enter your choice : 1

Enter Complex number 1 :

Real part : 1

Imaginary part : 1

Enter Complex number 2 :

Real part : 2

Imaginary part : 2

Entered Complex numbers are ...

c1 = (1, 1)

c2 = (2, 2)

c3 = c1 + c2 = (3, 3)

Complex number Arithmetic

-----------------------------------

1. Add

2. Sub

3. Multiply

4. Divide

5. Exit

Enter your choice : 2

Enter Complex number 1 :

Real part : 1

Imaginary part : 1

Enter Complex number 2 :

Real part : 2

Imaginary part : 2

Entered Complex numbers are ...

c1 = (1, 1)

c2 = (2, 2)

c3 = c1 - c2 = (-1, -1)

Complex number Arithmetic

-----------------------------------

1. Add

2. Sub

3. Multiply

4. Divide

5. Exit

Enter your choice : 3

Enter Complex number 1 :

Real part : 1

Imaginary part : 1

Enter Complex number 2 :

Real part : 2

Imaginary part : 2

Entered Complex numbers are ...

c1 = (1, 1)

c2 = (2, 2)

c3 = c1 * c2 = (0, 4)

Complex number Arithmetic

-----------------------------------

1. Add

2. Sub

3. Multiply

4. Divide

5. Exit

Enter your choice : 4

Enter Complex number 1 :

Real part : 1

Imaginary part : 1

Enter Complex number 2 :

Real part : 2

Imaginary part : 2

Entered Complex numbers are ...

c1 = (1, 1)

c2 = (2, 2)

c3 = c1 / c2 = (0.5, 0)

Complex number Arithmetic

-----------------------------------

1. Add

2. Sub

3. Multiply

4. Divide

5. Exit

Enter your choice : 5

RESULT:

Thus the C++ Program for the manipulation of complex numbers was Compiled and Executed Successfully.

Ex No 4)

Date:

SINGLE INHERITANCE

STUDENT DETAILS

AIM:

To write a C++ Program for processing student details using Single Inheritance.

ALGORITHM :

Create base class stu_info with attributes name, rollno and sex.
Create sub class physical_fit with attributes height and weight.
Read no of students, n
i = 0
Repeat until i < n

begin

Use getdata() member function to get the member values of the class.

i = i + 1

end

i = 0
Repeat until i < n

begin

Use display() member function to display the member values of the class.

i = i + 1

end

Quit the program

PROGRAM :

// Single Inheritance using array of objects

#include <conio.h>

#include <iostream.h>

#include <iomanip.h>

const int MAX = 100;

class stu_info

{

private:

char name[20];

long int rollno;

char sex;

public:

void getdata();

void display();

};

class physical_fit:public stu_info

{

private:

float height;

float weight;

public:

void getdata();

void display();

};

void stu_info::getdata()

{

cout << "\n\nName : ";

cin >> name;

cout << "\n\nRollNo : ";

cin >> rollno;

cout << "\n\nSex : ";

cin >> sex;

}

void stu_info::display()

{

cout << name << "\t\t\t";

cout << rollno << "\t ";

cout << sex << "\t";

}

void physical_fit::getdata()

{

stu_info::getdata();

cout << "\n\nHeight : ";

cin >> height;

cout << "\n\nWeight : ";

cin >> weight;

}

void physical_fit::display()

{

stu_info::display();

cout << setprecision(2);

cout << height << "\t";

cout << weight << "\t";

}

void main()

{

int n;

physical_fit stu[MAX];

clrscr();

cout << "\nEnter the no. of students : ";

cin >> n;

for(int i=0;i<n;i++)

{

cout <<"\n\nStudent " << i+1 << "... \n";

stu[i].getdata();

}

cout << "\n\n";

cout << "---------------------------------------------------------\n\n";

cout << " Name Roll No Sex Height Weight\n\n";

cout << "---------------------------------------------------------\n\n";

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

{

cout << "\n\n";

stu[i].display();

}

cout << "\n\n";

cout << "-----------------------------------------------------------\n\n";

getch();

}

OUTPUT:

Student 1...

Name : Haniel

RollNo : 1

Sex : M

Height : 153

Weight : 50

Student 2...

Name : Bettina

RollNo : 2

Sex : F

Height : 158

Weight : 48

Student 3...

Name : Phebina

RollNo : 3

Sex : F

Height : 157

Weight : 49

--------------------------------------------------------------------------------

Name Roll No Sex Height Weight

--------------------------------------------------------------------------------

Haniel 1 M 153 50

Bettina 2 F 158 48

Phebina 3 F 157 49

--------------------------------------------------------------------------------

RESULT:

Thus the C++ Program for the Student details using Single Inheritance was Compiled and Executed Successfully.

Ex No 5)

Date:

LIST ADT USING ARRAYS

AIM:

To write a C++ Program for processing a List ADT using Arrays.

ALGORITHM :

MAX = 10, maximum number of elements in the array
If the option is Create, then Read the number of elements, n and pass ‘n’ as a parameter to the member function create

begin

i = 0

Repeat until i < n

begin

Read arr[i]

i = i + 1

end

If the option is Insert, Read the position, pos and read the element, num and pass the pos and num as parameters to the member function insert

begin

i = MAX – 1

Repeat until i >= pos

begin

arr[i] = arr[i - 1]

end

i = i - 1

arr[i] = num

end

If the option is Delete then Read the element to be deleted, num and pass it as parameter to the member function del

begin

loc = find(num)

if loc != -1 then

begin

i = loc+1

Repeat until i < MAX

begin

arr[i - 1] = arr[i]

i = i + 1

end

arr[i - 1] = 0

end

else

Display “The element is not present in the array"

end

If the option is find then Read the element to be found, num and pass it as parameter to the member function find and it returns the position if the number is found else -1

begin

i = 0

Repeat until i < MAX

begin

if ( arr[i] == num ) then

return i

i = i + 1

end

return -1

end

If the option is count then

begin

i = 0

Repeat until i < MAX and arr[i] != NULL

begin

i = i + 1

end

return i

end

If the option is display then

begin

i = 0

Repeat until i < MAX and arr[i] != NULL

Begin

Display arr[i]

i = i + 1

end

If the option is Exit, quit the program.

PROGRAM :

// Program to implement an List ADT using array.

#include <conio.h>

#include <iostream.h>

const int MAX = 10;

class array

{

private :

int arr[MAX] ;

int nElements;

public :

array();

void create(int numtot) ;

void insert(int pos, int num) ;

void del(int num) ;

void display() ;

int count();

int find (int num) ;

};

array::array()

{

for(int i=0; i < MAX; i++)

arr[i] = NULL;

}

// creates an initial array

void array::create(int numtot)

{

int num;

for(int i = 0; i < numtot; i++)

{

cin >> num;

arr[i] = num ;

}

// inserts an element num at given position pos

void array::insert(int pos, int num)

{

// shift elements to right

for ( int i = MAX - 1 ; i >= pos ; i-- )

arr[i] = arr[i - 1] ;

arr[i] = num ;

}

// deletes an element from the given position pos

void array::del(int num)

{

int loc = find(num);

if(loc != -1)

{

// skip to the desired position

for ( int i = loc+1 ; i < MAX ; i++ )

arr[i - 1] = arr[i] ;

arr[i - 1] = 0 ;

}

else

cout << "\n\nThe element " << num << " is not present in the array" ;

}

// searches array for a given element num

int array::find(int num)

{

// Traverse the array

for ( int i = 0 ; i < MAX ; i++ )

{

if ( arr[i] == num )

return i;

}

return -1;

}

// Counts the number of elements inserted into the array

int array::count()

{

// Traverse the array

for ( int i = 0 ; i < MAX && arr[i] != NULL; i++ );

return i;

}

// displays the contents of a array

void array::display()

{

cout<< endl ;

// traverse the entire array

for ( int i = 0 ; i < MAX && arr[i] != NULL; i++ )

cout << " " << arr[i] ;

}

void main()

{

array a ;

int ch, loc, num, ntot;

{

clrscr();

cout << "\n\tList ADT using Arrays";

cout << "\n\t---------------------";

cout << "\n\n1. Create";

cout << "\n\n2. Insert";

cout << "\n\n3. Delete";

cout << "\n\n4. Find";

cout << "\n\n5. Count";

cout << "\n\n6. Display";

cout << "\n\n7. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

cout << "\n\nEnter the number of elements to be added : ";

cin >> ntot;

cout << "\n\nEnter the numbers...\n";

a.create(ntot);

a.display();

break;

case 2:

a.display();

cout << "\n\nEnter the number : ";

cin >> num;

cout << "\n\nEnter the position : ";

cin >> loc;

a.insert(loc, num);

a.display();

break;

case 3:

a.display();

cout << "\n\nEnter the number to be deleted : ";

cin >> num;

a.del(num);

a.display();

break;

case 4:

a.display();

cout << "\n\nEnter the number to be found : ";

cin >> num;

loc = a.find(num);

if(loc == -1)

cout << "\n\nThe element " << num

<< " is not present in the array" ;

else

cout << "\n\nThe element " << num

<< " is present at position "<< ( loc + 1 );

break;

case 5:

a.display();

ntot = a.count();

cout << "\n\nThe number of elements is " << ntot;

break;

case 6:

a.display();

break;

default:

break;

}

getch();

}while(ch<7);

}

OUTPUT:

List ADT using Arrays

----------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 1

Enter the number of elements to be added : 3

Enter the numbers...

27 35 86

List ADT using Arrays

----------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 2

27 35 86

Enter the number : 54

Enter the position : 2

27 54 35 86

List ADT using Arrays

----------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 3

27 54 35 86

Enter the number to be deleted : 27

54 35 86

List ADT using Arrays

----------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 4

54 35 86

Enter the number to be found : 54

The element 54 is present at position 1

List ADT using Arrays

----------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 4

54 35 86

Enter the number to be found :

The element 21 is not present in the array

List ADT using Arrays

----------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 5

54 35 86

The number of elements is 3

List ADT using Arrays

----------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 6

54 35 86

List ADT using Arrays

----------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 7

RESULT:

Thus the C++ Program for the List ADT using Arrays was Compiled and Executed Successfully.

Ex No 6)

Date:

LIST ADT USING LINKED LISTS

AIM:

To write a C++ Program for processing a List ADT using Linked Lists.

ALGORITHM :

Create a node with a data field and pointer next pointing to the node data type
If the option is Create, then Read the number of elements, n and call the member function append

begin

i = 0

Repeat until i < n

begin

Read num

Call append(num)

i = i + 1

end

If the option is Insert at beginning, Read the the element, num and pass the num as parameter to the member function addatbeg

begin

temp = create a new node

temp -> data = num

temp -> link = p

p = temp

end

If the option is Insert at a position, Read the the element, num and the position, loc and pass the loc, num as parameters to the member function addafter

begin

temp = p

i = 0

Repeat until i < loc-1

begin

temp = temp -> link

if ( temp == NULL )

begin

Display there is lesser elements than the location, loc

Return

end

r = create a new node

r -> data = num

r -> link = temp -> link

temp -> link = r

end

If the option is Insert at end, Read the the element, num and pass the num as parameter to the member function append

p is the head node

begin

if ( p == NULL )

begin

p = Create a new node

p -> data = num

p -> link = NULL

end

else

begin

temp = p

Repeat until ( temp -> link != NULL )

temp = temp -> link

r = create a new node

r -> data = num

r -> link = NULL

temp -> link = r

end

If the option is Delete then Read the element to be deleted, num and pass it as parameter to the member function del

begin

temp = p

repeat until ( temp != NULL )

begin

if ( temp -> data == num )

begin

if ( temp == p )

p = temp -> link

else

old -> link = temp -> link

delete temp

return

end

else

begin

old = temp

temp = temp -> link

end

Display Element not found

end

If the option is find then Read the element to be found, num and pass it as parameter to the member function find and it returns the position if the number is found else -1

begin

node *q = p

pos = 1

Repeat until q != NULL and q->data != num

begin

q = q->link

pos = pos + 1

end

if(q != NULL) then

Display the number is found at position, pos

else

Display the number is not found in the list

end

If the option is count then

begin

node *temp = p

c = 0

Repeat until ( temp != NULL )

begin

temp = temp -> link

c = c + 1

end

return c

end

If the option is display then

begin

node *temp = p

Repeat until ( temp != NULL )

begin

Display temp->data

temp = temp -> link

end

return c

end
If the option is Exit, quit the program.

PROGRAM :

// Program to maintain a List ADT using linked list

#include <conio.h>

#include <iostream.h>

class linklist

{

private :

struct node

{

int data ;

node * next ;

}*p ;

public :

linklist() ;

void create();

void append (int num) ;

void addatbeg (int num) ;

void addafter (int loc, int num) ;

void display() ;

void find(int num);

int count() ;

void del (int num) ;

~linklist() ;

};

// initializes data member

linklist::linklist()

{

p = NULL ;

}

// adds a node at the end of a linked list

void linklist::append (int num)

{

node *temp, *r ;

// if the list is empty, create first node

if ( p == NULL )

{

p = new node ;

p -> data = num ;

p -> next = NULL ;

}

else

{

// go to last node

temp = p ;

while ( temp -> next != NULL )

temp = temp -> next ;

// add node at the end

r = new node ;

r -> data = num ;

r -> next = NULL ;

temp -> next = r ;

}

// adds a new node at the beginning of the linked list

void linklist::addatbeg(int num)

{

node *temp ;

// add new node

temp = new node ;

temp -> data = num ;

temp -> next = p ;

p = temp ;

}

// adds a new node after the specified number of nodes

void linklist::addafter(int loc, int num)

{

node *temp, *r ;

temp = p ;

// skip to desired portion

for ( int i = 0 ; i < loc-1 ; i++ )

{

temp = temp -> next ;

// if end of linked list is encountered

if ( temp == NULL )

{

cout << "\nThere are less than " << loc << " elements in list\n";

return ;

}

// insert new node

r = new node ;

r -> data = num ;

r -> next = temp -> next ;

temp -> next = r ;

}

// counts the number of nodes present in the linked list

int linklist :: count( )

{

node *temp = p ;

int c = 0 ;

// traverse the entire linked list

while ( temp != NULL )

{

temp = temp -> next ;

c++ ;

}

return c ;

}

// displays the contents of the linked list

void linklist::display()

{

node *temp = p ;

cout << endl ;

// traverse the entire linked list

while ( temp != NULL )

{

cout << temp -> data << " " ;

temp = temp -> next ;

}

// deletes the specified node from the linked list

void linklist::del(int num)

{

node *old, *temp ;

temp = p ;

while ( temp != NULL )

{

if ( temp -> data == num )

{

// if node to be deleted is the

// first node in the linked list

if ( temp == p )

p = temp -> next ;

// deletes the intermediate nodes in the linked list

else

old -> next = temp -> next ;

// free the memory occupied by the node

delete temp ;

return ;

}

// traverse the linked list till the last node is reached

else

{

// old points to the previous node

old = temp ;

// go to the next node

temp = temp -> next ;

}

cout << "\n\nElement " << num << " not found" ;

}

// Searches for the element

void linklist::find(int num)

{

node *q = p ;

// traverse the linked list

int pos = 1;

while ( q != NULL && q->data != num)

{

q = q->next ;

pos++;

}

if(q != NULL)

cout << "\n\nThe number " << num << " is found at position " << pos;

else

cout << "\n\nThe number " << num << " is not found in the list";

}

// deallocates memory

linklist :: ~linklist( )

{

node *q ;

while ( p != NULL )

{

q = p -> next ;

delete p ;

p = q ;

}

void main( )

{

linklist l ;

int ch, ch1, loc, num, numtot, ctr;

{

clrscr();

cout << "\n\tList ADT using Linked List";

cout << "\n\t--------------------------";

cout << "\n\n1. Create";

cout << "\n\n2. Insert";

cout << "\n\n3. Delete";

cout << "\n\n4. Find";

cout << "\n\n5. Count";

cout << "\n\n6. Display";

cout << "\n\n7. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

cout << "\n\nEnter the number of elements to be added : ";

cin >> numtot;

ctr = 0;

cout << "\n\nEnter the numbers...\n";

while (ctr < numtot)

{

cin >> num;

l.append(num);

ctr++;

}

l.display();

break;

case 2:

l.display();

cout << "\n\n1. Insert at Beginning";

cout << "\n\n2. Insert after a position";

cout << "\n\n3. Insert at End";

cout << "\n\n4. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch1;

switch(ch1)

{

case 1:

cout << "\n\nEnter the number : ";

cin >> num;

l.addatbeg(num);

break;

case 2:

cout << "\n\nEnter the number : ";

cin >> num;

cout << "\n\nEnter the position : ";

cin >> loc;

l.addafter(loc, num);

break;

case 3:

cout << "\n\nEnter the number : ";

cin >> num;

l.append(num);

break;

default:

break;

}

l.display();

break;

case 3:

l.display();

cout << "\n\nEnter the number to be deleted : ";

cin >> num;

l.del(num);

l.display();

break;

case 4:

l.display();

cout << "\n\nEnter the number to be found : ";

cin >> num;

l.find(num);

break;

case 5:

l.display();

numtot = l.count();

cout << "\n\nThe number of elements is " << numtot;

break;

case 6:

l.display();

break;

default:

break;

}

getch();

}while(ch<7);

}

OUTPUT:

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 1

Enter the number of elements to be added : 3

Enter the numbers...

1 5 8

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 2

1 5 8

1. Insert at Beginning

2. Insert after a position

3. Insert at End

4. Exit

Enter your choice : 1

Enter the number : 9

9 1 5 8

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 2

9 1 5 8

1. Insert at Beginning

2. Insert after a position

3. Insert at End

4. Exit

Enter your choice : 2

Enter the number : 48

Enter the position : 3

9 1 5 48 8

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 2

9 1 5 48 8

1. Insert at Beginning

2. Insert after a position

3. Insert at End

4. Exit

Enter your choice : 3

Enter the number : 78

9 1 5 48 8 78

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 3

9 1 5 48 8 78

Enter the number to be deleted : 7

Element 7 not found

9 1 5 48 8 78

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 4

9 1 5 48 8 78

Enter the number to be found : 1

The number 1 is found at position 2

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 5

9 1 5 48 8 78

The number of elements is 6

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 6

9 1 5 48 8 78

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 7

RESULT:

Thus the C++ Program for the List ADT using Linked List was Compiled and Executed Successfully.

Ex No 7)

Date:

LIST ADT USING CURSORS

AIM:

To write a C++ Program for processing a List ADT using Linked Lists.

ALGORITHM :

Create a node with a data field and next field pointing to the node data type
If the option is Create, then Read the number of elements, n and call the member function insert

begin

i = 0

Repeat until i < n

begin

Read num

Call insert(num)

i = i + 1

end

If the option is Insert, Read the the element, num and pass the num as parameter to the member function Insert

begin

if(p == NULL) then

begin

p = alloc();

cursorspace[p].next = 0;

cursorspace[p].data = num;

end

else

begin

int pos = p;

int tmp = alloc();

Repeat while(cursorspace[pos].next != 0)

pos = cursorspace[pos].next;

cursorspace[tmp].data = num;

cursorspace[tmp].next = cursorspace[pos].next;

cursorspace[pos].next = tmp;

end

If the option is Delete then Read the element to be deleted, num and pass it as parameter to the member function del

Begin

if(cnt == 0) then

begin

Display “The List is empty..."

return;

end

int num;

Display “Enter the number to be deleted “

Read num;

if(cnt == 1 && cursorspace[p].data == num) then

begin

initialize();

return;

end

int temp = findprevious(num);

if(temp == 0) then // The Head node - so no previous node

begin

int t = cursorspace[p].next;

free(p);

p = t;

return;

end

pos = temp;

if(cursorspace[pos].next != 0)then

begin

t = cursorspace[pos].next;

cursorspace[pos].next = cursorspace[t].next;

free(t);

end

else

Display “Element ", num, “ not found" ;

end

If the option is find then Read the element to be found, num and pass it as parameter to the member function find and it returns the position if the number is found else -1

begin

temp = p

c =1

// traverse the entire linked list

Repeat while ( temp != 0 && cursorspace[temp].data != num)

begin

temp = cursorspace[temp].next ;

c = c + 1

if(temp != NULL) then

Display the number is found at position, c

else

Display the number is not found in the list

end

If the option is count then

begin

if(p==NULL) then

return 0;

c = 1;

pos = p;

Repeat while(cursorspace[pos].next != 0)

begin

c++;

// traverse the entire linked list

pos = cursorspace[pos].next;

end

return c

end

If the option is display then

begin

int pos = p;

Repeat while(pos != 0)

begin

Display cursorspace[pos].data;

// traverse the entire linked list

pos = cursorspace[pos].next;

end

If the option is Exit, quit the program.

PROGRAM :

// Program to maintain a List ADT using Cursors

#include <conio.h>

#include <iostream.h>

const int MAX = 20;

class cursorlist

{

private :

struct node

{

int data ;

int next ;

}cursorspace[MAX];

int p;

public :

cursorlist() ;

int alloc();

void free(int t);

void create();

void initialize();

void insert(int num) ;

void display() ;

void find(int num);

int findprevious(int num);

int count() ;

void del () ;

~cursorlist() ;

};

// initializes data member

cursorlist::cursorlist()

{

initialize();

}

void cursorlist::initialize()

{

for(int i = 0; i<MAX; i++)

{

cursorspace[i].data = NULL;

cursorspace[i].next = i+1;

}

cursorspace[MAX-1].next = NULL;

p = NULL;

}

int cursorlist::alloc()

{

int temp = cursorspace[0].next;

cursorspace[0].next = cursorspace[temp].next;

return temp;

}

void cursorlist::free(int t)

{

cursorspace[t].next = cursorspace[0].next;

cursorspace[0].next = t;

cursorspace[t].data = NULL;

}

// adds a new node at the beginning of the linked list

void cursorlist::insert(int num)

{

if(p == NULL)

{

p = alloc();

cursorspace[p].next = 0;

cursorspace[p].data = num;

}

else

{

int pos = p;

int tmp = alloc();

while(cursorspace[pos].next != 0)

pos = cursorspace[pos].next;

cursorspace[tmp].data = num;

cursorspace[tmp].next = cursorspace[pos].next;

cursorspace[pos].next = tmp;

}

// counts the number of nodes present in the linked list

int cursorlist :: count( )

{

if(p==NULL)

return 0;

int c = 1;

int pos = p;

while(cursorspace[pos].next != 0)

{

c++;

// traverse the entire linked list

pos = cursorspace[pos].next;

}

return c ;

}

// displays the contents of the linked list

void cursorlist::display()

{

int pos = p;

while(pos != 0)

{

cout << cursorspace[pos].data << " " ;

// traverse the entire linked list

pos = cursorspace[pos].next;

}

// deletes the specified node from the linked list

void cursorlist::del()

{

int cnt = count();

if(cnt == 0)

{

cout << "\n\nThe List is empty...";

return;

}

int num;

cout << "\n\nEnter the number to be deleted : ";

cin >> num;

if(cnt == 1 && cursorspace[p].data == num)

{

initialize();

return;

}

int temp = findprevious(num);

if(temp == 0) // The Head node - so no previous node

{

int t = cursorspace[p].next;

free(p);

p = t;

return;

}

int pos = temp;

if(cursorspace[pos].next != 0)

{

int t = cursorspace[pos].next;

cursorspace[pos].next = cursorspace[t].next;

free(t);

}

else

cout << "\n\nElement " << num << " not found" ;

}

// Searches for the element

int cursorlist::findprevious(int num)

{

int temp = p;

// if(temp == 0 && cursorspace[p].data == num) //head node

// return 0;

while ( temp != 0)

{

int t = cursorspace[temp].next;

if(cursorspace[t].data != num)

temp = cursorspace[temp].next ;

else

break;

}

return temp;

}

// Searches for the element

void cursorlist::find(int num)

{

int temp = p;

int c = 1;

// traverse the entire linked list

while ( temp != 0 && cursorspace[temp].data != num)

{

temp = cursorspace[temp].next ;

c++;

}

if(temp != NULL)

cout << "\n\nThe number " << num << " is found at position " << c;

else

cout << "\n\nThe number " << num << " is not found in the list";

}

// deallocates memory

cursorlist :: ~cursorlist( )

{

for(int i=0; i<MAX; i++)

{

cursorspace[i].data = NULL;

cursorspace[i].next = i+1;

}

free(p);

}

void main( )

{

cursorlist l ;

int ch, ch1, loc, num, numtot, ctr;

{ clrscr();

cout << "\n\tList ADT using Linked List";

cout << "\n\t--------------------------";

cout << "\n\n1. Create";

cout << "\n\n2. Insert";

cout << "\n\n3. Delete";

cout << "\n\n4. Find";

cout << "\n\n5. Count";

cout << "\n\n6. Display";

cout << "\n\n7. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

cout << "\n\nEnter the number of elements to be added : ";

cin >> numtot;

ctr = 0;

cout << "\n\nEnter the numbers...\n";

while (ctr < numtot)

{

cin >> num;

l.insert(num);

ctr++;

}

l.display();

break;

case 2:

l.display();

cout << "\n\nEnter the number : ";

cin >> num;

l.insert(num);

l.display();

break;

case 3:

l.display();

l.del();

l.display();

break;

case 4:

l.display();

cout << "\n\nEnter the number to be found : ";

cin >> num;

l.find(num);

break;

case 5:

l.display();

numtot = l.count();

cout << "\n\nThe number of elements is " << numtot;

break;

case 6:

l.display();

break;

default:

break;

}

getch();

}while(ch<7);

}

OUTPUT:

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 1

Enter the number of elements to be added : 3

Enter the numbers...

1 2 3

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 2

1 2 3

Enter the number : 4

1 2 3 4

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 3

1 2 3 4

Enter the number to be deleted : 2

1 3 4

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 3

1 3 4

Enter the number to be found : 4

The number 4 is found at position 3

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 5

1 3 4

The number of elements is 3

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice :

1 3 4

List ADT using Linked List

----------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 7

RESULT:

Thus the C++ Program for the List ADT using Cursors was Compiled and Executed Successfully.

Ex No 8)

Date:

STACK ADT USING ARRAYS

AIM:

To write a C++ Program for processing a Stack ADT using Arrays.

ALGORITHM :

MAX = 10, maximum number of elements in the array
If the option is Create, then Read the number of elements, n and pass ‘n’ as a parameter to the member function create

begin

i = 0

Repeat until i < n

begin

Read num

Call push(num)

i = i + 1

end

If the option is Push, Read the element, num and pass the num as parameter to the member function push

begin

if ( top == MAX - 1 ) then

begin

Display Stack is full

return

end

top = top + 1

arr[top] = item

end

If the option is pop then return the data popped

begin

if ( top == -1 ) then

begin

Display Stack is empty

return NULL

end

data = arr[top]

top = top - 1

return data

end

If the option is display then

begin

if(top != -1)

begin

i=top

Repeat until i >= 0

begin

Display arr[i]

i = i -1

end

else

Display Stack is empty

end

If the option is Exit, quit the program.

PROGRAM:

// Program implements array as a stack

#include <conio.h>

#include <iostream.h>

const int MAX = 10 ;

class stack

{

private :

int arr[MAX] ;

int top ;

public :

stack( ) ;

void push ( int item ) ;

int pop( ) ;

void display();

} ;

// initializes data member

stack :: stack( )

{

top = -1 ;

}

// adds an element to the stack

void stack :: push ( int item )

{

if ( top == MAX - 1 )

{

cout << endl << "Stack is full" ;

return ;

}

top++ ;

arr[top] = item ;

}

// removes an element from the stack

int stack :: pop( )

{

if ( top == -1 )

{

cout << endl << "Stack is empty" ;

return NULL ;

}

int data = arr[top] ;

top-- ;

return data ;

}

void stack :: display()

{

if(top != -1)

{

cout << "\n\nStack Elements...\n\n";

for(int i=top; i >= 0; i--)

cout << " " << arr[i] << "\n";

}

else

cout << endl << "\nStack is empty\n" ;

}

void main( )

{

stack s ;

int ch, num, numtot, ctr;

{

clrscr();

cout << "\n\tStack ADT using Array";

cout << "\n\t---------------------";

cout << "\n\n1. Create";

cout << "\n\n2. Push";

cout << "\n\n3. Pop";

cout << "\n\n4. Display";

cout << "\n\n5. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

cout << "\n\nEnter the number of elements to be added : ";

cin >> numtot;

ctr = 0;

cout << "\n\nEnter the numbers...\n";

while (ctr < numtot)

{

cin >> num;

s.push(num);

ctr++;

}

s.display();

break;

case 2:

s.display();

cout << "\n\nEnter the number : ";

cin >> num;

s.push(num);

s.display();

break;

case 3:

s.display();

num = s.pop();

cout << "Item Popped - " << num << "\n";

s.display();

break;

case 4:

s.display();

break;

default:

break;

}

getch();

}while(ch < 5);

}
OUTPUT:

Stack ADT using Array

-----------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 1

Enter the number of elements to be added : 5

Enter the numbers...

1 3 5 7 9

Stack Elements...

Stack ADT using Array

-----------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 2

Stack Elements...

Enter the number : 2

Stack Elements...

Stack ADT using Array

-----------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 2

Stack Elements...

Enter the number : 8

Stack Elements...

Stack ADT using Array

-----------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 3

Stack Elements...

Item Popped - 8

Stack Elements...

Stack ADT using Array

-----------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 5

Stack Elements...

Stack ADT using Array

-----------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 5

RESULT:

Thus the C++ Program for the Stack ADT using Arrays was Compiled and Executed Successfully.

Ex No 9)

Date:

STACK ADT USING LINKED LISTS

AIM:

To write a C++ Program for processing a Stack ADT using Linked Lists.

ALGORITHM :

Create a node with a data field and pointer next pointing to the node data type
If the option is Create, then Read the number of elements, n and pass ‘n’ as a parameter to the member function create

begin

i = 0

Repeat until i < n

begin

Read num

Call push(num)

i = i + 1

end

If the option is Push, Read the element, num and pass the num as parameter to the member function push

begin

if ( temp == NULL ) then

begin

Display Stack is full

return

end

temp -> data = item

temp -> link = top

top = temp

end

If the option is pop then return the data popped

begin

if ( top == -1 ) then

begin

Display Stack is empty

return NULL

end

node *temp

temp = top

item = temp -> data

top = top -> link

delete temp

return item

end

If the option is display then

begin

if(top != -1)

begin

node *temp, *p

p = top

Repeat while ( p != NULL )

begin

Display p->data

p = p -> link

end

else

Display Stack is empty

end

If the option is Exit, quit the program.

PROGRAM:

// Program implements linked list as a stack

#include <conio.h>

#include <iostream.h>

class stack

{

private :

// structure containing data part and linkpart

struct node

{

int data ;

node *link ;

} *top ;

public :

stack( ) ;

void push ( int item ) ;

int pop( ) ;

void display();

~stack( ) ;

} ;

// initializes data member

stack :: stack( )

{

top = NULL ;

}

// adds a new node to the stack as linked list

void stack :: push ( int item )

{

node *temp ;

temp = new node ;

if ( temp == NULL )

cout << endl << "Stack is full" ;

temp -> data = item ;

temp -> link = top ;

top = temp ;

}

// pops an element from the stack

int stack :: pop( )

{

if ( top == NULL )

{

cout << endl << "Stack is empty" ;

return NULL ;

}

node *temp ;

int item ;

temp = top ;

item = temp -> data ;

top = top -> link ;

delete temp ;

return item ;

}

void stack :: display()

{

if ( top == NULL )

return ;

cout << "\n\nStack Elements...\n\n";

node *temp, *p;

p = top;

while ( p != NULL )

{

cout << p->data << "\n";

p = p -> link ;

}

// deallocates memory

stack :: ~stack( )

{

if ( top == NULL )

return ;

node *temp ;

while ( top != NULL )

{

temp = top ;

top = top -> link ;

delete temp ;

}

void main( )

{

stack s ;

int ch, num, numtot, ctr;

{

clrscr();

cout << "\n\tStack ADT using Linked List";

cout << "\n\t---------------------------";

cout << "\n\n1. Create";

cout << "\n\n2. Push";

cout << "\n\n3. Pop";

cout << "\n\n4. Display";

cout << "\n\n5. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

cout << "\n\nEnter the number of elements to be added : ";

cin >> numtot;

ctr = 0;

cout << "\n\nEnter the numbers...\n";

while (ctr < numtot)

{

cin >> num;

s.push(num);

ctr++;

}

s.display();

break;

case 2:

s.display();

cout << "\n\nEnter the number : ";

cin >> num;

s.push(num);

s.display();

break;

case 3:

s.display();

num = s.pop();

cout << "Item Popped - " << num << "\n";

s.display();

break;

case 4:

s.display();

break;

default:

break;

}

getch();

}while(ch < 5);

}

OUTPUT:

Stack ADT using Linked List

------------------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 1

Enter the number of elements to be added : 3

Enter the numbers...

23 56 89

Stack Elements...

Stack ADT using Linked List

------------------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 2

Stack Elements...

Enter the number : 44

Stack Elements...

Stack ADT using Linked List

------------------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 2

Stack Elements...

Enter the number : 80

Stack Elements...

Stack ADT using Linked List

------------------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 3

Stack Elements...

Item Popped - 80

Stack Elements...

Stack ADT using Linked List

------------------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 4

Stack Elements...

Stack ADT using Linked List

------------------------------------

1. Create

2. Push

3. Pop

4. Display

5. Exit

Enter your choice : 5

RESULT:

Thus the C++ Program for the Stack ADT using Linked List was Compiled and Executed Successfully.

Ex No 10)

Date:

STACK APPLICATION

BALANCING PARANTHESIS

AIM:

To write a C++ Program for Balancing Paranthesis in an expression using Stack ADT.

ALGORITHM :

Read the expression into an array
Make an empty stack
Read characters until end of file
If the character is an opening symbol, push it onto the stack.
If it is a closing symbol, then if the stack is empty report an error.
Otherwise pop the stack.
If the symbol popped is not the corresponding opening symbol, then report an error.
At the end of file, if the stack is not empty, report an error.
Otherwise, report that the xpression is well balanced.

PROGRAM :

STACKBAL.H

// Program implements linked list as a stack

#include <conio.h>

#include <iostream.h>

const int MAX = 50;

class stack

{

private :

// structure containing data part and linkpart

struct node

{

char data ;

node *link ;

} *top ;

public :

stack( ) ;

void push ( char item ) ;

char pop( ) ;

char peek( ) ;

int Isempty( ) ;

~stack( ) ;

} ;

// initializes data member

stack :: stack( )

{

top = NULL ;

}

// adds a new node to the stack as linked list

void stack :: push ( char item )

{

node *temp ;

temp = new node ;

if ( temp == NULL )

cout << endl << "Stack is full" ;

temp -> data = item ;

temp -> link = top ;

top = temp ;

}

// pops an element from the stack

char stack :: pop( )

{

if ( top == NULL )

return NULL ;

node *temp ;

char item ;

temp = top ;

item = temp -> data ;

top = top -> link ;

delete temp ;

return item ;

}

// pops an element from the stack

char stack :: peek( )

{

if ( top == NULL )

return NULL ;

char item ;

item = top -> data ;

return item ;

}

// pops an element from the stack

int stack :: Isempty( )

{

if ( top == NULL )

return 1 ;

else

return 0;

}

// deallocates memory

stack :: ~stack( )

{

if ( top == NULL )

return ;

node *temp ;

while ( top != NULL )

{

temp = top ;

top = top -> link ;

delete temp ;

}

BALPARAN.CPP

#include<iostream.h>

#include<conio.h>

#include<malloc.h>

#include<string.h>

#include"stackbal.h"

// Creating a NODE Structure

class balance:public stack

{

public:

int bal(char str[]);

};

// Balance parenthesis

int balance::bal(char str[])

{

int i = 0;

int count = 0;

int len = strlen(str);

while (i < len)

{

if (str[i] == ' ')

{

i++;

continue;

}

if ( str[i] == '(' || str[i] == '{' || str[i] == '[' )

{

push(str[i]);

count++;

}

if ( str[i] == ')' || str[i] == '}' || str[i] == ']' )

{

if ( Isempty() == 1 )

{

cout << " parenthesis " << str[i] << " at position "

<< i << " is unbalanced " << endl;

return -1;

}

else

{

if ( (str[i] == ')' && peek() == '(') ||

(str[i] == '}' && peek() == '{') ||

(str[i] == ']' && peek() == '['))

{

pop();

count--;

}

else

{

cout << " \n\nParenthesis mismatch";

return -1;

}

i++;

}

if(count == 0)

return 1;

else

return -1;

}

// Main function

void main()

{

balance b;

char sExpr[MAX];

cout << "\n\nEnter the expression to be balanced : ";

cin >> sExpr;

int result = b.bal(sExpr);

if(result == 1)

cout << "\n\nExpression " << sExpr << " is balanced..";

else

cout << "\n\nExpression " << sExpr << " is not balanced...";

getch();

}

OUTPUT :

Enter the expression to be balanced : (a+b)*{e+g}

Expression (a+b)*{e+g} is balanced..

Enter the expression to be balanced : (a+b)*({a+f}/{a*g)

Parenthesis mismatch

Expression (a+b)*({a+f}/{a*g) is not balanced...

RESULT:

Thus the C++ Program for Balancing Paranthesis in an expression using Stack ADT was Compiled and Executed Successfully.

Ex No 11)

Date:

STACK APPLICATION

INFIX TO POSTFIX

AIM:

To write a C++ Program for Coverting an expression from infix to postfix using Stack ADT.

ALGORITHM :

Read the expression into an array
Make an empty stack
When an operand is read it is immediately placed onto the output.
The operators are pushed onto the stack.
When a left paranthesis is encountered it is pushed onto the stack
When a right paranthesis is encountered pop the stack, writing symbols until we encounter a corresponding left paranthesis, which is popped not output
If we see any other symbol ‘+’, ‘*’, ‘(‘, then we pop entries from the stack until we find an entry of lower priority.
A left paranthesis is removed from the stack only when a right paranthesis is encountered.
When the popping is done, the operator is pushed onto the stack
Finally, if we read the end of input, we pop the stack until it is empty, writing symbols onto the output.

PROGRAM :

STACKARY.H

// The Stack Class

const int MAX = 50;

class stack

{

public :

char stack[MAX] ;

int top ;

public :

stack( ) ;

void push ( char c ) ;

char pop( ) ;

} ;

// initializes data member

stack :: stack( )

{

top = -1 ;

strcpy ( stack, "" ) ;

}

// adds an element to the stack

void stack :: push ( char c )

{

top++ ;

stack[top] = c;

}

// removes an element from the stack

char stack :: pop( )

{

char data = stack[top] ;

top-- ;

return data ;

}

INFXPSFX.CPP

// Program to convert an Infix form to Postfix form

#include <conio.h>

#include <iostream.h>

#include <string.h>

#include <ctype.h>

#include "stackary.h"

class infix:public stack

{

public :

char target[MAX] ;

char *s, *t ;

public :

infix( ) ;

void setexpr ( char *str ) ;

void convert( ) ;

int priority ( char c ) ;

void show( ) ;

} ;

// initializes data members

infix::infix( )

{

top = -1 ;

strcpy ( target, "" ) ;

t = target ;

s = "" ;

}

// sets s to point to given expr.

void infix::setexpr ( char *str )

{

s = str ;

}

// converts the given expr. from infix to postfix form

void infix::convert( )

{

while ( *s )

{

if ( *s == ' ' || *s == '\t' )

{

s++ ;

continue ;

}

if ( isdigit ( *s ) || isalpha ( *s ) )

{

while ( isdigit ( *s ) || isalpha ( *s ) )

{

*t = *s ;

s++ ;

t++ ;

}

if ( *s == '(' )

{

push ( *s ) ;

s++ ;

}

char opr ;

if ( *s == '*' || *s == '+' || *s == '/' || *s == '%' || *s == '-' || *s == '$' )

{

if ( top != -1 )

{

opr = pop( ) ;

while ( priority ( opr ) >= priority ( *s ) )

{

*t = opr ;

t++ ;

opr = pop( ) ;

}

push ( opr ) ;

push ( *s ) ;

}

else

push ( *s ) ;

s++ ;

}

if ( *s == ')' )

{

opr = pop( ) ;

while ( ( opr ) != '(' )

{

*t = opr ;

t++ ;

opr = pop( ) ;

}

s++ ;

}

while ( top != -1 )

{

char opr = pop( ) ;

*t = opr ;

t++ ;

}

*t = '\0' ;

}

// returns the priority of an operator

int infix :: priority ( char c )

{

if ( c == '$' )

return 3 ;

if ( c == '*' || c == '/' || c == '%' )

return 2 ;

else

{

if ( c == '+' || c == '-' )

return 1 ;

else

return 0 ;

}

// displays the postfix form of given expr.

void infix :: show( )

{

cout << target ;

}

void main( )

{

clrscr();

char expr[MAX] ;

infix q ;

cout << "\nEnter an expression in infix form: " ;

cin.getline ( expr, MAX ) ;

q.setexpr ( expr ) ;

q.convert( ) ;

cout << "\nThe postfix expression is: " ;

q.show( ) ;

getch();

}

OUTPUT :

Enter an expression in infix form: a+b*c+(d*e+f)*g

The postfix expression is: abc*+de*f+g*+

RESULT:

Thus the C++ Program for coverting an expression given in Infix to Postfix using Stack ADT was Compiled and Executed Successfully.

Ex No 12)

Date:

STACK APPLICATION

EVALUVATION OF EXPRESSIONS

AIM:

To write a C++ Program for Evaluvating an expression using Stack ADT.

ALGORITHM :

Read an expression in postfix form into an array
If white spaces encountered skip
If digit is encountered push it onto the stack
Otherwise it is an operator, hence pop the operands and perform the operationusing the operator
Push the result onto the stack
The final result is in the stack, hence after processing the expression, pop the stack and print the contents popped.

PROGRAM :

STCKEXPR.H

// The Stack Class

const int MAX = 50;

class stack

{

public :

char stack[MAX] ;

int top ;

public :

stack( ) ;

void push ( int item ) ;

int pop( ) ;

void display();

} ;

// initializes data member

stack :: stack( )

{

top = -1 ;

// strcpy ( stack, "" ) ;

}

// adds an element to the stack

void stack :: push ( int item )

{

top++ ;

stack[top] = item;

}

// removes an element from the stack

int stack :: pop( )

{

int data = stack[top] ;

top-- ;

return data ;

}

EXPREVAL.CPP

// Program to evaluate an epression entered in postfix form

#include <conio.h>

#include <iostream.h>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include "stckexpr.h"

class postfix:public stack

{

private :

int stack[MAX] ;

int top, nn ;

char *s ;

public :

postfix( ) ;

void setexpr ( char *str ) ;

void calculate( ) ;

void show( ) ;

} ;

// initializes data members

postfix :: postfix( )

{

top = -1 ;

}

// sets s to point to the given expr.

void postfix :: setexpr ( char *str )

{

s = str ;

}

// evaluates the postfix expression

void postfix :: calculate( )

{

int n1, n2, n3 ;

while ( *s )

{

/* skip whitespace, if any */

if ( *s == ' ' || *s == '\t' )

{

s++ ;

continue ;

}

/* if digit is encountered */

if ( isdigit ( *s ) )

{

nn = *s - '0' ;

push ( nn ) ;

}

else

{

/* if operator is encountered */

n1 = pop( ) ;

n2 = pop( ) ;

switch ( *s )

{

case '+' :

n3 = n2 + n1 ;

break ;

case '-' :

n3 = n2 - n1 ;

break ;

case '/' :

n3 = n2 / n1 ;

break ;

case '*' :

n3 = n2 * n1 ;

break ;

case '%' :

n3 = n2 % n1 ;

break ;

case '$' :

n3 = pow ( n2 , n1 ) ;

break ;

default :

cout << "Unknown operator" ;

exit ( 1 ) ;

}

push ( n3 ) ;

}

s++ ;

}

// displays the result

void postfix :: show( )

{

nn = pop ( ) ;

cout << "Result is: " << nn ;

}

void main( )

{

char expr[MAX] ;

clrscr();

cout << "\nEnter postfix expression to be evaluated : " ;

cin.getline ( expr, MAX ) ;

postfix q ;

q.setexpr ( expr ) ;

q.calculate( ) ;

q.show( ) ;

getch();

}

OUTPUT :

Enter postfix expression to be evaluated : 345*28*++

Result is: 39

RESULT:

Thus the C++ Program for Evaluvating an expression using Stack ADT was Compiled and Executed Successfully.

Ex No 13)

Date:

QUEUE ADT USING ARRAYS

AIM:

To write a C++ Program for processing a Queue ADT using Arrays.

ALGORITHM :

MAX = 10, maximum number of elements in the array
If the option is Create, then Read the number of elements, n and pass ‘n’ as a parameter to the member function create

begin

i = 0

Repeat until i < n

begin

Read num

Call addq(num)

i = i + 1

end

If the option is Add, Read the element, num and pass the num as parameter to the member function addq

begin

if(rear == MAX - 1)

begin

Display Queue is full

return ;

end

rear = rear + 1 ;

arr[rear] = item ;

if ( front == -1 )

front = 0 ;

end

If the option is delete then Read the element, num and pass the num as parameter to the member function delq

begin

if ( front == -1 )

begin

Display Queue is Empty

return NULL ;

end

data = arr[front] ;

arr[front] = 0 ;

if ( front == rear )

front = rear = -1 ;

else

front = front + 1

return data ;

end

If the option is display then

begin

i=0

Repeat until i < MAX and arr[i] != 0

begin

Display arr[i]

i = i -1

end

If the option is find then Read the element, num and pass the num as parameter to the member function find

begin

i=0

Repeat until i < MAX

begin

if arr[i] = num then

return i

end

return -1

end

If the option is Exit, quit the program.

PROGRAM:

// Program that implements queue as an array

#include <conio.h>

#include <iostream.h>

const int MAX = 10 ;

class queue

{

private :

int arr[MAX] ;

int front, rear ;

public :

queue( ) ;

void create(int numtot);

void addq (int item) ;

int delq( ) ;

int find(int item);

void display();

int count();

} ;

// initialises data members

queue::queue()

{

front = -1 ;

rear = -1 ;

for(int i=0; i < MAX; i++)

arr[i] = 0;

}

// Creates a queue of length numtot

void queue::create(int numtot)

{

int num;

for(int i = 0; i < numtot; i++)

{

cin >> num;

addq(num);

}

// adds an element to the queue

void queue:: addq (int item)

{

if(rear == MAX - 1)

{

cout << "\nQueue is full" ;

return ;

}

rear++ ;

arr[rear] = item ;

if ( front == -1 )

front = 0 ;

}

// removes an element from the queue

int queue::delq()

{

int data ;

if ( front == -1 )

{

cout << "\nQueue is Empty" ;

return NULL ;

}

data = arr[front] ;

arr[front] = 0 ;

if ( front == rear )

front = rear = -1 ;

else

front++ ;

return data ;

}

// searches queue for a given element num

int queue::find(int num)

{

// Traverse the array

for ( int i = 0 ; i < MAX ; i++ )

{

if ( arr[i] == num )

return i;

}

return -1;

}

// Counts the number of elements inserted into the queue

int queue::count()

{

return front - rear + 1;

}

// displays the contents of a queue

void queue::display()

{

cout<< endl ;

// traverse the entire array

for ( int i = 0 ; i < MAX; i++ )

{

if( arr[i] != 0)

cout << " " << arr[i] ;

}

void main()

{

queue q;

int ch, loc, num, ntot;

{

clrscr();

cout << "\n\tQueue ADT using Arrays";

cout << "\n\t----------------------";

cout << "\n\n1. Create";

cout << "\n\n2. Insert";

cout << "\n\n3. Delete";

cout << "\n\n4. Find";

cout << "\n\n5. Count";

cout << "\n\n6. Display";

cout << "\n\n7. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

cout << "\n\nEnter the number of elements to be added : ";

cin >> ntot;

cout << "\n\nEnter the numbers...\n";

q.create(ntot);

q.display();

break;

case 2:

q.display();

cout << "\n\nEnter the number : ";

cin >> num;

q.addq(num);

q.display();

break;

case 3:

q.display();

num = q.delq();

if(num != NULL)

cout << "\n\nThe element " << num << " is deleted" ;

q.display();

break;

case 4:

q.display();

cout << "\n\nEnter the number to be found : ";

cin >> num;

loc = q.find(num);

if(loc == -1)

cout << "\n\nThe element " << num

<< " is not present in the queue" ;

else

cout << "\n\nThe element " << num

<< " is present at position "<< ( loc + 1 );

break;

case 5:

q.display();

ntot = q.count();

cout << "\n\nThe number of elements is " << ntot;

break;

case 6:

q.display();

break;

default:

break;

}

getch();

}while(ch<7);

}OUTPUT:

Queue ADT using Arrays

-------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 1

Enter the number of elements to be added : 5

Enter the numbers...

1 3 5 6 9

Queue ADT using Arrays

-------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 2

1 3 5 6 9

Enter the number : 10

1 3 5 6 9 10

Queue ADT using Arrays

-------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 3

1 3 5 6 9 10

The element 1 is deleted

3 5 6 9 10

Queue ADT using Arrays

-------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 4

3 5 6 9 10

Enter the number to be found : 3

The element 3 is present at position 2

Queue ADT using Arrays

-------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 5

3 5 6 9 10

The number of elements is 5

Queue ADT using Arrays

-------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 6

3 5 6 9 10

Queue ADT using Arrays

-------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 7

RESULT:

Thus the C++ Program for the Queue ADT using Arrays was Compiled and Executed Successfully.

Ex No 14)

Date:

QUEUE ADT USING LINKED LISTS

AIM:

To write a C++ Program for processing a Queue ADT using Linked Lists.

ALGORITHM :

Create a node with a data field and pointer next pointing to the node data type
If the option is Create, then Read the number of elements, n and pass ‘n’ as a parameter to the member function create

begin

i = 0

Repeat until i < n

begin

Read num

Call addq(num)

i = i + 1

end

If the option is Add, Read the element, num and pass the num as parameter to the member function addq

begin

temp = create a new node ;

if ( temp == NULL )

cout << "\nQueue is full" ;

temp -> data = item ;

temp -> link = NULL ;

if ( front == NULL )

begin

rear = front = temp ;

return ;

end

rear -> link = temp ;

rear = rear -> link ;

end

If the option is delete then call the member function delq

begin

if ( front == NULL )

begin

cout << "\nQueue is empty" ;

return NULL ;

end

item = front -> data ;

temp = front ;

front = front -> link ;

delete temp ;

return item ;

end

If the option is display then call the member function display

begin

temp = front ;

Repeat while ( temp != NULL )

begin

cout << temp -> data << " " ;

temp = temp -> link ;

end

end

If the option is find then Read the element, num and pass the num as parameter to the member function find

begin

q = front ;

pos = 1;

Repeat while ( q != NULL and q->data != num)

begin

q = q->link ;

pos++;

end

if(q != NULL) then

Display The number is found at position, pos;

else

Display The number is not found in the list;

end

If the option is Exit, quit the program.

PROGRAM:

// Program that implements queue as a linked list

#include <conio.h>

#include <iostream.h>

class queue

{

private :

struct node

{

int data ;

node *link ;

} *front, *rear ;

public :

queue( ) ;

void create(int numtot);

void addq ( int item ) ;

int delq( ) ;

void find(int item);

void display();

int count();

~queue( ) ;

} ;

// initialises data member

queue :: queue( )

{

front = rear = NULL ;

}

// Creates a queue of length numtot

void queue::create(int numtot)

{

int num;

for(int i = 0; i < numtot; i++)

{

cin >> num;

addq(num);

}

// adds an element to the queue

void queue :: addq ( int item )

{

node *temp ;

temp = new node ;

if ( temp == NULL )

cout << "\nQueue is full" ;

temp -> data = item ;

temp -> link = NULL ;

if ( front == NULL )

{

rear = front = temp ;

return ;

}

rear -> link = temp ;

rear = rear -> link ;

}

// removes an element from the queue

int queue :: delq( )

{

if ( front == NULL )

{

cout << "\nQueue is empty" ;

return NULL ;

}

node *temp ;

int item ;

item = front -> data ;

temp = front ;

front = front -> link ;

delete temp ;

return item ;

}

// Searches for the element

void queue::find(int num)

{

node *q = front ;

// traverse the linked list

int pos = 1;

while ( q != NULL && q->data != num)

{

q = q->link ;

pos++;

}

if(q != NULL)

cout << "\n\nThe number " << num << " is found at position " << pos;

else

cout << "\n\nThe number " << num << " is not found in the list";

}

// displays the contents of the linked list

void queue::display()

{

node *temp = front ;

cout << endl ;

// traverse the entire linked list

while ( temp != NULL )

{

cout << temp -> data << " " ;

temp = temp -> link ;

}

// counts the number of nodes present in the linked list

int queue::count( )

{

node *temp = front ;

int c = 0 ;

// traverse the entire linked list

while ( temp != NULL )

{

temp = temp -> link ;

c++ ;

}

return c ;

}

// deallocates memory

queue :: ~queue( )

{

if ( front == NULL )

return ;

node *temp ;

while ( front != NULL )

{

temp = front ;

front = front -> link ;

delete temp ;

}

void main( )

{

queue q ;

int ch, loc, num, ntot;

{

clrscr();

cout << "\n\tQueue ADT using Linked List";

cout << "\n\t---------------------------";

cout << "\n\n1. Create";

cout << "\n\n2. Insert";

cout << "\n\n3. Delete";

cout << "\n\n4. Find";

cout << "\n\n5. Count";

cout << "\n\n6. Display";

cout << "\n\n7. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

cout << "\n\nEnter the number of elements to be added : ";

cin >> ntot;

cout << "\n\nEnter the numbers...\n";

q.create(ntot);

q.display();

break;

case 2:

q.display();

cout << "\n\nEnter the number : ";

cin >> num;

q.addq(num);

q.display();

break;

case 3:

q.display();

num = q.delq();

if(num != NULL)

cout << "\n\nThe element " << num << " is deleted" ;

q.display();

break;

case 4:

q.display();

cout << "\n\nEnter the number to be found : ";

cin >> num;

q.find(num);

break;

case 5:

q.display();

ntot = q.count();

cout << "\n\nThe number of elements is " << ntot;

break;

case 6:

q.display();

break;

default:

break;

}

getch();

}while(ch<7);

}

OUTPUT:

Queue ADT using Linked List

-------------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 1

Enter the number of elements to be added : 5

Enter the numbers...

82 45 67 23 79

Queue ADT using Linked List

-------------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 2

82 45 67 23 79

Enter the number : 33

82 45 67 23 79 33

Queue ADT using Linked List

-------------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 3

82 45 67 23 79 33

The element 82 is deleted

45 67 23 79 33

Queue ADT using Linked List

-------------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 4

45 67 23 79 33

Enter the number to be found : 33

The number 33 is found at position 5

Queue ADT using Linked List

-------------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 5

45 67 23 79 33

The number of elements is 5

Queue ADT using Linked List

-------------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 6

45 67 23 79 33

Queue ADT using Linked List

-------------------------------------

1. Create

2. Insert

3. Delete

4. Find

5. Count

6. Display

7. Exit

Enter your choice : 7

RESULT:

Thus the C++ Program for the Queue ADT using Linked List was Compiled and Executed Successfully.

Ex No 15)

Date:

BINARY SEARCH TREE

AIM:

To write a C++ Program for Balancing Paranthesis in an expression using Stack ADT.

ALGORITHM :

Create a node with a data field and pointer left and right pointing to the node data type
If the option is Insert, then Read the number of elements, n and call the member function Insert with the parameters btreenode and n

begin

if ( sr == NULL ) then

begin

sr = create a new btreenode

if(root == NULL)

root = sr

sr->leftchild = NULL

sr->data = num

sr->rightchild = NULL

end

else

begin

if ( num < sr->data )

sr->leftchild=insert(sr->leftchild, num) ;

else

sr->rightchild=insert(sr->rightchild, num ) ;

end

return sr;

end

If the option is Delete then Read the element to be deleted, num and pass it as parameter to the member function del

begin

if ( sr == NULL )

begin

return NULL;

end

if(num < sr->data) then

sr->leftchild = rem(sr->leftchild, num;

else if(num > sr->data)

sr->rightchild = rem(sr->rightchild, num)

else if(sr->leftchild && sr->rightchild)

begin

x = FindMin(sr->rightchild)

sr->data = x->data

sr->rightchild = rem(sr->rightchild, sr->data)

end

else

begin

x = sr

if(sr->leftchild == NULL)

sr = sr->rightchild

else if(sr->rightchild == NULL)

sr = sr->leftchild

if(x==root)

root = NULL;

delete x

end

If the option is find then Read the element to be found, num and pass it as parameter to the member function find

begin

if ( sr == NULL )

return NULL

if( num < sr->data)

return Find(sr->leftchild, num)

else if(num > sr->data)

return Find(sr->rightchild, num)

else

return sr;

end

If the option is Minimum/Maximum then call the member function FindMin/FindMax

Procedure FindMin

begin

if ( sr == NULL )

begin

Display Tree is empty

return NULL

end

else if(sr->leftchild == NULL)

return s

else

return FindMin(sr->leftchild)

end

Procedure FindMax

begin

if ( sr == NULL )

begin

Display Tree is empty

return NULL

end

else if(sr->rightchild == NULL)

return s

else

return FindMin(sr->rightchild)

end

If the option is traverse then call the member functions inorder, postorder, preorder

Procedure preorder

begin

if ( sr != NULL )

begin

Display sr -> data

preorder ( sr -> leftchild )

preorder ( sr -> rightchild )

end

else

return

end

Procedure inorder

begin

if ( sr != NULL )

begin

inorder ( sr -> leftchild )

Display sr -> data

inorder ( sr -> rightchild )

end

else

return

end

Procedure postorder

begin

if ( sr != NULL )

begin

postorder ( sr -> leftchild )

postorder ( sr -> rightchild )

Display sr -> data

end

else

return

end

If the option is Exit, quit the program.

PROGRAM :

// Program for Binary Tree Operations

// Program with inorder, preorder and postorder functions

#include <iostream.h>

#include <conio.h>

struct btreenode

{

btreenode *leftchild ;

int data ;

btreenode *rightchild ;

}*root;

class btree

{

public :

btree( ) ;

void buildtree ( int num ) ;

btreenode* insert ( btreenode *sr, int num ) ;

void traverse( ) ;

void inorder ( btreenode *sr ) ;

void preorder ( btreenode *sr ) ;

void postorder ( btreenode *sr ) ;

void levelorder ( btreenode *sr );

void del ( btreenode *sr ) ;

btreenode* FindMin ( btreenode *sr ) ;

btreenode* FindMax ( btreenode *sr ) ;

btreenode* Find ( btreenode *sr, int num ) ;

void remove ( int num ) ;

btreenode* rem ( btreenode *sr, int num) ;

~btree( ) ;

};

// initialises data member

btree :: btree( )

{

root = NULL ;

}

// build tree by calling insert( )

void btree :: buildtree ( int num )

{

insert(root, num ) ;

}

// inserts a new node in a binary search tree

btreenode* btree :: insert ( btreenode *sr, int num )

{

if ( sr == NULL )

{

sr = new btreenode ;

if(root == NULL)

root = sr;

sr->leftchild = NULL ;

sr->data = num ;

sr->rightchild = NULL ;

}

else // search the node to which new node will be attached

{

// if new data is less, traverse to left

if ( num < sr->data )

sr->leftchild=insert(sr->leftchild, num) ;

else

// else traverse to right

sr->rightchild=insert(sr->rightchild, num ) ;

}

return sr;

}

// traverses btree

void btree :: traverse( )

{

cout << "\n\nIn-order Traversal: " ;

inorder ( root ) ;

cout << "\n\nPre-order Traversal: " ;

preorder ( root ) ;

cout << "\n\nPost-order Traversal: " ;

postorder ( root ) ;

}

// traverse a binary search tree in a LDR (Left-Data-Right) fashion

void btree :: inorder ( btreenode *sr )

{

if ( sr != NULL )

{

inorder ( sr -> leftchild ) ;

// print the data of the node whose

// leftchild is NULL or the path

// has already been traversed

cout << "\t" << sr -> data ;

inorder ( sr -> rightchild ) ;

}

else

return ;

}

// traverse a binary search tree in a DLR (Data-Left-right) fashion

void btree :: preorder ( btreenode *sr )

{

if ( sr != NULL )

{

// print the data of a node

cout << "\t" << sr -> data ;

// traverse till leftchild is not NULL

preorder ( sr -> leftchild ) ;

// traverse till rightchild is not NULL

preorder ( sr -> rightchild ) ;

}

else

return ;

}

// traverse a binary search tree in LRD (Left-Right-Data) fashion

void btree :: postorder ( btreenode *sr )

{

if ( sr != NULL )

{

postorder ( sr -> leftchild ) ;

postorder ( sr -> rightchild ) ;

cout << "\t" << sr -> data ;

}

else

return ;

}

// calls rem to delete node

void btree :: remove ( int num )

{

rem ( root, num ) ;

}

// deletes a node from the binary search tree

btreenode* btree :: rem ( btreenode *sr, int num )

{

btreenode *x;

// if tree is empty

if ( sr == NULL )

{

// cout << "\nTree is empty" ;

return NULL;

}

if(num < sr->data) // Traverse towards left

sr->leftchild = rem(sr->leftchild, num);

else if(num > sr->data) // Traverse towards right

sr->rightchild = rem(sr->rightchild, num);

// Found element to be deleted

else if(sr->leftchild && sr->rightchild)

{

// Replace with the smallest data

x = FindMin(sr->rightchild);

sr->data = x->data;

sr->rightchild = rem(sr->rightchild, sr->data);

}

else // One or Zero children

{

x = sr;

if(sr->leftchild == NULL)

sr = sr->rightchild;

else if(sr->rightchild == NULL)

sr = sr->leftchild;

if(x==root)

root = NULL;

delete x;

}

return sr;

}

// returns whether the node is found or not

btreenode* btree :: Find ( btreenode *sr, int num)

{

// if tree is empty

if ( sr == NULL )

return NULL;

if( num < sr->data)

return Find(sr->leftchild, num);

else if(num > sr->data)

return Find(sr->rightchild, num);

else

return sr;

}

// Finds minimum from the Tree

btreenode* btree :: FindMin( btreenode *sr)

{

// if tree is empty

if ( sr == NULL )

{

cout << "\nTree is empty" ;

return NULL;

}

else if(sr->leftchild == NULL)

return sr;

else

return FindMin(sr->leftchild);

}

// Finds maximum from the Tree

btreenode* btree :: FindMax( btreenode *sr)

{

// if tree is empty

if ( sr == NULL )

{

cout << "\nTree is empty" ;

return NULL;

}

else if(sr->rightchild == NULL)

return sr;

else

return FindMax(sr->rightchild);

}

// calls del to deallocate memory

btree :: ~btree( )

{

del ( root ) ;

}

// deletes nodes of a binary tree

void btree :: del ( btreenode *sr )

{

if ( sr != NULL )

{

del ( sr->leftchild ) ;

del ( sr->rightchild ) ;

}

delete sr ;

}

void main( )

{

btree bt ;

int numtot, num, ch;

btreenode *btn;

{

clrscr();

cout << "\n\tBINARY TREE";

cout << "\n\t-----------";

cout << "\n\n1. Insert";

cout << "\n\n2. Delete";

cout << "\n\n3. Traversal";

cout << "\n\n4. Search";

cout << "\n\n5. Find Minimum / Maximum";

cout << "\n\n6. Exit\n";

cout << "\nEnter your choice : ";

cin >> ch;

switch(ch)

{

case 1:

cout << "\n\nEnter Number of items to be inserted: " ;

cin >> numtot ;

cout << "\n\nEnter the data... " ;

for(int i=0; i< numtot; i++)

{

cin >> num ;

bt.buildtree ( num ) ;

}

break;

case 2:

bt.inorder(root);

cout << "\n\nEnter item to be deleted : ";

cin >> num ;

btn = bt.rem(root, num);

if(btn == NULL)

cout << num << " is not found in the Tree";

else

cout << num << " is found in the Tree";

bt.inorder(root);

break;

case 3:

bt.traverse();

break;

case 4:

bt.inorder(root);

cout << "\n\nEnter item to be searched : ";

cin >> num ;

btn = bt.Find(root, num);

if(btn == NULL)

cout << num << " is not found in the Tree";

else

cout << num << " is found in the Tree";

break;

case 5:

bt.inorder(root);

btn = bt.FindMin(root);

cout << "\n\nMinimum : " << btn->data;

btn = bt.FindMax(root);

cout << "\n\nMaximum : " << btn->data;

break;

default :

break;

}

getch();

}while(ch < 6);

}

OUTPUT :

BINARY TREE

---------------------

1. Insert

2. Delete

3. Traversal

4. Search

5. Find Minimum / Maximum

6. Exit

Enter your choice : 1

Enter Number of items to be inserted: 6

Enter the data...

1 3 5 7 9 11

BINARY TREE

---------------------

1. Insert

2. Delete

3. Traversal

4. Search

5. Find Minimum / Maximum

6. Exit

Enter your choice : 2

1 3 5 7 9 11

Enter item to be deleted : 11

1 3 5 7 9

BINARY TREE

---------------------

1. Insert

2. Delete

3. Traversal

4. Search

5. Find Minimum / Maximum

6. Exit

Enter your choice : 3

In-order Traversal: 1 3 5 7 9

Pre-order Traversal: 1 3 5 7 9

Post-order Traversal: 9 7 5 3 1

BINARY TREE

---------------------

1. Insert

2. Delete

3. Traversal

4. Search

5. Find Minimum / Maximum

6. Exit

Enter your choice : 4

1 3 5 7 9

Enter item to be searched : 6

6 is not found in the Tree

BINARY TREE

---------------------

1. Insert

2. Delete

3. Traversal

4. Search

5. Find Minimum / Maximum

6. Exit

Enter your choice : 5

1 3 5 7 9

Minimum : 1

Maximum : 9

BINARY TREE

---------------------

1. Insert

2. Delete

3. Traversal

4. Search

5. Find Minimum / Maximum

6. Exit

Enter your choice : 6

RESULT:

Thus the C++ Program for Balancing Paranthesis in an expression using Stack ADT was Compiled and Executed Successfully.

Ex No 16)

Date:

HEAP SORT

AIM:

To write a C++ Program for sorting a given set of numbers using Heap sort

ALGORITHM :

Read no of elements, n
Use getdata() member function to get the member values of the class.

i = 0

Repeat until i < n

begin

Read, a[i]

i = i + 1

end

Use the sort member function to sort the elements

int i,temp,c=1;

for(i=(n/2)-1;i>=0;i--)

deletemax(a,i,n);

for(i=n-1;i>=1;i--)

{

temp=a[0];

a[0]=a[i];

a[i]=temp;

deletemax(a,0,i-1);

cout<<"\nPass "<<c<<"\n";

c++;

display();

cout<<"\n";

}

Procedure deletemax

begin

Repeat while((root*2<=bottom))

begin

if(root*2==bottom) then

max=root*2

else if(a[root*2]>a[root*2+1])

max=root*2

else

max=root*2+1

if(a[root]<a[max]) then

begin

temp=a[root];

a[root]=a[max];

a[max]=temp;

root=max;

end

else

break;

end

Use display() member function to display the member values of the class.

Procedure display

begin

i = 0

Repeat until i < n

begin

Display a[i]

i = i + 1

end

Quit the program

PROGRAM :

// Program for Heap Sort

#include<iostream.h>

#include<conio.h>

class heap

{

public:

void getdata();

void deletemax(int *, int, int);

void sort();

void display();

private:

int a[50],n;

};

void heap::getdata()

{

cout<<"\nEnter the no. of elements \n";

cin>>n;

cout<<"\nEnter the elements \n";

for(int i=0;i<n;i++)

{

cin>>a[i];

}

void heap::sort()

{

int i,temp,c=1;

for(i=(n/2)-1;i>=0;i--)

deletemax(a,i,n);

for(i=n-1;i>=1;i--)

{

temp=a[0];

a[0]=a[i];

a[i]=temp;

deletemax(a,0,i-1);

cout<<"\nPass "<<c<<"\n";

c++;

display();

cout<<"\n";

}

void heap::deletemax(int a[],int root, int bottom)

{

int max,temp;

while((root*2<=bottom))

{

if(root*2==bottom)

max=root*2;

else if(a[root*2]>a[root*2+1])

max=root*2;

else

max=root*2+1;

if(a[root]<a[max])

{

temp=a[root];

a[root]=a[max];

a[max]=temp;

root=max;

}

else

break;

}

void heap::display()

{

for(int l=0;l<n;l++)

cout<<a[l]<<" ";

}

void main()

{

heap h;

clrscr();

h.getdata();

cout<<"\n\nThe given array is... \n";

h.display();

cout << "\n\nPasses of the Heap Sort\n";

h.sort();

cout<<"\n\nThe sorted array is... \n";

h.display();

getch();

}

OUTPUT :

Enter the no. of elements 6

Enter the elements

23 56 41 89 13 9

The given array is...

23 56 41 89 13 9

Passes of the Heap Sort

Pass 1

56 41 13 23 9 89

Pass 2

41 23 13 9 56 89

Pass 3

23 13 9 41 56 89

Pass 4

13 9 23 41 56 89

Pass 5

9 13 23 41 56 89

The sorted array is...

9 13 23 41 56 89

RESULT:

Thus the C++ Program for sorting a given set of numbers using Heap Sort was Compiled and Executed Successfully.

Ex No 17)

Date:

QUICK SORT

AIM:

To write a C++ Program for sorting a given set of numbers using Quick sort

ALGORITHM :

Read no of elements, n
Use getdata() member function to get the member values of the class.

i = 0

Repeat until i < n

begin

Read, a[i]

i = i + 1

end

Use the sort member function to sort the elements with the parameters, left and right position

begin

if(left < right)

{

i=left+1;

j=right;

pivot=left;

static int ctr=1;

{

while(a[pivot]>=a[i])

i++;

while(a[pivot]<a[j])

j--;

if(i<j && a[pivot]<a[i] && a[pivot]>a[j])

{

temp=a[i];

a[i]=a[j];

a[j]=temp;

cout << "\n" << ctr << "\t";

for(k=0;k<n;k++)

cout << a[k] << "\t";

cout << endl;

ctr++;

}

else

break;

} while(1);

temp=a[pivot];

a[pivot]=a[j];

a[j]=temp;

cout << "\n" << ctr << "\t";

for(k=0;k<n;k++)

cout << a[k] << "\t";

cout << endl;

ctr++;

sort(left, j-1);

sort(j+1, right);

}

return;

end

Use display() member function to display the member values of the class.

Procedure display

begin

i = 0

Repeat until i < n

begin

Display a[i]

i = i + 1

end

Quit the program

PROGRAM :

// Quick sort Program

#include <iostream.h>

#include <conio.h>

// Quick sort Class

class quicksort

{

public:

int a[50], b[50], i,j,t,temp, temp1[50];

int n;

void getdata();

void sort(int left, int right);

void display();

};

// Getting the data for the array

void quicksort::getdata()

{

cout<<"\nEnter the no. of elements \n";

cin>>n;

cout<<"\nEnter the elements \n";

for(int i=0;i<n;i++)

{

cin>>a[i];

}

// Printing the array elements in sorted order

void quicksort::display()

{

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

cout << a[i] << " ";

}

// Sorting of the Array - Quick Sort

void quicksort::sort(int left, int right)

{

int i, j, pivot, temp, k;

if(left < right)

{

i=left+1;

j=right;

pivot=left;

static int ctr=1;

{

while(a[pivot]>=a[i])

i++;

while(a[pivot]<a[j])

j--;

if(i<j && a[pivot]<a[i] && a[pivot]>a[j])

{

temp=a[i];

a[i]=a[j];

a[j]=temp;

cout << "\n" << ctr << "\t";

for(k=0;k<n;k++)

cout << a[k] << "\t";

cout << endl;

ctr++;

}

else

break;

} while(1);

temp=a[pivot];

a[pivot]=a[j];

a[j]=temp;

cout << "\n" << ctr << "\t";

for(k=0;k<n;k++)

cout << a[k] << "\t";

cout << endl;

ctr++;

sort(left, j-1);

sort(j+1, right);

}

return;

}

// The actual call in the main program

void main()

{

quicksort srt;

clrscr();

srt.getdata();

cout << "\n\nThe given Array is....";

srt.display();

cout << "\n\nPasses of the Quick Sort\n";

srt.sort(0, srt.n-1);

cout << "\n\nSorted array...\n\n";

srt.display();

getch();

}

OUTPUT :

Enter the no. of elements 6

Enter the elements

23 11 56 34 89 7

The given Array is....23 11 56 34 89 7

Passes of the Quick Sort

1 23 11 7 34 89 56

2 7 11 23 34 89 56

3 7 11 23 34 89 56

4 7 11 23 34 89 56

5 7 11 23 34 56 89

Sorted array...

7 11 23 34 56 89

RESULT:

Thus the C++ Program for sorting a given set of numbers using Quick Sort was Compiled and Executed Successfully.

Natchatran

Thursday, August 1, 2013

EC2209 - Data Structures And Object Oriented Programming Lab - Manual

No comments: