* 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: -

**Address
of A[k]= Base_Address(A)+ W(k- Lower_Bound)**

**Where,**

*A** is the array.*

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

*Base_Address** is the base address of the array A.*

*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]: -*

**marks[4]= Base_Address(marks)+ w(k-
Lower_Bound)**

*Base_Adress = 1000 **(given)*

*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.

**Row major
address calculation: -**

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-l _{r})+(j-l_{c})}**

**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*

*L _{r} *

*is the index of the first row.*

*L _{c} *

*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, L_{r}=0, L_{c}=o,
i=10, j=7

A/q

Address of [i, j]^{th} element in row
major = B+W{C(i-L_{r}) +(j-L_{c})}

Address at P[10][7]=1400+8{10(10-0)+(7-0)}

Address at P[10][7]=1400+8{100+7}

Address at P[10][7]=1400+856

Address at P[10][7]=2256

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

** **

**Column major
address calculation: -**

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-l _{c})+(i-l_{r})}**

**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.*

*L _{r} *

*is the index of the first row.*

*L _{c} *

*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, L_{r}=2, L_{c}=1,
i=5, j=4

Address of [i, j]^{th} element in column
major = B+W{R(j-L_{c})+(i-L_{r})}

Address at B[5][4]= 2140+2{10(4-1)+(5-2)}

Address at B[5][4]= 2140+2{30+3}

Address at B[5][4]= 2140+ 66

Address at B[5][4]= 2206

**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 ***************

For more information
whats_app:- **8873466244 **

**Follow on Instagram:- mohit13kumar1 **

For more information contact us: - Click me

Or follow our FACEBOOK page @diploma.1234

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

ReplyDeletewellDone