lOMoARcPSD|21950806

Wondershare
PDFelement
CS3CRT09-Data Structures using C++ 2.a

Non- Primitive data structures

These are more sophisticated data structures. They are derived from the primitive data
structures. The non-primitive data structures emphasize on structuring of a group of
homogeneous (same type) or heterogeneous (different type) data items. There are two different
types of Non- Primitive data structures
1. Linear Data Structure
2. Non Linear Data Structure
1) Linear Data Structure
In linear data structure data elements stored in sequential manner. Stack, Queue and
Linked List are the types of linear data structure.
2) Non Linear Data Structure
In Non-Linear data structure data elements are not stored in the sequence manner. Tree
and Graph are the type of non-linear data structure.

Description of Various Data Structures

Arrays:
An array is a collection of similar type of data items (homogeneous) and each data item is
called an element of the array. The data type of the element may be any valid data type like char,
int, float or double.
The elements of array share the same variable name but each one carries a different index
number known as subscript. The array can be one dimensional, two dimensional or
multidimensional.
Declaration of a one-dimensional array age is as follows
int age[3];
The individual elements of the array age are:
age[0], age[1], age[2].
Linked List:
A list (Linked List) can be defined as a collection of variable number of data items. It can
be seen as the collection of nodes stored at non-contiguous memory locations. Each node of the
list contains a pointer to its adjacent nod

In simple words, a linked list consists of nodes where each node contains a data field and a
reference(link) to the next node in the list.
Stack:
Stack is a linear list in which insertion and deletions are allowed only at one end,
called top. Due to this property it is also called as Last-in-First-out (LIFO) data structure.
Insertion of an element into stack is called Push and Deletion of an element from the stack is
called Pop.

Downloaded by Sreya S (sreya.12c@gmail.com)

 lOMoARcPSD|21950806

Wondershare
PDFelement
CS3CRT09-Data Structures using C++ 2.b

The Stack can be implemented in two ways:

a. Using arrays.
b. Using pointers.
Queues:
Queues are First-In-First-Out(FIFO) type of data structures. In a Queues elements are
added from one end called REAR end, and the elements are always removed from other end
called FRONT end. The people standing in a railway reservation row are an example of queue.

The Queue can also be implemented in two ways:

a. Using arrays.
b. Using pointers.
Trees:
Trees are multilevel data structures with a hierarchical relationship among its elements
known as nodes. The bottommost nodes in the herierchy are called leaf node while the topmost
node is called root node. Each node contains pointers to point adjacent nodes.

Tree data structure is based on the parent-child relationship among the nodes. Each node in the
tree can have more than one children except the leaf nodes whereas each node can have atmost
one parent except the root node.

Downloaded by Sreya S (sreya.12c@gmail.com)

 lOMoARcPSD|21950806

Wondershare
PDFelement
CS3CRT09-Data Structures using C++ 2.c

Graphs
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are
sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes
in the graph. A Graph consists of a finite set of vertices(or nodes) and set of Edges which
connect a pair of nodes.

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The
networks may include paths in a city or telephone network or circuit network.

Arrays
An array is a collection of similar type of data items (homogeneous) and each data item is
called an element of the array. The data type of the element may be any valid data type like char,
int, float or double.
The elements of array share the same variable name but each one carries a different index
number known as subscript. The array can be one dimensional, two dimensional or
multidimensional.
One-Dimensional Arrays
A one- Dimensional Array is one in which only one subscript specification is needed to
specify a particular element of the array. One dimensional array can be defined as follows:
data_type var_name[expression];
Here data_type is the type of element to be stored in the array, var_name specifies the name of
the array, it may be given any name like other simple variables. The expression or subscript
specifies the number of values to be stored in the array. Arrays are also called subscripted values.
The subscript must be an integer value. The subscript of an array starts from 0 onwards.
An array can be declared as follows:
int num[10];
The array will store ten integer values as follows:

num
22 1 30 9 3 55 0 10 7 90
0 1 2 3 4 5 6 7 8 9

To access a particular element in the array use the following statement:

var_name[subscript];
For example, to access fourth element from array num we write

Downloaded by Sreya S (sreya.12c@gmail.com)

 lOMoARcPSD|21950806

Wondershare
PDFelement
CS3CRT09-Data Structures using C++ 2.d

num[3];
The size of an array can be determined as follows:
Size=(UpperBound-LowerBound)+1
For array num as described above, the size will be as follows
Size=(9-0)+1=10
The total size of array in bytes can be computed as:
Size in bytes= size of array x size of(base type)
For example, the total memory in bytes that the array num would occupy will be
Size in bytes = 10 x size of(int)
=10 x 2 = 20
Initializing One Dimensional Array
Either it is a One Dimensional Array or Multidimensional Array, it could only be
initialized at the place of declaration.
Example
int value[5]={10, 40, 92, 32, 60};
Accessing One Dimensional Array Elements
Individual elements of the array can be accessed using the following syntax:
array_name[subscript];
Example
value[2]=92;
Implementation of One Dimensional Array in Memory
The address of a particular element in a One Dimensional Array is given by the relation
Address of element a[k]=B+W*k
Where B is the base address of the array, W is the size of each element of the array, and k is the
number of required element in the array.
Example:
Let the base address of the array is 2000 and each element of the array occupies 4 bytes in the
memory, then the address of the fifth element of the array a[10] will be given as:
Address of element a[5] = 2000 + 4*5
= 2020

Array Operations

Insertion in One Dimensional Array

Insertion of new element in an array can be done in two ways:
i. Insertion at the end of the array
ii. Insertion at requires position

