Capital University of Science

and Technology, Islamabad

LAB MANUAL
V1.1 Spring 2021

DATA STRUCTURES (SE2141 / CS2141)

DEPARTMENT OF SOFTWARE ENGINEERING AND

COMPUTER SCIENCE
Department of Software Engineering/Computer Science

Capital University of Science & Technology Islamabad

Department of Software Engineering and Computer
Science, Faculty of Computing
Lab Course Development Team

Supervision and Coordination

Mr. Danish Hamid

Lecturer
Faculty of Computing

Lab Designers

Ms. Sara Ibrahim

Junior Lecturer
Faculty of Computing
Department of Software Engineering/Computer Science

Course Outline of DATA STRUCTURES LAB

WEEK CONTENTS PAGE NO

1 Development of Arrays (Static, Dynamic and Multi-dimensional) 1

in C++
2 List Implementation with array 15

3 Array-based Stack Implementation 29

4 Array-based Queue Implementation 44

5 Circular and Priority Queues 57

6 Singly Linked List Implementation 72

7 Singly Linked List based Implementation for Stack and Queue 87

8 Doubly Linked List 100

9 Course Mid-term Exam

10 Mid Term

11 Recursion in C++ 111

12 Linked-List based BST- Recursive Traversal 121

13 Linked-List based BST - Iterative Traversal 136

14 AVL Trees: Insert and Delete 144

15 Heap: Array-based Implementation 156

16 Final Term
Department of Software Engineering/Computer Science

Lab Manual for Data Structures

Lab-1
Development of Arrays (Static, Dynamic and Multi-dimensional) in C++

1
Department of Software Engineering/Computer Science

Lab1: Development of Arrays (Static, Dynamic and Multi-

dimensional) in C++
1. Introduction
Objective of this lab is to provide you knowledge about development of arrays in C++.
You have come to know about the basic concepts about C++ language in courses: Computer
programming and Object oriented programming. You have learned about the statements used in
this language like input/output statements, selection statements (if..else, switch) and iterative
statements/loops (while, do..while, for). Further you will also have knowledge about classes,
encapsulation, inheritance and polymorphism.
In C++, every application/program contains a function called main(), which is a global
function. Execution of every program starts from this function, so you have to write this function
in each C++ program. You may write other functions also in your program beside main()
function, which depends on modular solution you have developed to solve your problem.

1.1 Basic Concepts about Data Structures

A program is a set of instructions that processes data which is given as input to it. If we
need to develop a good (efficient) program, we need to organize data in computer’s memory in
effective way. This organized data is called a Data Structure.

Study of computer science includes the study of how data (information) is organized in
computer and how it can be manipulated and utilized by programs. It is extremely important for
you to understand the concepts of data (information) organization and manipulation. Data
structures for storing information are lists, stacks, queues, trees, graphs and tables.

1.2 Arrays in C++

In C++ arrays are used to store such items whose data type is same. Normally arrays are
used to represent lists, trees and graphs; which are types of data structure. We can perform
different operations on arrays such as: inserting an item, removing an item, finding a value in
array, performing mathematical operations on elements of array etc. If we want to initialize any
global or local array by assigning some values to its element we can do so. We can access value
of an element of array in our program as it was a normal variable. We are allowed to read and
modify the values of these elements.
Static arrays are allocated memory at compile time and their size is fixed, it means it
cannot be changed latter during program execution. If we want to change the size of array at
program execution time, we will need to declare dynamic arrays. A dynamic array is allocated
memory using new operator and is used in the same way as a static array. Dynamic arrays are
accessed using pointers.

1.3 Dynamic Memory Allocation

Assume you have a program which is used to store information about the employees of
some organization, when this program starts its execution we are not sure that how many number

2
Department of Software Engineering/Computer Science

of employee records will be stored in this program. Therefore how much memory is required for
this program is dependent on the fact that how many records we will enter when program will be
executing. So memory required by program is to be estimated at program execution time, so we
will need a memory allocation mechanism which is called dynamic memory allocation for this
program, which should allocate and de allocate memory at runtime according to requirements of
program.

1.4 Multi-Dimensional Arrays

Sometimes the data which we need to process in our program is more easily interpretable
if represented in the form of a table. A table is a structure which contains some rows and some
columns, on intersection of each row and a column some data is stored. Examples of such data
representations may be a parcel weight-location chart used by some post office; a public
transport rent chart and representation of a digital image etc. So we may easily understand this
data representation if we use a two dimensional array to represent it (remember a two
dimensional array is a special case of a multi dimensional array).
Sometimes data to be represented is based on more than two dimensions, for example if
we need to represent the sales of some departmental stores by product, year of sale and location
wise, it can be easily represented by a three dimensional structure, which may be logically
represented as a cube. To represent such data we will use three dimensional arrays.

1.5 Relevant Lecture Readings

a) Revise Lecture No. 1 and 2 available at \\fs\lectures$\ in instructor’s folder.

b) From books: C++ Data Structures by Nell Dale (Page79-85) and Data structures
using C++ by D. S. Malik (Page130-135).
c) From books: C++ Data Structures by Nell Dale (Page 99-102) and Data structures
using C++ by D. S. Malik (Page 138-145).

2. Activity Time boxing

Table 1: Activity Time Boxing
Task Activity Name Activity time Total Time
No.
5.1 Design Evaluation 15 mins 15 mins

6.2 Editing and compiling a C++ 5mins 5mins

program in Visual Studio
2017
6.3 Walk Through Task 20mins 20mins

7 Practice tasks 30 mins for task 1,2 and 40 70mins

mins for task 3, 4

9 Evaluation Task 60mins for all assigned task 60mins

3
Department of Software Engineering/Computer Science

3. Objectives of the experiment

• To get basic understanding of static and dynamic arrays in C++.
• To get basic understanding of dynamic memory allocation and multi-dimensional arrays
in C++
• To write programs in C++ using Microsoft Visual Studio 2017 environment.
• To get an understanding of identifying basic errors in a C++ program by using debugging
techniques.
• To get an understanding of identifying basic errors in a C++ program by using debugging
techniques.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in
lab.

4.1 Arrays in C++

In C++ arrays are used to store such items whose data type is same. Normally arrays are
used to represent lists, trees and graphs; which are types of data structure. We may perform
different operations on arrays such as: inserting an item, removing an item, finding a value in
array, performing mathematical operations on elements of array etc.

Example:

An array named “Numbers” containing five elements of type integer (int) can be defined as:

int Numbers [5];

Figure 1 represents the logical representation of this array, which shows elements of the array are
located consecutively:

Figure 1: Logical representation of an array of integer elements

4.2 Initializing Arrays

When an array is declared in a local scope, if not specified otherwise, its elements are not
initialized by some value by default. Elements of global and static arrays are automatically
initialized by their default values (zeros for numeric data types).

4
Department of Software Engineering/Computer Science

If we want to initialize any global or local array by assigning some values to its element
we can do so. Following example represents the initialization of an array of 5 integer elements.

Example:

int Numbers [5] = { 16, 2, 77, 40, 12071 };

OR
int Numbers [] = { 16, 2, 77, 40, 12071 };

Figure 2 represents the above initialized array with values.

Figure 2: An array initialized by values

4.3 Accessing values from an array

We can access value of an element of array in our program as it was a normal variable.
We are allowed to read and modify the values of these elements. Following the previous
examples in which Numbers array has 5 elements and each of those elements was of type int, the
name which we can use to refer to each element is the following:

For example, to store the value 25 in the third element of Numbers, we could write the following
statement:

Numbers [2] = 75;

To pass the value of the third element of Numbers to a variable called a, we could write:

a = Numbers[2];

4.4 Static Arrays

Static arrays are allocated memory at compile time and their size is fixed, it means it
cannot be changed latter during program execution. For example two int arrays are declared, one
initialized and one without initialization.
int a[10];
int b[5] {8, 20, 25, 9, 14};

4.5 Dynamic Memory Allocation in C++

Dynamic memory allocation in C++ is performed using new and delete operators. These
operators can be used with primitive data types (int, float, char etc) as well as with user defined
data types (UDT), such as classes. Following examples illustrate usage of new and delete
operators for primitive as well as user defined data types.

5
Department of Software Engineering/Computer Science

For int data type, new operator can be used as:

int *pointer;
pointer = new int;
*pointer = 5;
delete pointer;

Above code will create a pointer variable named “pointer” which is pointing to a dynamic
variable of int type created by new operator. After the creation of variable a constant value 5 is
assigned to this variable using the pointer variable, because a dynamic variable does not have a
name to be referenced. When dynamic variable is used and is no more required, we can de
allocate its memory by using delete operator. With delete operator we use name of pointer
variable which is pointing to that dynamic variable required to be de allocated.

We may allocate and de allocates memory space dynamically to an array of integers.

Following example illustrates this concept.

int size;

cout<< "Enter size of array: ";

cin>> size;

int* array = new int[size];

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

{
array[i] = i+1;
cout<< array[i] << " ";
}

delete [] array;

new and delete operators can be used with a user defined type or class/struct as well. Assume
following is a class definition for which we need to create a dynamic object.

class Rectangle {
private: int x, y;
public:
void set_values (int,int);
int area () {return (x*y);}
};

