Module 2

ARRAYS

2.0 Introductions
In many situations, sets of data items such as the set of examination marks for a class
may be conveniently arranged into a sequence and referred to by a single identifier, e.g.
MARK= (56 42 89 65 48). Such an arrangement is a data structure called an array.
Individual data items in the array may be referred to separately by stating their position in
the array. Thus MARK(1) refers to 56, MARK(2) refers to 42, MARK(3) refers to 89, and so
on. The position numbers given in the parenthesis are called subscripts. Variables may also
be used as subscripts, e.g. MARK(i), so when i=2 we are referring to mark (2), i.e. 42, and
when i=4 we are referring to MARK (4), i.e. 65.
Arrays can be declared in various ways in different languages. But consider the following
example:

As per the above illustration, the following are the important points to be considered.
• Index starts with 0.
• Array length is 10 which means it can store 10 elements.
• Each element can be accessed via its index. For example, we can fetch an element at
index 6 as 27.
The following are the basic operations supported by an array.
• Traverse – move across all the array elements one by one.
• Insertion − Adds an element at a given index.
• Deletion − Deletes an element at the given index.
• Search − Searches an element using the given index or by the value.
• Update − Updates an element at the given index.
2.1 Array elements: The individual data items in array are often called its elements. Strictly
speaking however, a data item occupies an element, i.e. elements, rather like pigeonholes, are
regarded as locations into which data items may be placed and removed.

2.2 The Computer Main Memory

In computing, memory refers to the computer hardware integrated circuits that store
information for immediate use in a computer; it is synonymous with the term "primary
storage". Computer memory normally operates at a high speed, for example random-access
memory (RAM), as a distinction from storage that provides slow-to-access information but
offers higher capacities. If needed, contents of the computer memory can be transferred to
secondary storage; a very common way of doing this is through a memory management
technique called "virtual memory"
 Proper management of memory is vital for a computer system to operate properly.
Modern operating systems have complex systems to properly manage memory. Failure to do
so can lead to bugs, slow performance, and at worst case, takeover by viruses and malicious
software. Nearly everything computer programmers do requires them to consider how to
manage memory. Even storing a number in memory requires the programmer to specify how
the memory should store it.
The computer main storage operationally may be regarded as an array in which:
i. The locations correspond to elements, and
ii. Location addresses correspond to subscripts.
One particular use of this fact is that skills learned in handling arrays are transferable to the
handling of storage.

2.3 Matrices are arrays containing only numbers and no alphabetic data. Two dimensional
arrays have elements arranged into rows and columns and are used for a variety of data
tables. For example, the examination marks of a class for several subjects could be placed in
a two-dimensional array thus:
Student English Maths c
1 A (1,1)= 56 A(1,2)=44
2 A(2,1)= 42 A(2,2)=36
3 A(3,1)= 89 A(3,2)= 73
4 A(4,1)= 65 A(4,2)= 86
5 A(5,1)= 48 A(5,2)= 51
We can represent this table as an array called A.
A = 56 44
42 36
89 73
65 86
48 51
Individual elements can be identified with two subscripts [in this particular case]: Rows 1st,
columns 2nd e.g. A (3,1) = 86. Again subscripts may be variables, as for one dimensional
array, so for A(r,c), if r=3 and c = 2, we are referring to A(3,2) = 73.

2.4 Operations on an Array

There are three basic operations on arrays. These are array insertion, deletion of an
element and searching for the existence of a value in the array.
2.4.1 Adding data(Insertion)
Insert operation is to insert one or more data elements into an array. Based on the
requirement, a new element can be added at the beginning, end, or any given index of array.
A. Before adding data to an array, make sure that the array is large enough to hold one or
more data item, so you don’t get an error. Data insertion involves the following:
i. Decide the position in the array where the element will be placed.
ii. Move through the array and shift every element after this point one element down.
This creates a free element.
III. Copy the new data into this element. Insertion increases the total number of elements
with data in the array.
If we have an array that can take a maximum of 15 elements, but with 10 elements
having data as follows: 1,32,55,20,11,12,100,23,27,50 Assuming we want to insert 67 after
the fourth element, 20, giving eleven elements. We shift 50,27,23,….,11 down by one
element so that 50 occupies location 11, 27 occupies location 10, etc., up to 11 occupying the
sixth element. Then copy 67 to the free fifth element. This is illustrated in the BASIC
program below. The line numbers are for illustration purposes only.