Downloaded by Sreya S (sreya.12c@gmail.com)

 lOMoARcPSD|21950806

Wondershare
PDFelement
CS3CRT09-Data Structures using C++ 2.e

Algorithm
For inserting an element into a linear array insert(a, len, pos, num), where a
is linear array, len be total number of elements in the array, pos is the position at which number
num will be inserted.

insert(a, len, pos, num)

1. [initialize the value of i]
Set i= len
2. Repeat for i=len down to pos
Set a[i+1]=a[i]
3. [insert the element at required position]
Set a[pos]=num
4. [Reset len]
Set len=len+1
5. Display the new list of array
6. End

Deleting an element from one-dimensional array

For deleting an element from an array is straightforward. Deleting an element at the end
of an array presents no difficulties, but deleting elements somewhere in the middle of the array
would require to shift all elements to fill the space emptied by the deletion of the element.

Downloaded by Sreya S (sreya.12c@gmail.com)

 lOMoARcPSD|21950806

Wondershare
PDFelement
CS3CRT09-Data Structures using C++ 2.f

Algorithm
The following algorithm deletes the element stored at position pos from a linear array a
and assign it to a variable item.
delete (a, pos, len)
where a is linear array, pos is the position at which number num will be inserted, len be total
number of elements in the array,
delete (a, pos, len)

1. Set item=a[pos]
2. Repeat for j=pos to len-1
Set a[j]=a[j+1]
3. [Reset len]
Set len=len-1
4. Display the new list of array.
5. End

Traversing of Array
Traversing means to access all the elements of the array, starting from the first element up to the
last element in the array one by one.
Traverse (a, LB, UB)

Downloaded by Sreya S (sreya.12c@gmail.com)

 lOMoARcPSD|21950806

Wondershare
PDFelement
CS3CRT09-Data Structures using C++ 2.g

where a is linear array, LB is the lower bound, UB is the upper bound of the array a.
Traverse (a, LB, UB)
1. Set i= LB
2. Repeat for i=LB to UB
Display a[i]
3. Exit

Multi-dimensional Arrays
A multi-dimensional array is an array of arrays. 2-dimensional arrays are the most
commonly used. They are used to store data in a tabular manner. For an array of size MxN, the
rows are numbered from 0 to M-1 and columns are numbered from 0 to N-1, respectively.
2D array declaration:
To declare a 2D array, you must specify the following:
Row-size: Defines the number of rows
Column-size: Defines the number of columns
Type of array: Defines the type of elements to be stored in the array i.e. either a number,
character, or other such datatype.
A sample form of declaration is as follows:
type arr[row_size][column_size]
A sample array is declared as follows:
int arr[3][5];
2D array initialization:
An array can either be initialized during or after declaration. The format of initializing an array
during declaration is as follows:
int arr[3][3] = {{5, 12, 17}, {13, 4, 8}, {9, 6, 3}};
or int arr[3][3] = {5, 12, 17, 13, 4, 8, 9, 6, 3};

Accessing two dimensional array element

Elements of the two dimensional array elements can be accessed as follows
int arr[3][5];
arr[0][0] = 5;
arr[1][2] = 8;
Implementation of two-dimensional array in memory
Let, A be a two-dimensional array m x n array. Although A is pictured as a rectangular
array of elements with m rows and n columns, the array will be represented in memory by a
block m x n sequential memory location. Specifically, the programming language will store the
array A either,
1. column by column is called column major order or
2. Row by row, in row major order

Downloaded by Sreya S (sreya.12c@gmail.com)

 lOMoARcPSD|21950806

Wondershare
PDFelement
CS3CRT09-Data Structures using C++ 2.h

Where B is the base address of the array, W is the size of each array element, n is the number of
columns. L1 is the lower bound of row, L2 is the lower bound of column.
Example
Suppose we want to calculate the address of element A [1, 2] in array A of 2 rows and 4
columns. It can be calculated as follow:
Here,
B = 2000, W= 2, m=2, n=4, i=1, j=2, L1=0, L2=0

LOC (A [i, j]) = B+W(n(i-L1)+(j-L2))

LOC (A[1, 2]) = 2000 + 2 *[4*(1-0) + (2-0)]
= 2000 + 2 * [4 + 2]
= 2000 + 2 * 6
= 2000 + 12
= 2012
Address of elements in Column major implementation
Address of element a[i][j]=B+W((i-L1)+ m(j-L2))
Where B is the base address of the array, W is the size of each array element, m is the number of
rows. L1 is the lower bound of row, L2 is the the lower bound of column.
Example
Suppose we want to calculate the address of element A [1, 2] in array A of 2 rows and 4
columns. It can be calculated as follow:
Here,
B = 2000, W= 2, m=2, n=4, i=1, j=2, L1=0, L2=0

LOC (A [i, j]) = B+W(m(j-L2)+(i-L1))

LOC (A[1, 2]) = 2000 + 2 *[2*(2-0) + (1-0)]
= 2000 + 2 * [4 + 1]
= 2000 + 2 * 5
= 2000 + 10
= 2010

Application of Arrays
1. Sparse matrix representation.
2. Polynomials representation.
3. Array can be used for sorting elements.
4. Array can perform matrix operation.
5. Array can be used in CPU scheduling.
Arrays can be used in various CPU scheduling algorithms. CPU Scheduling is
generally managed by Queue. Queue can be managed and implemented using the
array.
6. Array can be used in recursive function.

11

Downloaded by Sreya S (sreya.12c@gmail.com)