void Rectangle::set_values (int a, int b) {

x = a;
y = b;

6
Department of Software Engineering/Computer Science

Following code segment creates and destroys a dynamic object of above described class.

Rectangle *ptr = new Rectangle();

ptr->set_values(3,5);
cout<<ptr->area();
delete ptr;

4.6 Multi-Dimensional Arrays

An array of arrays is called a multi-dimensional array. Number of dimensions in a multi-

dimensional array is represented by number of subscripts in definition of that array. A multi-
dimensional array can represent data from different dimensions point of view. For example
product sales information of departmental store from product, location/city and year of sale
dimensions point of view is an example of multi-dimensional array. It can be logical represented
by following figure 1.

Figure 1: A logical representation of a multi-dimensional (3-dimensional) array

4.6.1 Two Dimensional Arrays in C++

A two dimensional array is a specific case of multi-dimensional array in which two
subscripts are involved in definition of array. For example “Numbers” represents an array of 3
per 5 elements. The way to declare this array in C++ should be:

int numbers [3][5];

Following figure 2 shows a logical representation of a two dimensional array “numbers”.

7
Department of Software Engineering/Computer Science

Figure 2: A logical representation of a two dimensional array

Indices of first subscripts are logical represented as rows and indices of second subscripts
are logically represented as columns. Now for example the way to reference the second element
vertically and fourth horizontally in an expression would be:
numbers [1][3];

Following figure 3 shows the element in the two dimensional array which is referred above.

Figure 3: Referencing an element in two dimensional arrays

To assign some value to elements of a two-dimensional array, we simply use two subscripts:

numbers[1][3] = 7;

To initialize a two-dimensional array, it is easiest way to use nested braces, with each set of
numbers representing a row:

int numbers[3][5] =
{{ 1, 2, 3, 4, 5, }, // row 0
{ 6, 7, 8, 9, 10, }, // row 1
{ 11, 12, 13, 14, 15 } // row 2 };

We may initialize a two dimensional array of type int by values 0 by using following statement.
Remember that we have to specify the size of array in terms of rows and columns for proper
initialization.

int numbers[3][5] = { 0 };

8
Department of Software Engineering/Computer Science

Two dimensional arrays can be created and accessed using pointers to pointers. Following code
segment provides information that such array usage.

int **a = new int*[height];

for(int i=0; i < height; i++ )
a[i] = new int[width];

The above code segment declares an array of integer pointers to integer pointers. The first thing
we do is then make a point to an array of integer pointers. Then we have to loop through all of
those pointers and assign them to an array of ints of size width. What this does is create an array
in the size of Height x Width.

4.6.2 Three Dimensional Arrays in C++

Multi-dimensional arrays may be larger than two dimensions, arrays which have 3 dimensions
are called multi-dimensional arrays, they can be logical represented by a cube shape. An array
representing product sales for departmental stores at five cities/locations, 10 products and
containing sale information for 7 years can be declared as:

float productSales[5][10][7];

Where first subscript represents the location/city number, second subscript represents the product
number and third subscript represents the year number for which product sale information will be
stored in this array.

Three dimensional arrays cannot be easily initialized as compared to two dimensional arrays
initialization, so normally they are initialized by zero/blank value and then further initialization is
performed by using nested loops.

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

5.2 Problem description:

Design a program which should contain two arrays, both arrays should contain elements
of type integer (int). One of these arrays should be a static array and other should be a
dynamic array. User will provide numerical values as input for these arrays. Your
program should read value form each element and add these values to a single variable.

9
Department of Software Engineering/Computer Science

After completion of addition operation for two arrays, value of this variable should be
displayed on computer screen.

5.3 Practices from home

5.3.1 Task-1
Make a list of features of static and dynamic arrays in C++, which should provide
difference between these two types of arrays.

5.3.2 Task-2
Provide comparison between dynamic memory allocation schemes in C++ and Java,
provide differences and similarities.

6. Procedures & Tools

This section provides information about tools and programming procedures used for the lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Editing, Compiling and Running programs in Visual Studio 2017 [Expected
time = 5mins]

You are required to use Microsoft Visual Studio 2017 environment for programming on data
structures. It is expected that you are already familiar with this environment in your courses of
Computer Programming and Object Oriented Programming. You should be able to write code in
source code files (cpp files) and perform compilation of code. Beside that you are also required
to be proficient in performing line by line debugging and break point based debugging to remove
the errors from your code.

6.3 Walk through Task [Expected time = 20mins]

Following program represents the concept related to static and dynamic arrays; you are
required to type this program in editor of Visual Studio 2017, compile and run to see the output
of this program. Figure 3 shows the source code window of this program in Visual Studio 2017.

10
Department of Software Engineering/Computer Science

Figure 3: A program about static and dynamic arrays in Visual Studio 2017

Output of this program is shown in figure 4, when program is compiled and executed.

Figure 4: Output window displaying results of program after compilation

11
Department of Software Engineering/Computer Science

Figure 5: Use of two dimensional arrays in Microsoft Visual Studio 2017

Figure 6: Output window displaying values of elements of two dimensional arrays in Microsoft
Visual Studio 2017

7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and place solution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

12
Department of Software Engineering/Computer Science

7.1 Write a C++ program to create two pointers of integer type, now take values in these
pointers and pass them to a function. Function will update both the values by adding “1” to them.
Display the updated values in main.

7.2 Create a dynamic array of user defined size. Now take input in array from user. Take a new
(integer) value from user and search that how many times the entered number is present in the
array.

7.3 Write a program to create a dynamic array of user defined size. Array should be of character
type. Write a function ChangeCase() that should convert all the small alphabets to capital and
vice versa. All array operations should be done using pointers.

7.4 Write a program to create a dynamic array of user defined size. Size should be in the range
of 0 to 15. Write a function FindLarge that should ask user to enter a non-negative number.
Function should find the next largest number than the input number in the list.
Sample input:
Enter size: 5
After insertion:
13 4 55 29 32

Sample output:
Enter number: 15
Next largest number from 15 is: 29

7.5 Out comes

After completing this lab, student will be able to understand and develop programs related to
static and dynamic arraysin C++ using Microsoft Visual Studio 2017 environment.

8. Evaluation Task (Unseen) [Expected time = 60mins for two tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

13
Department of Software Engineering/Computer Science

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7 Practice tasks and Testing 35
4 8 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10. Further Readings

10.1 C++ Tutorial Web Sites

1. http://www.cplusplus.com/doc/tutorial/
2. http://www.learncpp.com/
3. http://www.tutorialspoint.com/cplusplus/

10.2 Web sites containing supporting material

1. http://www.engppt.com/2012/08/data-structures-with-c-ppt-slides.html
2. http://www.compgeom.com/~piyush/teach/3330/slides/

14
Department of Software Engineering/Computer Science

Lab Manual for Data Structures

Lab-2
List Implementation using Arrays

15
Department of Software Engineering/Computer Science

Lab 2: Dynamic List Implementation and Stack ADT

(Abstract Data Type)

1. Introduction
In this lab, you will learn about the dynamic list implementation using arrays in C++,
ADT (Abstract Data Types) and Stack ADT. A list is a collection of items of the same type. The
list can be based on numbers (natural or floating-point), text, dates, times, or such values as long
as the items are of the same type.An abstract data type (ADT) is a precise model for a certain
class of data structures that have similar actions; or for definite data types of one or more
programming languages that have similar semantics. Stack is a data structure which allows
placement of elements in Last in First out (LIFO) fashion.

1.1 Lists and Dynamic Lists

Lists are such data structures which are used to maintain elements of same data type in a
linear/sequential way. A list or series is an abstract data type that implements an ordered
collection of values, where the same value can occur more than one time. Static list structures
allow only inspection and enumeration of the values of its elements. A dynamic list may allow
items to be inserted, replaced, or deleted during the list's existence. Size of dynamic lists can be
changed during program execution.

1.2 Relevant Lecture Readings

a) Revise Lecture No. 5 and 6 available at \\fs\lectures$ in instructor’s folder.
b) From books: C++ Data Structures by Nell Dale (Page 196-199) and Data
structures using C++ by D. S. Malik (Page 396-399).

2. Activity Time boxing

Table 1: Activity Time Boxing

Task Activity Name Activity time Total Time
No.
5.1 Design Evaluation 20mins 20mins
6.2 Walk through tasks 20mins 20mins
7 Practice tasks 15 mins for task 1, 30 mins 70mins
for task 2 and 25 mins for
task 3
9 Evaluation Task 60mins for all assigned tasks 60mins

16
Department of Software Engineering/Computer Science

3. Objectives of the experiment

• To get basic understanding of dynamic lists using arrays in C++

• To write programs related to dynamic lists using arrays in C++ using Microsoft Visual
Studio 2017 environment.
• To get an understanding of identifying basic errors in a C++ program by using debugging
techniques from program representing dynamic list using arrays.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in lab.
4.1 Dynamic Lists in C++ using Arrays

Dynamic list in C++ can be designed using arrays. We may add or remove elements from this
list during execution of program and arrays size can controlled at program execution time.

Following code segment represents a list using arrays:

const int MaxItems = 20;

class CListOfNumbers
{
private:
double Item[MaxItems];

public:
CListOfNumbers();
~CListOfNumbers();
};

You are required to count the number of elements in list after performing each add or delete
operation on list.

class CListOfNumbers
{
private:
double Item[MaxItems];
int Size;

public:
int Count() const;
CListOfNumbers();
};

17
Department of Software Engineering/Computer Science

CListOfNumbers::CListOfNumbers()
{
Size = 0;
}
intCListOfNumbers::Count() const
{
return Size;
}

Creating a list, consists of adding elements to it. Elements are usually added one at a time and
easiest way to do this is to add an item at the end of the list.

To add an item to the list, you first need to test whether the list is already full or not. A list is full
if its count of items is equal to or higher than the maximum number you had set. If the list is not
empty, you can add an item at the end and increase the count by one. Following code segment
represent this functionality.

Bool ListOfNumbers::Add(double item)

{
if( size < 20 )
{

Item[size] = item;
size++;

return true;
}

return false;
}

After adding elements to a list, you can retrieve them to do what you intended the list for. To
retrieve an item, you can locate an item by its position. By using index of this array, you can
check if the position specified is negative or higher than the current total of elements. It means
index is out of range. If the index is in the right range, you can retrieve its item against that
index. Following code segment represents this functionality.

Double ListOfNumbers::Retrieve(int pos)

{
if(pos>= 0 &&pos<= size )
return Item[pos];

return 0;
}

18
Department of Software Engineering/Computer Science

Inserting a new item in the list allows you to add it at a position of you chooses. To insert a new
element in the list, you must provide the new item and the desired position. Before performing
this operation, you must first check two conditions. First, the list must not be empty. Second, the
specified position must be in the valid range. Following code segment provides implementation
of this method.

Bool ListOfNumbers::Insert(double item, int pos)

{
if( size < 20 &&pos>= 0 &&pos<= size )
{
for(int i = size; i > pos-1; i--)
Item[i+1] = Item[i];

Item[pos] = item;

size++;

return true;
}

return false;
}

Another operation you may perform on a list consists of deleting an element. To delete an item
from the list, you need to provide its position in the list. Before performing the operation, you
can first check that the specified position is valid. Following code segment provides
implementation.

Bool ListOfNumbers::Delete(int pos)

{
if(pos>= 0 &&pos<= size )
{

for(int i = pos; i < size; i++)

Item[i] = Item[i+1];

size--;

return true;
}

return false;
}

19
Department of Software Engineering/Computer Science

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should access and grade it.

5.2 Problem description:

Design a dynamic list using array whose each element is an object of “person” class.
“person” class should have some privately defined attributes: per_id (int),
per_name(string) and per_age (int). Some member functions which are defined publicly
are: constructor function which should initialize the attributes of “person” object using
blank and zero values, input() function which should allow user to provide input for
attributes of object, output() function which should allow user to display the values of
attributes of object. This dynamic array should allow insertion, removal, count of total
element and displaying the values of elements of list.

5.3 Practices from home

5.3.1 Task-1
Make a list of at least 5 benefits we may get while using dynamic lists.

5.3.2 Task-2
Provide comparison between implementation of lists using static and dynamic arrays.

6. Procedure& Tools
This section provides information about tools and programming procedures used for the lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Walk through Tasks [Expected time = 20mins]

Dynamic list using array can be implemented in visual studio 2017. Following figure 2 shows
screens containing this cod

20
Department of Software Engineering/Computer Science

Figure 2: Dynamic list using array in Microsoft Visual Studio 2017

Operations related to list such as addition, removal, element count and element retrieval are
implemented in this program as well. Figure 3 shows some of these operations.

Figure 3: Insert operation on lists using arrays in Microsoft Visual Studio 2017

21
Department of Software Engineering/Computer Science

7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and place solution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 15mins]

Partial solution of a List Class is given below. Complete the missing code in the functions to run
the program properly.
int *elements;
int size;
int length;
////////////////////////////////// Constructor
List(int maxsize)
{
size=maxsize;
elements=new int[size];
length=0;
}
/////////////////////////////////// Destructor
~List ()
{
delete []elements;
}
/////////////////////////////////// Output the list structure
void showStructure ()
{
if(!isEmpty())
{
for(int i=0;i<length;i++)
{
cout<<"Element:"<<elements[i]<<endl;

22
Department of Software Engineering/Computer Science

}
}
else
{
cout<<"Display: No items to be displayed. List is empty\n";
}
}
////////////////////////////////// List manipulation operations
// Insert after cursor
void insert (int newDataItem)
{
if(!isFull())
{
elements[length]=newDataItem;
length++;
}
else
{
cout<<"Insert: Cannot insert more items. List is full\n";
}
}
// Remove data item
int remove ()
{
if(!isEmpty())
{
length--;
return elements[length];
}
else

23
Department of Software Engineering/Computer Science

{
cout<<"Remove: Cannot remove the item. List is empty\n";
}
}
// Replace data item
void replace ( int newDataItem, int position )
{
//Condition: List contains at least position+1 data items.
//Result: Removes the data item present at the position from a list and replace the number
requested by user at its position.
if(length<position)
{
cout<<"Replace: Cannot replace the item. Invalid position requested\n";
}
else
{
//implement your logic here
}
}
// find any number
bool find ( int searchDataItem )
{
//Condition: List is not empty.
//Result: Check if the number is present in the list or not

if(!isEmpty())
{
for(int i=0;i<length;i++)
{
//implement your logic here
}

24
Department of Software Engineering/Computer Science

}
}
/////////////////////////////////////// List status operations
// check if List is empty
bool isEmpty ()
{
// implement your logic here
}

// check if List is full

bool isFull ()
{
// implement your logic here
}

7.2 Practice Task 2 [Expected time = 30mins]

Create a list of at least 10 books (Title, Author, Price, Book_id) with the following functions:
1) Sequential insert in the list on the basis of Book_id
2) Sequential delete in the list and then adjust the list afterwards
3) Insert a value at a specific index and adjust remaining list afterwards
4) Delete a value at a specific index and adjust remaining list afterwards
5) Show all values present in the list
6) Show the length of the list

7.3 Practice Task 3 [Expected time = 25mins]

Create a list of Employees (List can be as long as user wants). Program should save the
following information for each Employee: Name, Emp. No., Experience, Designation and
Salary. Now perform the following tasks:
a) Your program should save the information of only those employees whose experience is
at least 2 years.
b) Display only those Employees whose Salary is greater than 50,000
c) Display the Employees alphabetically

25
Department of Software Engineering/Computer Science

7.4 Out comes

After completing this lab, student will be able to understand the concepts related to dynamic list
using arrays and stack abstract data type. They will be able to develop programs related to
dynamic lists using arrays in C++ using Microsoft Visual Studio 2017 environment.

7.5 Testing
Test Cases for Practice Task-1
Sample Input Sample Output
2
3
4
6
9
Delete an element from Element deleted
location: 3

Enter a value to search 9 is at location 3 in list

in list: 9

Test Cases for Practice Task-2

Sample Sample
Inputs-1 Outputs-1
Input elements in list:
Bookno : B123
Title: C++ programming
Price: 234.95
Author: Jone Sage
Bookno: B345
Title: Object Oriented Programming in C++
Price: 235.95
Author: B J Shamy
Bookno: B133
Title: Data Structures using C and C++
Price: 400.35

26
Department of Software Engineering/Computer Science

Author: Dietel J.
Enter an index to place a in list: Book with bookno:
B133 is Placed at
7 location 7 in list
Please enter the information of book:
Bookno: B133
Title: Data Structures using C and C++
Price: 400.35
Author: Dietel J.
Enter an index to place a book in the list: Sorry the entered index
has already a book.
3

Test Cases for Practice Task-3

Sample Input Sample Output

Enter the size of list: Sorry the list is empty yet.
5
Press 1 to add an
employee
Press 2 to Check the
employees having
experience more than 2
years
Press 3 to display all
the employee
information

Press 1 to add an Please enter the information of employee:

employee
Press 2 to Check the
employees having
experience more than 2
years

27
Department of Software Engineering/Computer Science

Press 3 to display all

the employee
information

