CBSE Class 12 Computer Science Data Structure Notes Set 01

Data Structure

In Computer Science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks.

The data structure can be classified into following two types:

Simple Data Structure: These data structures are normally built from primitive data types like integers, floats, characters. For example arrays and structure. Compound Data Structure:

simple data structures can be combined in various ways to form more complex structure called compound structures. Linked Lists, Stack, Queues and Trees are examples of compound data structure.

Data Structure Arrays

Data structure array is defined as linear sequence of finite number of objects of same type with following set of operation:

· Creating : defining an array of required size

· Insertion: addition of a new data element in the in the array

· Deletion: removal of a data element from the array

In linear search algorithm, if the searched item is the first elements of the array then the loop terminates after the first comparison (best case), if the searched item is the last element of the array then the loop terminates after size time comparison (worst case) and if the searched item is middle element of the array then the loop terminates after size/2 time comparisons (average case). For large size array linear search not an efficient algorithm but it can be used for unsorted array also.

Binary search algorithm
Binary search algorithm is applicable for already sorted array only. In this algorithm, to search for the given item from the sorted array (in ascending order), the item is compared with the middle element of the array. If the middle element is equal to the item then index of the middle element is returned,

otherwise, if item is less than the middle item then the item is present in first half segment of the array (i.e. between 0 to middle-1), so the next iteration will continue for first half only, if the item is larger than the middle element then the item is present in second half of the array (i.e. between middle+1 to size-1), so the next iteration will continue for second half segment of the array only. The same process continues until either the item is found (search successful) or the segment is reduced to the single element and still the item is not found (search unsuccessful).

#include<iostream.h>

int binary_search(int a[ ], int size, int item)

{ int first=0,last=size-1,middle;

while(first<=last)

{

       middle=(first+last)/2;

       if(item==a[middle])

       return middle; // item is found

       else if(item< a[middle])

       last=middle-1; //item is present in left side of the middle element else

       first=middle+1; // item is present in right side of the middle element

}

return -1; //given item is not present in the array, here, -1 indicates unsuccessful search

}

        void main()

{ int b[8]={2,4,5,7,8,9,12,15},size=8;

int item;

cout<<”enter a number to be searched for”;

cin>>item;

int p=binary_search(b, size, item); //search item in the array b

if(p==-1)

     cout<<item<<” is not present in the array”<<endl;

else

     cout<<item <<” is present in the array at index no “<<p;

}

Let us see how this algorithm work for item=12

Initializing first =0 ; last=size-1; where size=8

Iteration 1

      =0, last=7

       middle=(first+last)/2=(0+7)/2=3 // note integer division 3.5 becomes 3

       value of a[middle] i.e. a[3] is 7

       7<12 then first= middle+1 i.e. 3 + 1 =4

iteration 2

       first=4,    last=7

       middle=    (first+last)/2=(4+7)/2=5

       value of a[middle] i.e. a[5] is 9

       9<12 then first=middle+1;5+1=6

iteration 3

       first=6,last=7

       middle=(first+last)/2 = (6+7)/2=6

        value of a[middle] i.e. a[6] is 12 which is equal to the value of item being search i.e.12

As a successful search the function binary_search() will return to the main function with value 6 as index of 12 in the given array. In main function p hold the return index number.

Note that each iteration of the algorithm divides the given array in to two equal segments and the only one segment is compared for the search of the given item in the next iteration. For a given array of size N= 2n elements, maximum n number of iterations are required to make sure whether the given item is present in the given array or not, where as the linear requires maximum 2n number of iteration.

For example, the number of iteration required to search an item in the given array of 1000 elements,

binary search requires maximum 10 (as 1000»210) iterations where as linear search requires maximum 1000 iterations.

Inserting a new element in an array

We can insert a new element in an array in two ways

· If the array is unordered, the new element is inserted at the end of the array

· If the array is sorted then the new element is added at appropriate position without altering the order. To achieve this, all elements greater than the new element are shifted. For example, to add 10 in the given array below:

#include<iostream.h>

void insert(int a[ ], int &n, int item) //n is the number of elements already present in the array

{ int i=n-1;

while (i>=0 && a[i]>item)

        {

        a[i+1]=a[i]; // shift the ith element one position towards right

        i--;

}

a[i+1]=item; //insertion of item at appropriate place

n++; //after insertion, number of elements present in the array is increased by 1

}

void main()

{int a[10]={2,4,5,7,8,11,12,15},n=8;

int i=0;

cout<<“Original array is:\n”;

for(i=0;i<n;i++)

           cout<<a[i]<<”, “;

insert(a,n,10);

cout<<”\nArray after inserting 10 is:\n”;

for(i=0; i<n; i++)

          cout<<a[i]<<”, “;

}

Output is

Original array is:

2,  4,  5,  7,  8,  11,  12,  15

Array after inserting 10 is:

2,  4,  5,  7,  8,  10,  11,  12,  15

Deletion of an item from a sorted array

In this algorithm the item to be deleted from the sorted array is searched and if the item is found in the array then the element is removed and the rest of the elements are shifted one position toward left in the array to keep the ordered array undisturbed. Deletion operation reduces the number of elements present in the array by1. For example, to remove 11 from the given array below:
Following program implement deletion operation for sorted array

#include<iostream.h>

void delete_item(int a[ ], int &n, int item) //n is the number of elements already present in the array

{int i=0;

while(i<n && a[i]<item)

i++;

if (a[i]==item) // given item is found

Please click the link below to download pdf file for CBSE Class 12 Computer Science - Data Structure.