Table of Contents

1 Array Data Structure in C

Array Data Structure in C

Array is a linear Data Structure. A computer science students should have the knowledge of array data structure for developing the project.

Array Data Structure is widely used data structure in developing the various real world applications and system software.

Questions based on Array are asked in GATE and UGC NET Exam. In this tutorial we explained some basic concepts of array. After reading this tutorial students will able to answer the questions asked in technical interview for the post of software developer.

Frequently asked Array Questions

We have explained the various array concepts. After reading this tutorial students can answer the following questions easily.

What is Array ?
Why do we need Array ?
How to declare Array in c ?
How to initialize Array in c ?
Give some example of Array.
What are properties of Array ?
What are various types of array in Data Structure?
What are array limitation?
What is two dimensional array ?
What is Sparse Matrix ?
How to find location of an array elements ?
What is row major and column major order ?
Write the difference between upper triangular and lower triangular matrix.
Explain memory as array.

Let’s start with introduction of array.

What is Array ?

Array data structure is a collection of data elements which are stored in contagious memory manner and have the same data type.

During array definition we should also keep in mind that array in data structure is a user define data type. Array in programming is a best data structure.

Implementation of array in programming is important because of following reasons

Most assembly language have concept of array.
From an array any other data structure we can be built.

Why do we need array?

In general if we store any data , it store at any random location. Data at any random location is very tough to retrieve that’s why we need array data structure.

Example of an Array Data Structure

Consider three variable

int a=10;

int b=20;

int c=30;

In array contain three elements we can write as follow

int a[3]={10,20,30};

The above statement represent the array declaration as well as array initialization.

Where 1000, 1002 and 1004 are the addresses where these variable are stored.

Applications of Array Data Structure

Different applications of array in data structure are as follows –

Array is used to sort the elements.
Array can be used to perform the matrix operations.
Array is used to implement the CPU Scheduling.
Array can be used in recursive function.

Properties of an Array in C

There are following properties of an array data structure –

Each element is to the same size.
Element are stored contagious, with the first element stored at the smallest memory address.
Starting address of array is called base address.
By default array is start from 0 and the element number is an address.

Memory as an Array in C

Memory can also be view as an array. Memory is either Byte addressable or word addressable

Byte Addressing: if each byte has a unique address, we have byte addressing.
Word Addressing: if each word is given unique address, but the byte within a single word cannot be distinguished.

To know more about memory students can read this Memory Management Tutorial

Types of Array in Data Structure

In general array may be of following types of array data structure.

One Dimension array (1-D)
Two dimensional array (2-D)
Lower Triangular matrix array
Upper Triangular matrix array
Sparse matrix array .

Some other types of array in data structure are Tri diagonal matrix array, Z matrix array and Toeplitz Matrix array.

Order of an Array

An array can be ordered in two way

Row major order

Column major order

Consider the matrix as shown in following figure.

Row major array for this matrix is

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Column major order is

1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16

One Dimensional Array

One dimensional array in data structure or Single-Dimensional array can be think as the” list of variables which have similar data types” and each variable can be distinctly accessed by specifying its index in square brackets preceded by the name of that array.

int a=10;

int b=20;

int c=30;

In array contain three elements we can write

int a[3]={10,20,30};

Location of One D Array

Consider the array declaration A[Lb……………..Ub], base address is BA, C-size of an array and Lb and Ub are the lower and upper bound of an array.

Then address of the i^th element can be find out using following formulas

Loc(a[i]) = BA + (i – Lb) * C

Example: Suppose following array with its base address 1000 is given then address of the element at a[4] will be 1008,

int a [5] = {10,20,30,40,50}

Loc (a4) = BA + ( i – Lb) * c

= 1000 + ( 4 – 0 )*2

= 1000 + 8

= 1008

Two Dimensional Array

A Two Dimensional Array in data structure is an array which is stored in the form of the row-column matrix, where the first index indicate the row and second index indicates the column.

The second or the rightmost index of an array changes very fast as compared to first or left-most index while accessing the elements of an array.

Example – int a [4] [4] . This declaration represents an array which consist of 4 rows and 4 column.

Location of 2 D array in Row Major Order

int a[4] [4]= A[Lb1………Ub1,Lb2………Ub2]

Base Address =BA=1000

S- size of any element

No of rows- Ub1-Lb1+1

No of columns- Ub2-Lb2+1

LOC (aij)= BA+ [(i-lb1)* no of column + (j- lb2)] * S

Example: Suppose if we want to find out the address of the element 32 then it will be calculated by above formula as follow:

Loc (a32) = BA+[(i-lb1)*column+(j-lb2)] * s

= 1000+[(3-1)*4+(2-1)]*2

= 1000+[8+1]*2

= 1000+18

= 1018

So the location of a32 in 2-d array,RMO form is 1018.

Location of 2 D Array in Column Major Order

int a [4] [4]

a(Lb1…….Ub1,Lb2……Ub2)

CMO

Base address

S- size of any element

no of rows- Ub1-Lb1+1

no of columns- Ub2-Lb2+1

Loc(aij)= BA + [(J-lb2)*rows + (i-Lb1)] * S

Example

a[1…….4,1…….4]

CMO ( Column Major Order)

BA- 1000

Loc(a34) = BA +[(J-lb2) * no of rows + (I-Lb1)] *s

= 1000+[(4-1)*4+(3-1)]*2

= 1000+[12+2]*2

= 1000+28

= 1028

So that the location of a34 in 2-d array, CMO form is 1028.

Lower Triangular Matrix

A[Lb1……Ub1,Lb2…….Ub2]

LTM

Row major Order for this lower triangular matrix is

1 2 6 3 4 8 4 7 5 9 5 3 2 6 3

Base address

S- size of array

Loc (aij) = BA + [((i – Lb1)( i- Lb1+1)/2) + (j – Lb2)] * S

A[lb1……..ub1,lb2……..ub2]

LTM

Column Major Order for this lower triangular matrix is

1 2 3 4 5 6 4 7 3 8 5 2 9 6 3

Base address

size of array

loc(ai,j) = BA + [(col)(col+1)/2 –(ub2-j+1)(ub2-j+1+1)/2 + (i-j)] * s

Upper Triangular Matrix

A[Lb1……Ub1,Lb2……Ub2]

UTM

Column Major Order

Base address

S- size of array

LOC (aij) = BA + [((j – lb2)(j-lb2+1)/2) + (i-lb1)] * S

A[lb1…..ub1,lb2……ub2]

UTM

RMO

Base address

Size of array

LOC(ai,j) = BA + [(ub1-lb1+1)(ub1-lb1+1+1)/2 – (ub1-i+1)(ub1-i+1+1)/2 + (j-i)] * s

What is Sparse Matrix ?

Sparse matrix is a matrix which has most of the its elements of as 0 value, then it is called a sparse matrix.

Why to use Sparse Matrix instead of simple matrix ?

There are following reasons to use the sparse 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.

In array this matrix can be represented as

Limitations of Array

There are following limitation of an array data structure –

The dimension of an array is determined the moment the array is created, and cannot be changed later on.
An array is a static data structure. After declaring an array it is impossible to change its size. thus sometime memory spaces are misused.
Each element of array are of same data type as well as same size. we can not work with elements of different data type.
In an array the task of insertion and deletion is not easy because the elements are stored in contiguous memory location.
Array is a static data structure thus the number of elements can be stored in it are somehow fixed.

Previous Tutorial – Data Structure And Types of Data Structure

Next Tutorial – Character Array in C

Array Programs – One Dimensional Array Programs in C