Transcript Static Data Structures – Arrays

Problem Solving for
Programming
Session 8
Static Data Structures
Data Types
• We have looked at several data types so far (e.g. integer,
boolean, string, etc. )
• Of these, the string data type is different because it is
composed of two or more instances of a different data
type: character.
• In the example below, the string, myString, is composed of
eight characters. Each of these characters has a unique
reference (0-7) which indicates its position in the string.
User-Defined Data Types
• There are other instances where it would be useful to group
related items into a single data type in the same way
characters can be grouped together into a string.
• Take, for example, a patient record. A patient record
consists of several related data items (e.g. familyName,
postCode, birthMonth)
• Most programming languages provide a mechanism for
grouping related data into records using either userdefined data types or objects.
• In pseudo code, a user-defined data type for a patient
record might look something like the following:
User-Defined Data Types
NEWTYPE PatientRecord IS
RECORD
string: title ,
familyName ,
givenName ;
integer: birthDay ,
birthMonth ,
birthYear ;
string: streetAddress ,
postalTown ,
postCode ,
telephone ;
integer: joinDay ,
joinMonth ,
joinYear ,
checkUpDay ,
checkUpMonth ,
checkUpYear ;
ENDRECORD
User-Defined Data Types
• We can now create variables of this new data type in the same
way we would create variables of any other data type:
PatientRecord: patientOne ;
PatientRecord: patientTwo ;
•
And we can access the record’s fields using dot (.) notation
patientOne.title  professor ;
patientOne.familyName  ‘Higgins’ ;
patientOne.birthDay  15 ;
. . . . . . .
• We can also perform assignment statements on our records:
patientTwo.title  patientOne.title ;
patientTwo  patientOne ;
Static and Dynamic data
Structures
• A string is an example of a static data structure: it has a
fixed size (a typical string allows 2,147,483,647 characters
or bytes)
• Static data structures can neither grow (if more memory
capacity is needed) nor shrink, if capacity is unused.
• For this reason programming languages also provide
dynamic data structures
• Dynamic data structures can expand or shrink, using only
as much memory as needed
Static data structures
Dynamic data structures
Array, table , . . . .
List, stack, queue
Static Data Structures – Arrays
• We can think of an array as a set of linked boxes
• Each box is capable of holding one item of data
• All the data stored in the array must be of the
same data type, as well as being related
• The graphic below shows an array of six cake
weights, holding integer values
• Note that the array is indexed from 0 to 5 and
not 1 to 6. This is called zero indexing
Static Data Structures –
Arrays
• Consider the following scenario:
• Bob wants to find the average weight of
large chocolate cakes baked by Barbara.
Barbara works in batches of nine cakes.
She tells Bob a cake weight and he adds it
to a running total. When Bob has all the
cake weights, he can calculate the
average weight.
Static Data Structures – Arrays
• We might approach this problem as follows:
real: weight,
totalWeight ,
averageWeight ;
Where we are
integer: counter ;
getting out
integer: numberOfCakes IS 9 ;
data from.
totalWeight  0 ;
FOR counter GOES FROM 1 TO numberOfCakes
Get (Barbara, REFERENCE: weight) ;
totalWeight  totalWeight + weight ;
ENDFOR
averageWeight  totalWeight ÷ numberOfCakes ;
Display averageWeight ;
Static Data Structures – Arrays
• The problem here is that after calculating the
average weight the weight of each cake is
effectively lost.
• A way around this would be to start by declaring
variables for each cake weight: but what if we
were dealing with batches of 100 or even 1000
cakes?
• A more productive approach would be to store
the cake weights in an array. Once they are in
the array we can use them at any point in our
program (to find the lightest, heaviest, etc.)
Static data Structures – Arrays
• To declare an array we can use the following
pseudo code:
ARRAY: weights OF [9] real ;
• This gives us an array called weights with 9
places. This array can hold only real numbers
• When declaring arrays be careful you have
thought the size through carefully. If the array is
too small you will run out of space; too large and
you will be wasting memory
Static Data Structures –
Arrays
• We can access the data in any cell of an
array using the array’s index. For
example:
weights [2]  2.0 ;
weights [index] – 1  cakeWeight ;
Static data Structures – Arrays
• Some programming languages automatically
initialize arrays (numeric values to zero and
string values to null). Others demand that arrays
be initialized by the programmer at the point of
creation (what might happen if some cells in an
array are not initialized?)
• We can initialize each cell of an array
individually:
weights [0]  3.2 ;
weights [1]  4.6 ;
• However, with larger arrays this is not feasible.
With larger arrays some kind of repetition
structure is required
Static Data Structures –
Arrays
• The most appropriate structure to initialize an
array is a count controlled loop. As we will always
know the dimensions of the array we would use a
FOR loop:
integer counter ;
FOR counter GOES from 0 to 8
weights [counter]  0 ;
ENDFOR
• Here every value in the array of cake weights is
initialized to zero
Static Data Structures – Arrays
• Most programming languages have a predefined
function that allows us to access the length of an
array (In java this function is called simply
length)
• Using this function, we could rewrite our
initialization code as follows:
integer counter ;
FOR counter GOES from 0 to LENGTH (weights) - 1
weights [counter]  0 ;
ENDFOR
• The -1 is needed because the length function
returns the size of the array (In the cakes
weights example, 9)
Static Data Structures – Arrays
• Our code to get our cake weights into an array
might look as follows:
ARRAY: weights OF [9] real ;
integer: counter ;
FOR counter GOES FROM 0 TO LENGTH(weights) - 1
Display (‘Enter a cake weight: ‘) ;
GET (Barbara, REFERENCE: weights [counter]
ENDFOR
Static Data Structures – Arrays
• And to calculate the average cake weight and the
heaviest cake:
real: average ,
totalWeight ,
heaviestCake ;
average  0 ;
totalWeight  0 ;
average  0 ;
FOR counter GOES from 0 to LENGTH (weights) – 1
totalWeight  totalWeight + weights [counter] ;
IF (weights [counter] > heaviestCake)
heaviestCake  weights [counter] ;
ENDIF
ENDFOR
IF (totalWeight > 0.0)
average  total ÷ LENGTH (weights) ;
ENDIF
Display (average)
Display (heaviestCake)
Searching an Array
• Suppose we are looking for cakes that
weigh to little (below 1.8kg). As we have
all the cake weights stored in an array, all
we have to do is search that array for the
target values:
weights
2.0
1.8
2.1
1.9
2.0
2.0
1.7
2.0
1.9
[0]
[0]
[0]
[0]
[0]
[0]
[0]
[0]
[0]
• How might we do this?
Searching an Array
• We might use a boolean flag to indicate
whether or not the values has been found.
boolean: found  false ;
•
Then we might iterate through the array
using a loop until we find the target value
or not. What kind of loop would be the
most appropriate here?
Searching an Array
boolean: found  false ;
integer: counter  0 ;
WHILE (counter < LENGTH (weights)) AND (NOT found)
found  weights [counter] < 1.8 ;
counter  counter + 1 ;
ENDWHILE
IF (found)
Display (‘Low cake weight found at element no. ‘ ,
counter) ;
ENDIF
• Can you see any limitations with this approach?
How might it be improved?
Searching an Array
• This approach will only ever allow us to
find a single value below the required
weight. How could we alter the code so
that multiple possible values below 1.8kg
can be found?