Data Structure (KCS-301)

Unit 1

Prepared By
N. U. Khan
Computer Science And Engineering Department
IMS Engineering College, Ghaziabad
N U Khan 1
 Data Structure (Definition)
• It is a representation of the logical relationship
among individual elements of data
• It is a logical model of a particular organization of
data in computer’s memory in such a way that it
convenient to perform operations on it.
• DS = Organized data + Allowed operations
• i.e. DS is a collection of data elements whose
organization is characterized by accessing
functions that are used to store and retrieve
individual data elements
N U Khan 2
 Types of Data Structure
• On the basis of organization there are two type of
data structure
1. Linear Data Structure :
The elements form a sequence i.e. data
elements have only one successor and one
predecessor (e.g. Stack & Queue)
2. Non Linear Data Structure:
The elements do not form a sequence i.e. data
elements have multiple successor and multiple
predecessor (e.g. Tree & Graph)
N U Khan 3
Classification of Data Structure
Data
Structure

Non-
Primitive Primitive

Non Linear
Linear D.S.
D.S.

N U Khan 4
 Primitive Data Structure
• It is predefined data structure i.e. basic data
types which have single value (e.g. int, float,
char, pointer)
• There are basic structures and directly
operated upon machine instructions
• Data structures that are directly operated
upon the machine-level instructions are
known as primitive data structure

N U Khan 5
 Primitive Data Structure
int x, y; STACK AREA

main()
{
int p, q;
-------
-------
}
HEAP AREA

N U Khan 6
 Memory management in C
Local /Automatic variable are
stored on STACK they would
have descending address
Which grows downward in
memory

Global/External variables are

N U Khan 7
 Non-Primitive Data Structure
• It is also called as composite data structures
having multiple values (e.g. Arrays, Lists,
Stacks, Queues, Trees, Graphs )
• The data structures that are derived from the
primitive data structures are called Non-
primitive data structure

N U Khan 8
 Operations on Data Structure
• Create:
Allocation of memory
• Destroy:
De-allocation of Memory
• Selection:
Accessing the data elements
• Updation:
Store, Modify and Delete
• Searching
• Sorting

N U Khan 9
 Significance of Data Structures
• Data Structures + Algorithms = Programs
• Data structures are the building blocks of a
program
• Therefore selection of particular D.S. that best
suites the requirement is most important step
in the program design

N U Khan 10
 Algorithms
• It is a solving process of any task that can be
carried out systematically using a precise step
by step method which is performed by a
computer.
• i.e. Algorithm must be precise and
unambiguous the total time to carryout all the
steps in the algorithm must be finite

N U Khan 11
 Algorithm complexity
• There are number of way to solve the problem
but the efficient way is called good
programming,
• Criteria of efficient algorithm depends on:
1. Time complexity: Amount of time needs to
run a programs
2. Space complexity: Amount of memory space
needs to run a program

N U Khan 12
 Time-space trade-off
• There may be more than one approach to
solve a problem:
• One such approach may require more space
but takes less time to complete its execution.
• The second approach may require less space
but takes more time to complete its execution
• We have to choose the first approach if time is
our constrain if space is our constraint then
we have to choose the second approach
N U Khan 13
 Frequency count
float sum(float a[], int n)
{ 0
float sum=0; 1
int i; 1
for ( i=0; i<n; i++ ) n+1
sum += a[i]; n
return(sum) 1
} 0
Total: 2n+4
T(n) = O(n)
N U Khan 14
 Frequency count
Add( int a[][], int b[][], int c[][] int m, int n)
{ 0
for( i=0; i<m; i++ ) m+1
for(j=0; j<n; j++ ) m*(n+1)
c[i][j] = a[i][j] + b[i][j]; m*n
} 0
Total:2mn+2m+1
T(n) = O(mn)

N U Khan 15
 Tutorial Sheet
• Q1 Determine the frequency count for all
statements in the following program segment
1. for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
x++

• Q2 Compare the two functions n2 and 2n the for

N U Khan 16