Lab Manual

CS301 – Data Structures

Department of Computer Science, Virtual University of Pakistan

 Page
Week No. Lab Topic
No.
1 Lab 1: Learn to implement linked list data structure 2
2 Lab 2: Learn to implement stack data structure using array 3
3 Lab 3: Learn to implement queue data structure using link list 4
4 Lab 4: Learn to draw binary search tree and implement in-order traversal 5
5 Lab 5: Learn to implement binary search tree for string type data 7
6 Lab 6: Learn to understand and implement function call by value, reference 14
and pointer
7 Lab 7: Learn to understand and implement function call by value, reference 16
and pointer
8 Lab 8: Learn to delete nodes from BST 19
Midterm Exams
9 Learn to delete nodes from AVL tree 20
10 Learn to build frequency table and Huffman encoding tree 22
11 Lab 11: Learn to implement min heap using insert( ) method 24
12 Lab 12: Learn to implement min heap using buildHeap( ) method 29
13 Lab 13: Learn to build union tree 30
14 Lab 14: Learn to implement binary search algorithm 31
15 Lab 15: Build Hash table using linear probing collision resolution 33
technique
16 Lab 16: Learn to sort array using bubble sort algorithm 34

1|Page
 Lab 1
Lab Title: Learn to implement linked list data structure

Objectives: Get the knowledge of implementing linked list data structure using C++
programming language.

Tool: Dev C++

Description:
Write the C++ code to implement the List class. You need to write only add( ). remove( ), and
find( ) functions of the list class.

2|Page
 Lab 2
Lab Title: Learn to implement stack data structure using array

Objectives: Get the knowledge of implementing stack list data structure using array in C++
programming language

Tool: Dev C++

Description:
Write a C++ program to implement data structure Stack. You have to write all the stack
functions and using those functions insert the numbers 1 to 10 into the stack. The stack should be
able to show the error messages if the push( ) operation is initiated but the stack is full or the
pop( ) operation is initiated but the stack is empty.

3|Page
 Lab 3
Lab Title: Learn to implement queue data structure using link list

Objectives: Get the knowledge of implementing queue data structure using link list in C++
programming language.

Tool: Dev C++

Description:
Write the C++ Code for the enqueue( ), dequeue( ), front( ) and the rear( ) functions of the class
queue.

4|Page
 Lab 4
Lab Title: Learn to draw binary search tree and implement in-order traversal

Objectives: Learn to draw binary search tree and perform in-order traversal using C++
programming language.

Tool: Dev C++, MS Word, MS Visio

Description:
Task 1:

Draw BST from the given Data:

14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

Task 2:

Write C++ code that will perform inOrder traversal on the above given BST.

#include <iostream>

#include "TreeNode.cpp"

#include <queue>

using namespace std;

void inOrder(TreeNode<int>* );
5|Page
 int main()

int Array[]={14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5,-1};

TreeNode <int> * root = new TreeNode<int>();

root->set(&Array[0]);

for (int i = 1; Array[i] > 0; i++)

insert(root, &Array[i]);

cout << "\ninorder: ";

inOrder( root );

} // end of main

void inOrder(TreeNode<int>* treeNode)

if( treeNode != NULL )

inOrder(treeNode->getLeft());

cout << *(treeNode->get())<<" ";

inOrder(treeNode->getRight());

} //End of inOrder.

6|Page
 Lab 5
Lab Title: Learn to implement binary search tree for string type data

Objectives: Get the knowledge of implementing binary search tree for string data type using
C++ programming language.

Tool: Dev C++

Description:
Write C++ code that will draw BST using string type of data:

"babble", "fable", "jacket","backup", "eagle","daily","gain","bandit","abandon",

"abash","accuse","economy","adhere","advise","cease","debunk","feeder","genius","fetch","chai
n", NULL

Note: Template_BSTNode.cpp Template_Node_SLL.cpp and Template_Queue_LinkedList.cpp

files will students search from CS301 handouts or may be provided by the tutor/Instructor.

#include <iostream>

#include <cstring>

#include "Template_BSTNode.cpp"

#include "Template_Queue_LinkedList.cpp"

using namespace std;

template <typename T>

void insert(BSTNode<T> * , T);

template <typename T>

void insertChar(BSTNode<T> * , T);

template <typename T>

void inOrderTraverse(BSTNode<T> * );

template <typename T>

void preOrderTraverse(BSTNode<T> * );

7|Page
template <typename T>

void postOrderTraverse(BSTNode<T> * );

template <typename T>

void levelOrderTraverse(BSTNode<T> * );

int main()

