Appendix A: Review of Data Types in

Pascal

Scalar data types

There are four simple scalar data types in Pascal: INTEGER, REAL, CHAR
and BOOLEAN.
Arithmetic operators+,-,* are defmed for real and integers data types,
with the division operators MOD, DIV (integer division) and I (real division).
Standard functions such as SIN, COS, EXP are also provided.
Variables of type CHAR hold a single character value, while Booleans store
a value TRUE or FALSE.
Comparison operators allow variables or expressions of compatible types to
be compared (for=,<>,<, etc.) to yield a Boolean result. Boolean operators
AND, OR, NOT are available to test more complex conditions.
The assignment statement can be used to evaluate an expression involving
variables, constants and operators, and store the result in a variable of the
appropriate type. Type-checking is performed on all operations and assignments,
ensuring that only compatible data types are used. Integer expressions can be
assigned to integer or real variables, but real expressions can be assigned only
to real variables. Boolean expressions can be assigned to Boolean variables while
character expressions can be assigned to CHAR variables.

Defming new scalar data types

The simple data types can be used to build new data types. In Pascal there are
the subrange and enumeration types.

(a) Subranges

A new data type which is a subrange of integers or characters can be defined.

For example,
TYPE
posinteger= 0 .. maxint; ( * positive integers *)
capitals = 'A' .. 'Z'; ( * capital letters *)

249
250 Data Structures. Files and Databases

VAR
( * declare variables of these types *)
i: posinteger;
cap : capitals;
declares the variable i to be a positive integer which is a subrange of the
INTEGER data type, and the variable cap to be a capital letter which is a sub-
range of the data type CHAR.
The main advantages of using sub ranges are that they show clearly the
intended values of the variables and permit more error detection. The internal
representation of the subrange may be the same as for the full range, or it may
differ. Data items of these types can be used in operations with values from
the full range, and any necessary conversions will be done automatically.

(b) Enumeration types

An enumeration type is a list of names of constants which a variable of that

type can take. For example, the declaration
TYPE transactionType =(addition, deletion, enquiry, update);
sets up four constants called addition, deletion, enquiry and update. Variables
of this type can take any one of these four values.

(c) Ordinal types

The data types INTEGER, CHAR and enumeration types all share the property
that there is an underlying order to the values which allows you to determine
the successor or predecessor of any particular value. This property is not shared
by the data type REAL. The types sharing the property are called ordinal types
and are the only ones which can be used as the base type for subranges. Although
there may be situations when you would like to use a subrange of REAL values,
such a type cannot be defined in Pascal.

Structured data types

Pascal provides three structures to enable data values to be organised: sets,

arrays and records.

Sets

In Pascal, a type can be defined as a set of another base type. For instance
(assuming the declarations as above), in the statement
IF cap IN [ 'A' .. 'C' , 'L'] THEN ...
 Appendix A: Review of Data Types in Pascal 251

the set constant [ 'A' .. 'C' , 'L' ] is used in the test to see whether cap is any
one of the values 'A', 'B', 'C' or 'L'.
The similar statement
IF i IN [ 'A' .. 'C' , 'L' ] THEN ...
would be trapped as an error because the variable i is not of the correct type to
be compared with the characters in the set.
The base type of the set must be a subrange of an ordinal type, and may be
restricted in the number of elements allowed.
Set variables can be declared, and the operators+,* and- used for set union,
intersection and difference. Figure A.l shows a set variable ACCEPTED being
declared as a set whose base type is the letters A to Z. It is used in the code to
build up the set of characters found on one line of text.

(* declarations *)
VAR Accepted: SET OF 'A' .. 'Z':
(* code *)
Accepted:=(]: (*initialise to empty set*)
WHILE NOT EOLN DO
BEGIN
READ(ch):
IF chIN ['A' .. 'Z'] THEN
BEGIN
IF ch IN Accepted
THEN
WRITELN(' Character already given ')
ELSE
BEGIN
Accepted:=Accepted + [ch]:
(* add ch to Accepted set *)
WRITELN(' New character accepted')
END:
END
END:

Figure A. I Set variable declaration and use.

One-dimensional a"ays

A one-dimensional array is a block of elements, all of the same base type, each
value being identified by a subscript value. The subscript range must be from
an ordinal type such as 1 .. 20, -60 .. 43, or 'A' .. 'Z', and is specified as part
of the array declaration.
252 Data Structures, Files and Databases

