Chapter 3

Array Data Structure

EE121
FALL 2024
Dr. R. NAMANE
What is Data Structure?
 A data structure is a storage that is used to store and
organize data. It is a way of arranging data on a computer
so that it can be accessed and updated efficiently.
 There are many different data structures, each with its
own advantages and disadvantages. Some of the most
common data structures are: Arrays, Lists,Trees and Graphs.
 To develop a program of an algorithm we should select an
appropriate data structure for that algorithm. Therefore,
data structure is represented as:
Algorithm + Data structure = Program
Classification of Data Structure
 Data structures are divided into two types:
 Primitive data structures.
 Non-primitive data structures.
 Primitive Data Structure is a fundamental type of data structure
that stores the data of only one type. it contains fundamental data
types such as integer, float, character, pointer, and these
fundamental data types can hold a single type of value.

 Non-primitive data structure is a type of data structure that can

store the data of more than one type. Non-primitive data
structures are created with the help of primitive data structures.
Examples of non-primitive data structure are Array, Linked list,
Stack,Tree.
Classification of Data Structure
Data structures: Organization of data
 The collection of data we are using have some kind of
structure or organization. No matte how complex they are,
they can be divided into two fundamental types:
 Contiguous
 Non-Contiguous.

 In contiguous structures, terms of data are kept together in

memory. An array is an example of a contiguous structure.
Since each element in the array is located next to one or two
other elements. In contrast, items in a non-contiguous
structure and scattered in memory, but we linked to each
other in some way. A linked list is an example of a non-
contiguous data structure.
Array Data structure
 An array is a linear data structure that collects elements of
the same data type and stores them in contiguous and
adjacent memory locations.
 Array is a container which can hold a fix number of items
and these items should be of the same type. Following are
the important terms to understand the concept of Array:
 Element − Each item stored in an array is called an element.
 Index − Each location of an element in an array has a numerical
index, which is used to identify the element.
Why Arrays?
 If we want to store 5 assignment marks for a student, we can
create the variables M1, M2, M3, M4, M5
 If there are 10 to 20 marks to record, this approach becomes
clumsy!
 If we also have to record a matrix of 20 assignment marks for say
100 students, with a different variable for each assignment mark,
we have:
Stu1_M1, Stu1_M2, ……., Stu1_M20
Stu2_M1, Stu2_M2,…….., Stu2_M20
.
.
.

Stu100_M1,Stu100_M2,….,Stu100_M20
 Approach is inconvenient and prone to error
Arrays
 An array data structure allows us to use the same
variable name for the 20 assignment marks for one
student.
 Using an array, we replace M1, M2, ……,M20 with a
single variable M subscripted as: M[1], M[2], .., M[20].
 Thus, an array is a data structure allowing more than
one memory location to be designated for a single
variable.
 Each element of the array variable is referenced using its
subscript.
Arrays
 Arrays are useful for many data values of the same type, e.g.,
all ages, all grades etc.
 Arrays are easier to read and use in algorithm statements
than having different variables.
 To use arrays in an algorithm, they have to be declared and
the size of the array (number of elements) needs to be
included. Syntax used is shown below:
 E.g., to declare an array in an algorithm, we use the following
Syntax: Arrayname[size]:datatype ; e.g., M[20]:Real.
The base element in an array
 The first array element (the base element) is numbered zero
(has subscript 0) in some languages like C, but numbered 1
in some others.
 If the base element is 0, the second element is 1; and if the
base element is 1, the second element is 2.
One Dimensional and Two Dimensional Arrays
One Dimensional and Two Dimensional Arrays

2-D Array with 3*4=12 Elements

One Dimensional Arrays
 The array is one-dimensional when its elements are not
themselves arrays.
 We can visualize a one-dimensional array as a single row
to store the elements. All the elements are stored at
contiguous memory locations.
One Dimensional Arrays
In 1D arrays:
 The index of an element can be either a constant, a