8. Evaluation Task (Unseen) [Expected time = 60 mins for two tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks

1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10. Further Readings

10.1 Web sites related to C++ tutorials related to dynamic lists
1. https://www.w3schools.com/CPP
2. https://www.tutorialspoint.com/cplusplus/index.htm
10.2 Web sites containing supporting material

1. https://www.cplusplus.com/doc/tutorial/

28
Department of Software Engineering/Computer Science

Lab Manual for Data Structures

Lab-3
Array based Stack implementation

29
Department of Software Engineering/Computer Science

Lab 3: Array based Stack implementation with template

class

1. Introduction
Objective of this lab is to introduce the implementation of stack in C++ and further introduce
concept of class templates and defining a stack as a class template or generic class. A stack
allows last in first out (LIFO) operations. We can place a new element at top of stack and we
may remove an element from top of stack. Stacks can be implemented using static as well as
dynamic arrays. Further we may implement a stack as a generic class/class template.

1.1 Stack implementation as a static array

A stack can be implemented using a static array in C++. We need to define an array with a
maximum size and a variable of integer type normally called “top” for such stack. Stack is
initially set to empty when program is executed, so at start of program top is set to -1 which
represents an empty stack. There are two operations associated with a stack; push operation—
used to add an element at top of stack and pop operation – to remove an element from top of
stack. When push operation is performed we need to check that whether stack exceeds its
maximum size or not, this is called stack overflow condition check. When pop operation is
performed we need to test that whether stack is empty or not, this is called stack underflow
condition check.

1.2 Stack implementation as a dynamic array

When maximum size of stack is to be decided at program execution time, then we need a
dynamic array to represent the stack. Size of such array is specified at program execution time, a
pointer is defined in program which points to an array dynamically created. Even the stack with
dynamic array is implemented for stack overflow and underflow conditions in push and pop
operations respectively.

1.3 Stack as a class template

A class template is a generic class which is defined as a template, from which multiple different
classes can be generated. If we need to design a stack which can be used for integer, float, string
and other primitive data types, we can define this stack as a class template. From this class
template we may generate different stack classes which can be used to represent integers, floats,
strings and other primitive data types as well for user defined data types.

1.4 Relevant Lecture Readings

2. Revise Lecture No. 7 and 8 available at \\fs\lectures$ in instructor’s folder.

3. From books: C++ Data Structures by Nell Dale (Page 196-225) and Data structures using
C++ by D. S. Malik (Page 405-411).

30
Department of Software Engineering/Computer Science

2. Activity Time boxing

Table 1: Activity Time Boxing

Task Activity Name Activity time Total Time
No.
5.1 Design Evaluation 20mins 20mins
6.2 Walk through tasks 20mins 20mins
7 Practice tasks 15 mins for task 1, 20 mins 70mins
for task 2 and 35 mins for
task 3
9 Evaluation Task 60mins for all assigned tasks 60mins

3. Objectives of the experiment

• To get knowledge of implementing stacks using static arrays in C++.
• To get knowledge of implementing stacks using dynamic arrays in C++.
• To get knowledge of implementing stacks as stack class template in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in lab.

4.1 stack class using a static array

Following is an implementation of stack using static array in C++.
#include <iostream>
using namespace std;

const int STACKSIZE = 10;

class stack{
private:
int arr[STACKSIZE];
int tos;
public:
stack();
void push(int x);
int pop();
bool empty();
bool full();
int size();
void display();
};

stack::stack()

31
Department of Software Engineering/Computer Science

{
tos = -1;
}

void stack::push(int x)
{
if(!full())
arr[++tos] = x;
else
cout<< "Stack is full, Cannot push " << x <<endl;
}

int stack::pop()
{
if(!empty())
return arr[tos--];
else
cout<< "Stack is empty, cannot pop" <<endl;
return -1;
}

bool stack::empty()
{
if(tos == -1)
return true;
else
return false;
}

bool stack::full()
{
if(tos+1 == STACKSIZE)
return true;
else
return false;
}

int stack::size()
{
return tos;
}

void stack::display()
{
if(tos == -1)
{

32
Department of Software Engineering/Computer Science

cout<< "No elements to display" <<endl;

return;
}
for(int i=0;i < STACKSIZE; i++)
cout<<arr[i] << " ";
cout<<endl;
}

int main()
{
stackmystack;
cout<<mystack.size() <<endl;
mystack.push(1);
if(mystack.full())
cout<< "stack is full" <<endl;
mystack.pop();
if(mystack.empty())
cout<< "stack is empty" <<endl;
}

Following figure 1 represents the functionality of pop and push operations on a stack
implemented using a static array.

Figure 1: push and pop operations on a stack

4.2 Stacks using dynamic arrays

A stack which is implemented using an array whose size is determined at program execution
time is implemented using a dynamic array.

33
Department of Software Engineering/Computer Science

For the array implementation, we need to keep track of (at least) the array contents and a top
index. Definition of stack class will be as:
class Stack{
public:
Stack(int stack_size);
~Stack();
void push(int x);
int pop();
bool isEmpty();
bool isFull();

private:
char *contents;
int top;
};

Stack::Stack(int stack_size)
{

contents = new char[stack_size];

if (contents == NULL) {
cout<< "Insufficient memory to initialize stack.\n";
exit(1);
}

maxSize = stack_size;
top = -1;
}

Stack::~Stack()
{
delete [] contents;

contents = NULL;
maxSize = 0;
top = -1;
}

bool Stack::isEmpty() const

{
return top < 0;
}

void Stack::push(char element)

{
34
Department of Software Engineering/Computer Science

if (isFull()) {
cout<< "Can't push element on stack: stack is full.\n";
exit(1);
}

contents[++top] = element;
}

char Stack::pop()
{
if(!isEmpty())
return contents[--top];
else
cout<< "Stack is empty, cannot pop" <<endl;
return -1;
}

4.3 Stack using a class template

A stack using a class template provides a generic implementation of stack which provides facility
to use stack with many primitive and user defined data types. Following is an implementation of
stack using templates.
template <class Typ, intMaxStack>
class Stack {
int EmptyStack;
Typ items[MaxStack];
int top;
public:
Stack();
~Stack();
void push(Typ);
Typ pop();
int empty();
int full();
};

Template < class Typ, intMaxStack>

35
Department of Software Engineering/Computer Science

Stack <Typ, MaxStack>::Stack() {

EmptyStack = -1;
top = EmptyStack;
}
template< class Typ, intMaxStack>
Stack<Typ, MaxStack>::~Stack()
{ delete[] items; }
template< class Typ, intMaxStack>
void Stack<Typ, MaxStack>::push(Typ c)
{ items[ ++top ] = c; }
template< class Typ, intMaxStack>
Typ Stack<Typ, MaxStack>::pop()
{ return items[ top-- ]; }
template< class Typ, intMaxStack>
int Stack<Typ, MaxStack>::full()
{ return top + 1 == MaxStack; }
template< class Typ, intMaxStack>
int Stack<Typ, MaxStack>::empty()
{ return top == EmptyStack; }
int main() {
Stack<char, 10> s; // 10 chars
Char ch;
while ((ch = cin.get()) != '\n')
if (!s.full()) s.push(ch);
while (!s.empty())
cout<<s.pop();
cout<<endl;
Stack<double, 4> ds; // 4 doubles

36
Department of Software Engineering/Computer Science

double d[] =
{1.0, 3.0, 5.0, 7.0, 9.0, 0.0};
int i = 0;
while (d[i] != 0.0 && !ds.full())
if (!ds.full()) ds.push(d[i++]);
while (!ds.empty())
cout<<ds.pop() << " ";
cout<<endl;
return 0;
}

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

5.2 Problem description:

Write a program to implement a stack to store the objects of “person” class. “person”
class should contain attributes (privately defined) per_ssn (string), per_name (string),
per_age (int). “person” class should also contain member functions (publicly defined);
constructor, input and output functions. You are required to design two stack class, one
should use static array and other one should use dynamic array implementation. Your
stack classes should contain constructors, destructors (if required), push and pop
operations and functions to check empty or full stack.

5.3 Practices from home

5.3.1 Task-1
Compare implementations of stack with static array and dynamic array and provide at
least three differences between these two implementations.
5.3.2 Task-2
List three advantages of using stack as a class template.

6. Procedure& Tools
This section provides information about tools and programming procedures used for the lab.

37
Department of Software Engineering/Computer Science

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Walk through Tasks [Expected time = 20mins]

We will discuss the demonstration of stack using static array in Microsoft Visual Studio 2017.
You are required to open an empty Win32 console application. You have already knowledge of
creating a console application in Microsoft Visual Studio 2017 in your courses: computer
programming and object oriented programming, which you have previously studied.

Following figure 2 represents the implementation of class in editor window.

Figure 2: Stack definition using static array in Microsoft Visual Studio 2017

38
Department of Software Engineering/Computer Science

Figure 3 shows push and pop operations implementation.

Figure 3: Implementation of push and pop operations for stack using static array in Microsoft
Visual Studio 2017

Figure 4 represents the output of this program when executed.

Figure 4: Output window displaying values from stack in Microsoft Visual Studio 2017

39
Department of Software Engineering/Computer Science

7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and place solution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 15mins]

Write a program to implement a Stack using dynamic array of Character values. Implement the
following functions in Stack with necessary checks:
a) Insert value in Stack (PUSH)
b) Delete value from Stack (POP)
c) Display the Stack.

7.2 Practice Task 2 [Expected time = 20mins]

Create a Stack of integer using arrays. Give the following menu to the user and then implement
the given operations:

Press 1 to PUSH a value in Stack

Press 2 to POP a value from Stack
Press 3 to display the Stack
Press 4 to Show the next greater element in the Stack.
Sample Input:
Stack
3 2 6 7 8 13

Press 1 to PUSH a value in Stack

Press 2 to POP a value from Stack
Press 3 to display the Stack
Press 4 to Show the next greater element in the Stack.
4
Sample Output:
The next greater elements for the given Stack are:
3→6
2→6
6→7
7→8
8→13
13→-1

40
Department of Software Engineering/Computer Science

7.3 Practice Task 3 [Expected time = 20mins + 20mins]

Use stack to solve the following problems:

a) Find the Minimum number of bracket reversals needed to make an expression balanced.
A balanced expression is an expression in which all opening brackets have respective
closing brackets. For example 2+ {3*(7-2)} is a balanced expression whereas 2+{3*(7-
2}is not a balanced expression. Write a program to ask user to enter an expression.
Expression must consists of only brackets {or}, but the expression may not be balanced.
Find minimum number of bracket reversals to make the expression balanced.

b) Delete consecutive same characters in a sequence using stack. Ask user to enter a series
of characters until user enters ‘F’ or ‘f’. Now the task is to check if any two similar
characters come together then they destroy each other. Print the new sequence after this
pair wise destruction.

7.4 Out comes

After completing this lab, student will be able to understand and develop programs related stacks
using static and dynamic arrays and using stack as class template in C++ using Microsoft Visual
Studio 2017 environment.

7.5 Testing

Test Cases for Practice Task-1

Sample Sample
Inputs-1 Outputs-1
Push elements for stack:
2
3
4
5
8
Enter number of elements to be popped
from stack1: 3
Elements of stack popped:
8
5
4

41
Department of Software Engineering/Computer Science

Test Cases for Practice Task-3 a

Sample Sample
Inputs-1 Outputs-1
Enter expression:
{{{
Can't be made balanced using reversals
Enter expression:
{{{{
2
Enter expression:
{{{{}}
1

Test Cases for Practice Task-3 b

Sample Sample
Inputs-1 Outputs-1
Input : abaabcdabf
new sequence is:
acdab

8. Evaluation Task (Unseen) [Expected time = 60mins]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

42
Department of Software Engineering/Computer Science

10. Further Readings

10.1 Web sites related to C++ tutorials related to stacks
1. http://www.cplusplus.com/reference/stack/stack/
2. http://www.cppforschool.com/tutorial/dynamic-stack.html

10.2 Web sites containing supporting material

1. http://www.slideshare.net/nita23arora/stacks-queues-presentation

43
Department of Software Engineering/Computer Science

Lab Manual for Data Structures

Lab 4
Queue Implementation in C++

44
Department of Software Engineering/Computer Science

Lab 4: Stack Applications and Queue Implementation in C++

1. Introduction
This lab will help students to learn about using the stacks as postfix calculator and infix to
postfix convertor. Also this lab will introduce use of FIFO (First In First Out) Queue and
operations which may perform on this queue. A queue is a specific type of abstract data type in
which the elements are kept in order and the only operations on the collection are the addition of
elements to the rear terminal position, which is called addQueue or enqueue, and removals of
elements from the front terminal position, known as removeQueue or dequeue.In a FIFO data
structure, the first element which is added to the queue will be the first element to be removed
from queue.

1.1 Queue Operations

Two key operations which are defined for queues are addQueue (enqueue) and deleteQueue
(dequeue). As elements cannot be deleted from an empty queue and cannot be added to a full
queue, therefore we need two more operations called IsEmptyQueue (to check whether a queue
is empty) and IsFullQueue (to check whether a queue is full). Another operation which is
required for queues is initializeQueue: to initialize a queue in empty state, it means it should not
contain any elements in it when queue is created. To retrieve the front and last elements of queue
we need to have two operations called front and last operations.

1.2 Relevant Lecture Readings

a) Revise Lecture No. 9 and 10 available at \\fs\lectures$ in instructor’s folder.

b) From books: C++ Data Structures by Nell Dale (Page 199-210) and Data structures
using C++ by D. S. Malik (Page 428-437).
c) From books: C++ Data Structures by Nell Dale (Page 225-245) and Data structures
using C++ by D. S. Malik (Page 455-462).

2. Activity Time boxing

Table 1: Activity Time Boxing

Task Activity Name Activity time Total Time
No.
5.1 Design Evaluation 15mins 15mins
6.2 Walk through tasks 15mins 15mins
7 Practice tasks 20 mins for task 1, 30mins 80mins
for task 2 and 30 mins for
task 3.
9 Evaluation Task 60mins for all assigned tasks 60mins

45
Department of Software Engineering/Computer Science

3. Objectives of the experiment

• To get knowledge of implementing queues using static arrays in C++.
• To understand the operations related to queues in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in lab.

4.1 Queue as a static array

We will be using an array to store the queue elements, the variables queueFront and queueRear
will be used to keep track of the first and last elements of the queue, and the variable
maxQueueSize is used to specify the maximum size of the queue. Thus, we need at least four
member variables in class for queue.

Before writing the algorithms for queue operations, we need to decide that how queueFront and
queueRear will be used to access the queue elements. How queueFront and queueRear indicate
that status of queue that the queue is empty or full? If queueFront gives the index of the first
element of the queue and queueRear gives the index of the last element of the queue. To add an
element to the queue, first we advance queueRear to the next array position and then add the
element to the position that queueRear is pointing to. To delete an element from the queue, first
we retrieve the element that queueFront is pointing to and then advance queueFront to the next
element of the queue. It means queueFront will be changing after each deleteQueue operation
and queueRear will be changing after each addQueue operation.

Let us see what will happen when queueFront changes after a deleteQueue operation and
queueRear changes after an addQueue operation. Assume that size of array to holding queue
elements is 100.

Initially, the queue is empty. After the operation:addQueue(Queue,'A');

Figure 1 shows the effect of this operation on array.

Figure 1: Insertion of an element in queue at rear

46
Department of Software Engineering/Computer Science

After two more addQueue operations:

addQueue(Queue,'B');
addQueue(Queue,'C');
The array is as shown in Figure 2 after the effect of these two operations

Figure 2: Insertion of two more elements in queue at rare

Now consider the deleteQueue operation:

deleteQueue();
After this operation, the array containing the queue is as shown in Figure 3.

Figure 3: Removal of element from queue at front

An array for a queue is normally initialized by setting queueFront and queueRear to -1.
queueRear=-1; queueFront=-1;
When an element is required to be added in queue, we need to check that whether queue
overflow condition occurs or not, it means whether queue will exceed its maximum size on
addition of an element to queue or not? If x is an element to be inserted in a queue based on array
“Queue” with a maximum size MAX_QUEUE, then following code segment represents
implementation of addQueue or enqueue operation.
if(queueRear> MAX_QUEUE-1)
{ cout<<"queue over flow";

47
Department of Software Engineering/Computer Science

queueFront=queueRear=-1;
return; }
Queue[++queueRear]=x;
cout<<"inserted" <<x;
When an element is required to be remove from a queue, we need to check that whether queue is
empty or not, because we cannot remove an element from an empty queue. Following code
segment represents this operation.
if(queueFront==queueRear)
{ cout<<"queue under flow"; return; }
cout<<"deleted" <<Queue[++queueFront];

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

5.2 Practices from home

5.2.1 Task-2
Compare implementations of stack with a queue using static array and provide at least
three differences between these two implementations.

6 Procedure& Tools
This section provides information about tools and programming procedures used for the lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Walk through Tasks [Expected time = 20mins]

In this task we will implement and test the evaluation of post fix expression and a program for a
queue using static array using C++.Figure 4 and 5 represents the source code view of queue
program in visual studio. You are required to type this code and further debug and execute the
program.

48
Department of Software Engineering/Computer Science

Figure 4: Implementation of a queue using static array

Figure 5 also represents the remaining part of this code.

Figure 5: Implementation of a queue using static array

49
Department of Software Engineering/Computer Science

Following is output window of this program in figure 4 and figure 5, when executed.

Figure 6: Output of program for queue using static array

7 Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and place solution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1Practice Task 1 [Expected time = 20mins]

Partial solution of a Linear Queue Class is given below. Complete the missing code in the functions to
run the program properly.
Class Queue

int *elements;

int size;

int rear, front;

////////////////////////////////// Constructor

Queue (int maxsize)

50
Department of Software Engineering/Computer Science

size=maxsize;

elements=new int[size];

rear = 0, front = -1;

/////////////////////////////////// Destructor

~ Queue()

delete []elements;

/////////////////////////////////// Output the Queue structure

void showStructure ()

if(!isEmpty())

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

cout<<"Element:"<<elements[i]<<endl;

else

cout<<"Display: No items to be displayed. Queue is empty\n";

////////////////////////////////// Queue manipulation operations

// Insert in queue

void Enqueue (int newDataItem)

if(!isFull())

if(front==-1)

{front=0;}

elements[rear]=newDataItem;

rear++;

51
Department of Software Engineering/Computer Science

else

{cout<<"Insert: Cannot insert more items. List is full\n";}

// Remove data item

void Dequeue ()

if(!isEmpty())

//implement your logic here

// delete a data item from front end and shift all the remaining items to fill the gap at the front.

else

cout<<"Remove: Cannot remove the item. List is empty\n";

// Clear queue

void clear ()

//implement your logic here

// Removes all the data items in a queue but the queue itself

/////////////////////////////////////// Queue status operations

// check if queue is empty

bool isEmpty ()

// implement your logic here

// check if queue is full

bool isFull ()

// implement your logic here

};

52
Department of Software Engineering/Computer Science

7.2 Practice Task 2 [Expected time = 20 mins]

Write a program to implement Parking area reservation. The parking area has only one way out
and one-way inn; so scheduling has to be done for the arrival and departure of vehicles in the
parking area. At one time, only one vehicle can arrive or leave the area. Scheduling has to be
done on the basis of first come, first serve. Whichever vehicle comes first at the parking area will
be given the space in the parking area. Similarly, whichever vehicle requests for departure first,
will be given the space to the exit.
[Hint: Arrival of vehicle=enqueue, Departure of vehicle=dequeue]

7.3 Practice Task 3 [Expected time = 20 mins]

A queue can be used to simulate the flow of customers through a check-out line in a
departmental store. Your program must store Name, Customer_id and Bill of each customer.
You can model the flow of customers using a queue in which each data item corresponds to a
customer in the line. Customers come one by one and leave the queue after check-out. Each
customer takes approx. 5 minutes to check out. Implement the given system and provide the
following functionality to user:
1) Add a customer to queue
2) Delete a customer from queue after check out
3) Calculate the total number of customers served
4) Calculate the time required to serve all the remaining customers

7.4 Out comes

After completing this lab, student will be able to understand and develop programs related to
exception handling and use of stacks for evaluation of postfix arithmetic expressions, validating
parenthesis in infix arithmetic expressions in C++ using Microsoft Visual Studio 2017
environment.

7.5 Testing
Test Cases for Practice Task-1
Sample Sample
Inputs-1 Outputs-1
Enter values to be inserted for
queue
2
3
4
7
8
Dequeue: 2
Dequeue: 3
Dequeue: 4
Values in queue: 7 8

53
Department of Software Engineering/Computer Science

Test Cases for Practice Task-2

Sample Sample
Inputs-1 Outputs-1
Insert elements in queue:
Car ID: SH435
Car ID: PI567
Car ID: AB984
Element removed from rear of queue
is
Car ID: SH435

Test Cases for Practice Task-3

Sample input output:

Press 1 to add new customer to queue

Press 2 to remove a customer from queue
Press 3 to Calculate the total number of customers served
Press 4 to Calculate the time required to serve all the remaining customers
Enter choice: 1
Enter customer name: Ali
Press Y/y to continue: y

Press 1 to add new customer to queue

Press 2 to remove a customer from queue
Press 3 to Calculate the total number of customers served
Press 4 to Calculate the time required to serve all the remaining customers
Enter choice: 1
Enter customer name: Ahmed
Press Y/y to continue: y

Press 1 to add new customer to queue

Press 2 to remove a customer from queue
Press 3 to Calculate the total number of customers served

54
Department of Software Engineering/Computer Science

Press 4 to Calculate the time required to serve all the remaining customers
Enter choice: 1
Enter customer name: Aliya
Press Y/y to continue: y

Press 1 to add new customer to queue

Press 2 to remove a customer from queue
Press 3 to Calculate the total number of customers served
Press 4 to Calculate the time required to serve all the remaining customers
Enter choice: 2
Ali is removed from the queue
Press Y/y to continue: y

Press 1 to add new customer to queue

Press 2 to remove a customer from queue
Press 3 to Calculate the total number of customers served
Press 4 to Calculate the time required to serve all the remaining customers
Enter choice: 3
Number of customers served:1
Press Y/y to continue: y

Press 1 to add new customer to queue

Press 2 to remove a customer from queue
Press 3 to Calculate the total number of customers served
Press 4 to Calculate the time required to serve all the remaining customers
Enter choice: 4
Time required to serve all the remaining customers:04 mins
Press Y/y to continue: n

8. Evaluation Task (Unseen) [Expected time = 60mins for two tasks]

55
Department of Software Engineering/Computer Science

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).
Table 2: Evaluation of the Lab
Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10. Further Readings

