1. Number of vertex in graph G = Number of vertex in spanning tree.
2. If n = Number of vertex in graph G than spanning tree has (n-1) edges.
3. Spanning tree does not have any cycle.
Example:
Logic of Interpolation Search
int Interpolation-search(int a[50],int low,int high,int s)
{
int mid;
if(low<=high)
{
mid=low+(high-low)*((s-a[low])/(a[high]-a[low]));
if(a[mid]==s)
{
return(mid);
}
Logic of Shall sort
void shall-sort(int a[50],int n)
{
int d,temp,i,flag;
d=n/2;
while(d>=1)
{
Hashing :
Hashing is a search technique in which a specific function is used to store & retrieve data from memory this function is called hash function.
Deque or Double Ended Queue:
In Deque or Double Ended Queue insertion and deletion takes place from any end of queue. We can insert or delete from rare (R) end and also from front (F) end.
Circular Queue:
If Simple Queue have a single element at its last position i.e (size-1) and if we try to insert a new element than simple queue gives message " Queue is Full " , But almost queue is empty.
For overcoming this drawback we use Circular Queue.
Necessary Conditions for Circular Queue
Condition 1:
if (F=-1 and R==-1)
{
printf ("Queue is empty");
}
QUEUE:
Queue is data structure which follow the concept of FIFO & LIFO. In other words insertion can be made at one end called RARE and deletion can be done at other end called FRONT.
Conversion of Infix to Post fix Expression using stack
Example:
Infix : a + b * c - d
1. How we delete node at First ?
2. How we delete node at Last ?
3. How we delete node at specific position ?
I will give you a complete logic for every case.
In this post I will show you how we perform Insertion operation in Circular Linked List in different ways. Like:
1. How we insert node at First ?
2. How we insert node at Last ?
3. How we insert node at specific position ?
I will give you a complete logic for every case.
In this post I will show you how we perform deletion operation in Doubly Linked List in different ways. Like:
1. How we delete node at First ?
2. How we delete node at Last ?
3. How we delete node at specific position ?
I will give you a complete logic for every case.
In this post I will show you how we perform Insertion operation in Doubly Linked List in different ways. Like:
1. How we insert node at First ?
2. How we insert node at Last ?
3. How we insert node at specific position ?
I will give you a complete logic for every case.
In this post I will show you how we perform deletion operation in Singly Linked List in different ways. Like:
1. How we delete node at First ?
2. How we delete node at Last ?
3. How we delete node at specific position ?
I will give you a complete logic for every case.
In this post I will show you how we perform Insertion operation in Singly Linked List in different ways. Like:
1. How we insert node at First ?
2. How we insert node at Last ?
3. How we insert node at specific position ?
I will give you a complete logic for every case.
Radix Sort: In radix sort first we find the largest number from the given number and then count the number of digit that contain the largest number. In this algorithm we consider 10 columns 0-9 because each digit must lies between 0-9.In this process every time we will find first unit place digit,tens place,hundred place digit and so on... on the basis of that digit we will place that digit in the particular column .All the process is perform in a matrix so we will create matrix of [n][m] and by default place -999 into matrix. This process is perform until we are not getting sorted list.After that we will convert matrix into an array.
1. Find Big number.
2. Count number of digit of N numbers.
3. Find Position of digit.
4. Fill matrix with any number which are not in given array like -999
5. Matrix is converted into an array.
And than finally we get sorted list.
#include<conio.h>
#include<stdio.h>
void radixsort(int a[],int n);
int bigno(int a[20],int n);
int numdigit(int big);
void fillmat(int m[20][10],int n);
void makearray(int m[20][10],int a[20],int n);
void main()
{
int a[20]={2134,231,4513,177,6355,233,5},n,i;
//printf("Enter the value of n:");
//scanf("%d",&n);
n=7;
radixsort(a,n); // Call Radix Sort Function
getch();
}
// Radix Sort Function
void radixsort(int a[20],int n)
{
int big,k,col,m[20][10],row,i,j;
big= bigno(a,n);
//printf("Big number is:",big);
k= numdigit(big);
//printf("%d",k);
printf("\n");
for(i=1;i<=k;i++)
{
fillmat(m,n);
for(row=0;row<=n-1;row++)
{
col=poss(a[row],i);
m[row][col]=a[row];
}
makearray(m,a,n);
}
//print matrix
for(i=0;i<n;i++)
{
{
printf("%d\t",a[i]);
}
}
}
// Function for finding Big Number
int bigno(int a[20],int n)
{
int i,big;
big=a[0];
for(i=0;i<n;i++)
{
if(a[i]>big)
{
big=a[i];
}
}
return(big);
}
// Function for find number of digit in big number
int numdigit(int big)
{
int c=0;
while(big>0)
{
c++;
big=big/10;
}
return(c);
}
// Function for fill matrix
void fillmat(int m[20][10],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<10;j++)
{
m[i][j]=-999;
printf("%d\t",m[i][j]);
}
printf("\n");
}
}
// Function for find position of digit
int poss(int n,int pos)
{
int digit;
while(pos>=0)
{
digit=n%10;
n=n/10;
pos--;
}
return(digit);
}
// Function for convert matrix into array
void makearray(int m[20][10],int a[20],int n)
{
int i,j,k=0;
for(i=0;i<=10;i++)
{
for(j=0;j<n;j++)
{
if(m[j][i]!=-999)
{
a[k]=m[j][i];
k++;
}
}
}
}
Definition: A non-linear data structure is called tree.
Note :
👉 The line drawn from a node N of tree T to a successor (child) is called an edge
👉 A binary tree is defined as a finite set of element is called nodes.
👉 Those nodes which have no parent is called root node.
👉 Those node which have no child is called leaf node.
1. All leaf node are at same level.
2. All intermediate nodes except the roots can have at most 'm' non - empty children's and can have as few as integer value of m/2.
3. Each node of B-Tree has are less key than its number of children and keys are inserted in a search tree fashion.
4. The root of B-Tree can have at most 'm' non-empty children and can have as few as two if root is alone.
5. Each intermediate key has a similar copy in its successor or predecessor leaf.
6. All leaf are connected through a direct link in a link list fashion.
