ARRAYS

Arrays
• Data structures are either linear or non-linear
• Elements in a linear structure form a sequence.
• There are two ways of representing linear
structures in memory .
– One way is to have linear relationship between the
elements represented by means of sequential
memory locations. These linear structure are called
arrays
– Another way is to have linear relationships between
elements represented by means of pointers or links.
These linear structures are called linked lists.
• The non-linear structures are trees and graphs
 Arrays
• An Array is the simplest data structure that
can be used in a program
• Arrays are data structures that contain
data items of the same type.
• Arrays are static . This means that the size
of the array is fixed from the declaration all
the way to the final program
implementation.
 Why do we need Arrays in our
programming?
• For example if we wanted to keep a record
of personal expenditure for year 2011, you
can file all your receipts and details of
expenditure in multiple files according to
the month.
• This means that you have 12 different
files.
 Why do we need Arrays in our
programming?
• However, wouldn’t it be easier if you could
manage a single file with 12 compartments?
• In computer programming if we were to
computerize the above, we could either
declare 12 separate variables to represent
the total monthly expenditure or even better
still we could declare an array with 12
elements
 Arrays
• an array declaration is similar to normal
variable
• In general, we can declare one-
dimensional arrays as follows:
• data_type
array_name[number_of_elements];
• data_type - type of data that will be stored in the array
• array_name - the name of the array
• number_of_elements - a positive integer that indicates how many elements should
be stored in memory
 Arrays
• A one-dimensional array is an array that
has only one index or subscript.
• An index is a value that is written in the
brackets [ ] after an array name.
• An index can identify the number of
elements in an array.
 Arrays
• Some notations

• K in A[K] is called a subscript or index

• A[K] is called a subscripted variable
• If DATA is a 6 element linear array of integers such that :
– DATA[1]= 247, DATA[2]=56,
– DATA[3]=429 , DATA[4]=135,
– DATA[5]=87 , DATA[6]=156
 Linear Data Structures
• The elements of an array are referenced by an
index set consisting of n consecutive integers
• The elements of an array are stored respectively
in successive memory locations,
• The length or number of data elements in an
array can be obtained from the index set by the
formula
• Length = UB – LB + 1
UB => largest index called Upper Bound
LB => smallest index called Lower Bound
 Illustration of memory location of the
array name
declaration of int Expense[10]

Expense[0]
Expense[1]
Expense[2]

Expense[9]

array index
The memory of a computer is a
sequence of address locations
 Linear Data Structures
• In memory if LA is a linear array then:
• LOC(LA[K]) = address of element LA[K] of
the array LA.
• Elements of array LA are stored in
successive memory cells.
• The computer only needs to keep track of
the first element of LA denoted by
Base(LA) called the base address of LA.
 Linear Data Structures

• Consider an array HOTELS

• HOTELS[K] is the number of rooms in a hotel:
• LB = 0 , UB = 32
• Length = UB – LB + 1 = 32 – 0 + 1 = 33
=> HOTELS contains 33 elements and its’ index
set consists of all integers from 0 to 32.
• We can find the memory address of various
elements in the array HOTELS .
<<See Next Slide>>
 Linear Data Structures
• The computer calculates the address of any
element of LA by the formula:
• LOC(LA[K]) = Base(LA) + w(K – lower bound)
• w = # of words per memory cell for array LA
• Given any subscript K you can locate and
access the contents of LA[K] without scanning
any other element of LA
200 }
}
201 }
HOTEL[0]
}
}
}
}
}
}
HOTEL[1]

}
}
202 }
}
203 }
}
204 HOTEL[2]
}
205 }
}
206 }
Example:
• Given the memory address of the 1st
element –> BASE address = 200 , Lower
Bound = 0, and the number of words per
memory cell (w) = 4
The address of the 3rd element in memory
of the following array structure Hotel is
= Base address + w(K-Lower Bound)
where K is the Nth element (i.e. N-1 = 2)
= 200 + 4(2-0) = 208
 Linear Data Structures
• LOC(HOTEL[0]) = 200,
• LOC(HOTEL[1]) = 204,
• LOC(HOTEL[2]) = 208 ….
• LOC(HOTEL[29]) = ??
• A collection A of data elements is said to
be indexed if any element of A which we
will call Ak can be located and processed
in a time that is independent of K
 Linear Data Structures
• Operations that are performed on linear structures
whether it be an array or linked list include:

a) Traversal. Processing each element in the list

b) Search. Finding the location of the element with a
given value or a record with a given key.
c) Insertion . Adding a new element to the list
d) Deletion. Removing an element from the list
e) Sorting. Arranging the elements in some type of
order
f) Merging. Combining two lists into a single list.
g) Size. Number of elements in the list or array
h) IsEmpty? Is the list or array empty?
 Linear Data Structures
