Data Structures
Arrays
24 October 2019 Data Structures 1
Eastern University
Introduction to Arrays
Linear data structure
- The elements have a linear relationship represented by means
of sequential memory locations
Linear Arrays
- A Linear array is a list of a finite no. n of homogenous data
elements such that
- elements of the list are stored respectively in consecutive memory
locations.
- elements can be referenced respectively by an index set consisting
of n consecutive numbers.
- A Linear array has a length of Length = UB – LB + 1 ( = UB,
when LB = 1)
- Elements of a linear array A are denoted by A[1],A[2],….A[n]
24 October 2019 Data Structures 2
Eastern University
An Example
Let Student_Marks be a 6 element linear array of integers such that
Student_Marks[1] = 80, Student_Marks[2] = 69, Student_Marks[3] = 90,Student_Marks[4] = 78,
Student_Marks[5] = 65, Student_Marks[6] = 75,
The array Student_Marks can be viewed as follows -
1 80
2 69 The length of Student_Marks Upper Bound (UB) = 6
3 90 is
Lower Bound (LB) = 1
4 78 Length = UB – LB + 1
5 65 =6–1+1=6
6 75
Student_Marks
Memory view
24 October 2019 Data Structures 3
Eastern University
Accessing elements of a linear
Array
..
Computer memory .
Let LA be a linear array in memory 1000
Let Loc(LA[k]) = addr. of the element LA[k] in memory 1001
Let Base(LA) denotes the addr. of the first element of 1002
LA called the Base address. 1003
Computer can calculate the addr. of any element of LA .. .
Loc(LA[k]) = Base(LA) + w * ( k – lower bound ) . .
.
w = no. of memory cells for LA
Time to calculate the addr. of any element Ak of LA is the same for any
K. That’s why Linear Arrays are called indexed
That’s why, access to an array element is faster
24 October 2019 Data Structures 4
Eastern University
An Example
Let AUTO be an array which an automobile company uses to
record the no. of automobiles sold each year from 1981 to
2005. Suppose each element of AUTO takes 2 memory cells.
Here, Lower Bound of AUTO is 1981.
Memory address
..
Here, Base[AUTO] = 200 .
The address of the array element for the year 200 AUTO[1981]
k = 2005 can be obtained by using the formula - 201
202 AUTO[1982]
203
Loc(AUTO[2005]) = Base(AUTO) + w( 2005 - LB)
204
= 200 + 2*(2005 - 1981) 205
= 200 + 2* 24 206
= 248 .. ..
. . AUTO
24 October 2019 Data Structures 5
Eastern University
Array Operations
Traversing a Linear Array
- Let LA be a linear array. Then Traversing LA means accessing and processing
(if required) each element of LA exactly once.
Algorithm: This algorithm traverses the linear array LA with lower bound LB and
upper bound UB. Here the operation PROCESS may be any operation (e.g. printing etc.)
1. Set K := LB // Initialize a counter variable
2. Repeat steps 3 and 4 while K <= UB
While
loop 3. Apply PROCESS to LA[k] // Visit each element in LA
4. Set K := K + 1 // Increment the counter variable
5. Exit
1. Repeat for K := LB to UB
for 2. Apply PROCESS to LA[K] // Visit each element in LA
loop // End of for loop
3. Exit
24 October 2019 Data Structures 6
Eastern University
An Example
Consider the array AUTO in the previous example, which records the
number of automobiles sold each year from 1981 to 2005. Write an
algorithm to print each year and the no. of automobiles sold in that year.
Algorithm : This algorithm prints each year and the no. of automobiles sold in that year
from the array AUTO.
1. Repeat for K := 1981 to 2005
2. Print: K, AUTO[k] // Visit each element in LA
// End of step-1 loop
3. Exit
24 October 2019 Data Structures 7
Eastern University
Insertion and Deletion
Insertion
- Let A be a linear array. Insertion refers to the operation of adding another element to A.
- Inserting an element at the end of A is simply done provided that there is enough
memory space for the new element.
- Inserting an element at the middle of A requires that all the elements following that
position must be moved backward to new locations to accommodate the new element
Deletion
- Deletion refers to the operation of removing an element from A.
- Deleting an element from the end of A is simple. But deleting from the middle of A
requires that all the elements following that position must be moved forward
24 October 2019 Data Structures 8
Eastern University
An Example
Let Age be an 8 element linear array and suppose 5 elements
are in Age. Here we want to keep the ages in increasing order.
(a) what happens when the age 45 is inserted?
(b) what happens when the age 28 is inserted?
(c) what happens when the age 25 is deleted after performing (a) & (b)?
1 15 1 15 1 15 1 15
2 20 2 20 2 20 2 20
3 25 3 25 3 25 3 28 25 out
4 30 4 30 4 28 28 in 4 30
5 35 5 35 5 30 5 35
6 6 45 45 in 6 35 6 45
7 7 7 45 7
8 8 8 8
Initial state (a) Insertion at the end (b) Insertion at the middle (c) Deletion from the middle
24 October 2019 Data Structures 9
Eastern University
Insertion & Deletion Algorithms
Algorithm for Insertion: This algorithm inserts an element ITEM into the
K-th position of a linear array LA which has N elements. Here K must be <= N.
INSERT (LA, N, K, ITEM)
1. Set J := N // Initialize a counter variable
2. Repeat steps 3 & 4 while J > K // Starts an while loop
3. Set LA[J + 1] := LA[J] // Move J-th element downward
4. Set J := J – 1 // Decrease the counter variable
// End of step 2 loop
5. Set LA[K] := ITEM // Insert the element
6. Set N := N + 1 // Reset N
7. Exit
Algorithm for Deletion: This algorithm deletes the K-th element from a linear array
LA which has N elements and assigns the element to ITEM. Here K must be <= N
DELETE (LA, N, K, ITEM)
1. Set ITEM :=LA[K] // removes the K-th element
2. Repeat for J := K to N-1 // Starts a for loop
3. Set LA[J] := LA[J + 1] // Move J + 1st element upward
// End of step 2 loop
4. Set N := N - 1 // Reset N
• Exit
24 October 2019 Data Structures 10
Eastern University
Sorting; Bubble Sort
Let A be a list of n numbers
Sorting A refers to the operation of rearranging the elements of A
BUBBLE (DATA, N)
1. Repeat steps 2 and 3 for K =1 to N -1
2. Set PTR:=1 // Initializes pass pointer PTR
3. Repeat while PTR <= N – K // Execute pass
a) IF DATA[PTR] > DATA[PTR + 1], then:
Interchange DATA[PTR] and DATA[PTR + 1]
[End of IF Structure]
b) set PTR:=PTR + 1
[End of Inner Loop]
[End of Step 1 outer loop]
4. Exit
24 October 2019 Data Structures 11
Eastern University
Linear Search Algorithm
The Problem: Let DATA be a LA with N elements and ITEM
is the given information to be searched. This algorithm finds
the location LOC of ITEM in DATA or sets LOC := 0 if the
search is unsuccessful.
LINEAR (DATA, N, ITEM, LOC)
1. Set DATA[N + 1] := ITEM // Insert ITEM at the end of DATA
2. Set LOC := 1 // Initialize counter
3. [Search for ITEM]
Repeat while DATA[LOC] ≠ ITEM
Set LOC := LOC + 1
[End of loop]
4. If LOC = N + 1, then: Set LOC := 0 // Successful??
5. Exit
24 October 2019 Data Structures 12
Eastern University
Binary Search Algorithm
The Problem: Let DATA be a sorted LA with lower bound LB and
upper bound UB and ITEM is the given information to be searched. The
variables BEG, END and MID denote, respectively, the beginning, end
and middle locations of a segment of elements of DATA. This algorithm
finds the location LOC of ITEM in DATA or sets LOC := NULL if the
search is unsuccessful.
BINARY (DATA, LB, UB, ITEM, LOC)
1. [Initialize segment variables]
Set BEG := LB, END := UB and MID := INT( (BEG + END) / 2)
2. Repeat Steps 3 and 4 while BEG ≤ END and DATA[MID] ≠ ITEM
3. If ITEM < DATA[MID], then:
Set END := MID – 1
Else:
Set BEG := MID + 1
[End of If structure]
4. Set MID := INT( (BEG + END) / 2)
[End of Step 2 loop]
5. If DATA[MID] = ITEM, then:
Set LOC := MID
Else:
Set LOC := NULL
[End of If structure]
6. Exit
24 October 2019 Data Structures 13
Eastern University
Two-Dimensional Arrays
(matrices or tables)
A two-dimensional array A is a collection of m*n data elements
where A may be viewed as a table with m rows and n columns-
each element is specified by a pair of integers (such as J, K); called subscripts
with the property that 1 <= J <= m and 1 <= K <= n
The elements of A with first subscript J and second subscript K are denoted as
Aj,k or A[J, K]
The element A[J, K] appears in row J and column K.
columns
1 2 3 4
1 A[1, 1] A[1, 2] A[1, 3] A[1, 4]
A
2-dimensional 3*4
rows 2 A[2, 1] A[2, 2] A[2, 3] A[2, 4]
matrix
3 A[3, 1] A[3, 2] A[3, 3] A[3, 4]
24 October 2019 Data Structures 14
Eastern University
Representation of 2-D arrays
in Memory
Let A be a 2-dimensional m*n array. A will be represented
in memory by a block of m*n sequential memory locations.
A may be stored in memory in 2-ways
Row-major order
- The elements of the 1st row are stored first, then the 2nd row, then 3rd and so on.
Column-major order
- The elements of the 1st column are stored first, then the 2nd column, then 3rd and
so on. A subscript
subscript
A (1, 1) (1, 1)
(2, 1)
Column 1
(1, 2) Row 1
(1, 3) A (1, 2)
2-dimensional 2*3 Column 2
(2, 1) matrix
(2, 2)
(2, 2) Row 2 (1, 3)
Column 3
(2, 3) (2, 3)
(a) row-major order (a) column-major order
24 October 2019 Data Structures 15
Eastern University
2-D array representation (Cont.)
Recall for a linear array LA the address of the K-th element of
LA is given by the formula -
LOC( LA[K] ) = Base(LA) + w * ( K - LB) ; w is the word-length
Similar is the case with 2-D arrays. If A is an m*n 2-D array then the
address of the element A[J, K] is given by –
Row-major order
LOC( A[J, K] ) = Base(A) + w * [ (J-LBrow) * n + (K-LBcolumn) ]
Column-major order
LOC( A[J, K] ) = Base(A) + w * [ (K- LBcolumn) * m + (J- LBrow) ]
Here, Base[A] = addr. of the first element of A, i.e. A[1, 1]
w = no. of words per memory cell for A
24 October 2019 Data Structures 16
Eastern University
Row major order A
subscript
100 A[1, 1]
columns 101 A[1, 2]
Row 1
1 2 3 4 102 A[1, 3]
A 1 A[1, 1] A[1, 2] A[1, 3] A[1, 4] 103 A[1, 4]
104 A[2, 1]
rows 2 A[2, 1] A[2, 2] A[2, 3] A[2, 4]
105 A[2, 2]
Row 2
3 A[3, 1] A[3, 2] A[3, 3] A[3, 4] 106 A[2, 3]
107 A[2, 4]
108 A[3, 1]
109 A[3, 2]
Row 3
110 A[3, 3]
111 A[3, 4]
Row-major order
LOC( A[J, K] ) = Base(A) + w * [ (J-LBrow) * n + (K-LBcolumn) ]
Here, Base[A] = addr. of the first element of A, i.e. A[1, 1]
w = no. of words per memory cell for A
24 October 2019 Data Structures 17
Eastern University
Column major order A
subscript
100 A[1, 1]
columns 101 A[2, 1] Column 1
1 2 3 4 102 A[3, 1]
A 1 A[1, 1] A[1, 2] A[1, 3] A[1, 4] 103 A[1, 2]
104 A[2, 2] Column 2
rows 2 A[2, 1] A[2, 2] A[2, 3] A[2, 4]
105 A[3, 2]
3 A[3, 1] A[3, 2] A[3, 3] A[3, 4] 106 A[1, 3]
107 A[2, 3] Column 3
108 A[3, 3]
109 A[1, 4]
110 A[2, 4] Column 4
Column-major order
111 A[3, 4]
LOC( A[J, K] ) = Base(A) + w * [ (K- LBcolumn) * m + (J- LBrow) ]
Here, Base[A] = addr. of the first element of A, i.e. A[1, 1]
w = no. of words per memory cell for A
24 October 2019 Data Structures 18
Eastern University
Matrix Multiplication Algorithm
The Problem: Let A be an M x P matrix array, and
let B be a P x N matrix. This algorithm stores the
product of A and B in an M x N matrix array C.
MATMUL (A, B, C, M, P, N)
1. Repeat Steps 2 to 4 for I = I to M:
2. Repeat Steps 3 and 4 for J = 1 to N:
3. Set C[I, J] := 0 // Initializes C[I, J]
4. Repeat for K = 1 to P:
C[I, J] := C[I, J] + A[I, K] * B[K, J]
[End of inner for loop]
[End of Step 2 middle loop]
[End of Step 1 outer loop]
5. Exit
24 October 2019 Data Structures 19
Eastern University