variable or an arithmetic expression.
 Constant: A[1]
 Variable: A[i]
 An expression: A[i+1]
 An array element is handled exactly like a variable. We
can :
 Assign a value to it: A[4] ← 15
 Use it in an expression: a ← (A[1] + A[n])/5
 Make tests on it: IF (A[i]%2=0)Then Write(A[i]) EndIF
Declaring 1D array
 Before using a 1D array, you must declare its size so that
the system reserves the memory space necessary to store
all the elements of the array.
 The declaration of a 1D array is carried out by specifying
its name, its size, and its type.
 For example, the declaration A[10]:integer corresponds
to a 1D array named A with size of ten integer elements.
 The size of the array is the maximum number of
elements it can hold (array capacity). However, the array
may hold any number of elements less or equal its size.
 Like C language, we consider that the base element is 0.
Operations on 1D arrays
 Once the 1D array is declared, the efficient access and manipulation of
its data can be done in the body of the algorithm.
 Several operations can be performed on 1D arrays among which:
 Initializing the 1D array (Input elements in the array)

 Displaying all the elements of the array

 Finding out the sum of all elements and the average of the array

 Finding the position of any element in the array

 Searching for a given value if it exists in the array or not

 Finding out the largest and the smallest element in the array

 Inserting and deleting an element

 Merging two arrays

 Sort elements of the array in increasing or decreasing order

 …
Input elements in a 1D array
 Reading a 1D array consists of entering all elements of that
array. (Fill in successive elements of the array).
 To do that, we should use a loop that allows us to enter at
each iteration one element of the array.
Algorithm input_array
Variables A[10]:integer
i:integer
Start
For i=0 To 9 Do
Read(A[i])
End For
Stop
Display elements of a 1D array
 Displaying elements of a 1D array consists of writing all
elements of that array.
 To do that, we should use a loop that allows us to write at
each iteration one element of the array.
Algorithm display_array
Variables A[10]:integer
i:integer
Start
For i=0 To 9 Do
Write(A[i])
End For
Stop
Accessing individual elements in a 1D array
 Individual elements in the array can be accessed and
modified by specifying the name of the array and the index
of the corresponding element.
 Examples:
• A[2] ← 5
• A[3] ← 32
• B[5] ← ’a’
• K[i] ← K[i]+3
Finding the sum of all elements in a 1D array
Algorithm sum_of_elements
Variables A[10]:integer
S,i:integer
Start
For i=0 To 9 Do
Read(A[i])
End For
S←0
For i=0 To 9 Do
S ← S+A[i]
End For
Write (S)
Stop
Finding the maximum value of a 1D array
Algorithm finding_max
Variables A[10]:integer
max,i:integer
Start
For i=0 To 9 Do
Read(A[i])
End For
max ← A[0]
For i=0 To 9 Do
If (A[i] >max) Then
max ← A[i]
EndIf
End For
Write (max)
Stop
Searching for a given value if it exists in the array or not
Algorithm searching_value
Variables A[10]:integer
val,i,found:integer
Start
For i=0 To 9 Do
Solution 1 Read(A[i])
End For
Read(val)
found← 0
For i=0 To 9 Do
If (A[i] =val) Then
found← 1
EndIf
End For
If (found=1) Then
Write (“The entered value exists in the array”)
Else
Write (“The entered value doesn’t exists in the array”)
EndIf
Stop
Searching for a given value if it exists in the array or not
Algorithm searching_value
Variables A[10]:integer
val,i,:integer
found:boolean
Start
For i=0 To 9 Do
Solution 2 Read(A[i])
End For
Read(val)
found← False
i← 0
While ( (i<=9) AND (Not found) )
If (A[i] =val) Then
found← true
Else
i← i+1
EndIf
EndWhile
If (found) Then
Write (“The entered value exists in the array”)
Else
Write (“The entered value doesn’t exists in the array”)
EndIf
Stop
Sorting a 1D array
 There exist several techniques for sorting the values in a 1D