10.1 Web sites related to C++ tutorials related to queues
1. http://www.cprogramming.com/tutorial/computersciencetheory/queue.html
2. https://www.tutorialspoint.com/cplusplus-program-to-implement-queue-using-array

10.2 Web sites containing supporting material

1. http://thatchna.weebly.com/uploads/4/1/9/3/4193382/std_c_notes_03.pdf 3.
2. http://uet.vnu.edu.vn/~chauttm/dsa2012w/slides/Lec04_StacksQueues.pdf

56
Department of Software Engineering/Computer Science

Lab Manual for Data Structures

Lab 5
Circular and Priority Queues

57
Lab 5: Circular and Priority Queues

1. Introduction
This lab will introduce concept of circular and priority queues. In standard queues when
dequeue operation is performed a problem called de-bufferring occurs, to solve this problem we
need to use circular queues. Beside the circular queues we may also use priority queues, in such
queues we may delete an element from queue on the basis of some priority. In First in first out
queues, the element at start of queue has highest priority to be removed from queue.

1.1. Circular Queues

Circular queuesare linear data structures. It follows FIFO (First In First Out) rule.

• In circular queue the last element is connected back to the first element to make a
circle.
• Elements are inserted at the rear end and the elements are removedfrom front end of
the queue.
• Both the front and the rear pointers point to the beginning of the array.
• It is also called as “Ring buffer”.

1.2. Priority Queues

Priority queues are used in such situations where you want to remove an element from
queue which is not at the moment at front of queue, but its priority is high. For example in daily
life if in some hospital there is a queue of patients waiting for checkup/treatment from doctor. If
some patient comes whose have light threatening symptoms and need urgent treatment then he
should be at high priority in that queue and should be removed from queue on his priority, may
be patient at front of queue at the moment has come for general checkup.

A priority queue must at least support the following operations:

• insert_with_priority: add an element to the queue with an associated priority

• pull_highest_priority_element: remove the element from the queue that has the highest
priority, and return it.

1.3 Relevant Lecture Readings

d) Revise Lecture No. 9 and 10 available at \\dataserver\jinnah$\ in instructor’s folder.

e) From books: C++ Data Structures by Nell Dale (Page 225-245, 530-533) and Data
structures using C++ by D. S. Malik (Page 455-462, 471-480).

2. Activity Time boxing

58
Table 1: Activity Time Boxing
Task Activity Name Activity time Total Time
No.
5.1 Design Evaluation 20mins 20mins
6.2 Walk through tasks 20mins 20mins
7 Practice tasks 20mins for task 1, 25mins for 70mins
task 2 and 3.
9 Evaluation Task 60mins for all assigned tasks 60mins

3. Objectives of the experiment

• To understand implementation of circular queues in C++.

• To understand the implementation of priority queues in C++.
• To define and understand the ADT (Abstract Data Type) of priority queue in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in
lab.

4.1 Circular Queues in C++

Suppose we have given an array to implement a FIFO queue. We are using queueFront
and queueRear two elements referring indices of this array. Now if we perform addition and
removal of element on this array in such a way that after addition of three elements we remove
one element. On performing addition queueRear will move to index of next element of array.
When queueRear will point to last element of array after that it cannot use any other element of
array for insertion of further element in this array. Figure 1 shows this scenario.

Figure 1: Rear cannot move further in array.

So we may use this array in circular fashion so that rear can move to starting element
after reaching last element of array. Figure 2 represents the logical circular array which can be
used.

59
Figure 2: Logical representation of a circular array (Ring Buffer)

Because the array containing the queue is circular, we can use the following statement to
advance queueRear (queueFront) to the next array position:
queueRear = (queueRear + 1) % maxQueueSize;
If queueRear<maxQueueSize - 1,
ThenqueueRear + 1 <= maxQueueSize - 1,
so(queueRear + 1) % maxQueueSize = queueRear + 1.
IfqueueRear == maxQueueSize- 1
(That is, queueRear points to the last array position),
queueRear + 1 ==maxQueueSize,
So (queueRear + 1) % maxQueueSize = 0. In this case, queueRear will be set to 0, which
is the first array position.

4.2 Priority Queues in C++

Following is implementation example of a priority queue in C++. Following are some

definitions which will be used by this priority queue.

const int MAX=5;

struct data
{
char job[MAX];
int prno ;
int ord ;
};

struct pque
{
data d[MAX];
int front ;
int rear ;
};
60
Following function is used to initialize the queue attributes.

void initpque ( pque *pq )

{
int i ;

pq -> front = pq -> rear = -1 ;

for ( i = 0 ; i < MAX ; i++ )
{
strcpy ( pq -> d[i].job, '\0' ) ;
pq -> d[i].prno = pq -> d[i].ord = 0 ;
}
}

To add an item in this priority queue, following function is used.

void add (pque *pq, data dt )

{
data temp ;
int i, j ;

if ( pq -> rear == MAX - 1 )

{
cout"\nQueue is full."<<endl;
return ;
}

pq -> rear++ ;
pq -> d[pq -> rear] = dt ;

if ( pq -> front == -1 )
pq -> front = 0 ;

for ( i = pq -> front ; i <= pq -> rear ; i++ )

{
for ( j = i + 1 ; j <= pq -> rear ; j++ )
{
if ( pq -> d[i].prno>pq -> d[j].prno )
{
temp = pq -> d[i] ;
pq -> d[i] = pq -> d[j] ;
pq -> d[j] = temp ;
}
else
{

61
if ( pq -> d[i].prno == pq -> d[j].prno )
{
if ( pq -> d[i].ord>pq -> d[j].ord )
{
temp = pq -> d[i] ;
pq -> d[i] = pq -> d[j] ;
pq -> d[j] = temp ;
}
}
}
}
}
}

To remove an element from priority queue, following function is used.

data delete (pque *pq )

{
data t ;
strcpy ( t.job, "" ) ;
t.prno = 0 ;
t.ord = 0 ;

if ( pq -> front == -1 )
{
cout<<"\nQueue is Empty."<<endl;
return t ;
}

t = pq ->d[pq -> front] ;

pq -> d[pq -> front] = t ;
if ( pq -> front == pq -> rear )
pq -> front = pq -> rear = -1 ;
else

62
pq -> front++ ;

return t ;}

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide the
solution of following problems. Design the solutions of the problems in C++ and bring your code
to lab so that lab instructor should assess and grade it.

5.2 Problem description:

Write a program to implement a priority queue to store the objects of “person” class. “person”
class should contain attributes (privately defined) per_ssn (string), per_name (string), per_age
(int) and per_priority(int). “person” class should also contain member functions (publicly
defined); constructor, input and output functions. You are required to design a priority queue
class which should use static array implementation. Your queue class should contain constructor,
destructor (if required), enqueue, dequeue, displayElements operations and conditions to check
empty or full queue. The member function dequeue should remove an object of person class
which should have high priority number than that of object at front of queue.

5.3 Practices from home

5.3.1 Task-1
Compare FIFO circular queue with simple FIFO queue using static array and provide at
least three differences between these two implementations.
5.3.2 Task-2
List three real world examples in which priority queue structure is used.

6. Procedure& Tools
This section provides information about tools and programming procedures used for the
lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

63
6.2 Walk through Tasks [Expected time = 20mins]
By using Microsoft Visual Studio 2017, we can implement a program for a priority queue
using static array. Following figure 3 represent the source code view of this program in visual
studio. You are required to type this code and further debug and execute the program.

Figure 3: Implementation of a priority queue

64
Figure 4: Implementation of a priority queue

Figure 5: Implementation of a priority queue

65
Figure 6 shows output of program in figure 3, figure 4 and figure 5.

Figure 6: Output of program shown in figure 3, 4 and 5

7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and placesolution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 20 mins]

Write a program which should implement a circular queue using static array of size 10 (10
elements array), elements of array should be of integer (int) type. User will input values to be
inserted at rear of circular queue (enqueue) and also number of elements to be removed from
front of circular queue (dequeue). Your program should display the value of elements which are
being removed from circular queue. Program should also calculate and display the average of

66
elements which have been removed from circular queue. Implement the task using template
class.

7.2 Practice Task 2 [Expected time = 30 mins]

Implement a priority queue for interviewing candidates for a job position as Lecturer at CUST.
University has taken a written test and candidates have secured marks out of 50 in it. Now
candidates give his information (CV) and along with the marks in written test. You have to
prioritize the candidates on the basis of Experience (must be more than 3 years), Qualification
(must have done MS) and Written_test_marks (More marks high priority). Whenever panel calls
a candidate the person whose priority is highest must give the interview. Your program should
display all the candidates in the priority queue as well.
7.3 Practice Task 3 [Expected time = 30mins]
Write a program to implement Bill_paying Queue. Your Queue should store the Person Name,
CNIC and Age. Note that whenever a senior citizen comes in he/she should be given priority in
the queue.

7.4 Out comes

After completing this lab, student will be able to understand and develop programs related to
circular and priority queues using static arrays in C++ using Microsoft Visual Studio 2017
environment.

7.5 Testing
Test Cases for Practice Task-1
Sample Input Sample Output
Insert elements in rear of circular
queue:
2
3
4
5
7
8
6
9
11
1
Enter number of elements to be 2
removed from circular queue: 4
3
4
5
Average of removed values is: 3.5

67
Test Cases for Practice Task-2

Sample input/output:
Press 1 to enter Information
Press 2 to call for interview
Press 3 to view all Candidates
Enter choice: 1
Enter Name: Ali
Enter CNIC: XXXXX-XXXXXXX-X
Enter Qualification: MS
Enter Experience: 4
Enter Your Marks in Written Test: 35

Press 1 to enter Information

Press 2 to call for interview
Press 3 to view all Candidates
Enter choice: 1
Enter Name: Osama
Enter CNIC: XXXXX-XXXXXXX-X
Enter Qualification: MS
Enter Experience: 4
Enter Your Marks in Written Test: 40

Press 1 to enter Information

Press 2 to call for interview
Press 3 to view all Candidates
Enter choice: 1
Enter Name: Hamza
Enter CNIC: XXXXX-XXXXXXX-X

68
Enter Qualification: BS
Enter Experience: 4
Enter Your Marks in Written Test: 40

Press 1 to enter Information

Press 2 to call for interview
Press 3 to view all Candidates
Enter choice: 2
Osama please come in 5 minutes for interview

Press 1 to enter Information

Press 2 to call for interview
Press 3 to view all Candidates
Enter choice: 3
Osama
MS
4
40
Ali
MS
4
35
Hamza
BS
4
40
Test Cases for Practice Task-3

Sample input/output:

69
Press 1 to enter Information
Press 2 to call for bill Payment
Press 3 to view all persons
Enter choice: 1
Enter your Name: Firdous
Enter your CNIC: XXXXX-XXXXXXX-X
Enter your Age: 35

Press 1 to enter Information

Press 2 to call for bill Payment
Press 3 to view all persons
Enter choice: 1
Enter your Name: Ahmed Ali
Enter your CNIC: XXXXX-XXXXXXX-X
Enter your Age: 50