static char * x[] = {"babble", "fable", "jacket","backup",

"eagle","daily","gain","bandit","abandon",

"abash","accuse","economy","adhere","advise","cease","debunk","feeder","genius","fetch","chai
n", NULL};

BSTNode<char *> * Root = new BSTNode<char *>(x[0]);

for(int i = 0; x[i]; i++)

insertChar(Root, x[i]);

cout<< endl << endl<< "the inOrder BST is ... " << endl;

inOrderTraverse(Root);

cout<< endl << endl<< "the preOrder BST is ... " << endl;

preOrderTraverse(Root);

cout<< endl<< endl << "the postOrder BST is ... " << endl;

postOrderTraverse(Root);

cout<< endl << endl<< "the levelOrder BST is ... " << endl;

levelOrderTraverse(Root);

8|Page
} // end of main.

template <typename T>

void insert(BSTNode<T> * node, T x)

BSTNode<T> * newNode = new BSTNode<T>(x);

BSTNode<T> * tempRoot, * tempLeaf;

tempRoot = tempLeaf = node;

while(x !=tempRoot->getData() && tempLeaf != NULL)

tempRoot = tempLeaf;

if(x< tempRoot->getData())

tempLeaf = tempRoot->getLeft();

else

tempLeaf = tempRoot->getRight();

} // end of while , this loops only break when x = data hold by current node or it is leaf;

if(x == tempRoot->getData())

cout << "\nDuplicate element entry !!! "<< x << endl;

delete newNode;

else if(x< tempRoot->getData())

tempRoot->setLeft(newNode);

9|Page
 else

tempRoot->setRight(newNode);

template <typename T>

void insertChar(BSTNode<T> * node, T x) // OverLoaded Insert Funciton

BSTNode<T> * newNode = new BSTNode<T>(x);

BSTNode<T> * tempRoot, * tempLeaf;

tempRoot = tempLeaf = node;

while(strcmp(x, tempRoot->getData())!=0 && tempLeaf != NULL)

tempRoot = tempLeaf;

if(strcmp(x, tempRoot->getData())<0 )

tempLeaf = tempRoot->getLeft();

else

tempLeaf = tempRoot->getRight();

} // end of while , this loops only break when x = data hold by current node or it is leaf;

if(strcmp(x, tempRoot->getData())==0 )

cout << "\nDuplicate element entry !!! "<< x << endl;

delete newNode;

10 | P a g e
 }

else if(strcmp(x, tempRoot->getData())< 0 )

tempRoot->setLeft(newNode);

else

tempRoot->setRight(newNode);

template <typename T>

void inOrderTraverse(BSTNode<T> * node )

if(node!=NULL)

inOrderTraverse(node->getLeft() ); // it will keep caling function till reaches node

reach end

cout << endl<< node->getData();

inOrderTraverse(node->getRight() );

template <typename T>

void preOrderTraverse(BSTNode<T> * node )

if(node!=NULL)

cout << endl<< node->getData();

11 | P a g e
 preOrderTraverse(node->getLeft() ); // it will keep caling function till reaches
node reach end

preOrderTraverse(node->getRight() );

template <typename T>

void postOrderTraverse(BSTNode<T> * node )

if(node!=NULL)

postOrderTraverse(node->getLeft() ); // it will keep caling function till reaches

node reach end

postOrderTraverse(node->getRight() );

cout << endl<<node->getData();

template <typename T>

void levelOrderTraverse(BSTNode<T> * node )