array in either increasing or decreasing order.
 Selection sort is a simple sorting algorithm. The main
steps of that algorithm may be stated as follows:
1. Examine each element in the array to find the smallest.
2. Swap the element found in step 1 with the first
element in the array.
3. Repeat steps 1 and 2, each time ignoring the smallest
elements already swapped.
4. Stop when only one element is left in the array.
Sorting a 1D array in increasing order by selection sort
Algorithm selection_sort
Variables A[10]:integer
i,C:integer
Start
For i=0 To 9 Do
Read(A[i])
End For
For i=0 To 8 Do
For j=i+1 To 9 Do
If (A[i] >A[j]) Then
C ← A[j]
A[j] ← A[i]
A[i] ← C
EndIf
EndFor
EndFor
For i=0 To 9 Do
Write(A[i])
End For
Stop
Two Dimensional Arrays
 Arrays that we have consider up to now are one
dimensional.
 Often data come naturally in the form of a table, e.g.,
spreadsheet, which need a two-dimensional array.
 Examples:
 Grades of multiple students obtained in several courses
 Each row is a different student
 Each column is a different course
 Temperature measurement of multiple cities over all days of the week
 Each row is a different day
 Each column is a different city
Two Dimensional Arrays
 The two-dimensional array can be defined as an array of
arrays. The 2D array is organized as a matrix which can
be represented as the collection of rows and columns.
 2D arrays are indexed by two indices, one for the row
and one for the column.
 Example:
Declaring 2D Arrays
 Similar to 1D array, before using a 2D array, we must
declare it.
 The declaration of a 2D array is carried out by specifying
its name, its size (row size and column size), and its type.
 For example, the declaration A[50][5]:Real corresponds
to a 2D array named A with size of 50 rows and 5 columns
(250 real elements).
 Like C language, we consider that the base element in
2D array is (0,0).
Input elements in a 2D array
 Reading a 2D array consists of entering all elements of that
array. (Fill in successive elements of the array).
 To do that, we should use two nested loop that allow us to
enter elements row by row.
Algorithm input_array
Variables A[10][4]:integer
i,j:integer
Start
For i=0 To 9 Do
For j=0 To 3 Do
Read(A[i][j])
End For
End For
Stop
Display elements of a 1D array
 Displaying elements of a 2D array consists of writing all
elements of that array.
 To do that, we should use a two nested loops that allows us
to write elements of the array from top to bottom rows.
Algorithm display_array
Variables A[10][4]:integer
i,j:integer
Start
For i=0 To 9 Do
For j=0 To 3 Do
Write(A[i][j])
End For
End For
Stop
Accessing individual elements in a 2D array
 Individual elements in the array can be accessed and
modified by specifying the name of the array and the row
and column indices of the corresponding element.
 Examples:
• A[2][3] ← 5
• B[3][1] ← a+1
• C[1][1] ←’a’
Finding the sum of all elements in a 2D array
Algorithm sum_of_elements
Variables A[10][4]:integer
i,j,S:integer
Start
For i=0 To 9 Do
For j=0 To 3 Do
Read(A[i][j])
End For
End For
S ←0
For i=0 To 9 Do
For j=0 To 3 Do
S ←S+A[i][j]
End For
End For
Write(S)
Stop
Finding the sum of all elements in the primary diagonal
in a square matrix
Algorithm sum_of_elements
Variables A[10][10]:integer
i,j,S:integer
Start
For i=0 To 9 Do
For j=0 To 9 Do
Read(A[i][j])
End For
End For
S ←0
For i=0 To 9 Do
S ←S+A[i][i]
End For
Write(S)
Stop
N-Dimensional Arrays
 An N-dimensional array is declared similarly to 1D and
2D arrays. All what we need to add is to specify the size
of each dimension in that array.
 Examples:
 A[100][200][300]:integer
 Three dimensional array of 100*200*300 integer elements.
 B[10][25][15][5]:real
 Four dimensional array of 10*25*15*5 real elements.