Objectives :

• To understand how various data structures can

be classified
• To understand the most commonly used, basic
data types and data arrays
• To understand the characteristics and
mechanisms of problem-oriented data
structures used to solve specific problems, as
well as how to use a basic data structure for
program implementation
 What is Data Structure?
Data Structure is a set of the same kind of
data processed by a computer.
It is a way of organizing data that considers
not only the items stored but also the relationship
of each data.

It is also the data type that is represented

and programmed in the computer.
Classification of Data Structure
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
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.
Basic Data Type Simple Type

Logical - used to perform logical operations,

such as AND, OR, and NOT
operations.

Enumeration - defined as a data type that

enumerates all possible values of
variables. In here, integers can be
named.
Partial - used to specify an original value
subset by constraining existing data
types.
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
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
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
Structured Type Array Type

Two Dimensional Array Row major

Grade [0,0] = 71
Grade [0,1] = 85
Example: Grade [ 3 , 4 ] Grade [0,2] = 90
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
Structured Type Array Type

Two Dimensional Array Column major

Grade [0,0] = 71
Grade [1,0] = 97
Example: Grade [ 3 , 4 ] Grade [2,0] = 76
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
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 array

NE = UB – LB + 1
 Memory Map
Elements Address
3 245
4 249
5 253
Locate 
6 257
7 261
8 265
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
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) ]
 Memory Map
COLUMN
2 3 4 5 6

-3 81 83 85 87 89
R -2 91 93 95 97 99
O
W
-1 101 103 105 107 109 ROW MAJOR
 Locate
0 111 113 115 117 119

BACK
 Memory Map
COLUMN
2 3 4 5 6

-3 81 89 97 105 113
R -2 83 91 99 107 115
O
W
-1 85 93 101 109 117 COLUMN MAJOR
 Locate
0 87 95 103 111 119

BACK
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.
Address

100
a [1,1]
101
102
a [1,2]
103

a. 145 b. 185 c. 190 d. 208 e. 212

Problem-Oriented Data Structure
List Structure
A linear collection of data elements called
nodes and where linear order is given by means
of pointers.

NODE

DATA POINTER
Data  FIELD FIELD
 Address
Problem-Oriented Data Structure
Types of List Structure

Uni-directional List

01H 05H 03H 07H

MARCOS 05H AQUINO 03H RAMOS 07H ESTRADA NULL

HEAD TAIL
Problem-Oriented Data Structure
Types of List Structure

Bi-directional List
01H 05H 03H

NULL MARCOS 05H 01H AQUINO 03H 05H RAMOS 07H

HEAD

07H

03H ESTRADA NULL

TAIL
Problem-Oriented Data Structure
STACK
An ordered list where all operations are
restricted at one end of the list known as TOP.
List processing is based on Last-In First-Out
(LIFO).

 Top

Bottom 
Problem-Oriented Data Structure
STACK OPERATION

PUSH - inserts a new element at the

top of the stack

POP - retrieves the element at the top

and deletes it from stack.

TOP - retrieves the element at the top

of the stack
Exercise
What will be the content of the stack after
performing the following operation?

1. Pop (S)
2. Push (E,S) D
3. Push (F,S)
C
4. Pop (S)
5. Pop (S) B
6. Push (G) A
Problem-Oriented Data Structure
STACK APPLICATION

INFIX - an expression PREFIX - an expression

where operator is placed where operator is placed
in between the operands before the operands
Example : (A + B) Example : (+AB)

POSTFIX - an expression
where operator is placed
after the operands
Example : (AB+)
Exercise
Convert the following mathematical
expression into INFIX, PREFIX, and POSTFIX
Notation.

1.) AB2 2.) A B / G + M-N3 (G+H-J2)

+E
C- D 3 F
Problem-Oriented Data Structure
TREE Structure
It is a collection of data items called nodes.
Each node has a relationship with one or more
nodes thereby giving a hierarchical structure.

A Binary Tree
/
B C D
* +
E F G H I J
A B C D
K L M
Exercise
Create a Tree Structure based on the given
prefix and postfix notation.

1.) - + / *A B G M * ^ N 3 - + G H ^ I 2

2.) FM3^*S/K*M3^L*-QP2^*+