Unit 2: Introduction to Arrays,

- Dr. Diksha Joshi

 Data Structure
• Data Structure : classified as either linear or non-linear

• Linear data structure: if its elements form a sequence or linear list

• There are two basic ways of representing such linear structures in

memory:
– One way is to have the linear relationship between the elements represented by
means of sequential memory locations e.g. Arrays

– The other way – linear relationship between the elements represented by means of
pointers or links e.g. Linked Lists

4
 Linear Arrays
• A linear array – list of finite number of homogeneous data elements, finite
collection of similar elements with same data type stored in adjacent memory
locations.

• The elements of the array are referenced respectively by an index set

consisting of n consecutive numbers

• The elements of the array are stored respectively in successive memory

locations.

• n – indicates total number of elements in the array – size or length of the

array.

• Length = Total number of elements = UB –LB +1

• Array elements are denoted as A1, A2,… An or A(1), A(2),… A(n) or

A[1],A[2],….,A[n]. 5
 Linear Arrays
• Array declaration must give, three items of information:

– The name of the array

– The data type of the array
– The index set of the array

• Memory for array can be allocated in two ways:

– Statically : Compile time – size of array is fixed during program execution

– Dynamically: Run time – read value of n at run time and then allocate memory
while program execution.

6
Syntax of declaring an array
• data_type array_name [array_size];

• data_type : int,float,double etc.

• array_name : name of the variable
• array_size : integer values which determines size of the array or
memory locations to be allocated to an array

• Eg. int a[10];

 Arrays in C
• Declaration of an Array in C:
– Data type followed by array name.
– Subscript in bracket indicates the number of elements array will hold.
– By declaring an array, the specified number of memory locations are allocated in the
memory
– For example,
int age[20] ;
float sal[10];
char grade[10];
int arr[5]

Memory representation of an array of 5 elements

100 102 104 106 108
arr[0] arr[1] arr[2] arr[3] arr[4]
8
Initialization of Arrays
Strings
• In C programming, a string is a sequence of characters terminated
with a null character \0. For example:
• char c[] = "c string";
• When the compiler encounters a sequence of characters enclosed in
the double quotation marks, it appends a null character \0 at the end
by default.

• Memory diagram of strings in C programming

How to declare a string?

• char string_name[size];
• In the above syntax str_name is any name given to the string variable
and size is used to define the length of the string, i.e the number of
characters strings will store.

• char s[5];
How to initialize strings?

• You can initialize strings in a number of ways.

• 1. Assigning a string literal without size
• char c[] = "abcd";

• 2. Assigning a string literal with a predefined size

• char c[50] = "abcd";
• 3. Assigning character by character with size
• char c[] = {'a', 'b', 'c', 'd', '\0'};
• 4. Assigning character by character without size
• char c[5] = {'a', 'b', 'c', 'd', '\0'}
● Method 1
int Arr[5] = {1,2,43,14,52};

● Method 2 ● Method 4
int Arr[]={1,2,43,14,52}; int arr[5];

● Method 3 for(i=0; i<5; i++){

int arr[5]; scanf(“%d”, &arr[i]);
arr[0]=1; }
arr[1]=2;
arr[2]=43;
arr[3]=14;
arr[4]=52;
Properties of the Array

• Each element is of same data type and carries a same size i.e. int = 4
bytes.
• Elements of the array are stored at contiguous memory locations
where the first element is stored at the smallest memory location.
• 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.
Advantages of Array
• 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.
• 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.
• Any element in the array can be directly accessed by using the index.
Program to accept ‘n’ integers from user into an array and display them one in
each line
#include<stdio.h>
int main() {
int i, arr[50], num;

printf("\nEnter no of elements :");

scanf("%d", &num);

//Reading values into Array

printf("\nEnter the values :");
for (i = 0; i < num; i++) {
scanf("%d", &arr[i]);
}

//Printing of all elements of array

for (i = 0; i < num; i++) {
printf("\narr[%d] = %d", i, arr[i]);
}

return (0);
}
 What if the number of elements are less than the length
specified?
what if we are trying to access out of array What values are stored in remaining places?
bound
int i,arr[7]={1,2,3};
int i,arr[2]={1,2,3};
for(i=0 ; i<6 ; i++)
for(i=0 ; i<6 ; i++) {
{ printf("%d\n",arr[i]);
printf("%d\n",arr[i]); }
} • 1
Output: • 2
1 • 3
2
• 0
-1789569708
0 • 0
-1789569708 • 0
32767
Operations on an array
• Traversal
• Insertion
• Deletion
• Searching
• Sorting
 Traversing Linear Arrays
