**: Data types refers to a group of data which share similar properties and have common behaviour among them.**

__Data Types____There are two types of data__:

: These data types are those which are not composed of other data types. These are also known as standard or fundamental data types.__Primitive data type____Example__: int, float, double, char.: These data types are composed of primitive data types. These are also known as user defined data types.__Non-Primitive data type____Examples__: array, structure , class.

__: 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.__

**Data Structures**__Types of Data Structures__:

: These data structures are built from primitive data types like int , char , float.__Simple Data structures____Example__: array , structures.: These data structures are formed of simple data structures by combining them into various forms.__Compound Data structure____Example__: stack , queue , linked list.(linear data structures)

__: The basic operations thatare performed on data structures are :__

**Operations on data structures**__Insertion__: Insertion means addition of new data element in a data structure.__Deletion__: Removal of data element.__Searching__: Searching of a specified data element.__Traversal__: It means processing of all data elements.__Sorting__: Arranging of data elements.__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 sortUDF 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