Data Structure
What is Data Structure-?
Organized collection of data in a particular format is called data structure. It is a technique or method of study that how the data are inter-related to each other logically or mathematically.
Classification of the Data Structure:-
1. Linear and Non-Linear
2. Homogenous and Heterogenous
3. Static and Dynamic Data Structure
Searching in data structure with types
Searching is a method to finding an element from data structure with their appropriate location.
Divided in two types:-
1. Linear Search
2. Binary Search
What is Linear Search-?
Linear search is a very basic and simple search algorithm. In linear search we search an element in given array by traversing the array from the starting till the desired element is defined.
Algorithm of Linear Search
Step 1:- Begin
Step 2:- Set a[5] ⬅ {10,20,30,40,50}
Step 3:- Set i ⬅ 0
Step 4:- Input searching item
Step 5:- Repeat step 6 and 7 while i＜4
Step 6:- If a[i]=item, then print item found and location=i and exit
Step 7:- i ⬅ i+1
Step 8:- If i＞=5, then print item not found
Step 9:- End
Program of Linear Search
#include<stdio.h>
#include<conio.h>
void main( )
{
int a[5]={10,20,30,40,50}, i=0, item;
clrscr;
printf("Input searching item....";)
scanf("%d",& item);
while (i<5)
{
if (a[i]==item)
{
printf("Item found location=%d",i);
break;
}
i++;
}
if (i>=5)
printf("Item not found");
getch( );
}
User Input numbers
#include<stdio.h>
#include<conio.h>
void main( )
{
int a[5] i=0, j, item;
clrscr;
printf("Enter array element");
for(j=0;j<5;j++)
{
scanf("%d",&a[j];)
}
printf("Input searching item....";)
scanf("%d",& item);
while (i<5)
{
if (a[i]==item)
{
printf("Item found location=%d",i);
break;
}
i++;
}
if (i>=5)
printf("Item not found");
getch( );
}
Meaning of Algorithm
Step-by Step detailed description of any program is called Algorithm
What is Binary Search-?
Binary Search is the divide and conquer searching technique in which we have to arrange the data in particular format or order before searching operation. After that we find the middle element of array and compare with the target element.
If item is not found then we again check the target element is greater then or less then middle element, if it is greater then middle element other wise left side of middle element.
Algorithm of Binary Search
Step 1:- Begin
Step 2:- Set a[5] ⬅ {10,20,30,40,50}
Step 3:- Set lr ⬅ 0, up ⬅ 4, f ⬅ 0
Step 4:- Input searching item
Step 5:- Repeat step 6, 7 and 8 while (lr<=up)
Step 6:- Set mid ⬅ lr+up by 2
Step 7:- If a[mid]=item, then Set F=1 & break
Step 8:- If a[mid]<item, then Set lr ⬅ mid+1
else
Set up ⬅ mid-1
Step 9:- If F=1, then print item found with loc=mid
else
print item not found
Step 10:- Exit
Program of Binary Search
#include<stdio.h>
#include<conio.h>
void main( )
{
int a[5]={10,20,30,40,50}, lr=0, up=4, f=0, mid, item;
clrscr();
printf("Enter searching item:");
scanf("%d",&item);
while (lr<=up)
{
mid=(lr+up)/2;
if (a[mid]==item)
{
f=1;
break;
}
if (a[mid]<item)
lr=mid+1;
else
up=mid-1;
}
if (f==1)
printf("Item found with location=%d", mid);
else
printf("Item not found");
getch;
}
What is Stack-?
✱ Stack is a collection of data item where the insertion and deletion tales place on one end called TOP of the stack.
✱ In stack we can perform two operations i.e..., PUSH and POP.
➡ PUSH means inserting a new item into the stack
➡ POP means deleting an item from the stack
✱ Stack always perform LIFO operation that means last in first out, A stack can represent by the help of Array and linked list.
Difference between Stack and Queue.
S.no. | Stack | Queue |
1 | Stack follow LIFO operation, i.e.., last in first out | Queue follow FIFO operatio, i.e.., first in fist out |
2 | Insertion and Deletion takes places on one end | Insertion and deletion takes place on opposite end |
3 | Stack perform two operations, i.e.., PUSH and POP | Queue perform two operation, i.e.., REAR and FRONT |
4 | In Stack:- | In queue:- |
| 1. PUSH is used to insert the element in the stack | 1. REAR is used to insert the element in the queue |
| 2. POP is used to delete the element from the stack | 2. Front is used to delete the element from the queue |
5 | Stack doesn't have any type | Queue has various type like General Queue, Circular Queue and Doubly Queue |
6 | In stack only one pointer is used, i.e.., top of the stack | In queue two different pointers are used REAR & FRONT |
Algorithm for PUSH operation in Stack
Step 1:- Begin
Step 2:- If TOP =N then
Print overflow and exit
Step 3:- Input new item
Step 4:- Top ⬅ TOP+1
Step 5:- Stack [TOP] ⬅ item
Step 6:- Exit
Algorithm for POP operation in Stack
Step 1:- Begin
Step 2:- If TOP=-1
Step 3:- Set item ⬅ stack [TOP]
Step 4:- TOP ⬅ TOP-1
Step 5:- Print deleted item
Step 6:- Exit
Program of Stack
#include<stdio.h>
#include<conio.h>
int stack[5], top=-1;
void push( );
void pop( );
void show( );
void main( );
{
int ch;
clrscr( );
printf("1. PUSH\n");
printf("2. POP\n");
printf("3. SHOW\n");
printf("4. EXIT\n");
while(1)
{
printf("\n Enter choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:push( );
Break;
case 2:pop( );
Break;
case 3:show( );
Break;
case 4:exit( );
Break;
default:printf("Invalid Option");
}
}
}
void push( )
{
int item;
if (top==5-1)
{
printf("stack is full")
}
else
{
printf("Push element is stack: ");
scanf("%d",&item;)
top=top+1;
stack[top]=item;
}
}
void pop( )
{
if (top==-1)
{
printf("Stack is emplty");
}
else
{
printf("POPPED %d",stack[top]);
top=top=1;
}
}
void show( )
{
int i;
if (top>=0)
{
printf("Stack element %n ");
for(i=top;i>0;i--)
{
printf("%d, stack[i]");
}
}
else
{
printf("stack is empty");
}
}
No comments:
Post a Comment