1. What
is Data structure?
How
effectively we are storing the data it’s called as data structure.
Data structure is particular way of storing
and organizing data so that it can use efficiently.
Structuring the data which really help us
to manage it properly.
Let’s take the example of Dictionary (defined into liner form), Cash book (defined in tabular form)
Let’s take the example of Dictionary (defined into liner form), Cash book (defined in tabular form)
It is not a language it’s a set of algorithm
or process which help to store data effectively.
Data structure à
Algorithm à
Abstract Data type à
Set of rules
Algorithm à Array, Stack, Queue, linked list, tree, graphs
Algorithm (data structure) is divided into two types ::
Algorithm à Array, Stack, Queue, linked list, tree, graphs
Algorithm (data structure) is divided into two types ::
·
Liner Data structure – Data are structure in
sequential format one data connected to another. Like array, stack, queues,
Linked list.
·
Non Liner Data structure - Non Liner format. One
data connect to multiple data. example Trees and graph
2. Abstract
Data Type in Data structure
Data structure is all
about creating abstract data type.
Combination of data structure and their operation are known
as Abstract Data Type.
Store the given number of element into any type of element.
Read element by position or modify element by position is called as ADT.
Like: Arrays, Linked List, Stack, Queue, Tree, Graph etc.
2.1 Array:
Store the given number at given datatype, write & read element
in position.
Int i[10];
·
It holds more than one element. Finite number of
collections.
·
Homogenous data type.
·
Index based
·
Doesn’t follow any algorithm.
·
Derived datatype
How to initialize Array.
Int arr[5] = { 10, 20, 30,40, 50};
0
|
1
|
2
|
3
|
4
|
10
|
20
|
30
|
40
|
50
|
2046
|
2048
|
2050
|
2052
|
2054
|
Number of arr[n] is called
size of array.
Calculate the location of array value as (Base address +
size of int * n) e.g. a[3] :: 2046 + 2
*3 :: 2046 + 6 :: 2052
The process of one multiplication and one addition. This two
operation take the constant time and we
can say that array access can performed in constant time.
Array Dimension
A[n] : it is one Dimension array
arr[3]
0
|
1
|
2
|
10
|
20
|
30
|
2046
|
2048
|
2050
|
A[n][m] : it is two Dimension array
e.g : way of
representing data Arr[2][3]
0
|
1
|
2
|
|
0
|
20
|
30
|
40
|
1
|
12
|
10
|
12
|
2
|
10
|
4
|
5
|
3
|
6
|
78
|
8
|
2.2 Dynamic Array :
Empty List has 0 size, insert, Remove, count, Read &
modify element at the position.
When array is full create, create a new larger array, free
the memory for the previous array. But it is very costly operation to insert
the new element in the given position and shift the values.
Access – Read/write at an index. Constant
time O(1)
Insert – O(n).
Remove – O(n)
Add – O(n)
2.3 Linked List
It is liner data structure , its collection of element.
Element is called as Node, each element has value(data) and reference of Next
node. Microsoft Provide strongly typed linked list LinkedList(T) in
System.Collections.Generic namespace.
Linked List is mainly three types::
Singly Linked List: It contains the value and reference of next
node. Last node next reference will be null.
Benefits: It
is dynamic data structure, where length of array is predefined.
Doubly Linked List:
It contains data and 2 references. One of the next reference and another for
the previous reference.
Benefits: Doubly
linked list offers easy implementation of many operations, whereas singly
linked list requires more info for the same operation. e.g. Deletion of singly
linked list, we need a pointer to it for previous node.
It traverses in both forward and backward direction.
Circular Linked
List : Here last nodes reference
will be head or first element.
2.4 Stack :
Stack
is liner data structure, it is ADT which is used in most of the
programming language. It is follow the rule of FILO ( First In Last Out) or
LIFO (Last in first out).
Mainly two basic operation perform in stack.
Mainly two basic operation perform in stack.
Push : Add new items into stack. If the stack is full
than it is said to be overflow condition.
POP : Remove the items from
the stack.
We can check the status of stack as like:
Peek() : Get the top data
element of the stack.
IsFull() : Check if the stack
is full.
IsEmpty() : Check if the stack is
empty.
2.5
Queue
Queue is liner data type like Stack; treat as an abstract
datatype in Data structure. Unlike array it is open ended from both side.
One end is always use to insert data is called enqueue. Another is used to remove the data is called as Dequeue.
One end is always use to insert data is called enqueue. Another is used to remove the data is called as Dequeue.
It follow the process of FIFO(First in first out). The data
which store first will be accessed first.
Basic Operations in Queue:
Enqueue() : Add
(store) an item into queue.
Dequeue() :
Remove the items from the queue.
Peek() : Get the
element at the front of the Queue.
Isfull() : Checks
if the queue is full.
IsEmpty() : Check if the queue is empty.
2.6. Trees
Tree is non liner data type; it’s a ADT in data structure. You can see the data in the tree as like Multiple
nodes, where each node has some associated data and set of children. Nodes are
in two parts, parent and children.
Node just beneath of the other node are called as children node. Node just above the node is called as parent node. There is Root in all the tree, for root node don’t have any parent.
Node just beneath of the other node are called as children node. Node just above the node is called as parent node. There is Root in all the tree, for root node don’t have any parent.
e.g. Organization structure
of any company is in tree format.
There is special kind of tree where each parent node is
having only two children which is called as Binary Tree.
Nodes which don’t have any children which is called as Leaf node. Nodes which have one or Two
children are referred as internal nodes.
3. Analysis
of algorithm
Time & Space – less time and space is good algorithm
Calculate the good algorithm by Rate of Growth; the rate at
which the running time increases as a function of input is called rate of
growth.
Analyzing of time complexity
Running time depends upon:
a.
Single or multiprocessor
b.
Read/write speed of memory
c.
32 bit or 64 bit
d.
Input [
we need to check this in our programming]
Rate of growth of input machine.
Before calculating the time you need a model computer. Let’s
take an example and consider 1 unit time for arithmetical and logical and 1
unit for assignment and return.
Sum of number :
SumofNumber( a,b)
{
Return a+b; à
1 unit for sum and 1 Unit for return so total time for it is 2 Unit.
}
Let’s take another sum of n numbers in array;
Lets see the calculation for simple, liner and complex application.
4. Type of analysis
To analysis the algorithm we need to know on what input algorithm
is taking less time and what will take more time.
Worst case
Average case
Best case
Take an example of 10 number which you need to arrange in
order, if the number is already in order than it is best case. Suppose it
distorted like any thing than it can be the worst case and Average case is
middle of it.
5. Asymptotic
Notation
For all three case we need to identify the Upper and Lower
bounds.
Syntax representation of bounds are :
Big o notation –
finding the upper bound it is denote by O(n)
Omega notation –
finding the lower bound.
Theta notation –
finding the upper and lower bound both
6.
Recursion of Data structure
1.
The function which will call itself is called as
recursion.
2.
Recursive code is generally shorter and easier
to write than iterative problem.
3.
It terminate when base case has reached.
4.
Each recursive call requires extra space in the
stack memory. [In term of memory it is not good if more recursive]
5.
You need to have some point where you need to
close the recursion.
e.g:
6.1. List of application for recursion.
a.
Fibonacci Series
b.
Factorial of number
c.
Greatest common divisible
d.
Tower of Hanoi
e.
Graph traverse (DFS & BFS)
f.
Tree traversal
g.
Merge sort and Quick Sort
h.
Back tracking algo
6.2. Fibonacci series:
Sum the last two numbers.
It is as 0 1 1 2 3 5 8 13 21 34 55 89 …
To get the Fibonacci of Fib(5) you need to
add fib(4) and fib(3)
Fib(5) = fib(4) + fib(3)
Fib(4) = fib(3) + fib(2)
Fib(3) = fib(2) + fib(1)
Fib(2) = 1
Fib(1) = 1
Print the Fibonacci number is Recursive function
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter Number");
int val = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Fibonacci series is :: ");
for(int i = 1;i <= val;i++)
Console.Write(Fib(i) + ", ");
}
public static int Fib(int n)
{
if (n == 1 || n == 2)
return 1;
return ( Fib(n -1) + Fib(n - 2));
}
}
|
Program to check that number is Fibonacci or
not
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter Number");
int val = Convert.ToInt32(Console.ReadLine());
/// Print febonacci series
//Console.WriteLine("Febonacci series is ::
");
//for(int i = 1;i <= val;i++)
//
Console.Write(Fib(i) + ", ");
/// Is that fibonacci number
Console.WriteLine("It is {0}
Fibonacci", IsFibnacci(val) == true ? " " : " not" );
}
public static int Fib(int n)
{
if (n == 1 || n == 2)
return 1;
return ( Fib(n -1) + Fib(n - 2));
}
public static bool IsFibnacci(int n)
{
return IsperfectSquare(5
* n * n + 4) || IsperfectSquare(5 * n * n);
}
public static bool IsperfectSquare(int x)
{
int half = x/2;
int i =1;
bool isperfectsquare =
false;
while( i < x/2)
{
if(i * i == x)
{
isperfectsquare = true;
}
i++;
}
return isperfectsquare;
}
}
|
6.3. Factorial Number
Multiplication of
values till number pass.
5! = 5 X 4 X 3 X 2 X 1
Fact(5)
= 5 X fact(4)
Fact(4) = 4 X fact(3)
Fact(3) = 3 X fact(2)
Fact(2) = 2 X fact(1)
static void Main(string[] args)
{
Console.WriteLine("Enter Number");
int val = Convert.ToInt32(Console.ReadLine());
/// Print Factorial number
Console.WriteLine("Factorial series is :: {0}", fact(val));
}
public static long fact(int n)
{
if( n >0)
return (n * fact(n -1));
else
return 1;
}
|
6.4. Greatest common divisible
Finding the greatest
common divisible between the numbers.
E.g GCD of 4 and 6
4 = 4 2 1
6 = 6 3 2 1
So, 2 is greatest common divisible GCD(4,6)
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter 1st Number");
int val1 = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Enter 2nd Number");
int val2 = Convert.ToInt32(Console.ReadLine());
/// Get the gretest common
division
Console.WriteLine("GCD is :: {0}",
GCD(val1, val2));
}
public static int GCD(int n,int m)
{
if (n == m)
return n;
if(n % m == 0)
return m;
if (m % n == 0)
return n;
if (m < n)
return GCD(n % m, m);
else
return GCD(m % n, n);
}
}
|
7.
Searching Techniques
In data structure we come across many ways to search the
particular data in an array or list.
7.1. Liner Search
Liner search or sequential search are technique on which
every item will check sequentially and match with the given item. If find the
particular match than it will return that item.
Let’s see the algorithm for it.
Arr[6] = 12, 56, 18, 90, 38, 67, 72
Search value = 18
Step 1: Initialize i which work as count of array
Step2: Check condition if i <= arr.lenth -1
Step3: if value == arr[i] than break else Continue
Step 4 : increase count of i++. Goto step 2
Step 5 : Print : value found in ith position.
Step 6: Exit
The complexity of liner search algorithm in O(n).
No comments:
Post a Comment