# DATA STRUCTURE

UNIT: - 3

ARRAYS: -

Representation of arrays: single and multidimensional arrays.

Address calculation using column and row major ordering.

Various operations on Arrays,

Application of arrays: Matrix multiplication.

Array: -

1. An array is the collection of similar data type and it is a fundamental data structure that enables the storing and manipulation (handling) of potentially huge quantities (amount) of data.

2. An array can be defined as a data structure consisting of an ordered set of data values of the homogeneous (similar) type.

3. An array is the collection of individual data element: -

a. Ordered

b. Fixed size

c. Homogeneous (similar)

4. The elements of the array are stored in the consecutive memory allocation and are referenced by an integer known as its INDEX (also known as subscript).

5. The index begins at a zero (0) and is always written inside square brackets. E.g. [0], [1],[2]

6. Advantages of array are: -

a. Code optimization

b. Ease of traversing

c. Ease of sorting

d. Random access

Representation of array: -

Array can be represented in two ways:

a. Single dimensional array

b. Multi dimensional array

Single dimensional array: -

1. Single dimensional array are represented as vectors containing a row values.

2. Syntax: -

Data_type Array_name [size of the array]

Example: -

int student_id[10];

float height[10];

cahr name[10]

OR

Array can be initialized at compile time also using value list: -

Syntax: -

Data_type Array_name[size]={value list};

Example: -

int age[5]={10,23,25,14,18};

3. The size of array represents the maximum number of elements in the array.

4. Array_name must be valid identifier.

Two/Multi dimensional array: -

1. Multi dimensional array can be viewed as tables containing several rows and columns.

2. In multidimensional array the array is divided into rows and columns, mainly while considering multidimensional array we will be discussing about 2D array.

3. Syntax for two dimensional array: -

Data_type Array_name [row][column]; (For 2D)

Or

Data_type Array_name[i][j];

Where i=row j =column

Example: -

int A[2][3];

4. Syntax for multidimensional array: -

Data_type Array_name [size_1][size_2][size_3];

Address calculation using column and row major ordering.

Calculate the address of 1-Dimensional array: -

1. The name of the array is symbolic reference to the address of the first byte of the array while using the array name we are actually referring to the first byte of the array.

2. An array stores all its data elements in consecutive memory locations, storing just the base address i.e. the address of the first element in the array.

3. The address of other data elements can simply be calculated using the base address.

4. Formula to perform this calculation is as follows: -

Where,

A is the array.

k is the index of the element which we have to calculate the address.

W is the size of the one element in memory(i.e. size of data type used in the array A).

Example: - Given an array int marks[8]= {99, 67, 78, 55, 88, 90, 34, 85}, calculate the address of the marks[4] if the base address is 1000.

From the above diagram we easily conclude that the address of the index field marks[4] is 1008. Now we will use the given formula to find the address of the marks[4]: -

w= 2 (because int is of 2 byte)

k= 4 (marks[4])

lower bound = 0 (index stating value is 0 i.e. lowe_bound).

Now,

marks[4]=1000+2(4-0)

marks[4]=1000+8

marks[4]=1008

Calculate the address of 2-Dimensional array: -

There are two way to achieve the address of 2-Dimensional array i.e. row major and column major address.

1. Row major implementation is a linearization techniques in which element of array are redden from the keywords row wise.

2. The first row elements are placed, then the second row elements and so on.

3. The formula to calculate the address of [i,j]th block is:

Array[i,j]= B + W{C(i-lr)+(j-lc)}

Where,

B is the base_address (address of the first block in the array).

W is the size of the one element in memory(i.e. size of data type/ each block used in the array).

C is the total number of columns

Lr is the index of the first row.

Lc is the index of the first column.

i and j is number of rows and column respectively.

Example: -A matrix P[15][10] is stored with each element requiring 8 bytes of storage. If the base address at P[0][0] is 1400, determine the address at P[10][7] when the matrix is stored in Row Major wise.

Given,

B=1400, W=8, C=10, Lr=0, Lc=o, i=10, j=7

