COMPOUND DATA STRUCTURES IN PASCAL
data is either i) scalar
ordinal
(byte or char or boolean or integer)
real
ii) compound
set or array or string or record or
file or object
In Pascal...
Compound data types are used to individually store related pieces
of information, such that each piece of information is readily accessible.
More specifically...
A SET is a collection of values, used when
order and repetition is unimportant (ie. only one of each value needs
to be stored) - in Pascal, each element of the set is the same type
An ARRAY is an ordered collection
of memory cells of the same type (the order and repetition are important
as every value is stored). A one dimensional array (has length) is termed
a vector, a two dimensional array (length and width) is termed
a matrix, 3 and above dimensions are a headache (but is often
used)
A STRING is a special case of an ARRAY
- fixed or variable length one dimensional arrays (vectors) of CHARACTERS.
A RECORD is (usually) a multi-part
memory cell where values of varying types may be stored in a specific
order. (if it will help, visualise it as a ROW of a TABLE, where the
columns are different type information).
A TABLE (an invented type) is usually
an ARRAY of RECORDS
A FILE is an ordered collection of
RECORDS or CHARACTERS (in the case of a TEXT file) - accessible randomly
or sequentially
Typically, programmers use combinations of the above eg: records
of arrays of strings; arrays of arrays of sets....
THE PASCAL SET
A set is an un-ordered collection of distinct well defined items usually
of the same type. Each item in the set is called an element or member.
The cardinality of the set is the number of elements in the set.
The order of elements in a set, and the repetition of elements in a
set is strictly irrelevant
eg. setA = [2,3,5] setB = [5,2,3,3]
setA and B are EQUAL sets
2 is an element of setA and setB
setC = [2,5]
setC is a SUBSET of set A setA is the SUPERSET of setC
setD = [1,4,5,6,7]
the UNION of setA and setD = [1,2,3,4,5,6,7]
the INTERSECTION of setD with setC = [5]
the difference of setD-setC = [1,2,4,6,7]
the symmetric difference (XOR) of setD and setC = [1,2,3,6,7]
A LITTLE SETS EDUCATION
In memory, a SET is allocated to a single 32 byte memory cell
= 256 bits total --> LOGICAL limit to the number of different values
that can be stored in a set
the set [2,3,4] = 0011100000000...................
012345678901234567890123 (ordinal value)
the set[1,3,5,3] = 0101010000000...................
the set [] = 0000000000000................. (ie. a NULL set)
a set of char ['A','B','C']
= ............000111000000000......
^
65
User Enumerated types [eg. type Days = (sun, mon, tue...) ]
the set [sun,tue] = 10100000...................
Although this seems a grossly inefficient storage organ for small
sets, most Pascals re-use unallocated memory cell space.
Set Operations
Testing for inclusion of an element in a set makes use of the IN
operator:
1 in [2,1,3] results in TRUE
1 in [5,2,6] results in FALSE
7 in [3..25] results in TRUE
x in [3..25] depends on x's value for truth
To ADD elements to an existing set, we UNION the existing set
with a set containing the new element (this is equivalent to a bit-wise
OR)
eg: ['A','B','C'] + ['C','D'] results in ['A','B','C','D']
eg: Var barbie,ken : set of byte;
Begin
barbie := [];
barbie := barbie + [36,25,34]; {adding elements}
To find out COMMON elements, we INTERSECT (this is a bit-wise AND)
eg: newset := ken * barbie {the intersection of them}
eg: newset := ken * barbie {the intersection of them}
To REMOVE elements, we calculate as the DIFFERENCE of the original
set with a set containing the elements to be exterminated (this is a
bit-wise AND NOT)
eg: newset := ken - [36] {removes 36 from ken}
You will notice Pascal has recycled the +, - and * operators
which mean different things in other contexts.
To compare sets, we use = for EQUALITY, <>for INEQUALITY, <=
for SUBSET, >= for SUPERSET
eg: rupert := [42];
ken = barbie is FALSE as they are not equal sets
ken >= rupert is TRUE, rupert is a subset, ken is a sssuperset
CASE STUDY - a little bit more raw sets
Const max = 10
Type days = (1..max);
thing = set of days;
Var good, bad, fair : thing;
answer : thing;
Begin
good := [4,6,8,10];
fair := [1,4,5,7,3,10];
bad := [2,3,9];
answer := good + fair; {good OR fair days}
answer := good * fair; {good AND fair days}
answer := good - fair; {good AND NOT fair days}
if 1 in fair then {day 1 is a fair day}
if 2 in (good+fair) then {day 2 is either good or fair}
if fair * bad <> [] then {some days are both fair and bad}
Procedure WriteOutSet(barbie : thing);
{prints out set of days to screen}
var loop : days;
begin
for loop := 1 to 10 do
if loop in barbie
then write(loop:3);
writeln
end; {WriteOutSet}
Notes on Sets
- maximum cardinality (ie # in set) = 256*
- ordinal types only (boolean, char, byte, enumerated* and subrange*)
- NO MIXED TYPES in sets
- only way to output them is to test for elements presence, and
print conditionally (ie. loop process or the like)
Compound
Data Structures - Sets
