L E C T U R E # 04
INTRODUCTION TO ARRAY
Instructor: Ms.
Dur-e-Shawar Agha
ROAD M AP
Introduction to Array
Types of Array
1D- Array
Memory Representation of 1D Array
Operations on 1D Array
ARRAY
An array is a data structure, which can store a
fixed-size collection of elements of the same data
type (homogeneous).
An array is used to represent a list of numbers ,
or a list of names.
For Example :
1. List of employees in an organization.
2. Test scores of a class of students.
3. List of students in the college.
WHY WE N E E D A RRAY ?
Array is particularly useful when we are dealing with
lot of variables of the same type.
For example, lets say I need to store the marks in
math subject of 100 students. To solve this particular
problem, either I have to create the 100 variables of
int type or create an array of int type with the size
100.
Obviously the second option is best, because keeping
track of all the 100 different variables is a tedious
task.
On the other hand, dealing with array is simple and
easy, all 100 values can be stored in the same array at
different indexes (0 to 99).
TYPES OF ARRAY
1. One-dimensional arrays
2. Two-dimensional arrays
3. Multidimensional arrays
O N E DIMENSION ARRAY OR 1D A R R A Y
A variable which represent the list of items using
only one index (subscript) is called one-
dimensional array.
1D array also called Linear array
For Example , if we want to represent a set of
five numbers say(35,40,20,57,19), by an array
variable number, then number is declared as
follows
int number [5] ;
LENGTH OF ARRAY
N = length of array
Length = U B – L B + 1
⚫ U B = Upper Bound or Largest Index
⚫L B = Lower Bound or smallest Index
For Example
UB = 9
LB=0
Length = U B – L B + 1
Length = 9 – 0 + 1
Length = 10
REPRESENTATION IN M E M O R Y (1D-
A RRAY )
REPRESENTATION IN M E M O R Y (1D-
A RRAY )
Address of any element in Array =
LOC(LA[k])=Base (LA) + w (k - LB)
⚫ LOC(LA[k]) =Address of element LA[k] of the
Array L A
⚫ Base (LA) = Base Address of L A
⚫ w = No. of words per memory cell for the Array
LA
⚫ k = Any element of Array
EXAMPLE
EXAMPLE
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:
L O C (A [3]) = 1000 + 2 (3 – 1)
= 1000 + 2 (2)
= 1000 + 4
= 1004
OPERATIONS PERFORMED BY ARRAY
Traversal: Processing each element in the list
Search : Find the location of the element with
given value or the record with a given
key
Insertion : Adding new element to the list
Deletion : Removing an element from the list
Sorting : Arranging the elements in some type
of order
M erging : Combining two list into single list
TRAVERSING I N L I N E A R A RRA Y
Traversing a Linear Array
TraverseArray (LA, L B, UB)
Function: This algorithm traverse L A
applying an operation P R O C E S S
to each element of L A
Input: L A is a L inear Array with L ower
Bound L B and Upper bound U B
TRAVERSING ALGORITHM
1. [Initialize Counter] Set K:=LB
2. Repeat Steps 3 and 4 while K ≤ U B
3. [Visit element] Apply P R O C E S S to
LA[K]
4. [Increase counter] Set K:=K+1
[End of Step 2 loop]
5. Exit
EXAMPLE
Suppose we have an array of length 3 which
stores colour name in it.
Red Yellow Blue
arr[0] arr[1] arr[2]
Input : Traversing a linear array (LA) with Lower
Bound (LB) and Upper Bound (UB)
Output: Traverse Linear Array by applying
operation to each element
[Initialize Counter]
Set K:= L B
K:=0
EXAMPLE
Repeat step 3 and 4 while K <= U B (0 <= 2)
[Visit Element] Apply process to LA[1]
[Increment Counter]
Set K:= K + 1
K:=0 + 1 = 1
K=1
Repeat step 3 and 4 while K <= U B (1 <= 2)
[Visit Element] Apply process to LA[1]
[Increment Counter]
Set K:= K + 1
K:=1 + 1 = 2
EXAMPLE
K=2
Repeat step 3 and 4 while K <= U B (2 <= 2)
[Visit Element] Apply process to LA[1]
[Increment Counter]
Set K:= K + 1
K:=2 + 1 = 3
End of Loop
Exit
INSERTION I N L I N E A R A RRA Y
InsertElement (LA, IT EM, N, K)
Function: This algorithm insert an element in
a Linear Array at required position
Input: L A is a Linear Array having N
elements
I T E M is the element to be inserted at
given position K
Precondition: K≤N where K is a +ve integer
INSERTION ALGORITHM
Algorithm:
1. Set J : = N
2. Repeat step 3 and 4 while J > = K
3. [Move J t h element downward]
Set L A [ J + 1] := LA[J]
4. Set J : = J – 1 [Decrease Counter]
5. Set LA[K]:= I T E M [Insert Element]
6. Set N:= N + 1 [Reset N]
7. Exit
N= Filled position of linear array
K = Position in linear array where we insert item
EXAMPLE
Suppose we take an array of length 8 (LA[8]).
Initial 5 positions are occupied with data and
remaining 3 are free. We want to insert an
element on 3rd position of an array (LA[2]).
Red Blue Pink Green White
0 1 2 3 4 5 6 7
Input : ( LA , N , K , ITEM), L A is linear array with
N elements and K is a positive integer such that
K<=N.
Output: Insert an element ITE M into the Kth
position in LA .
EXAMPLE
I TE M = Orange
J =N =4
K =2
While (4 >=2)
[Move J t h element downward]
Set L A [ J + 1] : = LA[J]
LA[4 + 1] : = LA[4]
L A [5] : = L A [4]
[Decrease Counter]
Set J : = J – 1
4=4–1
J :=3
EXAMPLE
While (3 >=2)
[Move J t h element downward]
Set L A [ J + 1] : = LA[J]
LA[3 + 1] : = LA[3]
L A [4] : = L A [3]
[Decrease Counter]
Set J : = J – 1
3=3–1
J :=2
EXAMPLE
While (2 >=2)
[Move J t h element downward]
Set L A [ J + 1] : = LA[J]
LA[2 + 1] : = LA[2]
L A [3] : = L A [2]
[Decrease Counter]
Set J : = J – 1
2=2–1
J :=1
End of Loop
EXAMPLE
[Insert Element]
Set LA[K] : = I T E M
LA[2] : = Orange
[Reset N(5)]
Set N: = N + 1
4=4+1
N :=5
Exit
Red Blue Orange Pink Green White
DELETION IN LINEAR ALGORITHM
DeleteElement (LA, IT EM, N, K)
Function: This algorithm delete an element
from a given position in Linear
Array
Input: L A is a Linear Array having N elements
K is the position given from which
IT E M needs to be deleted
Output: I T E M is the element deleted from
the given position K
Precondition: K≤N where K is a +ve integer
DELETION ALGORITHM
1. Set ITEM:=LA[K]
2. Repeat for J : = K to N - J
3. [Move J t h element upward]
Set LA[J] := LA[J+1]
[End of Step 2 loop]
4. [Reset N] N:= N-1
5. Exit
EXAMPLE
Suppose we take an array of length 8 (LA[8]).
Initial 6 positions are occupied with data and
remaining 3 are free. We want to delete an
element on 2nd position of an array (LA[1]).
Red Blue Pink Green White Orange
0 1 2 3 4 5 6 7
Input: (LA, N , K , ITEM) where L A is Linear
Array with N elements and K is a positive integer
such that K <= N.
Output: Delete the Kth element from L A
EXAMPLE
Set I T E M : = LA[K]
I T E M : = Blue
Blue : = LA[1]
Delete element of LA[1]
Repeat for J = K to N-1
Repeat for J= 1 to 5-1
[Move J + [1+1] element upward]
Set LA[1] : = LA[1 + 1]
LA[1] : = LA[2]
EXAMPLE
Repeat for J=2 to 4-1
[Move J + [2+1] element upward]
Set LA[2] : = LA[2 + 1]
LA[2] : = LA[3]
Repeat for J= 3 to 3-1
[Move J + [3+1] element upward]
Set LA[3] : = LA[3 + 1]
LA[3] : = LA[4]
Repeat for J= 4 to 2-1
[Move J + [4+1] element upward]
Set LA[4] : = LA[4 + 1]
LA[4] : = LA[5]
End of Loop
Reset the number N(6) of elements in L A
Set N : = N – 1
N = 5Green White Orange
Red Pink
0 1 2 3 4 5 6 7
SUMMARY
Introduction to array
Introduction to 1D - Array
Operations on 1D- Array