- Home
- Technology
*MELJUN CORTES Instructional manual data_structures*

prev

next

out of 20

View

10Download

1

Embed Size (px)

CSCI05 CS INSTRUCTIONAL MANUAL

1

CSCI05 CS

(Instructional Manual)

MELJUN P. CORTES, MBA,MPA

CSCI05 CS INSTRUCTIONAL MANUAL

2

DATA STRUCTURES

Data Structures is a way of organizing data that considers not only the items

stored but also their relationship to each other.

A general understanding of data structures is essential to developing efficient

algorithms in virtually all phases of advanced data processing and computer science.

The ability to make right decisions is vital to anyone involved with computers. Such

decisions typically involve the following general issues:

- Efficiency of a program with respect to its run time. Does it perform its

task in a time allotment that does not detract from overall system

performance?

- Efficiency of a program with respect to its utilization of main memory

and secondary storage devices. Does it consume such resources in a

fashion that makes it use impractical?

Types of Data Structure

1. Linear the elements form a sequence

e.g. array, linked lists

2. Non-linear structured

e.g. trees, graphs

Data Types - composed of domain data elements

Data Item single unit of information

Types of Data Item

1. Group Item data item that can be divided into sub-items.

e.g. name (first name, middle name, last name), address (street, town,

city, country), date of birth (month, day, year), time (hour, minute, seconds),

etc.

2. Elementary Item - data item that cannot be divide into sub-items.

e.g. age, gender, etc.

Classification of Data Types

A. Elementary data types or Simple data types

- these are the basic data types

- the value of one of these components is atomic, that is it consists of a single

entity and could not be divided.

e.g. int, float, char in C.

1. Primitive data types - enumerated data types

2. Standard primitive built-in data types

e.g. int, char, float

CSCI05 CS INSTRUCTIONAL MANUAL

3

B. Structured data types collection of complex number of information.

1. Strings is an ordered sequence of characters that increases and

decreases dynamically.

2. Lists ordered sequence of components, which may themselves be

lists.

3. Arrays fixed-size, ordered collection of data elements all of the

same type.

4. Records also called the hierarchical or structured type.

- is an ordered collection of data elements that are not

necessarily of the same type.

ARRAYS

One of the most commonly used data structures.

Components of an array

1. array name collective name of an array.

2. index type set of subscripts that are used to differentiate one element

from another.

3. base type data type of array element.

Types of array

1. One-dimensional or single dimensional array - also terms a vector, this

type of array simply refers to a specific number of consecutive memory

locations.

2. Multi-dimensional array the position of data element must be specified

by giving coordinates, typically the row and column coordinates.

Operations of Array

1. Storage assign a value to a particular array element

2. Extraction getting a value from an array element

ONE DIMENSIONAL ARRAY

- also called the linear array

- it is a list of finite number of N elements of homogenous data elements that:

a) the element of the array are referenced respectively by an index, set

consisting of N consecutive numbers.

b) The elements of the array are stored respectively in successive

memory locations.

Syntax: [];

Example: int x[4];

To get the Total number of elements of an array:

CSCI05 CS INSTRUCTIONAL MANUAL

4

We use formula:

NE = UB + LB + 1

Where: NE number of elements

UB upper bound (highest index of an array)

LB lower bound (lowest index of an array)

To compute for the address of an element (memory location)

Loc[k] = base + w(k-LB)

Where: k- index of a specific element

base starting memory address

w - element size (words per memory cell/interval)

LB lower bound (lowest index of an array)

Sample Problems

1. Consider an array grade[8], w=2, base =100. Look for the address of

grade[5] and NE

Given: NE = UB LB + 1

UB=7 = 7 0 + 1

LB = 0 = 8

w = 2

base = 100 Memory Mapping

Find: Loc[5] & NE Element Address

0 100 - base

Solution: 1 102

Loc[k] = base + w(k-LB) 2 104

Loc[5] = 100 + 2(5-0) 3 106

= 100 + 2(5) 4 108

= 110 5 110

6 112

2. An array has an index of (-2..5) at the starting address of 200. It has 3 words

per memory cell, determine Loc[-1], Loc[3], NE.

Given:

LB = -2 NE = UB LB + 1

UB = 5 = 5 (-2) + 1

base = 200 = 7 + 1

w =3 = 8

Find: Loc[-1], Loc[3] & NE

Solution: Element Address

Loc[k] = base + w(k-LB) -2 200 -base

Loc[-1]= 200 + 3(-1 (-2)) -1 203

= 200 + 3(1) 0 206

= 203 1 209

2 212

Loc[k] = base + w(k-LB) 3 215

Loc[3]= 200 + 3(3 (-2)) 4 218

= 200 + 3(5) 5 220

= 215

CSCI05 CS INSTRUCTIONAL MANUAL

5

3. The starting address of an array is 872. 3 is the highest index of the array. If

it has 9 elements and w=4, find which element has the location of 892.

Given: k= Loc[k] base + LB

base = 872 w

UB= 3 k= 892 872 + (-5)

NE= 9 4

w=4 = 0

Find: k Memory Mapping

Element Address

Solution: -5 872 - base

Loc[k] = base + w(k-LB) -4 876

k= Loc[k] base + LB -3 880

w -2 884

-1 888

NE = UB LB + 1 0 892

LB = UB NE + 1 1 896

= 3 9 + 1 2 900

= 4 9 3 904

= -5

4. The third element of an array is 4 whose location is 558. If w=5 and there

are 7 elements in the array, compute for the base and Loc[0].

Given: Loc[k] = base + w(k-LB)

Loc[-4] = 558 Loc[0] = 548 + 5(0 (-6))

w = 5 = 548 + 30

NE = 7 = 578

LB = -6 1st element

Find: base & Loc[0] Memory Mapping

Element Address

Solution: -6 548 - base

Loc[k] = base + w(k-LB) -5 553

Base = Loc[k] w(k-LB) -4 558

558 = base + 5(-4 (-6)) -3 563

558 = base + 10 -2 568

base = 558 10 -1 573

base = 548 0 578

5. Consider an array of 12 elements. If the 1st element of the array starts at

memory address 997 and its highest index is 7 whose location is 1074, look

for the words per memory cell.

Given:

NE =12

base = 997

UB = 7

Loc[7] = 1074

Find: w

CSCI05 CS INSTRUCTIONAL MANUAL

6

Solution: Memory Mapping

NE = UB LB + 1 Element Address

LB = UB NE + 1 -4 997

= 7 12 + 1 -3 1004

= 8 12 -2 1011

= -4 -1 1018

0 1025

Loc[k] = base + w(k-Lb) 1 1032

1074 = 997 + w(7- (-4)) 2 1039

1074 997 = w(11) 3 1046

1074 997 = w(11) 4 1053

11 11 5 1060

w = 1074 997 6 1067

11 7 1074

w = 7

Seatwork

1. An array has an index (-1..7) and starting address of 354. If it has 9 words per

memory cell determine NE, Loc[2], Loc[4].

2. Array num has an index of (7..2). Element 2 is located in memory address 356.

Find which element has the location 374 if w=6.

3. Consider an array whose last element is 9. If the1st element is in 795, what is

the first elements index? NE=15. Find w if Loc[3]=891.

TWO-DIMENSIONAL ARRAY

- Collection of M x N elements such that each element in the array is

referenced by a pair of integer such as j,k called the subscript.

- Also called matrix in mathematics and tables in business applications

therefore they are considered to be matrix array

- Has elements that form a rectangular array

Syntax:

[] [];

e.g.

int x[3][4];

Illustration: 3 x 4 array in column major 3 x 4 array in row major

- row varies faster than column - column varies faster than row 1 2 3 4 1 2 3 4 1 1,1 1,2 1,3 1,4 1 1,1 2,1 3,1 4,1 2 2,1 2,2 2,3 2,4 2 1,2 2,2 3,2 4,2 3 3,1 3,2 3,3 3,4 3 1,3 3,2 3,3 4,3

To determine the Total number of elements:

NE = M * N

Where:

NE = number of elements

M = UB1 LB1 + 1

N = UB2 LB2 + 1

CSCI05 CS INSTRUCTIONAL MANUAL

7

To compute for the address of an element (memory

Recommended

View more >