DIM NUM (15)

CLS
PRINT”OLD ARRAY CONTENTS:”
FOR K =1 to 10
PRINT NUM (K),
NEXT K
“SHIFT CELLS DOWN BY ONE FROM ELEEMENT 10 TO 5
PRINT
FOR K =10 TO 5 STEP -1
NUM (+ 1)=NUM(K)
NEXT K
“NEW ARRAY AFTER SHIFT6ING“
PRINT
PRINT “ARRAY AFTER SHIFTING ELEMENTS”
FOR K = 1 TO 11
PRINT NUM (k),
NEXT K
“ASSIGN 67 TO FIFTH ELEMENT“
NUM (5) = 67
“CHECK NEW ARRAY CONTENTS“
PRINT: PRINT
PRINT: “NEW ARRAY WITH INSERTED NUMBER 67”
FOR K =1 TO 11
PRINT NUM (K),
NEXT K
DATA 1, 32, 55, 20, 11, 12, 100, 23, 27, 50
END

Comments In line 10, there are 10 elements we are working with, so we started with k
=10. We want to insert data in the fifth position, so we have k =10 to 5.
Step-1 indicates we are moving cells downwards from 10 to 5. In line 11,
Num (+ 1) = num ((k) copies the contents of the next elements 10 to position 11 in the array,

2.4.2 Removing Data From An Array (Deletion)

Deletion refers to removing an existing element from the array and re-organizing all elements
of an array. To delete an array element, locate the item in the array by searching the Array, if
you do not know the position of the elements in the array. Note the Subscript or position of
the element you want to delete. The operation then involves shifting all elements upwards to
overwrite the contents of the element whose data you are deleting. the code segment is
shown:

DIM NUM (15)

CLS
PRINT “OLD ARRAY CONTENTS:”
FOR K =1 TO 10
READ NUM (K)
NEXT K
DELETE THE SEVENTH ELEMENT
FOR K = 8 TO 10
NUM (K-1) = NUM (K)
NEXT K
DATA 89,42,55,20,31,92,10,23,27,50 END
Comments: Line 20 loops from 8 to 10. This is because we want to delete element number 7,
so we shift up element number 8 to position 7, elements number 9 to position 8, and element
number 10 to position 9 this overwrites the old Contents of elements number 7, which is the
deletion process. Line 30 carries Out the deletion process-it simply replaces the value in
elements 7 with that of element 8, the value of element 8 with that of elements 9, and the
value of elements 9 with that of elements 10 effectively, we have only nine elements left.
This is the essence of line 40 looping from 1 to 9 instead of 1 to 10.
An array is convenient for storing data that can be accessed with a single name it
makes deletions and insertion of data very easy since you have random access to any
elements at any time using the subscript but its disadvantage is that it involves the physical
movements of large volumes of data (if the array is large) during the insertion and deletion
process, which is waste of time and computer resources. Imagine moving elements in an
Array of 20,000 elements.

2.4.3 Sorting an Array:

There are many situations which the data items within elements of an array need to be
rearranged into ascending or descending sequence, depending on need (or choice). The order
of sequence is often based upon the numerical or alphabetical order of the data. for example ,
the data in the mark array could be sorted (i.e. re-arrange into order) from MARK =(42 48
56 65 89). Of course, there are many methods of sorting, but we are not going in to that
now.

2.4.4 Searching an Array:

If we wish to know whether or not a particular value is present within an array or not, we may
find out by conducting a search. Searching is a useful and common processing activity and
there are many methods that can be used. A simple method is known as the Linear Search.
If the data in the Array has already been sorted in to order then the search can usually be
performed faster than if the data has been left unsorted. This highlights another advantage of
sorting data, that is, in addition to helping in Presentation of data, sorting can also help to
make processing faster and possibly simpler too.
Suppose that we require a function that searches through an array of examination
scores of candidates to see if a particular candidate's number is in the array. The function
will return the Boolean value 'True' If the candidate's number is found otherwise it will
return the value 'False'. The linear search is conducted by examining each array element in
turn, from first to last, until the required value is either found or not found. Clearly, if the
value has not been found by the time the last element has been examined then the search has
failed. If the array has been sorted into order the failure may be detected even sooner. Why?
The program segment below searches for a number entered by the user using the
keyboard, If found, an appropriate message is displayed on the screen.

DIM N (10)
CLS
FOR K =1 TO 10
READ N (K)
NEXT K
INPUT "ENTER NUMBER TO SEARCH:", NUM
10 FOUND = 0
FOR K = 1 TO 10
50 IF NUM = N (K) THEN
20 FOUND = 1
PRINT "NUMBER" NUM " FOUND IN POSITION "; K
END IF
NEXT K
30 IF FOUND = 0 THEN
PRINT "NUMBER"; NUM; "NOT FOUND IN ARRAY"
END IF
DATA 45, 67, 23, 89, 12, 67, 89, 34, 58, 90

Comments: Before you begin a search, you usually declare a variable that is used to indicate
to the program if the search is successful or not. Here, the variable FOUND is used. It is
assumed first that the search item is not in the array, so we have FOUND = 0 in line 10.
Line 50 does the actual searching. It compares the value entered from the keyboard in the
variable num with the current array element in N (k). a match is found when the search item
is same as that of the current array element. At the same time, FOUND = 1 indicates that the
item is found. After traversing the array, the value of found determine what to display. If it is
still 0, it means we did not find the item required. An appropriate message is then printed.
 Module 3
STRINGS
3.0 Introduction
We now turn our attention to data structures that are used for text handling and related
problems. A finite sequence of characters handled as a unit of data is called a string. For
example, ‘ABC, 3gh’, ‘kossy nwa kene Emefoh’ and ‘ the cat sat on the mat are literal strings.
In other languages in which strings are used, they are present in the form of one –
dimensional arrays of characters. In the programming language BASIC all strings identifiers
have the “$” sign as a suffix. When strings are joined together, they are said to be
concatenated. So if A ‘Kossy’ and B = ‘kene’ the assignment. C: = AB concatenates A and B
to form C where C = “kossyKene”
Part of a string is called a substring, e.g. A = “kossy” and B = “kene” are substrings of C =”
kossykene”
We shall however, be concerned primarily with strings as data structures composed of
substrings that can be operated upon individually.

3.1 String handling:

String handling notation:
(a) We number each character position in the string in sequence just like the element in
one- dimensional array.
(b) We refer to each substring by taking its first and last character position separated by a
“:” See fig. 3.1(a-d)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

T H E C A T S A T O N T H E M A T
A: = “THE CAT SAT ON THE MAT”

1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 18 1 2 2 2 2
0 1 2 3 4 5 6 7 9 0 1 2 3
T H E C A T S A T O N T H E M A T
A(6:7) : = “AT”

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
T H E C A T S A T O N T H E H A T
A (20:20): =”H”

1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3
T H E C A T A T E U P T H E M A T
A(9:14): = “ATE UP”
Fig. 3.1 (a, b, c, d)

3.2 Fixed And Variable Length String:

A string may have fixed length or variable length. Fixed length string has fixed number of
character places available for data storage while variable length string provides the data with
just the number of spaces its needs. The manipulation of fixed length and variable length
string is often needed in programming problems.
Character 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 19 2
position 0 1 2 3 4 5 6 7 8 0
content K O S S Y Z I K O A N N T A M A
Comment 1 string
st
2 string
nd
3 string
rd
4th string
Fig. 3.2a Four fixed length string
The diagram above shows four-fixed-length strings concatenated into a single string called F.
Each string is five characters long.

Characte 1 2 3 4 5 6 7 8 9 1 11 1 13 14 15 16 17 18 19 2
r 0 2 0
position

content K O S S Y * Z I K O * A N N * T A M A s
a
v
e
d
s
t
o
r
a
g
e

comment 1ststring 2nd string 3rdstring 4th string

Fig. 3.2b Four fixed length string concatenated

The diagram above shows four variable-length string concatenated into a single string called
V. The same data [as in fig. 3.2a] is used but the end of each string is indicated by “*” Note
the saving in storage space.
Discuss: the possible advantage (s) variable length string (s) will have over fixed length
string (s). Discuss also the operations on the strings.