In some situations the array values will be processed element by element.

On occasions the whole array will be processed without specifying the elements
individually. Pascal allows an array to be copied to another array of exactly the
same type using a single assignment statement:
a:=b; (*a and bare arrays of the same type*)
( * that is, same base type and same subscript range *)
Although it may seem reasonable to compare two arrays of the same type for
equality or inequality, this can only be done element by element in Pascal.

Packed arrays of characters

Strings of characters: abstract and concrete views

In abstract, a string of characters is a single data item used to represent a name,

address, etc. These data items can sometimes be of varying length. Languages
like BASIC and, to some extent, COBOL directly support string data items, but
Pascal does not.
To handle strings of characters in Pascal, the data type used is a PACKED
ARRAY with base type CHAR. For instance, to hold a string of up to 20
characters, you could declare a type:
TYPE
String20 =PACKED ARRAY [1 .. 20] OF CHAR;
The attribute PACKED is specified to ensure the correct form of internal
storage is used.

Processing strings

Individual characters can be accessed as elements of such an array, while the full
string can be processed by referring to the array name without subscripts. With
the declarations
VAR name I , name2 : String20;
the assignment
namel:=name2;
can be used.
Furthermore, comparisons between strings are allowed, testing for equality,
inequality, or any of the order relations which check for alphabetic order, as in
IF (name I = name2) THEN .. .
IF (name I< name2) THEN .. .
 Appendix A: Review of Data Types in Pascal 253

A major limitation in this implementation is the requirement that the strings

be declared of a fixed size and that, for assignments and comparisons, the
variables must be of exactly the same type. Little help is provided in handling
strings of different lengths. The only remedies are either to pad all strings out
to the same length, thereby wasting space, or to process the strings element by
element which increases processing times. Conformant array parameters do
allow you to write procedures which can process PACKED arrays of CHAR
of varying lengths, thus providing a little help with this problem.
Several compilers for Pascal provide extensions to the language to help in this
area. Using these extensions makes string processing much simpler, but the price
is a loss of portability.

Higher-dimensional arrays

Representing matrices

A two-dimensional array (or matrix) is a grid of elements of the same base type.
Each element needs two subscripts to identify it. Often these two subscripts can
be regarded as the element's row and column position. We shall treat the first
subscript as the row position, the second as the column position.

M[1, 1] M[1, 2] M[1, 3]

M[2, 1] M[2, 2] M[2,3]
M[3, 1] .. . ...
.. . . .. . ..

Processing matrices

As with the one-dimensional case, the array can be processed element by element,
or treated as a single unit in an assignment. In addition, it is possible to consider
rows or columns as vectors in their own right. In Pascal, you can treat each row
as a vector and perform assignments to vectors of the same type. But columns
cannot be treated similarly. Figure A.2 shows an example where two rows of a
matrix are interchanged. It illustrates how Pascal regards a two-dimensional
array as a one-dimensional array of rows which are themselves vectors.

Representing higher-dimensional arrays

Arrays of three dimensions may be defined as a one-dimensional array of matrices,

and so on for higher dimensions.
254 Data Structures, Files and Databases

(* declarations *)
TYPE
vector ARRAY [1 •• 3) OF REAL;
matrix ARRAY [1 .• 6] OF vector;
VAR
M: matrix; (* 6 rows of 3 entries *)
c: vector; (* vector of 3 entries *)
i,j : 1..6; (* subscript for rows *)
BEGIN

.
(* swap row i with row j *)
c:= M[i); (* save row i *)
M[i] := M[j]; (* copy ro~ ~ to row i *)
M[j):= c; (* copy or1g1nal row i to row j *)

Figure A.2 Declaration of a"ays.

Records
Abstract view
Often a collection of data items, usually containing different values about the
same entity, are grouped together into a single unit called a record. The individual
items of data are called the fields of the record. For example, customer details
may be held in a record containing:

I account no. I name address tel. no.

The individual fields may be of the same or different types. Some processing
will look at the fields individually, while other processing will treat the whole
record as a unit.
Concrete representation and processing

In Pascal, the record's fields are defined in its type declaration, while the
records themselves are declared as variables of that type. In figure A.3 the
records are called CustomerA, CustomerB and CustomerC. The individual
fields are referred to as CustomerA.account, CustomerB.account, etc. The
WITH statement is used to allow one record name to qualify several references
to its fields without its name having to be written in front of each field name.
Where the whole record is accessed as a unit, only the record name is speci-
fied.
 Appendix A: Review of Data Types in Pascal 255

