DATA STRUCTURE USING C
MODULE 1
Prepared by,
Nasiya PM
Assistant Professor
Dept.of BCA
MES Asmabi College
P.Vemballur
DATASTRUCTURE
Data sructure is the way of organizing all data items in
order that not only elements to be stored but also the
relation between the elements
Data type vs data structure
GOALS OF DATA STRUCTURES
1. Correctness
Mean that a data structure is designed to work correctly
2. Efficiency
Useful data structure and their operations also need to befficient.
3. Robustness
Which means that program produces correct output for all input
4. Adaptability
need to increase cpu speed
5. Reusability
software reuse can be a cost and time saving technique.
1.Primitive data structure
Definition:
which are readily available in programming
language
eg: integer,float,double,pointer
Operations on primitive data structures
Creation
Selection
Update
Destroy
1.Non Primitive data structure
• That are composed of primitive data structure
Which are not readily available in programming
language
Classified as 2 (linear and non linear)
1. Linear data structure
A data structure is said to be linear if there is an
adjacency relationships between elements
Eg: Arrays,string,linked lists,stack,queue
Array : elements are always stored incontiguous memory
locations.
Linked lists:
Linked list is a collection of elements called nodes.Each
node contains two parts. they are data part and link part .
Stack : Stack is an ordered list of the same type of
elements.Stack is a LIFO (Last In First Out) structure.
Queues : Queue is an abstract data structure, Unlike
stacks, a queue is open at both its ends. One end is always
used to insert data (enqueue) and the other is used to
remove data (dequeue).
It follows the FIFO (First - In - First Out) structure
2, Non Linear data structure
Which insertion and deletion operation is not possible in
a linear fashion.
Eg: Tree,Graph,set,Table
Tree :defined as a finite set of one or more nodes such
that there is one specially designated node called ROOT.
and the remaining nodes are partitioned into a collection
of sub-trees of the root each of which is also a tree.
Graph : A Graph is a non-linear data structure
consisting of nodes and edges. The nodes are sometimes
also referred to as vertices and the edges are lines or arcs
that connect any two nodes in the graph.
Operations on non primitive data structures
Traversing
Sorting
Merging
Searching
Insertion
Deletion
Complexity of Algorithm
Algorithm is step by step procedure to solve a problem.
There are 2 main reason to judge an algorithm
1.correctness of the algorithm
2. simplicity of the algorithm
Correctness of an algorithm can be analyzed by tracing the
algorithm with certain sample data and by trying to answer
certain questions questions.
Simplicity of an algorithm can be analyzed by trying to
understand whether the algorithm can be implemented in a
better and much simpler way.
There are 2 parameters to measure efficiency of algorithm
1. Time Complexity
2. Space Complexity
Time complexity
Time complexity of algorithm is the amount of time
it needs to run to completion.
The time complexity of a program (for a given
input) is the number of elementary that this program
executes.
The time T(P) taken by a program P is the sum of
compile time and the run(or execution ) time.
Space complexity
Space complexity of an algorithm is the amount of
memory it needs to run to completion.
The space complexity of a program (for a given
input) is the number of elementary objects that this
program needs to store during its execution.
This number is computed with respect to the size of
n of the input data.
Best case, Worst case and Average case complexity
Worst case complexity
Worst case complexity of an algorithm is the
function defined by the maximum number of steps
taken on any instance of size n.
It represents the curve parsing through highest point
of each column
Average case complexity
function defined by the average number of steps
taken on any instance of size n.
Best case complexity
function defined by the minimum number of steps
taken on any instance of size n.
It represents the curve parsing through lowest point
of each column.
O-notation [Big oh]
We use O-notation, where we have only an asymptotic
upper bound.
For a given function g(n),we denote by O(g(n)) the set
of functions.
Definition:
O(g(n))= {f(n) :there exist positive constants C and no
such that 0≤ f(n) ≤ C g(n) for all n≥ no }
Forall values of n to the right of no ,the value of f(n) is
on or below g(n) .
O-notation [Big oh]
Example :3n+2= O (n) as,
f(n)=3n+2≤4n for all n≥2
solution:
f(n)=3n+2
f(n)=3n+2 ≤4n
if n=1,
3*1+2=6 ≤4*1(wrong)
if n=2,
3*2+2=8≤4*8(correct)
So for all n≥2, f(n) ≤c. g(n)
Hence, f(n)=O(g(n))
O(1)-means computing time is constant
O(n)- ’’ ” linear
O(n2)- ’’ ” quadratic
O(n3)- ’’ ” cubic
O(2n)- ’’ ” exponential.
LIMITATION OF BIG “OH” NOTATION
1. It contains no effort to improve the programming
methodology. Big Oh Notation does not discuss the way
and means to improve the efficiency of the program.
2. It does not exhibit the potential of the constants.
