Data Structures and
Algorithm
Continuation…
Objectives:
Data Structure and Algorithm relationship
Identify the categories types of Data Structures
Basic Concepts
The term data structure is used to describe the
way data is stored, and the term algorithm is used
to describe the way data is processed.
Data structures and algorithms are interrelated.
Choosing a data structure affects the kind of
algorithm you might use, and choosing an
algorithm affects the data structures we use.
Basic Concepts
An Algorithm is a finite sequence of
instructions, each of which has a clear
meaning and can be performed with a
finite amount of effort in a finite length of
time. No matter what the input values may
be, an algorithm terminates after executing
a finite number of instructions.
To develop a program of an algorithm we should
select an appropriate data structure for that
algorithm. Therefore, data structure is
represented as:
Algorithm + Data structure = Program
Categories of Data Structure:
The data structure can be sub divided into
major types:
Linear Data Structure
Non-linear Data Structure
Categories of Data Structure:
Linear Data Structure: A data structure is said to be
linear if its elements combine to form any specific
order. There are basically two techniques of
representing such linear structure within memory.
The common examples of linear data structure are:
Arrays
Queues
Stacks
Linked lists
Categories of Data Structure:
Non linear Data Structure: This structure is
mostly used for representing data that contains a
hierarchical relationship among various elements.
Examples of Non Linear Data Structures are listed
below:
Graphs
family of trees and
table of contents
Types of Data Structure:
Data structures are divided into two types:
• Primitive data structures.
• Non-primitive data structures.
Data structures are divided into two types:
Primitive Data Structures are the basic
data structures that directly operate upon
the machine instructions. They have
different representations on different
computers. Integers, floating point
numbers, character constants, string
constants and pointers come under this
category
Data structures are divided into two types:
Non-primitive data structures are more
complicated data structures and are
derived from primitive data structures.
They emphasize on grouping same or
different data items with relationship
between each data item. Arrays, lists and
files come under this category.
Organization of data
The collection of data you work with in a program
have some kind of structure or organization. No
matter how complex your data structures are they
can be broken down into two fundamental types:
• Contiguous
• Non-Contiguous.
In contiguous structures, terms of data are kept
together in memory (either RAM or in a file). An array
is an example of a contiguous structure. Since each
element in the array is located next to one or two
other elements. In contrast, items in a non-
contiguous structure and scattered in memory, but we
linked to each other in some way. A linked list is an
example of a non-contiguous data structure. Here,
the nodes of the list are linked together using
pointers stored in each node.
Contiguous structures:
Contiguous structures can be broken drawn
further into two kinds: those that contain data
items of all the same size, and those where the
size may differ. The first kind is called the array.
The second kind of contiguous structure is called
structure. In a struct, elements may be of
different data types and thus may have different
sizes.
Non-contiguous structures:
Non-contiguous structures are implemented
as a collection of data-items, called nodes,
where each node can point to one or more
other nodes in the collection. The simplest
kind of non-contiguous structure is linked
list.
Algorithm Part-2
Example
Psuedocode Time Space
sum(n): 1
i, sum = 0 1 1+1
for (i=1; i <= n ; i++) n+1
sum = sum + 1 n
return sum 1
T(x) = 1 + (n+1) + n +1
s(x) = 3
T(x) = 2n + 3
Example
Psuedocode Time Space
sum(arr[], n): n+1
i, sum = 0 1 1+1
for (i=0; i < n ; i++) n+1
sum = sum + arr[i] n
return sum 1
T(x) = 1 + (n+1) + n +1 S(x) = n+1+1+1
T(x) = 2n + 3 T(x) = n + 3
Example
Psuedocode Time Space
sum(arr[], n):
i, sum = 0
for (i =0; i < n ; i++)
sum = sum + arr[i]
for (i =0; i < n ; i++)
sum = sum + arr[i]
return sum
Activity #1
Psuedocode Time Space
sum(int arr[][], n):
i, j, sum = 0
for (i =0; i < n ; i++)
for (j =0; j < n ; j++)
sum = sum + arr[i][j]
return sum
Activity #1
Psuedocode Time Space
sum(int arr[][], n):
i, j, k, sum = 0
for (i =0; i < n ; i++)
for (j =0; j < n ; j++)
for (k =0; k < n ; k++)
sum = sum + arr[i][j]
return sum