TYPE
(* declare record type *)
CustomerDetail =
RECORD
account INTEGER;
name PACKED ARRAY [1 .. 15] OF CHAR;
address PACKED ARRAY [1 •• 40) OF CHAR;
tel No PACKED ARRAY [1 •• 12] OF CHAR
END;
VAR
(* declare three records of this type *)
CustomerA, customers, CustomerC : customerDetail;
BEGIN
(* read values into fields of CustomerA record
one by one *)
WITH CustomerA DO
READLN( account, name, address, telNo);
(* repeat for CustomerS *)
WITH CustomerS DO
READLN( account, name, address, telNo);
(* compare account fields of records *)
IF (CustomerA.account = CustomerB.account) THEN
WRITELN(' Same account numbers ')
ELSE
IF (CustomerA.account > CustomerB.account) THEN
BEGIN (* swap the records *)
Customerc .- CustomerA;
(* save first record *)
CustomerA := CustomerS;
(* copy second record to first *)
Customers := Customerc;
(* copy original first record to second *)
END;

END.

Figure A.3 Declaring and processing records.

Appendix B: Text Files in Pascal

A text file is a serial file whose basic component type is character.

Data in a text file is usually arranged in lines, corresponding to the lines on
a screen display or a printed page. The end of each line is marked by one or
more special characters. For example, the two characters CR (carriage return)
and LF (linefeed) could be used. Sent to a screen display they would cause the
cursor to be positioned at the start of the next line. On a disc or tape file these
characters are stored as components of the file (figure B.l).

Figure B.l End-of-line markers.

The exact format of the end-of-line markers varies from machine to machine.
Programming language features can isolate the programmer from these details
by providing ways of writing end-of-line markers, detecting them and skipping
over them. The programmer must be aware that special markers are there, but
need not know exactly what the markers are.
In Pascal, the two files INPUT and OUTPUT are pre-declared text files. Other
text files can be declared as variables of the file type TEXT, as in
VAR reportFile : TEXT;
Some Pascal implementations require the names of all files used in a program
to be declared in the program header. A program using three files could use a
program header statement of the form
PROGRAM Sales (INPUT ,OUTPUT ,report File);
The file variable name is used inside the program to identify the file. The
correspondence between this name and the actual file is done by the operating
system in a manner which depends on the system.
A file being used for input must be initialised by the RESET statement, while
one being used for output must be initialised by the REWRITE statement. The
two pre-declared files are already initialised. The procedures READ and WRITE
can be used to process text files. The first parameter to these procedures is the
file variable. If omitted, the file INPUT or OUTPUT is assumed.

256
 Appendix B: Text Files in Pascal 257