Press 1 to enter Information

Press 2 to call for bill Payment
Press 3 to view all persons
Enter choice: 1
Enter your Name: Zulfiqar
Enter your CNIC: XXXXX-XXXXXXX-X
Enter your Age: 40

Press 1 to enter Information

Press 2 to call for bill Payment
Press 3 to view all persons
Enter choice: 2

70
Ahmed Ali please come for billpayment.

8. Evaluation Task (Unseen) [Expected time = 60mins for two tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10. Further Readings

10.1 Web sites related to C++ tutorials related to circular and priority queues
1. https://www.tutorialspoint.com/cplusplus-program-to-implement-priority-queue
2. http://www.cplusplus.com/reference/queue/priority_queue/

10.2 Web sites containing supporting material

1. http://web.eecs.utk.edu/~bvz/cs302/notes/PQueues/

71
Lab Manual for Data Structures
Lab 6
Linked List Implementation

72
Lab 6: Linked List Implementation

1. Introduction

This lab will introduce concept of dynamic memory based data structures such as linked
lists. In case of some real world applications we don’t know about the storage requirements of
program before program execution, in that scenario dynamic data storage systems are useful. We
will learn about linear linked list structure and how linked lists are helpful to store data during
program execution.

1.1 Linear Linked Lists

A linked list is a collection of elements, called nodes. Every node (except the last node)
stores the address of the next node. Therefore, every node in a linked list has two components:
one to store the data and other to store the address, called the link, of the next node in the list.
The address of the first node in the list is stored in a separate location, called the head or first.

Figure 1 is a representation of a node.

Figure 1: Structure of a node

Linked list: A list of elements, called nodes, in which the order of the nodes is determined by the
address, called the link, stored in each node.

The list in Figure 2 is an example of a linear linked list.

Figure 2: Linear Linked List of nodes

We may perform different operations on linked lists such as inserting a node, deleting a node,
traversing a linked list etc.

1.2 Relevant Lecture Readings

f) Revise Lecture No. 11 and 12 available at \\fs\lectures$ in instructor’s folder.

g) From books: C++ Data Structures by Nell Dale (Page334 - 358) and Data structures
using C++ by D. S. Malik (Page 266 – 280, 326 – 338, 310 - 320).

73
2. Activity Time boxing

Table 1: Activity Time Boxing

Task Activity Name Activity time Total Time

No.
5.1 Design Evaluation 20mins 20mins
6.2 Walk through tasks 20mins 20mins
7 Practice tasks 20mins for task 1 , 30 mins 80mins
for task 2 and 30 mins for
task 3
9 Evaluation Task 60mins for all assigned tasks 50mins

3. Objectives of the experiment

• To understand and implement linear linked lists with their operations in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in
lab.

4.1 Linear Linked Lists in C++

Node of a linked list is a self-referential structure which can be represented by following code.

Struct nodeType
{
int info;
nodeType *link;
};

The basic operations of a linked list are as follows: Search the list to find out whether aparticular
item is in the list, insert an item in the list, and delete an item from the list.These operations
require the list to be traversed. That is, given a pointer to the first nodeof the list, we must step
through the nodes of the list. Following code segment helps in traversal.

74
current = head;
while (current != NULL)
{
//Process current
current = current->link;
}

This section discusses how to insert an item into, and delete an item from, a linked list.Consider
the following definition of a node. (For simplicity, we assume that the infotype is int.)

struct nodeType
{
int info;
nodeType *link;
};

We will use the following variable declaration:

nodeType *head, *p, *q, *newNode;

Suppose that p points to the node with info 65, and a new node with info 50 is to becreated and
inserted after p. Consider the following statements:

newNode = new nodeType; //create newNode

newNode->info = 50; //store 50 in the new node
newNode->link = p->link;
p->link = newNode;

To delete a node from linked list we can use following code segment.

75
q = p->link;
p->link = q->link;
delete q;

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

5.2 Problem description:

Write a program of linear linked list of objects of “person” class. Attributes of “person”
class (privately defined) are per_id (int), per_name (string) and per_age (int). “person”
class contains member functions (publicly defined): constructor, input and output
functions. You are required to define a class for linear linked list. This class should
contain the member functions to insert, delete nodes from linear linked list. This class
should also contain the member functions to display values of all nodes of linear linked
list.

5.3 Practices from home

5.3.1 Task-1
Compare linear linked list with circular linked list and provide three differences between
the two structures.
5.3.2 Task-2
List three real world examples in which linked list structures can be used.

6. Procedure& Tools
This section provides information about tools and programming procedures used for the
lab.

76
6.1 Tools

Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Walk through Tasks [Expected time = 20mins]

Following screens in figure 5 to 13represent source code implementation of a linear linked list
class in Microsoft Visual Studio 2017. You are required to type, debug and execute this program
in Microsoft Visual Studio 2017.

This linked list program provides different functions like addition of node at start of list,
deletion of node from list, displaying elements of list, addition of node at end of list, add a node
after some specific node in the list.

Figure 5: Implementation of linear linked list class in Visual Studio 2017

77
Figure 6: Implementation of linear linked list class in Visual Studio 2017

Figure 7: Implementation of linear linked list class in Visual Studio 2017

78
Figure 8: Implementation of linear linked list class in Visual Studio 2017

Figure 9: Implementation of linear linked list class in Visual Studio 2017

79
Figure 10: Implementation of linear linked list class in Visual Studio 2017

Figure 11: Implementation of linear linked list class in Visual Studio 201

80
Figure 12: Implementation of linear linked list class in Visual Studio 2017

Figure 13: Implementation of linear linked list class in Visual Studio 2017

81
7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and placesolution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 20mins]

Implement the following functions for linked list:
1) Insert front
2) Insert End
3) Insert after number
4) Delete front
5) Delete End
6) Delete any number from list
7) Display all element
8) Limit user so that he/she can only add 10 numbers in the list. After that give error that list
is full.

7.2 Practice Task 2 [Expected time = 20mins]

Use Practice task 1 and add two functions Remove_Duplicate() and Count() in the class.
Remove_Duplicate() function should remove all the number that are occurring more than one
time. Count() function should count the number of nodes present at any time in the list.

7.3 Practice Task 3 [Expected time = 30mins]

Manage data of Books (Title, Authors, Edition, Price) using linked list. Add Books in the list.
Now delete all Books having price more than 2000 from the list.

7.4 Out comes

After completing this lab, student will be able to understand and develop programs related to
linear linked lists, circular linked lists and doubly linked listsin C++ using Microsoft Visual
Studio 2017 environment.

7.5 Testing

82
Test Cases for Practice Task-1
Sample Input Sample Output
Enter the values of elements of
linked list:
2
3
4
5
7
8
6
9
11
1
Enter the value after which you New value inserted after 11
want to insert: 11
Enter the value to delete from Key value 5 is deleted from linked
linked list: 5 list.

Test Cases for Practice Task-2

Sample Input Sample Output
Enter the values of elements of
linked list:
12
33
43
12
52
12
52
After Removing duplicates:
33
43
Total nodes present in the list are: 2

Test Cases for Practice Task-3

Sample input/output:
Press 1 to add Book
Press 2 to delete Books having price more than 2000
Press 3 to display list
Enter choice:1
Enter Title: The Art of Computer Programming

83
Enter Authors: Donald Knuth
Enter Edition: 3
Enter Price: 1500
Press Y/y to continue: y

Press 1 to add Book

Press 2 to delete Books having price more than 2000
Press 3 to display list
Enter choice:1
Enter Title: Introduction to Algorithms
Enter Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein
Enter Edition: 3
Enter Price: 1000
Press Y/y to continue: y

Press 1 to add Book

Press 2 to delete Books having price more than 2000
Press 3 to display list
Enter choice:1
Enter Title: Programming Pearls
Enter Authors: Jon Bentley
Enter Edition: 2
Enter Price: 2000
Press Y/y to continue: y

Press 1 to add Book

Press 2 to delete Books having price more than 2000
Press 3 to display list
Enter choice:1
Enter Title: Algorithms + Data Structures = Programs
84
Enter Authors: Niklaus Wirth
Enter Edition: 2
Enter Price: 2500
Press Y/y to continue: y

Press 1 to add Book

Press 2 to delete Books having price more than 2000
Press 3 to display list
Enter choice:2
Algorithms + Data Structures = Programs has been deleted
Press Y/y to continue: y
n

8. Evaluation Task (Unseen) [Expected time = 60mins for two tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

85
10. Further Readings

10.1 Web sites related to C++ tutorials about linked lists

a) http://www.cprogramming.com/tutorial/lesson15.html
b) http://www.element14.com/community/community/code_exchange/blog/2013/03/2
6/c-tutorial--linked-list
c) http://www.dreamincode.net/forums/topic/31357-c-linked-lists-custom-linked-lists-
part-1/

10.2 Web sites containing supporting material

a) https://www.cpp.edu/~ftang/courses/CS240/lectures/slist.htm
b) http://www.baumann.info/public/cpp_lernaufgabe_linked_list.pdf

86
\

Lab Manual for Data Structures

Lab 7
Linked Lists as Stack and Queue

87
Lab7: Linked Lists as Stack and Queue

1. Introduction

Objective of this lab is to make you understand the usage of linked list structure for
implementation of stack and queue ADT (Abstract Data Types). If we need to maintain a stack
whose individual elements are allocated memory space during program execution, we need to
use linked list for that purpose, same is case for queue. In case of array based stacks and queues
we may only store finite number of elements which will be limited to maximum size of array.

1.1 Linked Lists as Stack

Stack can be implemented by linked lists structure. In this case we need to maintain a
pointer to node of linked list which always point to a node before the top of stack, when an
element is inserted in list it is placed at top of stack and when an element is removed it is also
removed from top of stack. In this way stacks can be used by linked list structures. As memory
of elements of stack is dynamically allocated so stack will never be filled (we don’t need to
check for stack overflow conditions). Figure 1 provides information about the use of stack as a
linked list structure.

Figure 1: Use of stack as a linked list structure.

1.2 Linked Lists as Queue

Because the size of the array to stock up the queue elements is fixed, only a finite number
of queue elements can be stored in the array. Also, the array implementation of the queue
requires the array to be handled in a special way together with the values of the indices
queueFront and queueRear. The linked list implementation of a queue simplifies many of the
special cases of the array implementation and, because the memory to store a queue element is
allocated dynamically, the queue is never full. It means we don’t need to check for queue
overflow condition, we need to maintain only queue underflow condition that is we need to
check whether queue is empty or not while removing an element from the queue.
1.3. Relevant Lecture Readings
88
ii. Revise Lecture No. 23 and 24 available at \\dataserver\jinnah$\ in instructor’s
folder.
iii. From books: C++ Data Structures by Nell Dale (Page280 - 317) and Data structures
using C++ by D. S. Malik (Page415 - 423).

2. Activity Time boxing

Table 1: Activity Time Boxing

Task Activity Name Activity time Total Time
No.
5.1 Design Evaluation 20mins 25mins
6.2 Walk through tasks 20mins 25mins
7 Practice tasks 30mins for task 1 and 30 60mins
mins for task 2
9 Evaluation Task 60mins for all assigned tasks 60mins

3. Objectives of the experiment

• To understand and implement stacks using linked lists with their operations in C++.
• To understand and implement queues using linked lists with their operations in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in
lab.

4.1 Linked Lists as Stack in C++

The first operation that isto be considered is the default constructor. The default constructor
initializes the stack to an empty state when an object of stack class is declared. Thus, this
function sets stackTop pointer to NULL. The definition of this function is as follows:

template<class Type>
linkedStackType<Type>::linkedStackType()
{
stackTop = NULL;
}

89
The operations isEmptyStack and isFullStack are easy to understand. The stack is empty if
stackTop is NULL. Also, because the memory for elements of stack is allocated and deallocated
dynamically, the stack is never full. Thus, the function isFullStack always returns the value false.
The definitions of the functions to implement these operations are asfollows:

template<class Type>
bool linkedStackType<Type>::isEmptyStack() const
{
return(stackTop == NULL);
} //end isEmptyStack
template<class Type>
bool linkedStackType<Type>::isFullStack() const
{
return false;
} //end isFullStack

Push operation for stack can be defined by following code segment.

template<class Type>
void linkedStackType<Type>::push(const Type &newElement)
{
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the node
newNode->info = newElement; //store newElement in the node
newNode->link = stackTop; //insert newNode before stackTop
stackTop = newNode; //set stackTop to point to the
//top node
} //end push

90
Pop operation for stack can be defined by following code segment.

template<class Type>
void linkedStackType<Type>::pop()
{
nodeType<Type> *temp; //pointer to deallocate memory
if(stackTop != NULL)
{
temp = stackTop; //set temp to point to the top node
stackTop = stackTop->link; //advance stackTop to the
//next node
delete temp; //delete the top node
}
else
cout<< "Cannot remove from an empty stack." <<endl;
}//end pop

4.2 Linked Lists as Queue in C++

Some operations related to implementation of queue as a linked list are provided in this
section. The queue is empty if queueFront pointer is NULL. Memory to store the queue elements
is allocated dynamically. Therefore, the queue is never full and so the function to implement the
isFullQueue operation returns the value false. Implementation of functions for checking empty or
full queue is given below:

template<class Type>
boollinkedQueueType<Type>::isEmptyQueue() const
{
return(queueFront == NULL);
} //end
template<class Type>

91
bool linkedQueueType<Type>::isFullQueue() const
{
return false;
} //end isFullQueue

The addQueue operation inserts a new element at the rear of the queue. To implement this
operation, we will use the pointer queueRear. If the queue is non-empty, the operation front
returns the first element of the queue and therefore the element of the queue indicated by the
pointer queueFront is returned. If thequeue is empty, the function front stops execution of
program. If the queue is nonempty, the operation back returns the last element of the queue and
so the element of the queue indicated by the pointer queueRear is returned. If the queue isempty,
the function back stops the execution of program. Similarly, if the queue is nonempty, the
operation deleteQueue removes the first element of the queue, and so we access the pointer
queueFront for this purpose. The definitions of the functions to implement these operations are
as follows:

template<class Type>
void linkedQueueType<Type>::addQueue(const Type&newElement)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>; //create the node
newNode->info = newElement; //store the info
newNode->link = NULL; //initialize the link field to NULL
if (queueFront == NULL) //if initially the queue is empty
{
queueFront = newNode;
queueRear = newNode;
}
else //add newNode at the end
{
queueRear->link = newNode;

92
queueRear = queueRear->link;
}
}//end addQueue

template<class Type>
Type linkedQueueType<Type>::front() const
{
assert(queueFront != NULL);
return queueFront->info;
} //end front

template<class Type>
Type linkedQueueType<Type>::back() const
{
assert(queueRear!= NULL);
return queueRear->info;
} //end back

