Data
It is an entity piece of information that is fact.
Information
Instruction + Data
Data Structure
It is a way of organizing data that considers not
only the items stored but also the relationship of
each data.
K. Adisesha 3
Definition
Primitive data structures
Data structure which can be directly operated by
machine level instruction
Non primitive data structures
Data structure which can not be directly operated by
machine level instruction
Linear data structure
Non-Linear data structure
K. Adisesha 4
Data Structure
Basic Data Structure Problem-Oriented
Abstract Data Type List Structure
Structure Type Basic Data Type Stack
Array Type Pointer Type Queue
Record Type Simple Type Tree
Integer Hash
Logical
Real Number
Enumeration
Character
Partial
K. Adisesha 5
Dynamic memory allocation and pointers
Recursion
Searching and Sorting
Stack
Queue
Linked list
Tree
K. Adisesha 6
Basic Data Type Simple Type
Integer - represents whole number and is
represented inside a computer as binary
numbers of fixed-point numbers that have no
significant digits below the decimal point.
Real Number - represents fixed-point and
floating point numbers.
Character - represents fixed-point and floating point
numbers.
Logical - used to perform logical operations,
such as AND, OR, and NOT operations.
K. Adisesha 7
Structured Type Array Type
One Dimensional Array
One of the simplest and most common type
of data structure. It is an ordered set consisting of a
variable number of elements.
The number of subscripts of an array
determines its dimensionality.
ArrayX [ j ]
Element / Subscript / Index
Array Name
K. Adisesha 8
Structured Type Array Type
One Dimensional Array
Example:
Grade [ j ] Grade [ 0 ] = 95
Grade [ 5 ] Grade [ 1 ] = 85
Grade [ 2 ] = 75
Grade [ 3 ] = 100
Grade [ 4 ] = 65
K. Adisesha 9
Structured Type Array Type
Two Dimensional Array
An array with two subscripts. The first
subscripts is called the “row”, and the second is
called the “column”.
int ArrayX [ j ,
k ]
Base type index
Array Name
K. Adisesha 10
Structured Type Array Type
Two Dimensional Row
Array major
Grade [0,0] = 71
Grade [0,1] = 85
Example: Grade [ 3 , Grade [0,2] = 90
4 ] Grade [0,3] = 95
Grade C0 C1 C2 C3 Grade [1,0] = 97
Grade [1,1] = 88
R0 71 85 90 95 Grade [1,2] = 78
Grade [1,3] = 87
R1 97 88 78 87 Grade [2,0] = 76
Grade [2,1] = 84
R2 76 84 92 65 Grade [2,2] = 92
Grade [2,3] = 65
K. Adisesha 11
Structured Type Array Type
Two Dimensional Column major
Array Grade [0,0] = 71
Grade [1,0] = 97
Example: Grade [ 3 , Grade [2,0] = 76
4 ] Grade [0,1] = 85
Grade C0 C1 C2 C3 Grade [1,1] = 88
Grade [2,1] = 84
R0 71 85 90 95 Grade [0,2] = 90
Grade [1,2] = 78
R1 97 88 78 87 Grade [2,2] = 92
Grade [0,3] = 95
R2 76 84 92 65 Grade [1,3] = 87
Grade [2,3] = 65
K. Adisesha 12
Exercise
An array has an index of x[3..8] and start at
the address 245. It has 4 words per memory cell.
What will the location of element x[5]?
To get the location of elements
Loc [k] = base + w (k-LB)
To get the number of elements in an
arrayNE = UB – LB + 1
K. Adisesha 13
Memory Map
Element Address
s 3 245
4 249
Locate 5 253
6 257
7 261
8 265
K. Adisesha 14
Exercise
An automobile company uses array AUTO to
record the number of automobile sold each year
from 1932 to 1996. Locate AUTO[1980]. Assume
801 as starting address with 5 words long. Also find
the length of the array AUTO.
ANSWER:
Loc[1980] = 1041
NE = 65
K. Adisesha 15
Exercise
Given a 4x5 array with [-3..0, 2..6) index,
starting address is 81 with 2 words per memory cell.
Locate [-1,5] using row major and column major
representation.
To get the number of elements in an
array
M = UB1 – LB1 + 1 NE = M x N
N = UB2 – LB2 + 1
To get the location of elements ( ROW
MAJOR)
Loc [j,k] = base + w [ N (j-LB1) + (k-
LB2) ]
To get the location of elements ( COLUMN MAJOR
Loc [j,k] = base + w [ M (k-LB2) + (j-
LB1) ] K. Adisesha 16
Memory Map
COLUM
N
2 3 4 5 6
-3 81 83 85 87 89
R
O -2 91 93 95 97 99
W
10 ROW
-1 103 105 107 109 MAJOR
1
Locate
11
0 113 115 117 119
1
K. Adisesha
BAC17
Memory Map
COLUM
N
2 3 4 5 6
-3 81 89 97 105 113
R
O -2 83 91 99 107 115
W
COLUMN
-1 85 93 101 109 117 MAJOR
Locate
0 87 95 103 111 119
K. Adisesha
BAC18
Exercise
When storing a two-dimensional array “a” with ten rows
and ten columns in continuous memory space in the direction
of rows, what is the address where a [5,6] is stored? In this
question, the address is represented in decimal numbers.
Addres
s
100
a [1,1]
101
102
a [1,2]
103
a. 145 b. 185 c. 190 d. 208 e. 212
K. Adisesha 19