(* declarations *)
VAR infile, outfile TEXT:
ch : CHAR:
X : REAL:
i : INTEGER:
(* program body *)
BEGIN
RESET ( infile) :
(* prepare file for input *)
REWRITE (outfile):
(* prepare file for output *)
READ (infile, ch):
(* read a single character *)
READ (infile, x,i):
(* read a real value and an integer *)
WRITE (outfile, 'Character was •,ch,
' and numbers were •,x,' and ',i):
(* write text and values to output file *)

Figure B.2 Reading and writing values on text files.

Figure 8.2 shows how individual characters, real and integer values can be
handled by the READ and WRITE procedures. Real and integer data types are
said to be compatible with the me component type CHAR. Only values of
compatible data types can be read from or written to a text file. The appropriate
conversions are carried out as part of the READ or WRITE procedures.
The two Boolean functions, EOF and EOLN, can be used to detect the
end-of-file and end-of-line conditions. They return a value TRUE when the f:tle
is positioned at the end of f:tle or end of a line. READLN will skip over an
end-of-line marker, skipping any preceding characters still unread, while
WRITELN will write an end-of-line marker to the output f:tle.
Figure 8.3 is an example program which processes a text file character by
character. It reads an input text ftle and copies it to an output text ftle, including
line numbers on each line. Note that although the example uses its own me
variable names, the files INPUT and OUTPUT could have been used instead.
258 Data Structures, Files and Databases

PROGRAM addnumbers (infile, outfile):

CONST blank=' ':
VAR infile, outfile : TEXT:
ch : CHAR;
lineno : INTEGER;
(* program to copy a text file and incorporate
line numbers *)
BEGIN
RESET (infile); (*prepare file for input*)
REWRITE (outfile); (*prepare file for output*)
lineno:=O;
WHILE NOT EOF(infile) DO
BEGIN
lineno:=lineno+l;
WRITE (outfile, lineno:6, blank);
WHILE (NOT EOF(infile)) AND
(NOT EOLN (infile)) DO
BEGIN
READ (infile, ch);
(* read next character and *)
WRITE (outfile, ch);
(* write it to outfile *)
END;
READLN ( infile) ;
(* skip end of line marker *)
WRITELN (outfile);
(* write end of line marker to output *)
END;
END.

Figure B.3 Processing text files character by character.

Bibliography

In this section, we present a selective bibliography for references to the topics

covered in this book, and to material recommended for further reading.

(I) Pascal language texts

The following texts cover the features of Pascal including pointer data types
and recursion.
W. Findlay, and D. A. Watt, Pascal, An Introduction to Methodical Programming,
2nd edition, Computer Science Press, 1981.
D. M. Munro, A Crash Course in Pascal, Edward Arnold, 1985.
I. R. Wilson and A.M. Addyman,A Practical Introduction to Pascal- with
BS6I92, 2nd edition, Macmillan Computer Science Series, 1982.

(2) Data structures

The references on data structures include texts which give a fuller exposition
of the material covered in this text, including the topic of AVL-trees referred
to in chapter 6.
A. V. Aho, J. E. Hopcroft and J.D. Ullman, Data Structures and Algorithms,
Addison-Wesley, 1983.
E. Horowitz and S. Sahni, Fundamentals of Data Structures, Computer Science
Press, 1975.
D. E. Knuth, The Art of Computer Programming, Vol. I: Fundamental Algorithms
2nd edition, Addison-Wesley, 1973.
D. Kruse, Data Structures and Program Design, Prentice-Hall, 1984.
A.M. Tenenbaum and M. J. Augenstein, Data Structures using Pascal, 2nd
edition, Prentice-Hall, 1986.
N. Wirth, Algorithms+ Data Structures= Programs, Prentice-Hall, 1976.

259
260 Data Structures, Files and Databases

(3) Program design

Many of the above references cover the program design aspects of data struc-
tures. In addition, we give three other references.
D. Coleman, A Structured Programming Approach to Data, Macmillan Computer
Science Series, 1978.
M. Jackson, Principles of Program Design; Academic Press, 197 5.
M. J. King and J.P. Pardoe, Program Design UsingJSP- A Practical Introduction,
Macmillan Computer Science Series, 1985.

(4) Abstract data types and formal specifications

Texts dealing with formal specifications and the role of abstract data types
using different approaches are:

M. Azmoodeh,Abstract Data Types and Algorithms, Macmillan Computer

Science Series, 1987.
C. B. Jones, Software Development, A Rigorous Approach, Prentice-Hall, 1980.
J. J. Martin, Data Types and Data Structures, Prentice-Hall, 1986.
The language OBJ referred to in chapter 8 is specified in
J. Goguen, 'Parameterized Programming', IEEE Transactions on Software
Engineering, Vol. SE-10, No.5.

(S) Databases, SQL and 4GLs

Texts providing a more extensive treatment of databases include

A. Abdellatif, J. Le Bihan and M. Limame, Oracle -A User's Guide, Macmillan
Computer Science Series, 1990.
C. J. Date, 'A Critique of the SQL Database Language', SIGMOD Record,
Vol. 14, No.3, 1984.
C. J. Date, An Introduction to Database Systems, Vol 1, 4th edition, Addison-
Wesley, 1986.
C. J. Date, A Guide to the SQL Standard, Addison-Wesley, 1987.
S. M. Deen, Principles and Practice of Database Systems, Macmillan Computer
Science Series, 1985.
D. M. Kroenke, Database Processing, 2nd edition, SRA, 1983.
E. Lynch, Understanding SQL, Macmillan Computer Science Series, 1990.
F. R. McFadden and J. A. Hoffer, Database Management, Benjamin-Cummings,
1985.
J. Martin, Principles of Database Management, Prentice-Hall, 1976.
J. Martin, Fourth Generation Languages, Vol. 1, Prentice-Hall, 1985.
R. F. van der Laos, Introduction to SQL, Addison-Wesley, 1988.
Index

abstract data type 150-1 efficiency 2, 5-6, 9-10, 12-15,38-40,

abstract structure 1 42, 56,67-8, 70, 75, 77,94-5,
access vectors 38-42 104-5,111,137,187,196
adjacency matrix 135-6, 138 entity 158
array 4, 251-4 entity-relationship diagram 158-68
attributes 158, 165, 168-77, 197-204 expressions 46-50
AVL-trees 111 trees 111-15

B-trees 119-25 FIFO 50

B+-trees 124-5 file buffers 22-3
backtracking 45 file structure 1
batch update 26-33 formal specification 150-1
binary search 12-15 fourth generation languages 229-47
binary search tree 105-11 free storage lists 67-9
binary tree sort 100-5 functional analysis 162, 166-8
binary trees 98-115 functional dependency 171-3, 17 5-6
balance 104-5, 111
breadth-first search 129, 131 general trees 115-17
bubble sort 4-6 GET 22,79
graphics 231,243-5,247
graphs 127-48
circular chains 70-1, 73-4 acyclic 131-5
CODASYL database 179-89 weighted 127, 138-43
CODASYL set 180-2, 185
conceptual model 157, 162-77, hashed random files 79-81
209-10
concrete structure identifying attribute 158
cycles 131-3 IMAGE 179, 189-93
indexed sequential files 84-9, 123
data analysis 158, 162-77 indexes 41-2,80-9, 123-5,211-13
data structure indirect recursion 96-7
definition 1 Informix 203,231-47
design 152 menus 241-3
data types 2-4, 249-55 reports 232-9
database 1, 156-248 screen forms 239-41
dBase II 204-6 INGRES 203-4,231-47
dBase IV 203-4 ABF 242-3
DBMS 156-8 frames 242-3
depth-first search 129-30 OSL 243
difference 72-3, 198-200,219,251 RBF 233-4
direct files 77-9 VIFRED 239
DISPOSE 66 VIGRAPH 245
domain 197 inorder traversal 115
doubly linked list 74-5 intersection 72-3, 198-200, 219, 251
dummy entries 69, 70-1, 75 inverted files 8 9-90
261
262 Index

join 200-2, 219-20 schema 157, 190, 193

screen forms 231,239-41
LIFO 42 SEEK 78-9
linear search 9-10, 13-15 select 200-2, 215
linked list 56-61,64-7, 185-8, 191 sequential files 25-36
list 4-6 serial files 18-25
LOCATION mode 186-7 set 4, 72-3, 250-1
logical model 157, 179-208 set ORDER 187-8
shortest path 140-3
membership class 189 simulation 53-4
menus 231,241-3,247 spanning for est 12 9-31
merge 26-7 spanning tree 138-40
merge sort 33-5 sparse matrices 33-40
minimal spanning tree 138 spreadsheets 231, 243, 24 7
multi-way trees 118-25 SQL 203, 209-28, 230, 235-6, 238,
240-2
navigating CODASYL database 185 ALTER 212
network 127, 138-42 CREATE 210-12
network database 12 7, 179-93 data types 210
NEW 62 DELETE 213-14
non-serial file 77-90 DROP 212
normalisation 168-77, 209 GRANT 221-3
GROUP BY clause 220-1
OPEN 78 HAVING clause 221
Oracle 203, 244,247 host-language access 224-5
overflow areas 84-5 INSERT 213,241
interactive 223-4
physical model 15 7 join 219-20
pointers 38, 61-4 NULL 210
postorder traversal 115, 11 7, 12 9 ORDER BY clause 217
preorder traversal 115, 11 7, 12 9 SELECT 221-6,235-6,238
priority queues 73 SELECT DISTINCT 216-17
problem analysis 15 0 subqueries 217-19
procedure calls 45 UPDATE 214-15
project 200-2,215-16 VIEW 221
project planning 134-5 WHERE clause 213-22,225-6
prototypes 245-7 SQL/DS 203-4
PUT 23,79 stack 42-50, 69
static index file 82-3
queues 50-4,69-70,73 subschema 157

ragged array 38 table 7-15, 197

random access 77 text files 19-22, 256-8
Rdb/SQL 203 topological order 135
record 4, 215-16 transitive closure 136-7
files of 24-5 trees 97-125
nested 6-7
recursion 91-7 union 72-3, 198-200,208,219,
relation 145-8, 197 251
relational database 196-248
relationship 158-60
reports 231-9,246 variant record 15-16
resource allocation 133-4 volume of data 153
response time 15 3
Reverse Polish 47-50 Warsall's algorithm 137