A/q

Address of [i, j]th element in row major = B+W{C(i-Lr) +(j-Lc)}

Hence, Address at P[10][7] when the matrix is stored in row major wise is 2256

1. Column measure implementation memory location us done column by column.

2. The first column elements are placed, then the second column elements and so on.

3. The formula to calculate the address of [i,j]th block is:

Array[i,j]= B + W{R(j-lc)+(i-lr)}

Where,

B is the base_address (address of the first block in the array).

W is the size of the one element in memory(i.e. size of data type/ each block used in the array).

R is the total number of rows.

Lr is the index of the first row.

Lc is the index of the first column.

i and j is number of rows and column respectively.

Example: -A matrix B[10][20] is stored in the memory with each element requiring 2 bytes of storage. If the base address ay B[2][1] is 2140, find the address of B[5][4] when the matrix is stored in Column Major Wise.

Given,

B=2140, W=2, R=10, Lr=2, Lc=1, i=5, j=4

Address of [i, j]th element in column major = B+W{R(j-Lc)+(i-Lr)}

Hence, Address at B[5][4] when the matrix is stored in column major wise is 2206

Various operation on Array

There are number of operations that can be performed in arrays they are as follows: -

1.    Traversing an array: -

Traversing means to access all the elements of the array starting from first element up to the last element in the array one-by-one.

Algorithm: -

Step 1: - Let LB be the lower bound and the upper bound is UB of linear array A.

Step 2: - Set i= LB (lower bound)

Step 3: - Repeat for i= LB to UB

Display A[i];

[End of the loop]

Step 4: - Exit

2.   Inserting an element (Insertion): -

For inserting the element at required position, element must be moved one position right to new locations.

Time complexity is O(1).

Algorithm: -

Step 1: - Set i= n-1

Step 2: -Repeat steps while i>=pos

Set a[i+1] = a[i] (shift the elements by 1 position right)

Set i=i-1; (end of loop)

Step 3: - set a[pos] = ele;

Step 4: -set n=n+1

Step 5: - End

3.   Delete an element from an array (Deletion): -

For deleting the element form the array at required position elements must be moved one position left from the next position of the deleting element.

Time complexity is O(n).

Algorithm: -

Step 1: - set i=pos;

Step 2: -Repeat steps while i<=n-1

Set a[i] = a[i+1] (shift the elements by 1 position left)

Set i=i+1; (end of loop)

Step 3: - set n=n-1

Step 4: - End

4.   Searching an element from array: -

Search an array element using the given index or by the value.

5.   Update an array element: -

Update operation refers to updating an existing element from the array at a given index.

Application of array: -

1. Array maintains multiple variable names using a single name and helps to maintain large data under a single variable name which avoid the confusion of using multiple variables.

2. Arrays can be used to sorting data element using different sorting techniques like bubble sort, selection sort, insertion sort, merge sort.

3. Arrays can be used for performing matrix operations and also used for CPU scheduling.

4. Arrays are also used for implementing other data structure like stack, queue, heaps, hash tables etc.

5. Array matrix multiplication: -

a. Matrix multiplication are done by using arrays and we are going to discuss an algorithm for matrix multiplication which we can used to write programming code for square matrix (row=column) multiplication in a high-level language.

Algorithm: -

Step 1: -Start the program.

Step 2: -Enter the row and column of the first (a) matrix.

Step 3: -Enter the row and column of the second (b) matrix.

Step 4: -Enter the elements of the first (a) matrix.

Step 5: -Enter the elements of the second (b) matrix.

Step 6: -Print the element of the first (a) matrix in matrix form.

Step 7: -Print the element of the second (b) matrix in matrix form.

Step 8: - Set a loop up to row.

Step 9: - Set an inner loop up to the column.

Step 10:- Set another inner loop up to the column.

Step 11:- Multiply the first (a) and second (b) matrix and store the element in the third matrix (c).

Step 12: -Print the matrix (c) in matrix form.

Step 13:- End of the program.

*************** THE END ***************