{ queue <BSTNode<T> *> myQueue;

if (node == NULL) return;

myQueue.push(node);

while (!myQueue.isEmpty())

node = myQueue.peak();

12 | P a g e
 myQueue.pop();

cout << endl<< node->getData();

if(node->getLeft() != NULL)

myQueue.push(node->getLeft());

if(node->getRight() != NULL)

myQueue.push(node->getRight());

system("pause");

13 | P a g e
 Lab 6
Lab Title: Learn to implement function call by value, reference and pointer

Objectives: Get the knowledge of implementing function calls for call by value, call by
reference and call by pointer.

Tool: Dev C++

Description:
Write C++ program that will demonstrate how the value in a caller function is affected when it is
passed to a function by using call by value, by using pointers and by using call by reference
methods.

#include <iostream.h>
//Function 1, call by value
int intMinus1( int oldVal)
{
oldVal = oldVal – 1;
return oldVal;
}
// Function 2, call by using pointers
int intMinus2( int* oldVal)
{
*oldVal = *oldVal – 2;
return *oldVal;
}
// Function 3, call by reference
int intMinus3( int& oldVal)
{
oldVal = oldVal – 3;
return oldVal;
}
void main ()
{
int myInt = 31;
int retVal;
retVal = intMinus1( myInt ); //call by value
cout << “After returning from the called function intMinus1” << endl ;
cout << ”The value returned by the called function (retVal) is : ” << retVal ;
cout << endl ;
cout << ”The value of the calling function’s variable (myInt) is : ” << myInt ;
cout << endl << endl;

14 | P a g e
// now pass the argument by using pointer, also initialize the value of myInt
myInt = 31 ;
retVal = intMinus2( &myInt ); //call by passing a pointer
cout << “After returning from the called function intMinus2” << endl;
cout << ”The value returned by the called function (retVal) is : ” << retVal ;
cout << endl;
cout << ”The value of the calling function’s variable (myInt) is : ” << myInt ;
cout << endl << endl;
// now pass the argument by as reference, also initialize the value of myInt
myInt = 31 ;
retVal = intMinus3( myInt ); //call by passing a reference
cout << “After returning from the called function intMinus3” << endl;
cout << ”The value returned by the called function (retVal) is : ” << retVal ;
cout << endl;
cout << ”The value of the calling function’s variable (myInt) is : ” << myInt ;
}

15 | P a g e
 Lab 7
Lab Title: Learn to delete nodes from BST

Objectives: Understand to deletion process of nodes in BST

Tool: MS Word, MS Visio

Description:
Draw Binary Search Tree from the given data. Also draw Binary Search Tree after removal of
value ‘9’.

9 4 6 17 2 8 4 15 41 47 29

16 | P a g e
BST after removal of ‘9’.

17 | P a g e
 OR

18 | P a g e
 Lab 8
Lab Title: Learn to draw AVL

Objectives: Learn to build/draw AVL tree and understand different types of rotations

Tool: MS Word, MS Visio

Description:
Build AVL tree from the given Data: 3 5 6 7 9 10 11 21 20 18 19

Note: You have to show only final AVL tree after insertion of each node value.

19 | P a g e
 Lab 9
Lab Title: Learn to delete nodes from AVL tree

Objectives: Learn to delete nodes from AVL with the help of rotations

Tool: MS Word, MS Visio

Description:
Delete the node 14, 4 and 10 from given AVL three and perform necessary rotation to balance
the tree after deletion of each node.

8 8

3 10 3 10

1 6 14 1 6

7 4 7
4

20 | P a g e
 8
6

6 10
3 8

3 7
1 4 7 10

1 4

6 6

3 8 3 8

4 7 10 4 7

21 | P a g e
 Lab 10
Lab Title: Learn to build frequency table and Huffman encoding tree

Objectives: Get the knowledge of building frequency table and Huffman encoding tree.

Tool: MS Word, MS Visio

Description:
Consider the message “the clouds are dark and its about to rain” and construct frequency
table and Huffman encoding tree.

Frequency Table:

Character Frequency Character Frequency

a 5 n 2
b 1 o 3
c 1 r 3
d 3 s 2
e 2 t 4
h 1 u 2
i 2 SP 8
k 1 NL 1
l 1

22 | P a g e
 4
0 1

1 2
0
1 0 1

7 7 1 1
0 1 0 1 0 0
1 1

r 4 o 4 S 7 a 8

0 1 0 1 1 0 1
0

s 2 n 2 d 4 t 4

0 1 0 1 0 1
0 1

b c h k i 2
u e
0 1

l N

23 | P a g e
 Lab 11
Lab Title: Learn to implement min heap using insert( ) method

Objectives: Get the knowledge of implementing min heap using insert( ) method with the help
of C++ programming language.

Tool: Dev C++

Description:
Consider the Data: 18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29 and write the C++
code to construct min heap using insert method.

#include <iostream>

using namespace std;

class Heap {

public:

Heap (int capacity);

bool insert ( const int & x);

bool isEmpty ();

bool isFull();

void traverse();

public:

int currentSize; // number of elements in heap

int * array; // the heap array

int capacity;

};

24 | P a g e
Heap::Heap (int capacity) {

array = new int[capacity+1];

currentSize = 0;

bool Heap::insert ( const int & x) {

if(isFull()) {

cout <<endl<<"cannot insert Heap is full!!" << endl;

return 0;

int hole = ++currentSize;

for(/* declaration is above*/ ; hole>1 && x< array[hole/2]; hole /= 2) {

array[hole]= array[hole/2];

array[hole] = x;

void Heap::traverse() {

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

cout <<" "<< array[i] << " ";

bool Heap::isEmpty() {

return currentSize == 0;

bool Heap::isFull() {

25 | P a g e
 return currentSize==capacity;

main() {

int size = 16, arr[size] = {18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29};

Heap heap(size);

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

heap.insert(arr[i]); // insert number into heap one by one

cout << " Min Heap using insert method : "<<endl;

heap.traverse();

26 | P a g e
 Lab 12
Lab Title: Learn to implement min heap using buildHeap( ) method

Objectives: Get the knowledge of implementing min heap using buildHeap( ) and
perculateDown( ) methods with the help of C++ programming language.

Tool: Dev C++

Description:
Consider the Data: 18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29 and write the C++
code to construct min heap using buildHeap( ) method.

#include <iostream>

using namespace std;

class Heap {

public:

Heap (int capacity);

bool isEmpty ();

bool isFull();

void buildHeap(int * anArray, int n);

void traverse();

public:

int currentSize; // number of elements in heap

int * array; // the heap array

int capacity;

void percolateDown( int hole );

27 | P a g e
};

Heap::Heap (int capacity) {

array = new int[capacity+1];

currentSize = 0;

void Heap::percolateDown(int hole) {

int child;

int temp = array[hole];

for ( /*nothing*/ ; hole * 2 <=currentSize; hole = child) {

child = hole*2;

if (child !=currentSize && array[child+1] < array[child] )

child++;

if (array[child]< temp)

array[hole] = array[child];

else break;

array[hole] = temp;

void Heap::buildHeap(int * anArray, int n) {

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

array[i] = anArray[i-1];

28 | P a g e
 currentSize = n;

for (int i =currentSize/2; i>0; i--)

percolateDown(i);

void Heap::traverse() {

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

cout <<" "<< array[i] << " ";

bool Heap::isEmpty() {

return currentSize == 0;

bool Heap::isFull() {

return currentSize==capacity;

main() {

int size = 16, arr[size] = {18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29};

Heap heap(size);

heap.buildHeap(&arr[0],size);

cout << "\n Min Heap using build method: "<<endl;

heap.traverse();

29 | P a g e
 Lab 13
Lab Title: Learn to build union tree

Objectives: Get the knowledge of building union tree of any given data.

Tool: MS Word, MS Visio

Description:
Consider the following sequence of union commands on the set of elements {1, 2, 3, 4, 5, 6, 7, 8,
9, 10}.

union(3,1) union(5,6) union(3,5) union(4,2) union(3,4) union(1,7) union(7,8) union(2,3)

Show the resultant tree after performing union operations.

4 1 5

2 7 6

3 8

30 | P a g e
 Lab 14
Lab Title: Learn to implement binary search algorithm

Objectives: Get the knowledge of implementing binary search algorithm using C++
programming language.

Tool: Dev C++

Description:
Write a program in C++ language to find a number (element) from an array using binary search
algorithm.

You can use 18, 20, 23, 31, 37, 42, 47, 51, 79, 82, 85, 94, 96, 97 as data of array.

#include <iostream>

using namespace std;

int binarySearch(int arr[], int l, int r, int num) {

if (r >= l)

int mid = l + (r - l)/2;

if (arr[mid] == num)

return mid;

if (arr[mid] > num)

return binarySearch(arr, l, mid-1, num);

31 | P a g e
 return binarySearch(arr, mid+1, r, num);

return -1;

main() {

int size = 14, arr[size] = {18, 20, 23, 31, 37, 42, 47, 51, 79, 82, 85, 94, 96, 97};

int number = 15;

int result = binarySearch(arr, 0, size-1, number);

if(result == -1){

cout<<"Element "<<number<<" is not present in array";

else{

cout<<"Element "<<number<<" is present at index %d"<<result;

32 | P a g e
 Lab 15
Lab Title: Build hash table using linear probing collision resolution technique

Objectives: Learn to build Hash table using linear probing technique to resolve collision

Tool: MS Word

Description:
Consider the data given below and build a Hash table using linear probing technique to resolve
collision.

Data 18, 20, 23, 31, 37, 42, 47, 51, 79, 82, 85, 94, 96, 97

Use Hash function key % tablesize where tablesize is 20.

Index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
F(x) 20 97 42 3 82 85 47 11 51 94 96 37 18 79

33 | P a g e
 Lab 16
Lab Title: Learn to sort array using bubble sort algorithm

Objectives: Get the knowledge of sorting array using bubble sort algorithm.

Tool: Dev C++

Description:
Consider the data given below as an array and sort by implementing bubble sort algorithm using
C++ language.

Data: 18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29

#include <iostream>

using namespace std;

void bubbleSort(int *arr, int N) {

int i, temp, bound = N-1;

int swapped = 1;

while (swapped > 0 ) {

swapped = 0;

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

if ( arr[i] > arr[i+1] ) {

temp = arr[i];

arr[i] = arr[i+1];

arr[i+1] = temp;

swapped = i;

34 | P a g e
 }

bound = swapped;

main() {

int size = 16, arr[size] = {18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29};

bubbleSort(arr, size);

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

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

Mechanism to Conduct Lab:

Students and teacher communicate through Skype/Adobe Connect. Students perform the task
using the recommended tool given in each lab.

35 | P a g e