template<class Type>
void linkedQueueType<Type>::deleteQueue()
{
nodeType<Type> *temp;
if (!isEmptyQueue())
{
temp = queueFront; //make temp point to the first node
queueFront = queueFront->link; //advance queueFront
delete temp; //delete the first node
if (queueFront == NULL) //if after deletion the

93
//queue is empty
queueRear = NULL; //set queueRear to NULL
}
else
cout<< "Cannot remove from an empty queue" <<endl;
}//end deleteQueue

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

5.2 Problem description:

Write a program of linear linked list to implement a stack and a queue of objects of
“person” class. Attributes of “person” class (privately defined) are per_id (int), per_name
(string) and per_age (int). “person” class contains member functions (publicly defined):
constructor, input and output functions. You are required to define two more classes: one
of these classes should define the linked list implementation of stack for objects of
“person” class, this class should contain member functions like push, pop, display and to
check whether stack is empty or not? Other class should define the linked list
implementation of queue for objects of “person” class, this class should contain the
member functions like addQueue, RemoveQueue, display and check whether the queue is
empty or not?

5.3 Practices from home

5.3.1 Task-1
Compare linked list implementations of stack and queue and find at least three
differences between these implementations.
5.3.2 Task-2
Provide one example of stack and one of queue from real world where linked list
implementations are useful.

94
6. Procedure& Tools
This section provides information about tools and programming procedures used for the
lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Walk through Tasks [Expected time = 25mins]

Following screens in figure 2, 3 and 4 represent source code implementation of a linear

linked list classas a stack in Microsoft Visual Studio 2017. You are required to type, debug and
execute this program in Microsoft Visual Studio 2017.

This linked list implementation of stack program provides functionality to use a stack. It
contains a structure to represent the nodes of linked list and a class named “stack” which will be
representing the stack as linked list. This class contains constructor, push, pop and display
member functions. In main function we create an object of stack class and call member functions
of class to push and pop elements from the stack.

Figure 2: Implementation of stack as a linked list

95
Figure 3: Implementation of stack as a linked list.

Figure 4: Implementation of stack as a linked list.

96
7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and placesolution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 30mins]

Write a program to implement a stack using linked list. Stack is of Books (Title, Author, Price).
your program should find or delete a book entered by user from the stack. Remember that to
reach a book in stack all the books above must be checked first.

7.2 Practice Task 2 [Expected time = 30mins]

Organization ABC is taking online orders from its customers. Save the following information for
each order:
OrderID (Auto incremented)
Customer name
Address
Number of items in the order
Payment of order
Orders will be processed on first come first server basis.

7.3 Out comes

After completing this lab, student will be able to understand and develop programs related to
linked list implementation of stacks and queuesin C++ using Microsoft Visual Studio 2017
environment.

7.4 Testing
Test Cases for Practice Task-1
Sample Input Sample Output
Enter a string:
Evil olive
Entered string is palindrome
Enter a string:
Computer
Entered string is not palindrome

Test Cases for Practice Task-2

97
Enter order details:
Customer name: Ali
Items:4
Total cost:10000

Customer name: Ahmed

Items:2
Total cost:1000

Customer name: Zain

Items:7
Total cost:25000

Customer name: Mariya

Items:1
Total cost:5000

Press 1 for case 1

Press 2 for case 2
Enter choice:1
Processed orders:
Customer name: Ali
Items:4
Total cost:10000

Customer name: Ahmed

Items:2
Total cost:1000

Customer name: Zain

98
Items:7
Total cost:25000

Customer name: Mariya

Items:1
Total cost:5000

8. Evaluation Task (Unseen) [Expected time = 60mins for two tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks

1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10. Further Readings

10.1 Web sites related to C++ tutorials about linked list implementation of stack
and queues
1. http://www.programming-techniques.com/2011/11/stack-and-queue-implementation-of.html

2. http://stackoverflow.com/questions/3600245/fifo-queue-linked-list-implementation

10.3 Web sites containing supporting material

1. http://www.cs.cmu.edu/~rjsimmon/15122-s13/09-queuestack.pdf

99
Lab Manual for Data Structures
Lab 8
Doubly Linked List and DECK Implementations

100
Lab 8: Doubly Linked List and DECK Implementations

1. Introduction

This lab will introduce concept of dynamic memory based data structures such as linked
lists. In case of some real world applications we don’t know about the storage requirements of
program before program execution, in that scenario dynamic data storage systems are useful. We
will learn about linear, circular and doubly linked list structures and how linked lists are helpful
to store data during program execution.

1.1 Doubly Linked Lists

A doubly linked list is a linked list in which every node has a next pointer and a back
pointer. In other words, every node contains the address of the next node (except the last node),
and every node contains the address of the previous node (except the first node). See Figure 4.

Figure 4: Doubly Linked List

1.2 Relevant Lecture Readings

iv. Revise Lecture No. 21 and 22 available at \\fs\lectures$ in instructor’s

folder.
v. From books: C++ Data Structures by Nell Dale (Page 334 - 358) and
Data structures using C++ by D. S. Malik (Page 266 – 280, 326 – 338,
310 - 320).

2. Activity Time boxing

Table 1: Activity Time Boxing

Task Activity Name Activity time Total Time

No.
5.1 Design Evaluation 20mins 20mins
6.2 Walk through tasks 20mins 20mins
7 Practice tasks 30 mins for task 1 and 40 70mins
mins for task 2
9 Evaluation Task 60mins for all assigned tasks 60mins

101
3. Objectives of the experiment
• To understand and implement linear linked lists with their operations in C++.
• To understand and implement circular linked lists with their operations in C++.
• To understand and implement doubly linked lists with their operations in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in
lab.

4.1 Doubly Linked Lists in C++

Insertion of a node in a doubly linked list involves some cases which are given below:
Case 1: Insertion in an empty list
Case 2: Insertion at the beginning of a nonempty list
Case 3: Insertion at the end of a nonempty list
Case 4: Insertion somewhere in a nonempty list
Following code segment can be used to insert a node in a doubly linked list:
template <class Type>
void doublyLinkedList<Type>::insert(const Type& insertItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
nodeType<Type> *newNode; //pointer to create a node
bool found;
newNode = new nodeType<Type>; //create the node
newNode->info = insertItem; //store the new item in thenode
newNode->next = NULL;
newNode->back = NULL;
if (first == NULL)//if list is empty,newNode is the only node
{
first = newNode;
last = newNode;
count++;

102
}
else
{
found = false;
current = first;
while (current != NULL && !found) //search the list
if (current->info >= insertItem)
found = true;
else
{
trailCurrent = current;
current = current->next;
}
if (current == first) //insert newNode before first
{
first->back = newNode;
newNode->next = first;
first = newNode;
count++;
}
else
{
//insert newNode between trailCurrent and current
if (current != NULL)
{
trailCurrent->next = newNode;
newNode->back = trailCurrent;
newNode->next = current;
current->back = newNode;

103
}
else
{
trailCurrent->next = newNode;
newNode->back = trailCurrent;
last = newNode;
}
count++;
}}}//end insert
To delete a node from a doubly linked list, following cases should be considered:

Case 1: The list is empty.

Case 2: The item to be deleted is in the first node of the list, which would require us to
change the value of the pointer first.
Case 3: The item to be deleted is somewhere in the list.
Case 4: The item to be deleted is not in the list.

template <class Type>

void doublyLinkedList<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == NULL)
cout << "Cannot delete from an empty list." << endl;
else if (first->info == deleteItem) //node to be deleted is
//the first node
{
current = first;

104
first = first->next;
if (first!= NULL)
first->back = NULL;
else
last = NULL;
count--;
delete current;
}
else
{
found = false;
current = first;
while (current != NULL && !found) //search the list
if (current->info >= deleteItem)
found = true;
else
current = current->next;
if (current == NULL)
cout << "The item to be deleted is not in "
<< "the list." << endl;
else if (current->info == deleteItem) //check for equality
{
trailCurrent = current->back;
trailCurrent->next = current->next;
if (current->next != NULL)
current->next->back = trailCurrent;
if (current == last)
last = trailCurrent;
count--;

105
delete current;
}
else cout << "The item to be deleted is not in list." <<endl;}

4.2 Double ended queue (DECK):

A double ended queue is an abstract data structure. It can be implemented either using a linked
list or an array. Its implementation depends upon the programmer. Think of it as a special type of
queue which can accept elements both at the head and the tail.

On the other hand, a doubly linked list is a concrete data structure, i.e. its implementation would
be same for every programmer. It is a way for storing data.

Following cases should be considered while implementing DECK:

Case 1: Insert at the start of the queue
Case 2: Delete from the start of queue
Case 3: Insert at the end of the queue
Case 4: Delete from the end of queue

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

5.2 Problem description:

Write a program of doubly linked list of objects of “person” class. Attributes of “person”
class (privately defined) are per_id (int), per_name (string) and per_age (int). “person”
class contains member functions (publicly defined): constructor, input and output
functions. You are required to define a class for doubly linked list. This class should
contain the member functions to insert, delete nodes from linked list. This class should
also contain the member functions to display values of all nodes of linked list.

106
5.3 Practices from home

5.3.1 Task-1
Compare linear linked list with doubly linked list and provide three differences between
the two structures.
5.3.2 Task-2
List three real world examples in which doubly linked list structures can be used.

6. Procedure & Tools

This section provides information about tools and programming procedures used for the lab.

6.1 Tools

Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Walk through Tasks [Expected time = 20 mins]

Following screens in figure 5 to7 represent source code implementation of a doubly

linked list class in Microsoft Visual Studio 2017. You are required to type, debug and execute
this program in Microsoft Visual Studio 2017.

This linked list program provides different functions like addition of node at start of list,
deletion of node from list, displaying elements of list.

Figure 5: Implementation of doubly linked list

107
Figure 6: Implementation of doubly linked list

Figure 7: Implementation of doubly linked list

108
7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and place solution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 30 mins]

Write a program which should implement All four cases as mentioned in section 4.2.

7.2 Practice Task 2 [Expected time = 40 mins]

Implement a program using Doubly LinkedList. Your doubly linked list should store information
of students (Reg_no., Name, CGPA, city, age). Your program should provide following
functionalities:
▪ Insert at Front
▪ Insert at Rear
▪ Insert in middle
▪ Delete from front
▪ Delete from rear
▪ Delete from middle
▪ Display all the data

7.3 Out comes

After completing this lab, student will be able to understand and develop programs related to
linear linked lists, circular linked lists and doubly linked lists in C++ using Microsoft Visual
Studio 2017 environment.

8. Midterm [Expected time = 60 mins for two tasks]

The lab instructor will give you midterm exam.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

109
Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10.Further Readings
10.1 Web sites related to C++ tutorials about linked lists
1. http://www.cprogramming.com/tutorial/lesson15.html
2. http://www.element14.com/community/community/code_exchange/blog/2013/03/26/
c-tutorial--linked-list

10.2 Web sites containing supporting material

1. http://www.learnerstv.com/Free-Computer-Science-Video-lectures-ltv733-Page1.htm
2. http://www.cphstl.dk/Report/Double-ended-priority-queues/paper.pdf

110
Lab Manual for Data Structures
Lab-9
Recursion in C++

111
Lab9: Recursion in C++
1. Introduction

Objective of this lab is to provide you knowledge about recursion in C++. You have
come to know about the basic concepts about C++ language in courses: computer programming
and object oriented programming. You have learned about the statements used in this language
like input/output statements, selection statements (if..else, switch) and iterative statements/loops
(while, do..while, for). Further you will also have knowledge about classes, encapsulation,
inheritance and polymorphism.

In C++, every application/program contains a function called main(), which is a global

function. Execution of every program starts from this function, so you have to write this function
in each C++ program. You may write other functions also in your program beside main()
function, which depends on modular solution you have developed to solve your problem.

1.1 Basic Concepts about Data Structures

A program is a set of instructions that processes data which is given as input to it. If we
need to develop a good (efficient) program, we need to organize data in computer’s memory in
effective way. This organized data is called a Data Structure.

Study of computer science includes the study of how data (information) is organized in
computer and how it can be manipulated and utilized by programs. It is extremely important for
you to understand the concepts of data (information) organization and manipulation. Data
structures for storing information are lists, stacks, queues, trees, graphs and tables.

1.2 Recursion in C++

The process in which a function calls itself is known as recursion and the corresponding
function is called the recursive function. In recursion function there is a base condition which is
very important; without this base condition the function cannot execute properly. The purpose of
recursion is to divide the problem into smaller problems till the base condition is reached.

1.2.1 Direct recursion:

When function calls itself, it is called direct recursion, the example we have seen above is a
direct recursion example.

112
1.2.2 Indirect recursion:
When function calls another function and that function calls the calling function, then this is
called indirect recursion. For example: function A calls function B and Function B calls function
A.

1.3 Relevant Lecture Readings

a) From books: C++ Data Structures by Nell Dale (Page79-85) and Data structures using
C++ by D. S. Malik (Page130-135).
b) From books: C++ Data Structures by Nell Dale (Page 99-102) and Data structures
using C++ by D. S. Malik (Page 138-145).

2. Activity Time boxing

Table 1: Activity Time Boxing

Task Activity Name Activity time Total Time
No.
5.1 Design Evaluation 15 mins 15 mins
6.2 Editing and compiling a C++ 5mins 5mins
program in Visual Studio
2017
6.3 Walk Through Task 20mins 20mins
7 Practice tasks 80 mins for task 1,2 ,3 and 4 80mins
9 Evaluation Task 60mins for all assigned task 50mins

3. Objectives of the experiment

• To get basic understanding of recursion function.
• To write programs in C++ using Microsoft Visual Studio 2017 environment.
• To get an understanding of identifying basic errors in a C++ program by using debugging
techniques.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in
lab.

4.1 Recursion in C++

In C++ recursion is used when a function calls itself again and again. The popular
example to understand the recursion is factorial function.
Example:

113
4.2 Implementation of Recursion function in C++

A function that calls itself is known as recursive function. And, this technique is known as
recursion.

114
The recursion continues until some condition is met.

To prevent infinite recursion, if...else statement (or similar approach) can be used where one
branch makes the recursive call and other doesn't.

4.3 Example

115
5 Homework before Lab
This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

116
5.2 Problem description:
Design a program which should contain a recursive function for calculating sum of all
natural numbers up to a number given by user.

6 Procedures & Tools

This section provides information about tools and programming procedures used for the
lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Editing, Compiling and Running programs in Visual Studio 2017 [Expected
time = 5mins]

You are required to use Microsoft Visual Studio 2017 environment for programming on
data structures. It is expected that you are already familiar with this environment in your courses
of Computer Programming and Object Oriented Programming. You should be able to write code
in source code files (cpp files) and perform compilation of code. Beside that you are also
required to be proficient in performing line by line debugging and break point based debugging
to remove the errors from your code.

6.3 Walk through Task [Expected time = 20mins]

Following program represents the concept related to static and dynamic arrays; you are
required to type this program in editor of Visual Studio 2017, compile and run to see the output
of this program. Figure 3 shows the source code window of this program in Visual Studio 2017.

117
Figure 3: A program about recursion function in Visual Studio 2017.

