Scribd
Upload
6 views10 pages

Understanding Arrays in C Programming

The document defines and describes arrays. It discusses that arrays store similar data types in contiguous memory locations and allow random access via indexes. It provides an example of storing student marks in an array rather than separate variables. It also outlines properties of arrays like all elements being the same data type and size. It discusses the need for arrays when storing large amounts of similar data. Finally, it presents two methods for representing sparse matrices - using a 2D array and linked lists.

Uploaded by

rohitthebestplayer
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views10 pages

Understanding Arrays in C Programming

The document defines and describes arrays. It discusses that arrays store similar data types in contiguous memory locations and allow random access via indexes. It provides an example of storing student marks in an array rather than separate variables. It also outlines properties of arrays like all elements being the same data type and size. It discusses the need for arrays when storing large amounts of similar data. Finally, it presents two methods for representing sparse matrices - using a 2D array and linked lists.

Uploaded by

rohitthebestplayer
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

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

Common questions

Powered by AI

Array representation of a sparse matrix can be time-efficient for sequential access since elements are stored contiguously, allowing fast iterations over non-zero elements. The compact nature requires less memory compared to the matrix's original form. However, linked lists provide better space efficiency by dynamically allocating memory only for non-zero entries, which can be beneficial when updating entries since it allows insertions and deletions without shifting elements. Linked lists may incur a time overhead for access due to pointer-based navigation, which is typically slower than array indexing, affecting time efficiency in large datasets .

Understanding the time complexity of arrays is essential when selecting data structures for matrix data. Arrays offer O(1) access time, which is beneficial in scenarios requiring frequent random access. However, operations like insertion and deletion have O(n) complexity, making them less efficient for applications requiring frequent modifications. For matrices with numerous zero elements, such as sparse matrices, alternative structures like sparse matrices using linked lists may provide better time and space efficiency. Recognizing these trade-offs helps in selecting the most efficient data storage and manipulation strategy for a specific application .

Sparse matrices utilize specialized storage approaches due to their large numbers of zero elements. Using arrays, a sparse matrix can be stored by only recording the non-zero elements and their row and column indices, reducing memory usage. This is done by creating a 2D array with three rows: the row index, column index, and the values of the non-zero elements . The linked list approach involves creating nodes for each non-zero element with links to successive elements, additionally incorporating the row and column positions. This allows dynamic memory usage and easy traversal . Arrays provide faster access while linked lists offer more flexibility and dynamic memory management.

The location of an element in an array can be computed using the formula: base address + size of element * (index - first index). This formula accounts for both the indexing system (0-based or 1-based). For instance, if the base address is 999 and the size of each element is 2 bytes, the location of the element at index -1 in an array with a lower bound of -10 is computed as 999 + 18 = 1017 bytes. This systematic calculation allows accurate random access to any element within the array .

Arrays have a space complexity of O(n) in the worst-case scenario, meaning the memory requirement scales linearly with the number of elements. Each element occupies a fixed amount of memory, leading to efficient use of memory when dealing with large datasets of similar data types. However, this also implies that arrays lack flexibility in size once declared, potentially leading to memory waste if declared larger than necessary. This can affect applications where dynamic memory management is crucial, making arrays less suited for use cases requiring frequent resizing or where memory constraints are critical .

Arrays provide a single name for a group of variables of the same type, simplifying memory management and making the code easier to manage. They allow each data element to be accessed using its index in contiguous memory locations, which simplifies the process of traversing the dataset. The ability to randomly access any element using the index also increases efficiency .

An array-based solution allows all grades to be stored in a contiguous block of memory with a single identifier name, making the implementation more organized and reducing the chances of errors when handling large numbers of variables. By iterating over the array, individual element access and operations like summation are simplified and require less code than managing each variable separately. This results in cleaner, more maintainable code, eases summation calculations, and facilitates future modifications or extensions to the dataset .

Time complexity is crucial in understanding the efficiency of operations performed on data structures. For arrays, accessing an element typically has a constant time complexity of O(1) in both average and worst cases, allowing for quick direct access via indices. However, searching, insertion, and deletion all have a time complexity of O(n) in the worst and average cases, reflecting that these operations may require traversing the entire array or shifting elements . These complexities guide developers in selecting suitable data structures based on the operations frequently performed in particular applications.

Traversing an array is straightforward because elements are stored in contiguous memory locations and can be accessed sequentially using simple arithmetic on the index variable. This ability to increment the index allows programmers to iterate through elements efficiently, which is simpler compared to data structures like linked lists, where traversal requires following pointers. Sequential access minimizes overhead and complexity in the code, enhancing programming efficiency, especially when working with large datasets .

Arrays are stored in contiguous memory locations, with the base address representing the address of the first element. The indexing can affect how elements are accessed: in a 0-based index, the first element is at index 0, and in a 1-based index, it starts at 1. The specific location of any element can be calculated using the base address, size of an element, and the index system used. For example, the byte address of any element A[i] can be calculated with the formula: base address + size * (i - first index).

You might also like