Data Structures : ARRAYS

Data Types : Data types refers to a group of data which share similar properties and have common behaviour among them.
There are two types of data :
  1. Primitive data type : These data types are those which are not composed of other data types. These are also known as standard or fundamental data types.
    Example : int, float, double, char.
  2. Non-Primitive data type : These data types are composed of primitive data types. These are also known as user defined data types.
    Examples : array, structure , class.
Data Structures : Data structures are very important in a computer system as these not only allow the user to combine various data types in a group but also allow processing of the group as a single unit thereby making things much simplier and easier.
Types of Data Structures :
  1. Simple Data structures : These data structures are built from primitive data types  like int , char , float.
    Example : array , structures.
  2. Compound Data structure : These data structures are formed of simple data structures by combining them into various forms.
    Example : stack , queue , linked list.(linear data structures)
Operations on data structures : The basic operations thatare performed on data structures are :
  1. Insertion : Insertion means addition of new data element in a data structure.
  2. Deletion : Removal of data element.
  3. Searching : Searching of a specified data element.
  4. Traversal : It means processing of all data elements.
  5. Sorting : Arranging of data elements.
  6. Merging : Combining elements of two similar data structures to form a new data structure..
Introduction to Arrays :
It refers to named list of definite number of similar data elements. These are referenced by a set of consecutive numbers like 0,1,2,3.....,n
Arrays can be one dimensional, two dimensional or multi dimensional.

Need of an array :
Arrays are needed because a no. of data values can be stored under a same name and these data elements are stored in sequence.

One Dimensional Array :
It is the simplest form of an array. In C++ , it is denoted as  array_name[size]
where size specifies the number of elements in the array and the subscript value or index number ranges from 0 to (size-1).

Implementation of 1-D Array in memory :
In 1-D arrays data is stored in sequence in a single row or single column.
Address of element with index I= Base address + size of an array element(I- Lower bound of array)
arr[I]=B+w(I-L)

Searching :
Searching of a specific element in the array is known as searching.

Linear Search :
In this type, each element of the array is compared with given item to be searched for, one by one. This method which traverses the array sequentially to locate the given item is called linear search or sequential search.

UDF for linear search :
int linear_search(int ar[], int size, int item )
{
for(int i=0; i<size; i++)
{
if (ar[i]==item)
return i;                          //returns index of item if it is present in the list
}
return -1;;                      // if item is not present in the list
}


Binary search :
the technique of searching a specified element in the sorted array list by dividing the list into two parts and searching only in one half depending on the element to be greater than or less than the middle value.

UDF for binary search :
int binary_search(int ar[], int size , int item)
{
int beg, last, mid;
beg=0;
last= size-1;
while(beg<=last)
{
mid=(beg+last)/2;
if(item==ar[mid])
return mid;
else if(item>ar[mid])
beg=mid+1;
else
last=mid-1;
}
return -1;           // will run only if item is not present
}



Sorting :
Arranging of data either in ascending or descending order is known as sorting.

Selection sort :
In this type, basic idea is to repeatedly select the smallest key in the remaining an unsorted array.

UDF for selection sort
:
void sel_sort(int ar[], int size)
{
int small, pos, temp;
for(int i=0; i<size; i++)
{
small=ar[i];
pos=i;
for(int j=i+1; j<size; j++)
{
if(ar[j]<small)
{
small=ar[j];
pos=j;
}}
temp=ar[i];
ar[i]=ar[pos];
ar[pos]=temp;
cout<<"Array after pass"<<i+1<<"is";
for(j=0;j<size;j++)
cout<<ar[j];
}}


Bubble Sort :
In this type, two adjoining values are compared and then exchanged if are not in proper order.

UDF for bubble sort :
void bubble_sort(int ar[], int size)
{
int temp, ctr=0;
for(int i=0; i<size; i++)
{
for(int j=0; j<(size-1)--i; j++)
{
if (ar[j]>ar[j+1])
{
temp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=temp;
}}
cout<<"Array after iteration"<<++ctr<<"is";
for(int k=0;k<size;k++)
cout<<ar[k];
}}


Two Dimensional array :
Two dimensional array is a type of array  which is a one dimensional array in itself. It is written as    array_name[number of rows][number of columns]


Implementation of 2-D array in memory :

Row major implementation :
All elements are stored row wise
add of [I][J]=B+w(C(I-Lr)+(J-Lc))

Column major implementation :
add of [I]{J}=B+w(I-Lr)+(R(J-Lc))

where B is base address
w is size in bytes of one element
Lr-lower bound of rows
Lc-lower bound of columns
R-total number of rows
C-total number of columns

No comments:

Post a Comment