DATA  STRUCTURE


Data : It is a plural form of the word 'datum'. Data  are raw facts & figures that becomes information after processing. In computer science, everything's is considered as data but their forms are different.
Data can be found following forms : Text, Numerals, Images, Audio, Videos, etc.

Data Structure : It is a branch of computer science in which data are organized in different - different forms. It means, the organization of data in various pre-defined formats is called as data structure.
Each data structure has its working principle /  behavior, property & some pre-defined operations

.  Types of Data Structures :-
-  Basically two types of data structure :-
    1. Primitive Data Structure.
    2. Non - Primitive Data Structure.

1. Primitive Data Structure :- A data structure which organized primitives data such as integer, real(float/double), character, etc. is called primitive data structure. Example : int, char, float, double, etc.

2. Non - Primitive Data Structure :- A data structure in which organization is formed with the help of primitive data as well as some complex structures is known as non-primitive data structure. Example :- stack, queue, link-list, linear search, etc.

. Types of non-primitive data structures :-
- Basically two types of non-primitive data structure.
    1. Simple 2. Compound

1.) Simple :-  In simple data structure both similar and dissimilar types of data are organized. Example : Array, Structures.

2.) Compound :-  In compound data structure, multiple forms of data structures are combined to create a complex structure.

. There are two category of compound data structure :-
    1. Linear Data Structure 2. Non-linear Data Structure

1.) Linear Data Structure :- In linear data structure data organized in a particular form/pattern. A specific pattern such as LIFO (Last In First Out), etc. is used in linear data structure. Example : STACK, Queue, Link-List.

2.) Non-linear Data Structure :-  A Data Structure that does not follow any specific sequence/pattern is called as non-linear data structure. Example : Tree, Graph.

#  Operations performed on data structure :-
- Each Data Structure has its own operation's. There are following basic operations can be performed on a data structure :-

1.) Creation - It is the process of creating a new data structure.
2.) Transversal/Display - It is the process of visiting elements/items of a data structure.
3.) Insertion - It is the process of adding elements in data structure.
4.) Deletion - It is the process of removing elements in data structure.
5.) Reversal - It is the process of retrieving elements of a data structure from end to beginning.
6.) Searching - It is the process of locating an elements within data structure.
7.) Sorting - It is the process of ordering/sequencing elements of data structure. The order may be ascending or descending order.
8.) Merging - It is the process of combing two sorted data structure to create a new data structure.
9.) Concatenation - It is the process of adding a data structure at the end of another data structure.

# There are basically two types of searching operations :-
1. Linear/Sequential Search     2. Binary Search

1.) Linear / Sequential Search :-  In this technique elements is search into list from beginning to end till lit is not finished.
Example :- 
1.) Program for perform linear search.
-    /* Program for linear search. */
      #include<stdio.h>
       main()
       {
    int a[10], i, data, status=0;
    printf ("Enter 10 Elements:- \n");
    for(  i=0; i<10; ++i)
    {
          scanf("%i",&a[i]);
    }
    printf ("Enter a number to search in list = ");
    scanf("%d",&data);
    for( i=0;i<10;++i)
    {
      if(a[i] == data)
        {
              status=1;
              break;
    }
    }
    if(status==1)
    {
    printf ("%d is found at position %d", data, i+1);
    }
    else
    {
   printf ("%d is not found",data);
    }
        }
2.)  One another method to perform linear search.
-      /* Program for linear search. */
       #include<stdio.h>
        main()
        {
    int a[10], i, data;
    printf ("Enter 10 Elements:- \n");
    for(  i=0; i<10; ++i)
    {
scanf("%i",&a[i]);
    }
    printf ("Enter a number to search in list = ");
    scanf("%d",&data);
    for( i=0;i<10;++i)
    {
  if(a[i] == data)
    {
                    printf ("%d is found at position %d", data, i+1);
          break;
}
    }
    if(i==10)
    {
printf ("%d is not found",data);
    }
        }
3.) Program to find the occurrence / frequency of a number within a list / array with position of value in index.
-  /* Ocurrance /frequency of number within a list. */
    #include<stdio.h>
    main()
    {
       int array[10], i, data, count=0;
       printf ("Enter 10 elemnts :- \n");
       for (i=0;i<10;i++)
       {
            scanf("%d",&array[i]);
       }
       printf ("Which number you want to search = ");
       scanf ("%d",&data);
       for (i=0;i<10;i++)
       {
            if (data == array[i])
            count++;
       }
       printf ("Total number of %d is = %d",data, count);
       printf ("\n");
       for (i=0;i<10;i++)
       {
               if (data == array[i])
               printf ("%d found at index number %d\n",data,i);
       }
    }
4.) Program to find the frequency of each number stored in an array.
-  /* Prg to find the frequency of each number stored in array. */
  #include<stdio.h>
  main()
  {
        int array[10], i, data, j, count;
printf ("Enter 10 elemnts:- \n");
for (i=0;i<10;i++)
{
scanf ("%d",&array[i]);
}
for (i=0;i<10;i++)
{
    data=i;
    count=0;
    if(data!=99)
    {
        for(j=i;j<10;j++)
                {
                    if(array[j]==data)
                    {
                        array[j]=-99;
                        count++;
                    }
        }
    printf ("%d occurs %d  times.\n",data,count);
    }
         }
  }

2.) Binary Search :-  This searching technique is based on divide and conquer rule in which whole list is divides into two parts. In binary search, sorted list is used to performed searching. 
In this searching technique, search value is compared with the middle position of the list. If element is found at middle position of list then searching stopped, otherwise  searching is performed either towards left or right. If search value is less than the value of middle position of list then searching performed left otherwise searching performed towards right. This process continuously repeated until element is not found at middle position or the lower index cross the upper index.


Step : 1

    
    lower index = 0
    upper index = 9
    middle = ( 0 + 9) / 2 = 4
    if array[middle] = number,   here number > array[middle], so searching performed towards right.

Step : 2

    lower = middle + 1
              =  4 + 1
              =  5
    upper = 9
    middle = (5 + 9) / 2 = 7
    if number = array [mid]?,  here number < array[middle],  so searching is performing towards left.

Step : 3

    lower = 5
    upper = middle - 1
              =  7 - 1
              =  6
    upper = 9
    middle = (5 + 6) / 2 = 5
    if number = array [mid]?,  Yes, searching stop print the value of mid as position.

1.) Program for perform binary search.
- /* Program for binary search. */
  #include<stdio.h>
  #include<conio.h>
  void main()
  {
     int a[10], i, status=0, lower, upper, mid, num;
     printf ("Enter 10 sorted elements :- \n");
     for (i=0;i<10;i++)
     {
        scanf ("%d",&a[i]);
     }
     printf ("Enter which number you have to search = ");
     scanf ("%d",&num);
     lower = 0;
     upper = 9;
     while (lower <= upper)
     {
        {
    mid = (lower + upper) / 2;
}
if (num < a[mid])
{
    upper = mid - 1;
}
else if (num > a[mid])
{
    lower = mid + 1;
}
else
{
    status = 1;
    break;
}
if (status = 1)
{
    printf ("%d found at position %d \n", num, mid+1);
}
else
{
    printf("%d is not found",num);
}
      }