• Traversing a Linear Array
LA = Linear Array
LB = Lower Bound
UB = Upper Bound

1. [Initialize Counter] set K:=LB

2. Repeat Steps 3 and 4 while K<=UB
[Visit element] Apply Process to LA[K]
[Increase Counter] set K:=K+1
3. [End of Step 2 loop]
4. Exit

1. Repeat for K=LB to UB

Apply Process to LA[K]
2. [End of Loop]
3. Exit
21
 Traversing Linear Arrays
#include <stdio.h>

int main() {
int arr[5] = {10, 20, 30, 40, 50}; // Linear array
int i;

printf("Elements of the array are:\n");

for (i = 0; i < 5; i++) {
printf("arr[%d] = %d\n", i, arr[i]);
}

return 0;
}
Insertion of an element can be done:

• At the beginning
• At the end and
• At any given index of an array.
 Inserting into a Linear Arrays
N=4 NAME
• Inserting into a Linear Array Brown
LA = Linear Array Davis
LB = Lower Bound
Johnson
UB = Upper Bound
N = array with N elements Smith
K= K is a positive integer such that K<=N.
This algorithm Inserts an element ITEM into the Kth position in LA
INSERT(LA, N, K, Item)
1. [Initialize counter] Set J:=N
N=4 NAME
2. Repeat Steps 3 and $ while J>= K
3. [Move Jth element downward] Set LA[J+1]:=LA[J] K=3 Brown
NAME
4. [Decrease counter] Set J:=J-1 Item=Ford Davis
Brown
5. [End of step 2 loop]
Davis
J=N=4 Johnson
6. [Insert element] set LA[K]:=Item
Smith
7. [Reset N] Set N:= N+1 Ford
8. Exit
Johnson
Smith
24
1. We need to insert element 100 at
position 2.

2. Move all the elements from the

last index(4) to the position(2) to
one position right.
arr[4] (30) will be placed in arr[5].
arr[3] (78) will be placed in arr[4].
arr[2] (5) will be placed in arr[3].

3. Finally, the element 100 is placed

at the position 2.
#include <stdio.h> // Shift elements to the right
int main() {
for (i = n; i > pos; i--) {
int arr[100], n, i, pos, value;
arr[i] = arr[i - 1];
// Input original size and elements
printf("Enter number of elements (max 100): ");
}
scanf("%d", &n);
printf("Enter %d elements:\n", n); // Insert the value
for (i = 0; i < n; i++) { arr[pos] = value;
scanf("%d", &arr[i]);
n++; // Increase array size
}
// Input position and value to insert
printf("Enter the position to insert (0 to %d): ", n); // Display the updated array
scanf("%d", &pos); printf("Array after insertion:\n");
if (pos < 0 || pos > n) { for (i = 0; i < n; i++) {
printf("Invalid position!\n"); printf("%d ", arr[i]);
return 1;
}
}
printf("Enter the value to insert: ");
scanf("%d", &value); return 0;
}
Deletion
1. Start
2. Set J = K // k is the location to be deleted
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1 // N is the size of array reduced by 1
7. Stop
Array - Search Operation