Output of this program is shown in figure 4, when program is compiled and executed.

Figure 4: Output window displaying results of program after compilation.

118
7 Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and place solution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Estimated time: 20 min]

Write a C++ program to which will create a static array of size 10 now pass this array to a
function which will print the array elements using recursion.

7.2 Practice Task 2 [Estimated time: 20 min]

Create a C++ program to check a number is a prime number or not using recursion

7.3 Practice Task 3 [Estimated time: 20 min]

Create a C++ program which takes two integers from user. Your program should also have a
recursive function which will display odd numbers between the ranges given by user.

7.4 Practice Task 4 [Estimated time: 20 min]

Write a program to create a static character array. Write a recursive function FindPalindrome
which should tell whether or not the entered set of characters is palindromic sequence.
Sample input:
Enter the sequence of characters:
After insertion:
M O m

Sample output:
Entered sequence of characters is palindrome.

7.5 Out comes

After completing this lab, student will be able to understand and develop programs related to
static and dynamic arrays in C++ using Microsoft Visual Studio 2017 environment.

119
8. Evaluation Task (Unseen) [Expected time = 60mins for two
tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).
Table 2: Evaluation of the Lab
Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7 Practice tasks and Testing 35
4 8 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10. Further Readings

10.1 C++ Tutorial Web Sites
a) http://www.cplusplus.com/doc/tutorial/
b) http://www.learncpp.com/
c) http://www.tutorialspoint.com/cplusplus/

10.2 Web sites containing supporting material

a) http://www.compgeom.com/~piyush/teach/3330/slides/

120
Lab Manual for Data Structures
Lab 10
Binary Search Trees using Linked List and their Traversals

121
Lab 10: Binary Search Trees using Linked List and their
Traversals

1. Introduction

In this lab, we will discuss the usage of binary trees and binary search trees using linked
list notations. We will see that how we may insert and remove nodes from binary trees and how
pre order, post order and in order traversal can be performed on binary trees. We will further see
that how search operation can be performed on binary search trees which are stored using a
linked list notation.

1.1 Binary Trees as a Linked List

A binary tree is used for storing and retrieving data rapidly. A binary tree is composed of
a parent node and child nodes which are connected with parent node and this structure may be
further repeated as required in tree. Binary trees can be represented using linked list structures.
Figure 1 represents the linked list structure of a binary tree. Each node

Figure 1: Binary Tree as a Linked List structure

1.2 Binary Search Tree as Linked List

Binary search tree is sorted or ordered binary search tree, for which search operations can
be performed effectively. The left sub tree contains the nodes with keys less than that of root
node key and right sub tree contains nodes with keys greater than that of root node key. Both left
and right sub trees must be binary search trees. Binary search trees can also be represented using
linked list structure. Each node in tree is connected with other node using pointer variables. Each
node contains two pointers called left and right pointers. A leaf node contains left and right
pointers which are NULL. Left pointer of root node points to left sub tree and right pointer of
root node points to right sub tree.

122
1.3 Traversals in Binary Tree

When we need to insert, update or lookup items in a binary tree we need to perform
traversal of tree. Traversal of a binary tree means visiting each node of binary tree. Traversal
must start from the root node, for each node we have two options to traverse

• Visit the node first.

• Visit the sub tree first.

These choices lead to three different traversals of a binary tree—in order, preorder, and post
order.

In order Traversal: In an in order traversal, the binary tree is traversed as follows:

1. Traverse the left subtree.

2. Visit the node.
3. Traverse the right subtree.

Pre order Traversal: In a pre-order traversal, the binary tree is traversed as follows:

1. Visit the node.

2. Traverse the left subtree.
3. Traverse the right subtree.

Post order Traversal: In a post order traversal, the binary tree is traversed as follows:

1. Traverse the left subtree.

2. Traverse the right subtree.
3. Visit the node.

For a binary tree shown in figure 2 following are results of pre order, in order and post
order traversals.

Figure 2: A binary tree for traversal.

123
In order sequence: B D A C
Pre order sequence: A B D C
Post order sequence: D B C A

1.4 Relevant Lecture Readings

a. Revise Lecture No. 25 and 26 available at \\fs\lectures$ in instructor’s

folder.
b. From books: C++ Data Structures by Nell Dale (Page 456 - 503) and Data
structures using C++ by D. S. Malik (Page 600 - 626).

2. Activity Time boxing

Table 1: Activity Time Boxing

Task Activity Name Activity time Total Time

No.
5.1 Design Evaluation 20mins 10mins
6.2 Walk through tasks 20mins 10mins
7 Practice tasks 30 min for task 1, 30min for 90mins
task 2 and 30 min for task 3
9 Evaluation Task 60mins for all assigned tasks 60mins

3. Objectives of the experiment

• To understand and implement binary trees using linked lists with their operations in C++.
• To understand and implement binary search trees using linked lists in C++.
• To understand and implement pre order, post order and in order traversals on binary trees
and binary search trees using recursive functions in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in lab.

4.1 Binary Search Trees using Linked List in C++

Following are some operations performed on a binary search tree:

Searching in a BST
o Examine the root node. If tree is NULL value doesn't exist.
o If value equals the key in root search is successful and return.
o If value is less than root, search the left sub-tree.
o If value is greater than root, search the right sub-tree.
124
o Continue until the value is found or the sub tree is NULL.

Insertion in BST
o Insertion begins as a search.
o Compare the key with root. If not equal search the left or right sub tree
o When a leaf node is reached add the new node to left or right based on the value.

Deletion in BST
o There are three possible cases to consider:
o Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply
remove it from the tree.
o Deleting a node with one child: Remove the node and replace it with its child.
o Deleting a node with two children: Call the node to be deleted N. Do not delete N.
Instead, choose either its in-order successor node or its in-order predecessor node,
R. Replace the value of N with the value of R, and then delete R.

Following code segment provides representation of binary search tree operations:

#include <iostream>
using namespace std;
class Node {
int key;
Node* left;
Node* right;
Node* parent;
public:
Node() { key=-1; left=NULL; right=NULL; parent = NULL;};
void setKey(int aKey) { key = aKey; };
void setLeft(Node* aLeft) { left = aLeft; };
void setRight(Node* aRight) { right = aRight; };
void setParent(Node* aParent) { parent = aParent; };
int Key() { return key; };
125
Node* Left() { return left; };
Node* Right() { return right; };
Node* Parent() { return parent; };
};
class Tree {
Node* root;
public:
Tree();
~Tree();
Node* Root() { return root; };
void addNode(int key);
Node* findNode(int key, Node* parent);
void walk(Node* node);
void deleteNode(int key);
Node* min(Node* node);
Node* max(Node* node);
Node* successor(int key, Node* parent);
Node* predecessor(int key, Node* parent);
private:
void addNode(int key, Node* leaf);
void freeNode(Node* leaf);
};

4.2 Binary Tree Traversals

There are three types of traversal of binary trees. Post order, in order and pre order
traversals. We will discuss code segments to be used for traversal of a binary tree which is
represented by an array.

Pre Order Traversal:

126
Algorithm Preorder(Tree[1:N], root)
* Tree is the array holding the tree
* root is the subscript of the root node
* The empty positions in an array are denoted by -1
1. Print Tree[root]
2. if(Tree[2*root] ≠ -1) // Does a left child exist
3. call Preorder(Tree[], 2 * root)
4. end if
5. if ( Tree[2*root+1] ≠ -1) // Does a right child exist
6. call Preorder(Tree[], 2 * root+1)
7. end if
8. end Preorder

Post Order Traversal:

Algorithm Postorder(Tree[1:N], root)
* Tree is the array holding the tree
*root is the subscript of the root node
*The empty positions in an array are denoted by -1

1. if(Tree[2*root] ≠ -1) // Does a left child exist

2. call Postorder(Tree[], 2 * root)
3. end if
4. if ( Tree[2*root+1] ≠ -1) // Does a right child exist
5. call Postorder(Tree[], 2 * root+1)
6. end if
7. Print Tree[root]
8. end Postorder

127
In Order Traversal:
Algorithm Inorder(Tree[1:N], root)
* Tree is the array holding the tree
* root is the subscript of the root node
* The empty positions in an array are denoted by -1

1. if(Tree[2*root] ≠ -1) // Does a left child exist

2. call Inorder(Tree[], 2 * root)
3. end if
4. Print Tree[root]
5. if ( Tree[2*root+1] ≠ -1) // Does a right child exist
6. call Inorder(Tree[], 2 * root+1)
7. end if
8. end Inorder

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

5.2 Problem description:

Write a program of binary search tree using linked list for objects of “person” class.
Attributes of “person” class (privately defined) are per_id (int), per_name (string) and
per_age (int). “person” class contains member functions (publicly defined): constructor,
input and output functions. You are required to define two more classes: one of these
classes should define the node implementation of linked list for objects of “person” class.
Other class should define the binary tree implementation for objects of “person” class,
this class should contain the member functions like insert, search, delete, pre order, and
post order and in order traversals of binary tree.

128
5.3 Practices from home
5.3.1 Task-1
Provide differences between binary tree and binary search tree implementations using
linked list structures.

6. Procedure & Tools

This section provides information about tools and programming procedures used for the
lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Walk through Tasks [Expected time = 20 mins]

Following screens in figure 2 to 10 represent source code implementation of a binary

search tree using linked list implementation in Microsoft Visual Studio 2017. You are required to
type, debug and execute this program in Microsoft Visual Studio 2017

129
Figure 2: Binary search tree using linked list implementation.

Figure 3: Binary search tree using linked list implementation

130
Figure 4: Binary search tree using linked list implementation.

Figure 5: Binary search tree using linked list implementation.

131
Figure 6: Binary search tree using linked list implementation.

Figure 7: Binary search tree using linked list implementation.

132
Figure 8: Binary search tree using linked list implementation.

Figure 9: Binary search tree using linked list implementation.

Figure 10: Binary search tree using linked list implementation.

133
7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and place solution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 30 mins]

Create a BST of user defined values. Keep asking user values until he/she enters any negative
number. Now display the elements of the tree in In-order, Post-order and Pre-order form. Your
program should also contain a search function which should find a particular number entered by
user. Search function should be recursive.

7.2 Practice Task 2 [Expected time = 20 mins]

Modify question 1 and add a function in the program called “Display_less”. Function should ask
user to enter a number then display all elements from the tree that are less than or equal to the
number. Note that the number may not be present in the tree.

7.3 Practice Task 3 [Expected time = 30 mins]

Implement a C++ program to store Strings in Binary Search tree. Your program should have
following functions:
• Insert
• Display
• Search

7.4 Out comes

After completing this lab, student will be able to understand and develop programs related to
linked list implementation of binary trees and binary search trees in C++ using Microsoft Visual
Studio 2017 environment.

7.5 Testing
Test Cases for Practice Task-1

Sample Input Sample Output

Enter the values of elements for
binary search tree linked list:
2.3
3.4
1.5
5.6
2.1
1.9
Pre order: 2.3 2.1 1.9 1.5 3.4 5.6

134
Post order: 1.5 1.9 2.1 5.6 3.4 2.3
In order: 1.5 1.9 2.1 2.3 3.4 5.6

8. Evaluation Task (Unseen) [Expected time = 60 mins for two tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10. Further Readings

10.1 Web sites related to C++ tutorials about linked list implementation of
binary trees
1. http://www.dreamincode.net/forums/topic/10157-data-structures-in-c-tutorial/
2. http://www.dailyfreecode.com/Code/binary-search-tree-operations-1152.aspx

10.2 Web sites containing supporting material

1. http://web.eecs.utk.edu/~bvz/teaching/cs140Fa09/lecture_notes.html

135
Lab Manual for Data Structures
Lab 11
Binary Search Trees Iterative Traversals

136
Lab 11: Binary Search Trees Iterative Traversals

1. Introduction
This lab will introduce concept of generic binary trees, how they can be used to store
information. Further this lab will provide information about concept of performing different
traversal operations like pre order, in order and post order on binary trees.

1.1 Iterative Traversals in Binary Search Tree

When we need to insert, update or lookup items in a binary tree we need to perform
traversal of tree. Traversal of a binary tree means visiting each node of binary tree. Traversal
must start from the root node, for each node we have two options to traverse

• Visit the node first.

• Visit the sub tree first.

These choices lead to three different traversals of a binary tree—inorder, preorder, and post
order.

In order Traversal: In an in order traversal, the binary tree is traversed as follows:

1. Traverse the left subtree.

2. Visit the node.
3. Traverse the right subtree.

Pre order Traversal: In a pre-order traversal, the binary tree is traversed as follows:

1. Visit the node.

2. Traverse the left subtree.
3. Traverse the right subtree.

Post order Traversal: In a post order traversal, the binary tree is traversed as follows:

1. Traverse the left subtree.

2. Traverse the right subtree.
3. Visit the node.

For a binary tree shown in figure 2 following are results of pre order, in order and post
order traversals.

138
Figure 2: A binary tree for traversal

In order sequence: B D A C
Pre order sequence: A B D C
Post order sequence: D B C A

1.2 Relevant Lecture Readings

a) Revise Lecture No. 19 and 20 available at \\fs\lectures$ in instructor’s folder.

b) From books: C++ Data Structures by Nell Dale (Page 477 - 490) and Data structures
using C++ by D. S. Malik (Page 600 - 615).

2. Activity Time boxing

Table 1: Activity Time Boxing

Task Activity Name Activity time Total Time

No.
5.1 Design Evaluation 20mins 20mins
6.2 Walk through tasks 20mins 20mins
7 Practice tasks 30 mins for task 1 and 40 70mins
mins for task 2
9 Evaluation Task 60mins for all assigned tasks 60mins

3. Objectives of the experiment

• To understand implementation of binary trees in C++.
• To understand the implementation of binary tree traversals in C++.
• To understand the implementation of recursive functions for binary tree traversal in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in
lab.

139
4.1 Binary Tree Traversals

There are three types of traversal of binary trees. Post order, in order and pre order
traversals. We will discuss code segments to be used for traversal of a binary tree which is
represented by an array.

Pre Order Traversal:

Algorithm Preorder (Tree[1:N], root)
1. Create an empty stack node Stack and push root node to stack.
2. Do following while node Stack is not empty.
i. Pop an item from stack and print it.
ii. Push right child of popped item to stack
iii. Push left child of popped item to stack
Post Order Traversal:
Algorithm Postorder(Tree[1:N], root)
1.Push the root node to the first stack.
2.Pop a node from the first stack, and push it to the second stack.
3.Then push its left child followed by its right child to the first stack.
4.Repeat step 2) and 3) until the first stack is empty.
5.Once done, the second stack would have all the nodes ready to be traversed in
post-order. Pop off the nodes from the second stack one by one and you’re done.
In Order Traversal:
Algorithm Inorder(Tree[1:N], root)
1. Start from the root, let’s it is current.
2. If current is not NULL, push the node on to stack.
3. Move to left child of current and go to step 2.
4. If current is NULL, and stack is not empty, pop node from the stack.
5. Print the node value and change current to right child of current.
6. Go to step 2.

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