• Your choice of structure varies from one
situation to another and is dependent on
the relative frequency with which one
performs these different operations on the
structure.
 Insert and Delete operations of an
array
• Insert is an operation means adding another
element to the array
• Delete is an operation means removing one of
the elements from the array
• Inserting at the end of an array can be easily
done provided there is space to accommodate
the element
• Deleting at the end of an array is also easily
done provided there is something to be
removed.
 Insert and Delete operations of
an array
• Either operation requires movement of
elements in the array if insert or delete is
performed in the middle of an array.
• If an insert is performed into the middle of
array then on average half the elements of
the array must be moved downwards to
accommodate the new element and keep
the order of the other elements
• Similarly deleting an element in the middle
would require each subsequent element
would be moved one location upward in
order to fill up the array
 NAME NAME NAME NAME

0 0 0 Brown 0 Brown
Brown Brown
1 Davis 1 Davis 1 Davis 1 Ford
2 Johnson 2 Ford 2 Ford 2 Johnson
3 Smith 3 Johnson 3 Johnson 3 Smith
4 Wagner 4 Smith 4 Smith 4 Taylor
5 5 Wagner 5 Taylor 5
Wagner
6 6 6 Wagner 6
7 7 7 7

(a) (b) (c) (d)

 Insert and Delete operations of an
array
• 8 element linear array with five names listed
alphabetically.
• If we add Ford to the array then Johnson, Smith
and Wagner must move downward one location
as in fig b
• If we next add Taylor to the array then Wagner
must be moved as in fig c
• If Davis is removed from the array then five
names Ford, Johnson, Smith, Taylor, Wagner
must be moved upward one location.
Linear Array Deletes & Inserts
 Multidimensional Arrays
• The linear arrays we’ve been dealing with
are called one dimensional arrays since
each element is referenced by a single
subscript.
• Most programming languages allow 2, 3
dimensional and some up to 7 dimensional
 Multidimensional Arrays
• Two dimensional arrays called matrices in
mathematics and tables in business applications
• A two dimensional m x n array A where the
elements of A form a rectangular array with m
rows and n columns and where the element
A[J,K] appears in row J and column K.
• A row is a horizontal list of elements
• A column is a vertical list of elements.
 Multidimensional Arrays
• Two-dimensional 3 x 4 array A

A[1,1] A[1,2] A[1,3] A[1,4]

A[2,1] A[2,2] A[2,3] A[2,4]
A[3,1] A[3,2] A[3,3] A[3,4]
 Multidimensional Arrays
• Two-dimensional 25 x 4 matrix array SCORE
• SCORE[K,L] contains the contains the Kth student score on the Lth test.
• SCORE[2,1] , SCORE[2,2] , SCORE[2,3] , SCORE[2,4] contain the four
test scores of the 2nd student

Student Test 1 Test 2 Test 3 Test 4

1 84 73 88 81
2 95 100 88 96
3 72 66 77 72
….. ….. ….. ….. …..
25 78 82 70 85
Array SCORE
 Linear Data Structures

• An automobile company uses an array AUTO to

record automobiles sold each year from 1932
through to 1984.
AUTO[K] is the number of automobiles sold in the
year K then:
LB = 1932 , UB = 1984. If Base address = 250, nos.
of words per cell W = 4
a) What are the number of elements in AUTO
b) What is the address of AUTO[1945], AUTO[1979]
a) Number of elements in AUTO = UB – LB + 1
= 1984 – 1932 + 1
= 53

b) Address of AUTO[1945] =Base address + w(1945 – LB)

= 250 + 4(1945-1932)
= 250 + 52
= 302

Address of AUTO[1979]=Base address + w(1979 – LB)

= 250 + 4(1979-1932)
= 250 + 4(47)
= 438
 POINTER ARRAY
• Consider an array AGES, consider a
variable P, this is a pointer if it points to an
element in AGES. P contains the address
of an element in AGES
• Given an array of strings, use pointers to
order the strings in sorted form, leaving
the array unchanged.
 POINTER ARRAY
• In general, an array of pointers can be
used to point to an array of data items with
each element of the pointer array pointing
to an element of the data array.
 POINTER ARRAY
• The advantage of a pointer array is that
the pointers can be reordered in any
manner without moving the data items.
• For example, the pointer array can be
reordered so that the successive elements
of the pointer array point to data items in
sorted order without moving the data
items.
 POINTER ARRAY
• Reordering pointers is relatively fast
compared to reordering large data items
such as data records or strings. This
approach saves a lot of time, with the
additional advantage that the data items
remain available in the original order.
 1 Davis
2 Johnson
1 8 3 Smith
2 1 4 Evans
3 4 5 Harris
5 6 Segal
2 7 Baker
9 8 Johnson
9
10