## Array

**Array Definition**

The next complex type is common to several languages. An **array **may be defined as a collection of several objects of the same type. All these objects are allocated contiguously in memory and they may be accessed with an **index**, designating the rank of an object within an array.

An array is defined with the type of its elements and a dimension. An index always starts at zero in C. An index is applied to an array with the **[] **operators. No control is done to check that the index is in the proper range. It is possible to define an array of all the existing data types of C.

An array in C has only one dimension. Multidimensional arrays are possible by creating arrays of arrays.

– Purpose-

- To store multiple values of given data type in single variable.
- Structures of related data items
- Static entity – same size throughout program
- Dynamic data structures discussed in further chapters.

– Types of Array-

- Single Dimensional
- Two Dimensional
- Multi Dimentional
- Array

– Group of consecutive memory locations

– Same name and type

- To refer to an element, specify

– Array name

– Position number

- Format:

*arrayname***[** *position number* **]**

– First element at position **0**

– **n** element array named **c**:

**c[ 0 ]**,**c[ 1 ]**…**c[ n – 1 ]**

Name of array (Note that all elements of this array have the same name, **c**

C[0] | -45 |

C[1] | 6 |

C[2] | 0 |

C[3] | 72 |

C[4] | 1543 |

C[5] | -89 |

C[6] | 0 |

C[7] | 62 |

C[8] | -3 |

C[9] | 1 |

C[10] | 6453 |

C[11] | 78 |

Position number of the element within array **c**

- Array elements are like normal variables

** c[ 0 ] = 3;**

** printf( “%d”, c[ 0 ] );**

– Perform operations in subscript. If **x** equals **3**

**c[ 5 - 2 ] == c[ 3 ] == c[ x ]**

**Declaring Arrays**

** **

- When declaring arrays, specify

– Name

– Type of array

– Number of elements

**arrayType arrayName[ numberOfElements ];**

– Examples:

**int c[ 10 ]; **

**float myArray[ 3284 ];**

- Declaring multiple arrays of same type

– Format similar to regular variables

– Example:

**int b[ 100 ], x[ 27 ]; **

- Initializers

**int n[ 5 ] = { 1, 2, 3, 4, 5 }; **

– If not enough initializers, rightmost elements become **0**

**int n[ 5 ] = { 0 }**

- All elements 0

– If too many a syntax error is produced syntax error

– C arrays have no bounds checking

- If size omitted, initializers determine it

**int n[ ] = { 1, 2, 3, 4, 5 }; **

– 5 initializers, therefore 5 element array

**One dimensional array**

**Syntax:**

<data-type> <array_name> [size];

**Example:**

**int **a[3] = {2, 3, 5};

**char **ch[20] = “TechnoExam” ;

**float **stax[3] = {5003.23, 1940.32, 123.20} ;

**Total Size (in Bytes):**

total size = length of array * size of data type

In above example, a is an array of type integer which has storage size of 3 elements. The total size would be 3 * 2 = 6 bytes.

**MEMORY ALLOCATION :**

Memory allocation for one dimensional array

**Two dimensional array**

Syntax:

<data-type> <array_nm> [row_subscript][column-subscript];

Example:

inta[3][3];

} It is possible for arrays to have 2 or more dimensions.

} The two dimensional array is also called as ‘** matrix**’.

**MEMORY ALLOCATION :**

} E.g. :

main()

{

int stud[4][2];

int i, j;

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

{

printf (“\n Enter roll umber & marks”);

scanf (“%d %d”, &stud[i][0], &stud[i][1]);

}//for

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

printf (“\n %d %d”, stud[i][0], stud[i][1]);

}//main

**Initializing a 2-Dimensional Array**

int stud[4][2]={

{1234, 56},

{1212, 33},

{1434, 34},

{1342, 23},

}

**Or **

int stud[4][2]={1234, 56, 1212, 33, 1434, 34, 1342, 23}

} It is important to remember that while initializing a 2-D array it is necessary to mention the second (column) dimension, whereas the first dimension (row) is optional.

} Thus the declaration,

int arr[2][3]= {12,34,23,45,56,45};

int arr[][3]= {12,34,23,45,56,45};

Whereas,

int arr[2][]= {12,34,23,45,56,45};

int arr[][]= {12,34,23,45,56,45};

Would never work.

**Searching**

Searching refers to the operation of finding the location of a given item in a collection of items.

The search is said to be successful if ITEM does appear in DATA and unsuccessful otherwise.

The following searching algorithms are discussed in this chapter.

1. Sequential Searching

2. Binary Search

3. Binary Tree Search

**Sequential Search**

This is the most natural searching method. The most intuitive way to search for a given ITEM in DATA is to compare ITEM with each element of DATA one by one. .The algorithm for a sequential search procedure is now presented

**Algorithm**

SEQUENTIAL SEARCH

INPUT : List of Size N. Target Value T

OUTPUT : Position of T in the list-1

BEGIN

Set FOUND = false

Set I := 0

While (I <= N) and (FOUND is false)

IF List[i] ==t THEN

FOUND = true

ELSE

I = I+1

IF FOUND==false THEN

T is not present in the List

END

**Binary Search**

Suppose DATA is an array which is sorted in increasing numerical order. Then there is an extremely efficient searching algorithm, called binary search, which can be used to find the location LOC of a given ITEM of information in DATA.

The binary search algorithm applied to our array DATA works as follows. During each stage of our algorithm, our search for ITEM is reduced to a segment of elements of DATA:

DATA[BEG], DATA[BEG + 1], DATA[BEG + 2], …… DATA[END].

Algorithm

**Binary Search Tree**

Suppose T is a binary tree. Then T is called a binary search tree if each node N of T has the following property:

“The value at N is greater than every value in the left subtree of N and is less than every value in the right subtree of N.

Binary Search Tree(T)