Array

Definition
o Arrays are defined as the collection of similar type of data items stored at contiguous
memory locations.
o Arrays are the derived data type in C programming language which can store the
primitive type of data such as int, char, double, float, etc.
o Array is the simplest data structure where each data element can be randomly
accessed by using its index number.
o For example, if we want to store the marks of a student in 6 subjects, then we don't
need to define different variable for the marks in different subject. instead of that,
we can define an array which can store the marks in each subject at a the
contiguous memory locations.

The array marks[10] defines the marks of the student in 10 different subjects where each
subject marks are located at a particular subscript in the array i.e. marks[0] denotes the
marks in first subject, marks[1] denotes the marks in 2nd subject and so on.

Properties of the Array

1. Each element is of same data type and carries a same size i.e. int = 4 bytes.
2. Elements of the array are stored at contiguous memory locations where the first
element is stored at the smallest memory location.
3. Elements of the array can be randomly accessed since we can calculate the address
of each element of the array with the given base address and the size of data
element.

Need of using Array

In computer programming, the most of the cases requires to store the large number of data
of similar type. To store such amount of data, we need to define a large number of
variables. It would be very difficult to remember names of all the variables while writing the
programs. Instead of naming all the variables with a different name, it is better to define an
array and store all the elements into it.

Following example illustrates how array can be useful in writing code for a particular
problem.
 In the following example, we have marks of a student in six different subjects. The problem
intends to calculate the average of all the marks of the student.

In order to illustrate the importance of array, we have created two programs, one is without
using array and other involves the use of array to store marks.

Program without array:

#include <stdio.h>
void main ()
{
int marks_1 = 56, marks_2 = 78, marks_3 = 88, marks_4 = 76,
marks_5 = 56, marks_6 = 89;

float avg = (marks_1 + marks_2 + marks_3 + marks_4 + marks_5 +marks_6) / 6 ;

printf(avg);
}

Program by using array:

#include <stdio.h>
void main ()
{
int marks[6] = {56,78,88,76,56,89);
int i;
float sum, avg;
sum = avg = 0;
for (i=0; i<6; i++ )
{
sum = sum + marks[i];
}
Avg= sum/6;
printf(avg);
}

Complexity of Array operations

Time and space complexity of various array operations are described in the following table.
Time Complexity
Algorithm Average Case Worst Case

Access O(1) O(1)

Search O(n) O(n)

Insertion O(n) O(n)

Deletion O(n) O(n)

Space Complexity

In array, space complexity for worst case is O(n).

Advantages of Array
o Array provides the single name for the group of variables of the same type
therefore; it is easy to remember the name of all the elements of an array.
o Traversing an array is a very simple process; we just need to increment the base
address of the array in order to visit each element one by one.
o Any element in the array can be directly accessed by using the index.

Memory Allocation of the array

As we have mentioned, all the data elements of an array are stored at contiguous locations
in the main memory. The name of the array represents the base address or the address of
first element in the main memory. Each element of the array is represented by a proper
indexing.

The indexing of the array can be defined in three ways.

1. 0 (zero - based indexing) : The first element of the array will be arr[0].
2. 1 (one - based indexing) : The first element of the array will be arr[1].
3. n (n - based indexing) : The first element of the array can reside at any random
index number.
 In the following image, we have shown the memory allocation of an array arr of size 5. The
array follows 0-based indexing approach. The base address of the array is 100th byte. This
will be the address of arr[0]. Here, the size of int is 4 bytes therefore each element will take
4 bytes in the memory.

In 0 based indexing, If the size of an array is n then the maximum index number, an
element can have is n-1. However, it will be n if we use 1 based indexing.

Accessing Elements of an array

To access any random element of an array we need the following information:

1. Base Address of the array.

2. Size of an element in bytes.
3. Which type of indexing, array follows.

Address of any element of a 1D array can be calculated by using the following formula:

1. Byte address of element A[i] = base address + size * ( i - first index)

Example :