• Start
• 2. Set J = 0
• 3. Repeat steps 4 and 5 while J < N
• 4. IF LA[J] is equal ITEM THEN GOTO STEP 6
• 5. Set J = J +1
• 6. PRINT J, ITEM
• 7. Stop
#include <stdio.h>
#include <conio.h>
void main()
{
for (i = position-1; i < n-1; i++)
int array[100], position, i, n;
{
printf("Enter the number of elements in array"); array[i] = array[i+1];
scanf("%d", &n); }
printf("Enter %d elements", n); printf("Final array is");
for (i = 0; i < n; i++) for (i = 0; i < n-1; i++)
{ {
printf("%d", array[i]);
scanf("%d", &array[i]);
} } getch();
} }
printf("Enter the location where you wish to delete element");
scanf("%d", &position);
if (position >= n+1)
{
printf("Deletion not possible.");
}
else
{
 Representation of Linear Arrays in Memory
• Arr[] – linear array
• Loc(Arr[k]) = address of the element Arr[k ] of the array Arr

1000 Base(Arr)
1001
1002
1003
1004

No need to keep track of the address of every element of Arr.

Track only the address of the first element of Arr, denoted by Base (Arr)
Using base address, computer calculates address of any element of Arr by using below
formula:
Loc(Arr[k]) = Base(Arr) + w(K-Lower bound)
31
 Calculating the Address of Array Elements

Loc(Arr[k]) = Base(Arr) + w(K-Lower bound)

Here, Arr is the array, k is the index of the element of which we

have to calculate the address,
Base is the base address of the array A, and w is the size of one
element in memory, for example, size of
int is 2.
Suppose we want to find out Loc (A [3]). For it, we have:
Base (A) = 1000
w = 2 bytes (Because an integer takes two bytes in the memory).
K=3
LB = 1

After putting these values in the given formula, we get:

LOC (A [3]) = 1000 + 2 (3 – 1)
= 1000 + 2 (2)
= 1000 + 4
= 1004
 Calculating the Address of Array Elements

Given an array
int marks[] = {99,67,78,56,88,90,34,85},
calculate the address of marks[4]
if the base address = 1000 and size of each element
is 2 bytes..
 Calculating the Address of Array Elements
We know that storing an integer value requires 2 bytes, therefore, its size
is 2 bytes.
Loc(marks[4]) = 1000 + 2(4 – 0)
= 1000 + 2(4) = 1008
 Calculating the Address of Array Elements

Given an array
float pointers[] = {99.1, 60.5, 77.3, 90, 88.5, 92.7, 88.8, 70.5,
96.76, 91.3},
calculate the address of pointers[5]
if the base address = 2032.
 Calculating the Address of Array Elements
Given the base address of an array B[1300…..1900] as 1020 and size of each element is 2 bytes in the memory. Find the address of B[1700].
Base address B = 1020
Lower Limit/Lower Bound of subscript LB = 1300
Storage size of one element store in any array W = 2 Bytes
Subset of element whose address to be found I = 1700

Solution:
Address of A[1700] = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * (400)
= 1020 + 800
Address of A[1700] = 1820
 Calculating the Address of Array Elements
Base address B = 2023
Lower Limit/Lower Bound of subscript LB = 0
Address of the element 2 is 2039

Find the Storage size for one element and identify the data type of the array used
Example
• Suppose, an Array A [-15......64] is stored in a memory whose starting
address in a memory whose starting address is 459. Assume that
word size for each element is 2. Thenobtain the following:
• a)How many numbers of elements are there in the array A?
• b)If one word of the memory is equal to 2 bytes, then how much
memory is required to store the entire Array?
• c)What is the location for A [50]?
• d)What is the location of 10th element ?
• e)Which element is located at 589?
• a) How many elements are there in the array A?
• The array A is indexed from -15 to 64. To find the total number of elements, we calculate the range of the indices:
• Number of elements=(last index−first index+1)
• Number of elements=(64−(−15)+1)=64+15+1=80
• b) How much memory is required to store the entire Array?
• Each element of the array occupies 2 bytes. Therefore, the total memory required for the array can be calculated by multiplying
the number of elements by the size of each element:
• Memory required=(Number of elements)×(Size of each element) Memory required=80×2=160 bytes
• c) What is the location for A[50]?
• Index=LB+Pos-1
• 50=-15+pos-1
• Posn=66
• d) What is the location of the 10th element?
• Index of 10th element=−15+(10−1)=−15+9=−6
• Address=459+2(-6+15)
• =459+9*2=477
• e) Which element is located at 589?
• Address=base+w(k-LB)
• 589=459+2(k+15)
• 130=2k+30
• 100=2k
• K=50
• Suppose, an array A[-51...48] is stored in a memory whose starting
addressis 1000. Assume that the word size for each element is 4. Then
obtain the following:
• •(a) How many number of elements are there in the array A?
• •(b) How much memory is required to store the entire array?
• •(c) What is the address location for A[1]?
• •(d) What is the address location of 53rd element?
• •(e) Which element is located at address 1076?
Ans:
• A)100
• B)400
• C)1208
• D) 1208
• E)A[-32]
 Multi Dimensional Arrays
• Linear arrays – referenced by one sub scripts
• Multi Dimensional arrays- referenced by more than one subscript two or
three
• A two dimensional array A is a collection of M*N elements such that each
element is specified by pair of integers such as j, k called subscripts
• A two-dimensional array is specified using two subscripts where the first
subscript denotes the row and the second denotes the column.
• The element of A with subscript j and second subscript k is denoted by
Aj,k or A[j][k]
• Two dimensional arrays are called matrices with M rows and N columns.

47