140
5.2 Problem description:
Write a program of general binary tree using array. Elements of this array will be objects
of person class. Attributes of Book (privately defined) are
1. ISBN (String) (e.g. 1235-123-1)
2. author_name (string)
3. Edition (int)
Book class contains member functions (publicly defined): constructor, input and output
functions. You are required to define insert, delete and search functions for this binary
tree. Insert function should allow insertion of object of book class at appropriate location
in general binary tree, delete should delete an object of book class from tree whose ISBN
is specified by user. Search function should search an object of book class from this tree
whose ISBN is specified by user. You are required to implement pre order, in order and
post order traversal functions for this binary tree.

5.3 Practices from home

5.3.1 Task-1
Distinguish between recursive and iterative traversal in binary trees.

6. Procedure & Tools

This section provides information about tools and programming procedures used for the
lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Walk through Tasks [Expected time = 20 mins]

Following screens in figure 3 represent the implementation of binary tree using array in
Microsoft Visual Studio 2017 for in order traversal. You are required to type, debug and execute
this program in Microsoft Visual Studio 2017.

141
Post Order Iterative Traversal implementation:

Figure 1: Implementation of post order traversal of a binary tree.

7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and place solution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 30 mins]

Write a program which should implement a binary search tree using link list. User will provide
values as input. Your program should allow searching of a value specified by user in tree using
pre-order iterative traversal.

7.2 Practice Task 2 [Expected time = 40

mins]
Write a program which should implement a binary search tree using link list. User will provide
values as input. Your program should create two BST objects and take values in both of the

142
trees. Now pass the objects to a function which will display the intersection (common nodes) of
two trees. Note: Function must be iterative.

7.3 Out comes

After completing this lab, student will be able to understand and develop programs related to
operate general binary trees using linked list in C++ using Microsoft Visual Studio 2017
environment. Further students will be able to implement iterative traversal operations like pre
order, in order and post order traversal on general binary trees in C++.

8. Evaluation Task (Unseen) [Expected time = 60 mins for two tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10. Further Readings

10.1 Web sites related to C++ tutorials about binary search trees using arrays
1. http://www.dreamincode.net/forums/topic/201471-binary-tree-in-array/
2. http://cslibrary.stanford.edu/110/BinaryTrees.html

10.2 Web sites containing supporting material

1. http://www.cpp-home.com/tutorials/151_1.htm

143
Lab Manual for Data Structures
Lab 12
AVL Trees

144
Lab 12: AVL Trees and Heaps

1. Introduction
In this lab, we will discuss the usage of AVL (Adelson-Velskii and Landis' tree) and heap
data structures. AVL trees are called self-balancing binary search trees. We will see how to
perform insert, remove and search operations on AVL trees.

1.1 AVL Trees

An AVL tree (Adelson-Velskii and Landis' tree, named after the inventors) is a self-
balancing binary search tree. In an AVL tree, the heights of the two child sub trees of any node
are different by at most one; if at any time they be at variance by more than one, rebalancing is
done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the
average and worst cases, where n is the number of nodes in the tree proceeding to the operation.
Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

Figure 1 shows a representation of AVL Tree.

Figure 1: Representation of AVL Tree.

1.2 Relevant Lecture Readings

i. Revise Lecture No. 29 and 30 available at \\fs\lectures$ in instructor’s

folder.
ii. From books: C++ Data Structures by Nell Dale (Page 535 - 546) and Data
structures using C++ by D. S. Malik (Page 635 - 653).

2. Activity Time boxing

145
Table 1: Activity Time Boxing
Task Activity Name Activity time Total Time
No.
5.1 Design Evaluation 20mins 20mins
6.2 Walk through tasks 20mins 20mins
7 Practice tasks 30 mins for task 1, 20min for 80mins
task 2 and 30 mins for task 3
9 Evaluation Task 60mins for all assigned tasks 50mins

3. Objectives of the experiment

• To understand and implement AVL trees with their operations in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered in
lab.

4.1 AVL Trees in C++

An AVL tree is a special type of binary tree that is always "partially" balanced. The criteria that
is used to determine the "level" of "balanced-ness" is the difference between the heights of
subtree of a root in the tree. The "height" of tree is the "number of levels" in the tree. Or to be
more formal, the height of a tree is defined as follows:

The height of a tree with no elements is 0

The height of a tree with 1 element is 1
The height of a tree with > 1 element is equal to 1 + the height of its tallest subtree.

An AVL tree is a binary tree in which the dissimilarity between the height of the right and left
sub trees (or the root node) is never more than one.

#include <iostream>
using namespace std;
struct AVLTreeNode
{
int key;
// Other data fields can be inserted here
AVLTreeNode *left;

146
AVLTreeNode *right;
AVLTreeNode *parent;
char balanceFactor;
};
class Code203_Tree
{
private:
AVLTreeNode *root;
public:
Code203_Tree(); // Constructor
~Code203_Tree(); // Destructor
void Insert(AVLTreeNode *n);
void restoreAVL(AVLTreeNode *ancestor, AVLTreeNode *newNode);
void adjustBalanceFactors(AVLTreeNode *end, AVLTreeNode *start);
void rotateLeft(AVLTreeNode *n);
void rotateRight(AVLTreeNode *n);
void adjustLeftRight(AVLTreeNode *end, AVLTreeNode *start);
void adjustRightLeft(AVLTreeNode *end, AVLTreeNode *start);
// void Delete(int key); // Not implemented yet
void PrintTree();
private:
void ClearTree(AVLTreeNode *n);
void Print(AVLTreeNode *n);
};
#endif

147
5. Homework before Lab
This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to provide
the solution of following problems. Design the solutions of the problems in C++ and
bring your code to lab so that lab instructor should assess and grade it.

5.2 Problem description:

Write a program of AVL tree using linked list for objects of “person” class. Attributes of
“person” class (privately defined) are per_id (int), per_name (string) and per_age (int).
“person” class contains member functions (publicly defined): constructor, input and
output functions. You are required to define two more classes: one of these classes should
define the node implementation of linked list for objects of “person” class. Other class
should define the AVL tree implementation for objects of “person” class; this class
should contain the member functions like insert, search, delete and rotate for AVL trees.

5.3 Practices from home

5.3.1 Task-1
Compare AVL (self balancing) trees and balanced binary trees and find at least three
differences between these two implementations.
5.3.2 Task-2
Provide algorithmic representation of rotate function for AVL tree.

6. Procedure & Tools

This section provides information about tools and programming procedures used for the
lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

6.2 Walk through Tasks [Expected time = 20 mins]

Following screens in figure 2 to 6 represent the implementation of AVL tree. You are
required to code and execute this program in Microsoft Visual Studio 2017.

148
Figure 2: Implementation of AVL tree.

Figure 3: Implementation of AVL tree.

149
Figure 4: Implementation of AVL tree.

150
Figure 5: Implementation of AVL tree.

151
Figure 6: Implementation of AVL tree.

7. Practice Tasks
This section will provide information about the practice tasks which are required to be performed
in lab session. Design solutions of problems discussed in each task and place solution code in a
folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 20 mins]

Write a program to implement an AVL tree for integer values. User should be allowed to insert
values in tree and program should perform in order, pre order and post order traversals of this
tree.
152
7.2 Practice Task 2

Modify Task 1 and add a delete function in it. User will enter a number your function should first
search that number and then it should delete the number from the tree. The tree must remain
balanced after deletion.

7.3 Practice Task 3 [Expected time = 30

mins]

Write a program which should implement an AVL tree using linked list. Elements of tree are
objects of “student” class. “student” class contains attributes (privately defined) reg_no(int),
st_name (string) and cgpa (float). “student” class should also contain member functions
(publically defined); constructor, input and output functions. User will insert objects of class
“student” in AVL tree, values of attributes of objects will be provided by user. Program should
display the objects of student class in pre order, post order and in order traversal formats.
Program should also search an object from tree which is provided by user as input.

7.4 Out comes

After completing this lab, student will be able to understand and develop programs related to
AVL trees and heap trees in C++ using Microsoft Visual Studio 2017 environment.

7.5 Testing

Test Cases for Practice Task-1

Sample Input Sample Output
Enter the values for elements of
AVL tree:
2
3
4
5
6
Pre order traversal: 2 3 5 4 6
Post order traversal: 5 3 6 4 2
In order traversal: 5 3 2 6 4

153
Test Cases for Practice Task-3

Sample Input Sample Output

Insert elements in AVL tree:
Regno: 2
Name: ahmad
Cgpa: 2.35
Regno: 3
Name: Ali
Cgpa: 3.33
Regno: 4
Name: Amjad
Cgpa: 2.21
Enter the regno to find in the tree:
4
Following element is found in tree
Regno: 4
Name: Amjad
Cgpa: 2.21
Pre order: 2 3 4
Post order: 3 4 2

8. Evaluation Task (Unseen) [Expected time = 60 mins for two tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab whether
the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks
1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

154
10. Further Readings
10.1 Web sites related to C++ tutorials about AVL and Heap trees

1. http://www.cs.uah.edu/~rcoleman/Common/CodeVault/Code/Code203_Tree.html
2. http://www.cplusplus.com/reference/algorithm/make_heap/

10.2 Web sites containing supporting material

1. http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture04.pdf

155
Lab Manual for Data Structures
Lab 13
Heaps

156
Lab 13: Heaps

1. Introduction
In this lab, we will discuss the usage of heap data structures. Students will be able to
grasp the concept of heap trees. We will discuss the different operations to be performed on
heap trees.

1.1 Heap Trees

In computer science, a heap is a particular tree-based data structure that satisfies the
heap property: If A is a parent node of B then key (A) is ordered with respect to key (B) with
the same ordering apply across the heap. Either the keys of parent nodes are always greater
than or equal to those of the children and the highest key is in the root node (this kind of heap
is called max heap) or the keys of parent nodes are less than or equal to those of the children
and the lowest key is in the root node (min heap). Heaps are critical in several efficient graph
algorithms such as Dijkstra's algorithm, and in the sorting algorithm heap sort.

Note that there is no implied ordering between siblings or cousins and no implied sequence for
an in-order traversal (as there would be in, e.g., a binary search tree). The heap relation
mention above applies only between nodes and their immediate parents. The maximum number
of children each node can have depends on the type of heap, but in many types it is at most
two, which is known as a "binary heap". Figure 2 represents a complete binary max heap tree.

Figure 1: A complete binary max heap tree.

1.2 Relevant Lecture Readings

a) Revise Lecture No. 29 and 30 available at \\dataserver\jinnah$\ in instructor’s folder.

b) From books: C++ Data Structures by Nell Dale (Page 535 - 546) and Data structures
using C++ by D. S. Malik (Page 635 - 653).

157
2. Activity Time boxing
Table 1: Activity Time Boxing
Task Activity Name Activity time Total Time
No.
5.1 Design Evaluation 20mins 20mins
6.2 Walk through tasks 20mins 30mins
7 Practice tasks 30 mins for task 1 and 30 60mins
mins for task 2
9 Evaluation Task 60mins for all assigned tasks 60mins

3. Objectives of the experiment

• To understand and implement the heap trees with their operations in C++.

4. Concept Map
This concept map will help students to understand the main concepts of topic covered
in lab.

4.1 Heap Trees in C++

Heap is a binary tree that stores priorities (or priority-element pairs) at the nodes. It has
the following properties:
• All levels except last level are full. Last level is left filled.
• Priority of a node is at least as large as that of its parent (min-heap) (or) vice-versa
(max-
heap).
• If the smallest element is in the root node, it results in a min-heap.
• If the largest element is in the root node, it results in a max-heap.

Following is a class definition of heap tree:

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
class Heap {
public:
Heap();

158
~Heap();
void insert(int element);
int deletemin();
void print();
int size() { return heap.size(); }
private:
int left(int parent);
int right(int parent);
int parent(int child);
void heapifyup(int index);
void heapifydown(int index);
private:
vector<int> heap;
};

5. Homework before Lab

This homework will help students to study the concepts of topic before start of lab.

5.1 Problem Solution Modeling

After studying the introduction and concept map sections you should be ready to
provide the solution of following problems. Design the solutions of the problems in
C++ and bring your code to lab so that lab instructor should assess and grade it.

5.2 Practices from home

5.2.1 Task-1
Provide difference between a heap and an AVL tree.

6. Procedure & Tools

This section provides information about tools and programming procedures used for the
lab.

6.1 Tools
Microsoft Visual Studio 2017 with Visual C++ compiler configured.

159
6.2 Walk through Tasks [Expected time = 20 mins]
Following screens in figure 2 to 5 represent the implementation of a heap tree. You are
required to code and execute this program in Microsoft Visual Studio 2017.

Figure 2: Implementation of a heap tree

Figure 3: Implementation of a heap tree.

160
Figure 4: Implementation of a heap tree.

161
Figure 5: Implementation of a heap tree.

7. Practice Tasks
This section will provide information about the practice tasks which are required to be
performed in lab session. Design solutions of problems discussed in each task and place
solution code in a folder specified by your lab instructor.
Lab instructors are guided to help students learn how ACM problems work and provide
students with certain practice/home tasks on the pattern of ACM Problems.

7.1 Practice Task 1 [Expected time = 20

mins]
Write a program which should implement a max heap tree containing floating point values as
its elements. Program should allow user to insert a value in tree and program should perform
search a value input by user to check whether it exists in tree or not?

7.2 Practice Task 2

Implement a program in which you have to implement a minimum heap tree using arrays. Your
program should contain following functions:
• Insert
• Display
• Find minimum value
• Delete

7.3 Out comes

After completing this lab, student will be able to understand and develop programs related to
and heap trees in C++ using Microsoft Visual Studio 2017 environment.

7.4 Testing
Test Cases for Practice Task-1
Sample Input Sample Output
Enter the values of elements for
max heap tree:
2.3
3.4
1.5
5.6
2.1
1.9
Enter a value to exist in tree: 2.1 Value found in tree

162
8. Evaluation Task (Unseen) [Expected time = 60 mins for two tasks]

The lab instructor will give you unseen task depending upon the progress of the class.

9. Evaluation criteria
The evaluation criteria for this lab will be based on the completion of the following tasks. Each
task is assigned the marks percentage which will be evaluated by the instructor in the lab
whether the student has finished the complete/partial task(s).

Table 2: Evaluation of the Lab

Sr. No. Task No Description Marks

1 4 Problem Modeling 20
2 6 Procedures and Tools 10
3 7,8 Practice tasks and Testing 35
4 8.1 Evaluation Tasks (Unseen) 20
5 Comments 5
6 Good Programming Practices 10

10.Further Readings
10.1 Web sites related to C++ tutorials about AVL and Heap trees
1. http://www.cs.uah.edu/~rcoleman/Common/CodeVault/Code/Code203_Tree.html
2. http://www.cplusplus.com/reference/algorithm/make_heap/

10.2 Web sites containing supporting material

1. http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture04.pdf

163