In an array, A[-10 ..... +2 ], Base address (BA) = 999, size of an element = 2 bytes,
find the location of A[-1].
L(A[-1]) = 999 + [(-1) - (-10)] x 2
= 999 + 18
= 1017
 #include <stdio.h>
int summation(int[]);
void main ()
{
int arr[5] = {0,1,2,3,4};
int sum = summation(arr);
printf("%d",sum);
}

int summation (int arr[])

{
int sum=0,i;
for (i = 0; i<5; i++)
{
sum = sum + arr[i];
}
return sum;
}

The above program defines a function named as summation which accepts an array as an
argument. The function calculates the sum of all the elements of the array and returns it.
Sparse Matrix and its representations | Set 1 (Using
Arrays and Linked Lists)
A matrix is a two-dimensional data object made of m rows and n columns, therefore having total
m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.
Why to use Sparse Matrix instead of simple matrix ?

 Storage: There are lesser non-zero elements than zeros and thus lesser memory can be
used to store only those elements.
 Computing time: Computing time can be saved by logically designing a data structure
traversing only non-zero elements.

Example:
0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the
matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements,
we only store non-zero elements. This means storing non-zero elements with triples- (Row,
Column, value).
Sparse Matrix Representations can be done in many ways following are two common
representations:
1. Array representation
2. Linked list representation
Method 1: Using Arrays
2D array is used to represent a sparse matrix in which there are three rows named as
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index – (row,column)
PROGRAMING USING C++
// C++ program for Sparse Matrix Representation
// using Array
#include<stdio.h>

int main()
{
// Assume 4x5 sparse matrix
int sparseMatrix[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};

int size = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++;

// number of columns in compactMatrix (size) must be

// equal to number of non - zero elements in
// sparseMatrix
int compactMatrix[3][size];

// Making of new matrix

int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}

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

{
for (int j=0; j<size; j++)
printf("%d ", compactMatrix[i][j]);

printf("\n");
}
return 0;
}
Output:

0 0 1 1 3 3
2 4 2 3 1 2
3 4 5 7 2 6

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index – (row,column)
 Next node: Address of the next node

C program for Sparse Matrix Representation

// using Linked Lists
#include<stdio.h>
#include<stdlib.h>

// Node to represent sparse matrix

struct Node
{
int value;
int row_position;
int column_postion;
struct Node *next;
};

// Function to create new node

void create_new_node(struct Node** start, int non_zero_element,
int row_index, int column_index )
{
struct Node *temp, *r;
temp = *start;
if (temp == NULL)
{
// Create new node dynamically
temp = (struct Node *) malloc (sizeof(struct Node));
 temp->value = non_zero_element;
temp->row_position = row_index;
temp->column_postion = column_index;
temp->next = NULL;
*start = temp;

}
else
{
while (temp->next != NULL)
temp = temp->next;

// Create new node dynamically

r = (struct Node *) malloc (sizeof(struct Node));
r->value = non_zero_element;
r->row_position = row_index;
r->column_postion = column_index;
r->next = NULL;
temp->next = r;

}
}

// This function prints contents of linked list

// starting from start
void PrintList(struct Node* start)
{
struct Node *temp, *r, *s;
temp = r = s = start;

printf("row_position: ");
while(temp != NULL)
{

printf("%d ", temp->row_position);

temp = temp->next;
}
printf("\n");

printf("column_postion: ");
while(r != NULL)
{
printf("%d ", r->column_postion);
r = r->next;
}
printf("\n");
printf("Value: ");
while(s != NULL)
{
printf("%d ", s->value);
s = s->next;
}
printf("\n");
}
// Driver of the program
int main()
{
// Assume 4x5 sparse matrix
int sparseMatric[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};

/* Start with the empty list */

struct Node* start = NULL;

for (int i = 0; i < 4; i++)

for (int j = 0; j < 5; j++)

// Pass only those values which are non - zero

if (sparseMatric[i][j] != 0)
create_new_node(&start, sparseMatric[i][j], i, j);

PrintList(start);

return 0;
}
Output:
row_position: 0 0 1 1 3 3
column_postion: 2 4 2 3 1 2
Value: 3 4 5 7 2 6