lOMoARcPSD|4907642

Pascal Programming [Link] KSM

ICT Law (Kenyatta University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Sylvance Otieno (syloti@[Link])
 lOMoARcPSD|4907642

THE KISUMU NATIONAL POLYTECHNIC

DIPLOMA IN INFORMATION AND COMMUNICATION

TECHNOLOGY

PASCAL PROGRAMMING

STUDENTS’ STUDY NOTES

BY

DWASI G

©2019

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

Table of contents
Table of contents .......................................................................................................................... I
INTRODUCTION TO PASCAL................................................................................................. 1
THE STRUCTURE OF A PASCAL PROGRAM ...................................................................... 1
(a) The Pascal character set...................................................................................................... 1
(b) Reserved words .................................................................................................................. 2
(c) Identifiers ............................................................................................................................ 2
(d) Standard identifiers ............................................................................................................ 2
(e) Numbers ............................................................................................................................. 2
(f) String ................................................................................................................................... 3
(g) Data types ........................................................................................................................... 3
(h) Constants ............................................................................................................................ 3
(i) Variable ............................................................................................................................... 4
(j) Expressions ......................................................................................................................... 4
(k) Statements .......................................................................................................................... 4
SIMPLE TYPE DATA ................................................................................................................ 4
OPERATORS .............................................................................................................................. 5
(a) Arithmetic operators ........................................................................................................... 5
(b) Logical operators ................................................................................................................ 6
(c) Relational Operators ........................................................................................................... 6
(d) The assignment statement .................................................................................................. 6
ORDER OF PRECEDENCE ....................................................................................................... 7
STANDARD CONSTANTS ....................................................................................................... 8
STANDARD FUNCTIONS ........................................................................................................ 9
DATA INPUT & OUTPUT ....................................................................................................... 10
(a) The read statement ........................................................................................................... 10
(b) The readln statement ........................................................................................................ 10
(c) The write statement .......................................................................................................... 10
(d) The writeln statement ....................................................................................................... 10
CONTROL STRUCTURES ...................................................................................................... 11
SELECTION .......................................................................................................................... 11

II

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

The If Structure .................................................................................................................. 11

Nested Selection................................................................................................................. 12
The case structure .............................................................................................................. 12
REPETITION CONTROL STRUCTURES .......................................................................... 14
The While – Do Structure .................................................................................................. 14
The Repeat – Until Structure ............................................................................................. 14
The For Structure ............................................................................................................... 15
The Goto Statement ........................................................................................................... 16
PROCEDURE AND FUNCTIONS ........................................................................................... 17
PROCEDURE ........................................................................................................................ 17
PARAMETERS ..................................................................................................................... 19
TYPES OF PARAMETERS .............................................................................................. 20
(a) VALUE PARAMETERS ............................................................................................. 20
(b) VARIABLE PARAMETERS ...................................................................................... 20
FUNCTIONS ......................................................................................................................... 20
USER DEFINED SIMPLE TYPE DATA ................................................................................. 22
a) Enumerated type data......................................................................................................... 22
b) Subrange ............................................................................................................................ 23
c) Utilizing User Defined Data Type ..................................................................................... 23
ARRAYS ................................................................................................................................... 25
a) One dimensional array ....................................................................................................... 25
b) Two Dimensional Array .................................................................................................... 25
c) Multi dimension arrays ...................................................................................................... 27
d)Packed arrays ...................................................................................................................... 27
SORTING .................................................................................................................................. 28
a) Selection sort...................................................................................................................... 28
b) Bubble sort ......................................................................................................................... 29
c) Insertion Sort...................................................................................................................... 32
d) Quick Sort .......................................................................................................................... 32
e) Merge Sort ......................................................................................................................... 34
f) Shell Sort ............................................................................................................................ 36

III

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

SEARCHING ............................................................................................................................. 37
a)Linear Search ...................................................................................................................... 37
b) Binary Search .................................................................................................................... 38
DATA STRUCTURES .............................................................................................................. 40
(a) Sets ................................................................................................................................... 40
(i) Defining a Set Type ....................................................................................................... 40
(ii) Constructing a Set ........................................................................................................ 41
(iii) Operations with Sets ................................................................................................... 42
(b) Stacks ............................................................................................................................... 43
(i) Introduction ................................................................................................................... 43
(ii) Operations of stack ...................................................................................................... 44
(c) Queues .............................................................................................................................. 45
(i) Introduction ................................................................................................................... 45
(ii) Operations on Queue ................................................................................................... 45
(d) Linked Lists ...................................................................................................................... 47
Double linked Lists ............................................................................................................ 49
(e) Binary trees ....................................................................................................................... 50
(i) Introduction ................................................................................................................... 50
Binary Tree Traversal ........................................................................................................ 51
RECORDS ................................................................................................................................. 54
a) Defining a record ............................................................................................................... 54
b) Processing a record ............................................................................................................ 57
c) The with structure .............................................................................................................. 57
d) Declaration of records using arrays .................................................................................. 58
FILES ......................................................................................................................................... 59
a) Introduction ........................................................................................................................ 59
b) Defining of a file................................................................................................................ 60
c) Creating a file..................................................................................................................... 60
d) Reading a file ..................................................................................................................... 62
e) Updating a file ................................................................................................................... 62
TEXT FILES .............................................................................................................................. 64

IV

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

(a) File processing .................................................................................................................. 65

(i) Opening a file ................................................................................................................ 65
(ii) Reading a text file. ....................................................................................................... 65
(iii) Detecting the of line .................................................................................................... 65
(iv) Detecting the of a file .................................................................................................. 65
(v) Writing to file ............................................................................................................... 66
(vi) Closing a file ............................................................................................................... 66

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

INTRODUCTION TO PASCAL
Pascal is a general –purpose, high level programming language that was derived from ALGOL-
60. It‟s instructions are made up of algebra like expressions and certain English words such as
BEGIN, END, READ, WRITE, IF, THEN REPEAT, WHILE , DO. Pascal was designed to
encourage the use of structured programming.
Pascal was named in honour of Blaise Pascal (1623-1662), the brilliant French scientist
and mathematician whose many accomplishments include the invention of the world‟s first
calculating machine.
Pascal was originally developed in the early 1970‟s by Niklaus Wirth at the Technical University
in Zurich, Switzerland. Wirth‟s original idea was to develop a disciplined, high level language
for teaching structured programming. Pascal is widely used in in America and Europe both as a
teaching language and as a powerful general purpose language for a variety of different
applications.

THE STRUCTURE OF A PASCAL PROGRAM

Every Pascal program contains a header and a block. The header begins with the word
PROGRAM, followed by some additional required information. The block has two main parts,
the declaration part and the statement part. The declaration part defines the various data items
that are used within the program. The statement part contains the actual statements that cuse
actions to be taken. At least one stsement must be present in every Pascal program. This overall
structure is outlined below in greater details.
1 Header
2 Block
a. Declarations
i. Labels
ii. Constants
iii. Type definitions
iv. Variables
v. procedures and functions
b. statements

(a) The Pascal character set

Pascal uses the letters A to Z (both upper and Lower); the digits 0 to 9 and certain special
symbols as building blocks to form basic program elements(numbers, identifiers, expressions
etc). the special symbols are listed below
+, -, *, /:=, =, :, ;, ‘, ^, <, >, <=, >=,
<>, .. ( ), {}, ].

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

(b) Reserved words

There are certain words that have a standard, predefined meaning in pascal. They are AND,
END, NIL, SET, ARRAY, FILE, NOT, THEN ,BEGIN, FOR, TO, CASE,
FUNCTION, OR, TYPE, CONST, GOTO, PACKED, UNTIL, DIV, IF,
PROCEDURE, VAR, DO, IN, PROGRAM WHILE, DOWNTO
LABEL RECORD WITH ELSE MOD REPEAT.
These reserved words can be used only for the intended purpose, they cannot be arbitrarily
redefined by the programmer.

(c) Identifiers
An identifier is a name that is given to some program element, such as a constant, variable, a
procedure or a program. Identifiers are comprised of letters or digits. In order to except that the
first letter must be a letter. Both upper and lower case letters are permitted and are considered to
be indistinguishable.

(d) Standard identifiers

Pascal contains a number of standard identifiers that have certain predefined meanings. These
standard identifiers are:
ABS ARCTAN BOOLEN CHAR CHR COS DISPOSE, EOF EOLN
EXP, FALSE GET INPUT INTEGER IN MAXINT NEW ODD ORD
OUTPUT PACK PAGE PRED PUT READ READLN REAL, RESET
REWRITE ROUND SIN SQR SQRT SUCC TEXT TRUE TRUNC
UNPACK WRITE WRITELN

(e) Numbers
Numbers can be written in several different ways in Pascal. In particular a number can include
assign, a decimal point and an exponent. The following rules apply to all numbers.
1 Commas and blank spaces cannot be included within the number.
2 The number can be preceded by a plus (+) or a minus (-) sign if desire. If aa sign
does not appear the number will be assumed to be positive.
3 Numbers cannot exceed a specified maximum and minimum values. These values
depend upon the type of number, the particular computer and the particular compiler
being used.
a. Integer number
An integer number contains neither a decimal point nor a exponent.

b. Real number
A real number must contain either a decimal point or an exponent (or both). If a
decimal point is included it must appear between two digits

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

(f) String
A string is a sequence of characters (i.e letters, digits and special characters) enclosed by a
apostrophes. Both upper cae and lowercase letters can be used.
Example „red‟ „dit 05‟, „3453‟

(g) Data types

Pascal has ability to support deferent types of data. These include simple data types,
structured data types and pointer data types.
Simple type data
Are single items (numbers, characters e.t.c) that are associated with a single identifiers on one to
one basis.
Structured type data
Consist of multiple data items that are related to one another in some specified manner. Each
group of data items is associated with a particular identifier.
Pointer type data:
Used to construct dynamic structured data types.
The various data types are summarized below.
1 Simple type data
a. Standard data types
i. Integer
ii. Real
iii. Char
iv. Boolean
b. User defined data types
i. Enumerated
ii. Subrange
2 Structured type data
a. Arrays
b. Records
c. Files
d. Sets
3 Pointer type data

(h) Constants
It is often convenient to associate a simple data item, such as a numerical value or a string with
an identifier, thus providing a name for the data item. The identifier is called constant if the data
item is assigned permanently (constant must always be defined before it can appear in a Pascal
statement)
Const name= value
Name is an identifier that represents the constant name and value is the actual data item that is
assigned to a name.
Example
Const fraction = 0.1667

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

Const tittle=”computer department”

(i) Variable
An identifier whose value is allowed to change during the execution of a program is called
variable. Every variable must be individually declared (i.e. define) before it can appear in a
program.
The general form of a variable declaration
Var name : type if they are several then
Var name1, name2, - - - -- - - -namen; type
Name1, name2 --- namen are identifiers that represents individual variables and type refers to
the data type of the variables
Example var row,col:integer;
Value :real;
Flag:char;

(j) Expressions
An expression is a collection of operands (i.e. numbers, constants, variables etc) joined together
by certain operators to an algebraic term that represents a value (i.e. simple data item). There are
two types of expressions in Pascal: A numerical expression and Boolean expressions. A
numerical expression represents a numerical value where a Boolean expression represents a logic
condition which is either true or false.

(k) Statements
A Pascal statement is an instruction or a group of instructions that causes the computer to
carryout certain action. There are two basic types of statements in Pascal : simple and structured.
Simple statements are essentially single unconditional instruction that perform ano of the
following tasks
1. assign a data item to a variable (this is called assignment statement)
2. access a self-contained computational module called a procedure
3. transfer program control unconditional to another part of the program(The goto
statements

Pascal recognize different types of structured statements: these include

1. Compound statements
2. Repetitive statements
3. Conditional statements

SIMPLE TYPE DATA

These are standard (or inbuilt) simple data types that are included as part of the Pascal program.
These data types include integer, real, char, and Boolean. Three of the standard data types i.e.
integer, char and Boolean are often referred to as ordinal data types, since the data items that
comprise each of these data types are members of an ordered, finite set. User defined simple type
data (i.e. enumerated and sub range data) also fall in this category.

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

(a) Integer Type data

Integer types data are whole numbers (integer) quantities. Included within this category are
integer – type constants, variables, functions and expressions.

(b) Real type data

Real type refers to data items that represent real numerical quantities. These include real type
constants, variables, functions and expressions

(c) Char type data

Char type data are single character strings i.e. single characters enclosed in a apostrophes.
This data type include single character, constants identifiers that represents single characters
constants, char type variables and certain char-type functions

(d) Boolean type data

Are truth values that are either true or false. This category includes Boolean type, variables,
functions and expressions. The two values that apply to Boolean type data (True and False)
represent an ordered set with false preceding true.(note that false is encoded as 0 and true is
encoded as 1) Boolean type expressions are formed by combining operands of the same type
with relational operators

OPERATORS
Operators make it possible for you to manipulate data of the same type. Visual FoxPro operators
can be grouped according to the following data types

(a) Arithmetic operators

Collectively, the operators that are used to carry out numerical type operations are called
arithmetic operators. There are six arithmetic operators that can be used in Pascal
INTEGER TYPE REAL TYPE DATA
DATA
Operator Purpose Type of Type of Type of Type of
operands resultant operands resultant
+ Additions Integer integer Real Real
- Subtraction Integer Integer Real Real
* Multiplication Integer Integer Real Real
/ Division Integer Real Real Real
DIV Truncated Integer Integer N/A N/A
division
MOD Remainder Integer integer N/A N/A
after division

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

(b) Logical operators

Logical operators work with all data types and return a Logical value. Pascal contains three
logical operators. Two of theses operators allow Boolean type operands to be combined to form
Boolean-type expressions. The third is used to negate (i.e. to reverse) the value of a Boolean
operand
Operator Meaning
OR Expression will be true of either operand is true(or if
both operands are true)
AND Expressions will be true only if both operands are true
NOT This operator is used as a prefix to negate a Boolean
operand.

(c) Relational Operators

Relational operators work with all data types and return a Logical value. The following are
relational operators
Operator Meaning
= Equal
<> Not equal to
< Less than or equal
<= Less than or equal to
> Greater than
>= Greater than or equal to

(d) The assignment statement

The assignment statement is written in the form variable: = data item. A data item can be a
single item (e.g a constant, another variable or a function reference) or it can be an expression.
The data item must however be of the same type as the variable to which it is Assigned example

Area: = 3.14 x Sqr (radius);

The statement causes the value of the expression 3.14 x sqr (radius) to be assigned to the variable
area.

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

ORDER OF PRECEDENCE

An expression can sometimes become quite complex, because of the presence of multiple
operators within an expression. The order in which these operations are carried out is

Procedure Operators

1(Highest) NOT
2 X/DIV MOD AND
3 + - OR
4(LOWEST) = < > < < = > > = IN

NB Sometimes it is a good idea to use parentheses to clarify an expression even though the
parentheses may not be required.
The following grammatical rules must always be observed when constructing numerical &
Boolean expressions

1. The resultant will be positive if both operands are of the same sign. Otherwise the
resultant will be negative.
2. The two division operators (/ & DIV) and the MOD operator require that the second
operant be non zero
3. Use of the DIV operator with a negative operand will result in truncation toward zero. i.e
The resultant will be smaller in magnitude than the true quotient
4. Undefined identifiers cannot appear within an expression (In other words, each identifier
must be assigned a value before it can appear within an expression)
5. Proceeding an identifier with a minus sign is equivalent to multiplication by -1 thus – a x
b is equivalent to -1 x a x b
6. Arithmetic operators cannot appear consecutively. Hence, the expression a x –b is not
allowed but a x (-b) is permitted
7. Arithmetic operations cannot be implied expression 2 (x + y) is incorrect, but the
expression 2x (x + y) is valid.
8. Arithmetic operation cannot be carried out on char or Boolean type data therefore
expression such as „A‟ + „B‟ and (n>0) + (n<20) are not allowed

NB

DIV means truncated division

>/3 = 2.33
> DIV 3 = 2
& MOD means reminder after division
 MOD 3 = .3

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

STANDARD CONSTANTS

Pascal includes three standard identifiers that represent constants. They are Maxint, False or
true. The first of these maxint, specifies the largest value that may be assumed by an integer-
type quantity. False and True represent the two values that may be assigned to a Boolean-type
data item (Note false and True represent an ordered set with false preceding true)

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

STANDARD FUNCTIONS

Pascal also contains a number of standard function (i.e Intrinsic or built functions)

FUNCTI PURPOSE TYPE OF TYPE OF

ON PARAMETER X RESULT

Abs(x) Compute the absolute value of Integer or real Same as x

x
Arctan(x) Compute the arctangent of x Integer or real Real

Chr(x) Determine the character Integer Char

representedby x
Cos(x) Compute the cosine of X (x in Integer or real Real
radians)
Exp(x) Compute ex, where R = Integer/Real Real
2.71828 18 … is the base of
the natural (Na perian) system
of Logarithms
In(x) Compute the natural Integer/Real Real
Logarithm of x(x>0)
Odd(x) Determine if a is odd or even Integer Boolean
(Return a value of true of x is
odd false otherwise
Ord(x) Determine the (decimal) Char Integer
Integer that is used to encode
the character x
Pred (x) Determine the predecessor Integer,Char or Same as x
of x Boolean
Round(x) Round the value of x to Real Integer
the nearest Integer
Sin (x) Compute the sin of x to (x in Integer or real Same x
radians)
Sqr(x) Compute the square of x Integer/Real Same as x
Sqrt(x) Compute the square root of x Integer/Real Real
(x>=0)
Succ(x) Determine the successor to x Integer/Char as x or Same as x
Boolean
Trunc(x) Truncate x (i.e drop the Real Integer
decimal part of x)

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

DATA INPUT & OUTPUT

(a) The read statement

The read statement is used to read data items from the input file and assign to integer real or char
– type variables. The statement is written as
Read(input variables)
Where the input variable are separated by commas (note that Boolean type variable cannot be
included in the list of input variables)
Examples
Read(a);
Read(a,b,c)
The data items are read from the input file and assigned to their respective variables in the same
order that they are stored. Each variable must be of the same type as its corresponding data item.

(b) The readln statement

The readln statement, like the read statement is used to read data items from the input file and
assign them to integer, real or char variables.
Syntax readln (input variables)
The difference between read and readln is that readln statement causes the next (not the current
read or readln statement to begin by reading a new line of data, where as the read statement will
allow the next read or readln statement to begin on the same line.
Example
Readln(a)

(c) The write statement

The write statement is used to write data items to the output file.
Syntax write (output variables)
The output data items can be strings, numerical, constants or the values of the variables or
expressions. They may be type integer, real, char, or Boolean. Each string must be enclosed
within apostrophes)
Examples
Write(‘X’,x);
Write(‘sum ‘,a+b);

(d) The writeln statement

The writeln statement is identical to the write statement, except that the writeln statement
results in an end of line designation being written after the last data item. Therefore any
subsequent write or writeln statement will begin anew line of output.
Syntax
Writeln(output data items)
Where the output data item can be string numerical constants or the values or variables or
expressions of type integer, real char or boolen.

10

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

THE EOLN AND EOF FUNCTIONS

Pascal includes two standard functions EOLN and EOF that are useful where reading input data.
EOLN returns the Boolean value true if an end-of-designation has been detected on the line
being read otherwise it returns the value false.
The EOF function is often used to detect the end of an input file(i.e. are end of file
designation). This function returns the Boolean value true when an end-of-file designation has
been detected.

CONTROL STRUCTURES
SELECTION

The If Structure
The if structure is a conditional control structure that allows some action to be taken only. If
agiven logical condition has a specified value(either true or false ). This structure has two
different forms.
Syntax
If Boolean expression then
Statement
The statement part of the structure will be executed if and only if the boolean expression is true.
If the boolean statement is false, then the statement part will be ignored.
Examples

(i) If count <=100 then

Count:=count+1;
(ii) If tag =’*’ then
Begin
Writeln(accountno);
Credit :=0
End
The second form of the If structure is
If boolean expression then
Statement1
Else
Statement2
This is frequently referred to as the IF-THEN ELSE STRUCTURE. In this case statement 1 will
be executed if the boolean expression is ture; otherwise statement 2 will be executed. Individual
statement may be either simple or structured and are often compound statements.
Semi colons should not appear in an IF- THEN- ELSE structure except as separators within a
compound statement. Beginners sometimes make the mistake of placing a semicolon before the
keyword ELSE. This should be a voided as it will result in a compilation error.
Examples

IF status=’s’ THEN

11

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

Tax:+0.2*pay
ELSE
Tax:=0.14 *pay;

IF circle THEN
BEGIN
Readln(radius);
Area:=3.14*sgr(radius);
Writeln(‘area of cicle=’,area)
END
ELSE
BEGIN
Readln(lenth,width);
Area:=length*width;
Writeln(‘area of rectangle=’,area)
END;
NB
The IF statement is used in conjunction with boolean expressions, the value of which is either
true or false.

Nested Selection
When if statement are embedded one another they are said to be nested. If is
recommended that each IF-THEN- ELSE. Statement is terminated with the comment {endif}.
The most general form of nested loops

If Boolean expression 1 then

If boolean expression 2 then
Statement 1
Else
Statement 2
Else if boolean expression 3 then
Statement 3
Else
Statement 4
Where Boolean expression 1 Boolean expression 2 Boolean expression 3 represent expressions
and Statement 1 , Statement 2, Statement 3, Statement 4 represents statements.

The case structure

The CASE structure is a conditional control that allows some particular group of statements to
be chosen from several available to groups
The general form CASE structure

12

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

CASE EXPRESSION of
CASE Labell list 1 : Statement 1
CASE Labell list 2 : Statement 2
CASE Labell list 3 : Statement 3
.
.
.
CASE Labell list n : Statement n
Else
END;
The expression can be any simple type expression other than real. It often takes the form of a
single simple type variable. Each of the case labels represents one of the permissible values of
the expressions. Thus if the expressions is of type integer, the case labels would represents
integer values that fall within the permissible range. The statement can be either simple or
structure.
Example1
CASE choice OF
‘R’: writeln((‘RED’);
‘B’: Writeln(‘BLUE’);
‘W’:writeln(‘WHITE’);
ELSE
Writeln(‘BLACK’);
END;
Example2
CASE trunc(x/10) OF
1:y:=y+5;
3,5: y:=y-2
6: y:=2*(y+1)
2,4:;
9:y:=0
END;
Example 3

CASE operator OF
‘+’: Result:=a+b;
‘-’: Result:=a-b;
‘*’: Result:=a*b;
‘/’: Result:=a/b;
Else
Writeln(‘Error operator not value’);
END;

13

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

REPETITION CONTROL STRUCTURES

In writing computer programs it is often necessary to repeat part of a program a number of times.
This is achieved through the use of repetition control structures.

The While – Do Structure

The WHILE- DO structure is a repetitive control structure that is used to carry out conditional
looping. The general format of this structure is

WHILE boolean expression DO

Statements
The staeemnt part of the structure will be executed repeatedly as long as the boolean expression
rmains true. This statement can be simple or structured.
Example
Digit:=1;
WHILE digit <=20 DO
BEGIN
Writeln(digit)
Digit:=digit+1;
END;
Where digit is assumed to be an integer type variable. We therefore begin with a value of digit 1
we proceed to write out the current value of the digit increase it‟s value by 1 then repeat the
cycle. This process is continued as long as (i.e. while) the value assigned to digit does not exceed
20.
If we want to determine the sum of the first n digit where n is a known integer type variable.
Sum:=0;
Digit:= 1;
While digit<=n do
Begin
Sum:=sum+digit;
Digit:=succ(digit);
End;

The Repeat – Until Structure

Is a repetitive control structure that is used to carryout conditional looping. The general form or
syntax i
REPEAT
Sequence of statements
UNTIL boolean expression
The sequence of statement will be executed repeatedly until the boolean expression becomes
true. Note that the sequence of statements will always be executed at least once. NOTE also that
REPEAT – UNTIL does not use begin and end statements. REPEAT AND UNTIL acts as the
brackets that indicate the beginning and ending.
Example

14

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

digit :=1;
REPEAT
Writeln(digit);
Digit:=digit+1;
UNTIL DIGIT>20;

The For Structure

Is used to carryout unconditional looping I Pascal. This structure allows action to be repeated a
specified number of times. The syntax is
FOR control variable: =value1 to value 2 DO
Statements
The statement part can be simple or structured. This statement will be executed for each several
consecutive values assigned to the control variables. The number of values assigned to the
control variable therefore determines the number of times the statement will be executed. The
control variable must be simple type variable of any type other than real.
The statement will be executed (valu2-value1+1) times
Example
BEGIN
WRITELN(‘input hourly rate pay=>’);
READLN(rateofpay)
FOR counter:= 1 to 5 DO
Begin
Writeln(‘Input a number of hours=>’);
Read(hoursworked);
Grosspay:=hoursworked*rateofpay
Writeln(‘Gross weekly wage is’,grosspay);
END
{EndFor}

When the statement FOR counter := 1 to 5 D is executed, counter is initially set to 1 after the
initial executed of the code between BEGIN and END; the computer increase the value of the
counter by 1 and tests whether the new value of the counter ha exceeded the final value of 5.
Example 2
FOR digit:= 1 to 20 Do
Writeln(digit)
This second form of FOR structure is similar to the first except for the use of the key word
DOWNTO in the place of TO thus FOR structure can be written as

FOR control variable: =value1 DOWNTO value 2 DO

Statement;
This structure is the same as the first one except that the control variable is evaluated backward
rather than forward. The control variable if integer will decrease by 1 example

15

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

FOR i:= 0 to DOWNTO -12 DO

Begin
Z:=2*i+5
Writeln(„i:=‟,I,‟z= „,z)
End;

The Goto Statement

The GOTO statement is a simple type statement that is used to alter the sequence of a program
execution by transferring control (i.e. by jumping) to same remote part of the program. The form
of the GOTO statement is
GOTO statement label
Where statement label represents a positive integer not greater than 9999
Example
GOTO 100;
If flag then
GOTO 900;

If sum>= 1000 then

Begin
Writeln(sum);
GOTO 35;
End;

Each statement label must be declared before it can be utilized within a program (Remember
Label declaration must preceed the constant and variables declaration)

Example
PROGRAM sample;
LABEL 100, 200,300;
CONST factor=0.5;
Var a,b,c:Real ;
Labeled statements are written in the form
Statement label : statement
Example
10: readln(a,b,c)
20: For counter :=1 to n DO
Begin
.
.
End

A program may contain several different GOTO statements that transfer control to the same
palce (i.e. to the same remote statement) within the program.
Example
Program sample(input,output);

16

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

LABEL 10;20;
Var…..
BEGIN
.
.
.
10: READLN(A,B,C);
.
.
IF A<-0 then
GOTO 20;
.
.
GOTO 10
.
.
IF flag THEN
GOTO 20
20: WRITELN (X,Y,Z);
.
.
.
.
END

In general program of this type must be avoided. Some care must be exercised when using
GOTO statement. Control can be transferred out of or within a compound statements and control
can be transferred to the beginning of a compound statement. However control cannot be
transferred into compound statement. Moreover if control is transferred internally to the END of
a compound statement (i.e. if the keyword End is labeled) then the label must be preceded by an
empty (null) statement. This is accomplished by placing a semicolon after the statement that
proceeds END ;
Example

PROCEDURE AND FUNCTIONS

PROCEDURE
A procedure is a self – contained program structure that is included within a Pascal
program. In other programming languages this type of structure is known as subroutine. A
procedure may be referenced simply by writing the procedure name followed by an optional list
of parameters. The parameters must be enclosed in parentheses and if there are more than one
they are separated by commas
When a procedure is referenced, control is automatically transferred to the beginning of
the procedure. The action statements within the procedure are then executed taking into account

17

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

any special declaration that are unique to the procedure. When all action statements have been
executed control is immediately after the procedure reference.
Each procedure has it‟s own header and block. The header is written as

PROCEDURE name if formal parameters are inclusive then

PROCEDURE name(formal parameters)

The block consists of declaration part (which is local to the procedure) and a group of
action statements. A procedure can be thought of a special type of Pascal program that is
embedded within anther Pascal program
Consider a program used to determine a lager among 3 integers using a procedure
PROGRAM numbers(input,output)
{program to find the largest no from 3 numbers}
{the program is terminated by the integer type}
VAR a,b,c: integer;
PROCEDURE maximum;
(*This procedure find the largest of the 3 quantities*)
VAR max : integer;
BEGIN
IF a>b THEN
Max:=a
ELSE
Max:=b;
IF c> Max THEN
max:=c;
Writeln(‘The maximum number is ‘,max);
END;

BEGIN(*The main Block*)

Writeln(‘Enter the Three integers’);
Readln(a,b,c);
WHILE A<>) DO
BEGIN
Maxmum{The procedure calling}
Readln(a,b,c);
END;
END.
In the example above a,b,c are global variables and max is a local variable. The first line of a
procedure MUST contain the keyword PROCEDURE similar to program header.
Note: variables a,b,c are declared outside of this procedure and are therefore global to the
procedure. This can be utilized both within and outside the procedure. However max is declared
within the procedure. Thus max is local to the procedure and cannot be utilized elsewhere. A
procedure can be declared within another procedure.

18

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

PARAMETERS
The use of parameters offers a better approach to the exchange of information between a
procedure and its referenced point. Each data item is transferred between actual parameters
which is included within the procedure reference and corresponding formal parameter which is
defined within the procedure itself. When the procedure is accessed the actual parameters replace
the formal parameters thus creating an information exchange mechanism between the procedure
and it‟s reference point
Example

PROGRAM sample([Link]);
VAR a,b,c: Real;
PROCEDURE flush(x,y:real);
Begin
.
.
(*Process the values x,and y*)
.
.
End
Begin(*Main program action statements*)
.
.
.
Flush(a,b,);
.
.
Flush(c,d);
.
.
.
End

X,y – Formal parameters within the procedure . The first procedure reference causes the values
of the actual parameters a and b to be transferred to the formal parameters x and y. this process is
then repeated in the second. This process is then repeated in the second procedure statement this
time transferring the values of c and d to x and y. the values. The values of c and d are thus
passed to flash where they are processed accordingly.
The following rules must be observed when using parameters
1. The number of actual parameter in the procedure reference must be same as the number
of formal parameters in the procedure definitions.
2. Each actual parameter must same type as its corresponding formal parameter.
3. Each actual parameter must be in a manner which is consistent with sits corresponding
formal parameter as determined by the class of formal parameter.

19

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

TYPES OF PARAMETERS

(a) VALUE PARAMETERS passing a parameter by value

Value parameter can best thought of as input parameter for their respective procedures. The use
of actual parameter involves a transfer of value rather than an actual parameter substitution. Thus
when information is transferred between an actual parameter and a value parameter, the value of
the actual parameter is assigned to the value parameter. This value can then be processed within
the procedure (by refereeing to the value parameter) value that are represented by parameter
cannot however be transferred in the opposite direction i.e. from the procedure to the calling
portion of the program. This is why value parameters are regarded as input parameters. Value
parameters are very simply to use. They are declared by simply including their names and
corresponding data types within the procedure header, without any prefix (such as var). It is the
absence of such prefix that automatically identifiers this class of parameters.

(b) VARIABLE PARAMETERS passing a parameter by reference

In many applications, information must be transferred in both directions between the procedure
and the procedure reference. In other words, the procedure must be able to accommodate both
input from and output to the calling block. Variable parameters are generally used is such
situations. When a procedure containing a variable is accessed an actual parameter in the
procedure reference is substituted for the formal parameter within a procedure itself. Thus the
actual parameter will be utilized during the execution of the procedure. These contrasts with the
use of the value parameter where the value of the actual parameters is assigned to the formal
parameter (Note the distinction between Assignment and substitution). It is substitution process
that allows a two way transfer of information between the procedure reference and the procedure
itself. It should be pointed out that only variable can be substituted for another variable. Thus the
actual parameters that are substituted for variable parameters must themselves be variables. They
cannot be constants or expression. Another consequence of the substitution process is the fact
that any change in the procedure will also change the value of the corresponding actual
parameter outside the procedure. Thus variable parameters can affect a program globally, even
though their scope is local to the procedure within which they are declared.

FUNCTIONS
A function is a self contained program structure similar to a procedure, however a function
is used to return a single simple –type value to its reference point.
The function itself consists of a function header and a block.
General form/syntax
FUNCTION name; type or
FUNCTION name(formal parameters): type

Example
Program factorial;
(* this program uses a function to calculate a factorial of a given integer*)
Var x:integer;
FUNCTION factorial(n:integer):integer;

20

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

(*calculate the factotial of n*)

Var factor, product: integer
Begin
If n<=1 then
Factorial :=1
Else
Begin
Product :=1;
For factor := 1 to n do
Product :=product*factor;
Factorial:=product
End;
Begin(*the main program*)
Write(‘Enter a positive integer:’);
Readln(x);
Writeln((‘X=’,x,’ X!=’,factorial(x));
End.

NB 1: A procedure has the following characteristics

1. Procedure is accessed by a simple statement consisting of the procedure name followed
by an optional list of parameters
2. The parameters may represents information supplied to the procedure or under certain
condition, information returned by the procedure.
3. Any number of data items can be transferred between a procedure and its reference point.

NB 2: A function has the following characteristics

1. A function is accessed by specifying it‟s name within name within an expression as
though it were ordinary variable followed by an optional list of parameters.
2. The function name can be followed by an optional list of parameters. These parameters
are used only to transfer information to the function from it‟s reference point.
3. The function will return a single data item. These data item will be represented by the
function name itself.
4. A function must be of the correct data item for the expression in which it is accessed.

21

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

USER DEFINED SIMPLE TYPE DATA

They are data types which are designed by the programmer to meet special purpose. They are of
two types
i.) Enumerated
ii.) Subrange

a) Enumerated type data

Consists of an ordered sequence of identifiers, where each identifier is interpreted as an
individual data item. These data items will collectively be associated with a particular name
which serves to identify the data type. The association between the name of the data type and
individual data items is established bt a type definition.

Type name = (data item1, data item2 ,….., data item 2);
Where name is the name of the enumerated data type and data item1 data item2 are actual data
items.
Example1
Type day =(Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday)
Var offdays:day;

Note data items are enclosed in parenthesis and separated by commas.

Example 2
type day =(sun, mon, tue, wed, thu, fri, sat);

Since enumerated type data are defined in an ordered sequence, relational operators may be
applied to them to form Boolean expression. Also the standard function pre and succ may be
used to determine which data items precede or succeed any data item
using example 2 above

Expression Value
Sun< tue True
Wed >= sat False
Mon <> fri True
Pred(fri)= thu True
Succ(fri)=sat True
Succ(tue)<> pred(thu) False

22

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

b) Subrange
A sub-range refers to some portion of the original range of an ordered simple data. Sub-range
type are the data items that fall within this sub-range, thus forming a subset contiguous ordered
data. The original data is referred to as the host data type.
The sub range concept can be applied to any set of ordered simple data. This includes previously
defined enumerated data as well as three of the standard types i.e integer, char, Boolean.
The general form
Type name first data item.. last data item
Where
Name is the name of the sub-range data type .
First data item is the first of the ordered items within the subrange
Last data item is the las of the ordered data items

Examples
type day =(sun, mon, tue, wed, thu, fri, sat);
weekdays =mon..fri.
month =1..31;
caps =‟a‟..‟z‟;
var workdays,holidays: weekdays;
dayofthemonth: month;
hoursworked: 1..24;
grosspay,netpay: real;
employment: 1..999

c) Utilizing User Defined Data Type

Once enumerated and subrange data types have been defined, they can be used just as other
simple data items are used within apascal program this includes their use as control variables in
FOR and Case examples
for workkdays : mon to fri do
begin
writeln(workdays);
……
…….
end;

case workdays of
mon: writeln(„the first work day‟);
tue: writeln(„the secondwork day‟);
wed: writeln(„the third work day‟);
thu: writeln(„the fourth work day‟);

23

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

fri: writeln(„the fifth work day‟);

end;

24

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

ARRAYS
Is a structured type data which is referred to by a single identifier. In many situations sets of data
items such as set of examination for a class may be conveniently arranged in to a sequence. An
array becomes easier to use in this case. Individual data items in an array are often called
elements.
There are three types of arrays
a) One dimensional array
b) Two dimensional array
c) Multi dimensional array

a) One dimensional array

it can be thought of as a list of data items, all of the same type , that they are collectively
referred to by the same name. Each individual array element (i.e each of the data items) can be
referred to by specifying the array name followed by an index, enclosed in brackets. The general
expression of an array is

List[1]
List[2]
.
List = .
.list[n]

The easier way to defined are array is to include it in a variable declaration

Var array name: array [index type] of type

The index type can be ordinal simple (i.e integer, char, Boolean or enumerated or a
subrange. The array it self can be of any type including structured types. Examples of
declarations
i). VAR List : ARRAY[1..100] OF Real;
ii). Type index= 1..100;
VAR List: ARRAY [index] of Real;
Individual array elements can be used in expressions, assignment statements, read
and write statements as though they are ordinary simple type variables. An array
element must be written sa the array name followed by an appropriate index value
enclosed in square brackets

b) Two Dimensional Array

Can be thought of as a table of data items consisting of rows and columns. Is a repetition of one
dimension array. The structure can be thought of as a matrix or grid structure. The first
dimension might refer to the row number and the second dimension to the column number

25

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

table[1,1] table[1,2] ….. table[1,n]

table[2,1] table[2,2] ….. table[2,n]
table[3,1] table[3,2] ….. table[3,n]
. . .
table = . . .
. . .
. . .
. . .
. . .
table[m,1] table[m,2] ….. table[m,n]

The general expression

VAR array name : array [index 1 type, index 2 type ] of type
The index types can be ordinal, simple types(i.e integer char, boolen or enumerated) or
subranges. The array element must all be of the same type though they can be of any type.
Example of declarations
i.) Var table: array[1..60,1..150] of real;
ii.) Type index=1..60;
Index2=1..150;
Var: table :array [index1,index2] of real
iii.) Const limit1=60;
Limit2=150;
Type index1=1..limit1;
Index2=1..limit2;
Var table: array [index1,index2] of real
Example
program marks(input,output);
(*Program to enter values in a two dimensional array
and output*)
var
a: array [1..6,1..4] of integer;
k,i:integer;
begin
for i:= 1 to 6 do
begin
for k := 1 to 4 do
begin

26

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

writeln('Enter the for student ',i);

read(a[i,k]);
end;
end;
for i:= 1 to 6 do
begin
writeln;
for k := 1 to 4 do
begin
write(a[i,k],' ');
end;
end;
end.

c) Multi dimension arrays

A three dimension array might be thought of as a collection of two dimensional array (repetition)
afour dimension array might be thought of as a repetition of a three dimensional array etc .
regardless of its dimension, an array always consists of a collection of data items of the same
type.
Examples
i.) Type twod= array[1..10,1..5] of integer;
Var threed:array[1..4] of twod;
ii.) Type threed= array[1..10,1..5,1..10] of integer;
Var fourd: array [1..4] of threed;
The method of access to the arrays will be through their respective indices for example
Threed[2,2,4]:=20;
Readln(threed[1,8,3]);
Writeln(foud[3,2,8,4]);

d)Packed arrays
some types of arrays can be defined so that they can utilize the computer‟s memory more
efficiently by “packing” the data items close together. This feature allows a greater quantity of
information to be stored in a given amount of memory.
Example
Var list : packed array[1..4] of char
This feature is most effective with array elements of type char, boolen or enumerated or with
sub range type data. Storage economy gained by packing may offset by loss of computing speed.

27

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

SORTING
Sorting is the process of rearranging an initially unordered sequence of records until they are
ordered with respect to all of or that part of each record designated as its key. Usually desired
result is that the records be placed in ascending order.
At least five considerations may influence the choice of an internal sorting algorithm:
1. Running time: How long does it take to sort n records and by what factor does this time
increase ib order to sort 2n records?
2. Memory space: Do main memory limitations force choice of an algorithm that sorts “in
place”(only one or two record spaces are needed beyond the space needed to hold n
records), or are there an additional n record spaces available beyond the space needed to
hold the data to be sorted?
3. Initial order: are the records known to be already ordered with just a few exceptions?.
This is not the usual situation algorithm may well be one that is not at all efficient when
the initial order of the records is essentially random.
4. Key range: Do record keys span a very large range or possibly only a very restricted
range (such as integers 0 to 999). Certain algorithm applicable to keys of narrow range
are not feasible for keys that span a large range.
5. Programming language: For reasons of availability, must a particular programming
language be used if so, does that language support recursion since many of the most
efficient internal sorting algorithms are most naturally expressed recursively.

The following sorting algorithms will be discussed

a) Selection sort
b) Bubble sort
c) Insertion sort
d) Quick sort
e) Shell sort
f) Merge sort
g) Binary sort

a) Selection sort
Selection sort involves looking thro all n records to find the one with smallest key, then thro the
remaining n-1 records a to find the one of the next smallest key, etc. by exchanging each record
of successively smaller key with appropriate record at the top of the unsorted sequence of
records, the records can be sorted in place, the length of the sorted sequence at the top growing
gradually longer as the length of the unsorted sequence at the bottom shrinks to zero. Selection
sort is slow. Selection sort is suitable for few records. Another advantage of this algorithm is that
records of successively larger key are identified on one by one, so that output of the sorted list
can proceed virtually in parallel with the sort itself.
Example
APASCAL PROGRAM FOR SELECTION SORT.
program sorting;
var k,i,max,maxpos,temp:integer;

28

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

list:array[1..6]of integer;
begin
writeln(' enter numbers to sort');
for i :=1 to 6 do
read(list[i]);
for k:= 1 to 5 do
begin
max:=list[k];
maxpos:=k;
for i:=k+1 to 6 do
if list[i]>max then
begin
max:=list[i];
maxpos:=i;
end;
temp:=list[k];
list [k] := list[maxpos];
list[maxpos]:=temp;

end;
for i :=1 to 6 do
write(list [i], ' ');
end.

b) Bubble sort
Bubble sort is is based on obvious idea on the simplistic notion that if two adjacent records are
out of order they should be exchanged. If this is done to successive (overlapped) record pairs,
from the first thro the record pair that starts at the (n-1)st position, the original list will not
necessarily yet be sorted, but one can be sure that the record of the largest key (assuming an
ascending order sort) will have reached the end of the list. Then by repeating the process n-2
more times, the entire list is certain to be sorted. Successive phases of the sort are called passes.
Bubble sort is also known as exchange sort. Like selection sort this algorithm is very slow.

The idea of bubble sort is just comparing all the data. The first data is compared to the second, to
the third, and so on until the end of the data. Then the second data compared to the third, to the
fourth, so on. Then the third data to the fourth and so on ... and so on.

Why it is called as the Bubble sort. It is because that the comparison and the swapping make the
desired data to gradually come up like a bubble. Example : Suppose we have data like this

29

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

5 3 8 4 1 7 6 2 (unsorted)

Follow the algorithm -- i.e. comparing the first and the second data : 5 and 3. 5 is greater than 3,
hence it must be swapped out

3 5 8 4 1 7 6 2 (1st step)

Then the first and the third. Since 3 is smaller than 8, no swapping is necessary. Then the first
and the fourth : No swapping either. The first and the fifth -- since 1 is smaller than 3, it must be
swapped :

1 5 8 4 3 7 6 2 (4th step)

And so on, till the end of data, the sequence remains the same. Then the second with the third --
no changes this time. The second with the fourth. Change must be done :

14853762
then becomes :
13854762

And so on :

1 2 8 5 4 7 6 3
1 2 5 8 4 7 6 3
1 2 4 8 5 7 6 3
1 2 3 8 5 7 6 4
1 2 3 5 8 7 6 4
1 2 3 4 8 7 6 5
1 2 3 4 7 8 6 5
1 2 3 4 6 8 7 5
1 2 3 4 5 8 7 6
1 2 3 4 5 7 8 6
12345687

Finally, sorted : 1 2 3 4 5 6 7 8

You see that smaller data comes up like bubble and bigger data sank down gradually, as you may
note the 8. That's why this method is called bubble sort.
Example
A PASCAL PROGRAM FOR BUBBLE SORTING
program bubblesort(input,output);
{program that uses bubble sort to sort numbers in an
array}
const maxnum=8;

30

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

var
sort:array[1..maxnum]of integer;
sorted:boolean;
i,pass,temp:integer;
begin
writeln('enter the number to be sorted');
for i:=1 to maxnum do
read(sort[i]);
writeln('unsorted data');
for i:=1 to maxnum do
write(sort[i],' ');writeln;writeln;
begin
pass:=1;
repeat
sorted:=true;
for i:=1 to maxnum-pass do
begin
sorted:=false;
if sort[i] > sort[i+1] then
begin
temp:=sort[i];
sort[i]:=sort[i+1];
sort[i+1]:=temp;
end;
end;
pass:=pass+1;
until sorted;

writeln;
writeln('sorted data is');
for i :=1 to maxnum do
write(sort[i],' ');
readln;
end;
readln;
end.

31

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

c) Insertion Sort
The insertion sort algorithm is likely to occur to anyone who is playing cards by simply holding
them in the hand and inserting them one by one into the proper position in the stack or hand of
already sorted items. In the computer version room has to be made for insertion of the records at
the top of the list necessitating movements of all records in the partially ordered list down by one
position. But whenever a record is encountered whose key is larger than that of the last one in the
partially ordered list, it merely needs to be appended to the list. Insertion sort is done using the
same list by letting the partially sorted list at the top of the combined sequences gradually
displace the diminishing list of the unsorted records stored directly underneath.
Procedure InsertionSort(varA: list;n:integer);
{ sorts the n numbers of A, where type list = array[1..
limit]}
Var I,j,k,t,: integer;
Begin
For i:= 2 to n do
If A[i] < A[1] then
Begin
t:=A[i];
A[i]=A[1];
A[1]:=t;
End
For j:=1 to n-1 do
Begin
T:=A[j+1];
K:=j;
While A[k] >t do
Begin
A[k+1]:=A[k];
K:=k-1;
End;
A[k+1]:=t
End
end

d) Quick Sort
This is a fast sorting algorithm that sorts a list of n elements in O(nlogn) time. The method is
used as follows. One element is chosen as the partitioning element (central value). The elements
are partitioned into two sub list. Exchanges are performed so that all the elements to one side are
smaller than or equal to it and all the elements on the other side are greater the or equal to it.(One
contains the elements that are smaller than the partitioning element and the other contains

32

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

element larger than the partitioning element.). This should produce two lists of equal length.
Each of this is partially sorted in a similar way. In turn each of the four lists are sorted in similar
way and so on. It is sometimes referred to as partition exchange sort
Example
Program quicksort(input,output);
Const max=1001;
Var
A:array[1..max] of integer;
I:=integer;
N: integer;

Procedure quicksort(l,r:integer);
Var I, j, piv,t:integer;
Begin
If l<r then
Begin
I:=l+1;
J:=r;
Piv:=A[l];
Repeat
While A[i] <=piv do
I:=i+1;
While A[i] > piv do
J:=j-1;
If i<j then {exchange items pointed to by I
and j}
begin
t:=A[i];
A[i]:=a[j];
A[j]:=t;
End;
Until i>j;
[now two final replacements finish a partition]
A[l]:=A[j];
A[j]:=piv;
Quicksort(l,j-1);
Quicksort(j+1,r);
End;

33

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

End;
Begin
Write(„Enter number of integers to be sorted‟);
Readln(n);
For i:= 1 to n do
Read(a[i]);
A[n+1]:=maxint;
Quicksort(1;n)
For i:= 1 to n do
Write(A[i]:5);
Writeln;
End.

e) Merge Sort
Merging is an information processing technique similar to that of sorting that makes no sense
except when applied to two (or more) lits that are already separately in order. To merge such lists
then means to intersperse their elements to form one overall output liost that is entirely in order.
The merging algorithm can be stated in pseudocode as:
While{still more unmerged items in either list} do
Begin
If A is empty take the next item from B, else
If B is empty take the next item from A, else
Take the smaller of the two at the heads of list A and B
End;
In the course of being merged, each number in each list is processed only once. This means that
the running time needed to merge two lists of size m and n will be proportional to m+n.

Program merge(input,output);
{program that reads in two lists ordered numbers A and
B and merges them into C}
Const al=7;
Bl=9;
Cl=16;
Var A: array[1..al] of real;
B: array[1..bl] of real;
C: array[1..cl] of real;
Begin
For i=:= 1 to al do
Read(A[i]);

34

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

For j:=1 to bl do
Read(B[j]);
I:=1; j:=1; k:=1;
While (i<=al) and (j<bl) do
If A[i] <B[j] then
Begin
C[k]:= A[i];
I:=i+1;
K:=k+1;
End
Else
begin
C[k]:= B[j];
J:=j+1;
K:=k+1;
End;
While i<=al do
Begin
C[k] :=a[i];
I:=i+1;
K:=k+1;
End;
While j<=bl do
Begin
C[k] :=a[i];
j:=j+1;
K:=k+1;
End;

Writeln(„ Output of list A‟);

For i:= 1 al do
Write(A[i]:6:0);
Writeln(„ Output of list B‟);
For i:= 1 bl do
Write(B[i]:6:0);

Writeln(„ Output of list C‟);

35

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

For i:= 1 cl do
Write(C[i]:6:0);
End.

f) Shell Sort
This is a sorting algorithm resembles the bubble sort algorithm. The only difference between
them I that in this method successive elements are not compared and exchanged instead,
elements at a distance d are compared and exchanged if the second is smaller than the first.
The initial value of d is in n/2 location where n is the number of elements in the list. After one
iteration is over the value of d is reduces by half. This is continued until the list is sorted. The
sorting order decided by the user is encoded in the variable order.
Example
PASCAL PROGRAM FOR SHELL SORT
program shellsort;
const maxnum=8;
var
shell:array[1..maxnum]of integer;
p1,p2,p3,p4,temp,i,d:integer;
procedure datain;
begin
writeln('input numbers to be sorted');
for i:=1 to maxnum do
readln(shell [i]);
end;
procedure swap;
begin
p3:=p1-d;
p4:=p1;
temp:=shell[p1];
shell[p1]:=shell[p2];
shell[p2]:=temp;
while(p3>0)and(shell[p3]>shell[p4]) do
begin
temp:=shell[p3];
shell[p3]:=shell[p4];
shell[p4]:=temp;
end;
end;

36

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

procedure perform;
begin
repeat
begin
p1:=1;d:=trunc(d/2);
p2:=d+p1;
repeat
if shell [p1]>shell[p2] then
swap;
p1:=p1+1;
p2:=p1+1;
until p2> maxnum;
end;
until d=1;
end;
procedure dataout;
begin
writeln('sorted data is');
for i:=1 to maxnum do
write(shell[i], ' ');
end;
begin(*main block*);
d:=maxnum;
datain;
perform;
dataout;
readln;
end.

SEARCHING
Searching for an element in a list is the process of checking if a specified element is present in
the list and determining the location of the desired element. There are mainly two types of
searching algorithm namely
a) Linear Search
b) Binary Search

a)Linear Search
Is a searching technique also known as sequential search algorithm, given a list the elements are
scanned from the first one till either the required element is found or the list is exhausted. The

37

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

elements do not have to be in any specific order. The advantage of this method is its simplicity
however the method is inefficient when the number of elements is large.
Example
(i) Linear search
program linearsearch(input,output);
var a: array[1..5] of integer;
elem,i,n: integer;
found:boolean;
begin
writeln('enter the number of elements in the array');
readln(n);
for i:= 1 to n do
read(a[i]);
readln;
write('enter the element to be serached for ');
readln(elem);
i:=1;
while (not found) and (i<n) do
begin
if (a[i] = elem) then
found := true;
i:=i+1;
end;
if found then
writeln('element found at position
',i-1:2)
else
writeln('element not found in the
list');
end.

b) Binary Search
Binary search algorithm is used to search for an element in a sorted list. The search is conducted
as follows. The value of the element in the middle of the list is compared with the value of the
element to be searched for. If the middle element is smaller, them the desired element has to be
in lower half of the list. If the middle element is larger, the desired element has to be in the upper
half of its present. The number of elements to be searched is reduced by half in every iteration.
Example
Binary Search

38

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

program binary_search(input,output);
var a :array[1..50] of integer;
elem,low,n,i,mid,high:integer;
begin
writeln('binary_search');
write('enter the number of elements:');
readln(n);
writeln('enter the elements of the vector(sorted:');
for i :=1 to n do
read(a[i]);
readln;
writeln('enter the element to be searched
for');
readln(elem);
low:=1;
high:=n;
mid:=(low+high)div 2;
while((low<high) and (a[mid]<>elem))do
begin
if(a[mid]>elem)then
high:=mid-1
else
if(a[mid]<elem)then
low:=mid+1;
mid:=(low+high)div 2;
end;
if(a[mid]=elem)then
writeln('enter',elem:1,'found at position:',mid)
else
writeln('element',elem:1,'not found');
end.

39

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

DATA STRUCTURES

(a) Sets
In Pascal asset is a collection of ordered data items that are all of the same type. Thus a set may
be a collection of integers or characters or enumerated data items. In order to utilize the set
concept, we must first define a set type. We can then declare set type variables whose individual
values are elements of that set type.

(i) Defining a Set Type

We begin by associating a group of ordered simple, simple data items with a data type using
TYPE defining, as we have done earlier. This data type will be known as the base type. We can
therefore establish the base type as

TYPE base type =(data item1, data item 2, . . . ,data item n)

Or
TYPE base type= first data item .. last data item.

The set type that we wish to define is then introduced in terms of the base type i.e.;

Set type = SET Of base type

Thus, the set type will refer to the same collection of data items sat the base type
Once a set has been defined we can declare a set-type variable in the following manner
VAR set name: set type
Or if several different set-type variables are desired
VAR set name 1, set name 2, . . ., set name n: set type.
Examples 1
TYPE sizes=(small,medium,large);
Shirtsizes= SET Of sizes;
VAR shortsleeve, longsleeve: shirtsizes;

In this example is the base type; consisting of the enumerated data items small, medium and
large. The set type is shirtsizes. Note that shirtsizes is defined in terms of the base type sizes.
Finally, shortsleeve and longsleeve are set type variables of type shirtsizes.

Examples 2
TYPE sizes=(small,medium,large);
Shirtsizes, dresssizes= SET Of sizes;
VAR shortsleeve, longsleeve: shirtsizes;
Shorthem, lonthem : dresssizes;

40

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

We can also define asset type in terms of a standard, ordered simple type (e.g. integer or char) or
subrange of a standard, ordered simple type. In such situations the standard data type or its
subrange becomes the base.
Examples 3
TYPE numbers = SET OF integer;
TYPE digits = SET OF 0..9;
TYPE lowercase = SET OF „a‟..‟z‟;

(ii) Constructing a Set

A set can consist of any number of elements from associated base set. The set is constructed by
writing the individual elements consecutively, enclosed in square brakets and separated by
commas. Thus an individual set will appear as
[set element 1, set element 3, . . . . set element n]
The included elements are known as the members of the set. A set can consists of only one
element, and it is also possible to construct a set that does not contain any element. This is
known as an empty (or null) set. It is written as [].
Example

[small, medium, large]

[medium, large]
[small, large]
[medium]
[]

If some of the set members are consecutive set elements they may be represented as subrange
First consecutive element . . last consecutive element

TYPE sizes=(small,medium,large);
Shirtsizes = SET Of sizes;
VAR shirt, blouse: sizes;

[small . . large]
[shirt]
[shirt,blouse]
[small, medium, large]

Asset element may not be included in a set more than once. It is possible, however that a single
element will indirectly (and perhaps unintentionally) be specified two or more times, particularly
if the set specification includes both explicit set elements and variables( A variable may
represent a set element that has already been specified thus resulting in unwanted duplication.) in
such situations the repeated specifications will be ignored.

41

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

Once a set has been constructed, it can be assigned to asset type variables. This is accomplished
in the usual manner, by writing
Variable name: = [set element 1, set element 2 … set
element n]

It should be understood that the set appearing on the right hand side is regarded as a single-
valued data item. This data item must be of the same set type as the variable to which it is
assigned.

Program sample;
TYPE sizes=(small,medium,large);
Shirtsizes, = SET OF sizes;
VAR shortsleeve, longsleeve: shirtsizes;

Begin
……….
Shortsleeve:=[small,large];
………
Longsleeve:=[small,medium,large];
…………
End.

(iii) Operations with Sets

There are three difference operations that can be carried out with sets, each of which results in
the creation of a new set. We refer to the resultant of this operation (i.e., the newly created sets)
as the union, the intersection and the set difference of the original two sets, respectively.
Each set operation requires two operands(i.e, two set) of the same type. The resultant will then
be of the same type as the operands. The union of the two sets is a new set that contains all the
members of the original two sets. The + operator is used to indicate this operation as illustrated
below

Program sample;
TYPE sizes=(small,medium,large);
Shirtsizes, = SET OF sizes;
VAR shortsleeve, longsleeve: shirtsizes;

Begin
……….
Shortsleeve:=[small]+[large];
………
Longsleeve:=[small,medium]+[small,large];

42

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

…………
End.
The intersection of two sets is set whose members are common to both of the original sets. we
use the operator * to denote this operation.

Program sample;
TYPE sizes=(small,medium,large);
Shirtsizes, = SET OF sizes;
VAR shortsleeve, longsleeve: shirtsizes;

Begin
……….
Shortsleeve:=[small, medium]*[medium ,large];
………
Longsleeve:=[small]+[medium, large];
…………
End.
The set difference of two sets is set whose members are in the first set but not in the second.
This operation is denoted by the operator – as in the example below.
Program sample;
TYPE sizes=(small,medium,large);
Shirtsizes, = SET OF sizes;
VAR shortsleeve, longsleeve: shirtsizes;

Begin
……….
Shortsleeve:=[small, medium]-[small ,large];
………
Longsleeve:=[small, medium, large]- [medium] ;
…………
End.

(b) Stacks

(i) Introduction
A stack is an abstract data type consisting of sequence of items, in which the items are added and
removed from one end only. Another way of describing a stack is that the last item put in the
stack will be the first one to be taken out of the stack. Consequently, a stack is referred to as
“Last In First Out (LIFO)”, structure. For example if the integers 10, 20, 30, 40 and 50 are put in
a stack, they would come off the stack in the order 50, 40, 30, 20, and 10.

43

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

(ii) Operations of stack

Two main operations are involved in the use of stack. The operations of adding an item to the
stack is known as “pushing” the item on to the stack and the operation opposite pushing on to the
stack is a called “popping” the stack.
Push()
Pop()
Push() procedure is used to add new elements to the top of the stack where as the pop()
procedure is used to remove an element from the stack. Initially an empty stack must be created
whenever there is attempt to push an element into a stack, it must be checked whether any space
is there to accommodate new elements in the stack or not. While attempting to user popping
operation it must be checked whether any element is there which is to be popped out.
For example
Stack operation contents
Push(a) a
Push(b) ba
Push(c) cba
Push(d) dcba
Pop() cba d is removed
Pop() ba c is removed
Push(e) eba

A simple stack can be created using an array. Stack elements are integers but they can be float,
char, structures etc.

Algorithm for push() operation

The push() is an operation for storing an item in a stack. If s is attack and x is and item to be
pushed on to s, we will use push(s,x) to denote the process by which thee value denoted by x is
added to the top of the stack s. before pushing an item into a stack, it is essential to check
whether enough space is there to accommodate the item. Otherwise, an appropriate error
message ,stack full‟ will be displayed.
The following procedure shows how to realize push() operation for a stack:

procedure push(var s:stack; var spointer:integer;

item,max:intger);
begin
if spointer < max then
begin
spointer:=spoiter+1;
s[spointer]:=item;
end
else

44

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

writeln(„stack full‟);
end;
Algorithm for Pop() Operation

The pop() is an operation in which the top most item of a stack is to be removed or delete.
Popping the stack reference the value from the top of the stack. If s is a stack and v is a variable
of the type of element in the stack, pop(s,v) will put the value on the top of the stack s in the
variable v. pop also makes the stack one item shorter. Before one attempts to pop() an item from
the stack, it is essential to check whether any item is stored in the stack. If not, he stack is empty
and nothing can be popped ands hence an error message „stack is empty‟ will be displayed.
The following procedure shows how to realize pop() operation for a stack:

procedure pop(var s:stack; var item, spointer:integer);

begin
if spointer >0 then
begin
item:=s[spointer];
spointer:=spoiter-1;
end
else
writeln(„stack empty‟);
end;

(c) Queues

(i) Introduction
A queue is sequence of data items for which additions and deletions are possible only at an end
of the sequence. The difference between a queue and stack is that the addition and deletion of
items to a queue are at opposite ends whereas the addition and deletion of items in stack are done
at the same end.
Stacks are useful in problems that reverse the order of items and queues are useful in problems
that preserve the order of the items. A queue is an ordered group of items in which new elements
are added at one end called the rear and elements are removed at the other end called the front.
Queues are also known as FIFO-, First In First Out‟ structure. The term front will denote the end
of the queue from which items are removed and rear will denote the end at which items are
added.

(ii) Operations on Queue

The main operations on aqueue are additions of items of the queue and removal (deletiond) of
items from the queue

45

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

qstore()
qdelete()

The qstore() procedure is used to add new elements to the queue while qdelete() procedure is
used to remove an item from the queue.

For example
Stack operation contents
qstore(a) a
qstore(b) ba
qstore(c) cba
qstore(d) dcba
qdelete() dcb a is removed
qdelete() dc b is removed
qstore(e) edc

Algorithm for qstore()

The qstore() is an operation in which an item is stored in the queue. The end to which additions
are made is the rear of the queue. Before one attempts to store an item in to a queue, it essential
to check whether enough space is there to accommodate the item in the queue or not. If there is
no space in the queue an appropriate error message „queue full‟ is displayed.
The following procedure shows how to realize qstore() operation in a queue
procedure qstore(var q:queue; var rear: integer; item,
max, front :integer);
begin
rear:=rear+1;
if rear >max then
rear:=1;
if front<> rear then
q[rear]:=item
else
begin
writeln(„queue is full‟);
rear:=rear-1;
if rear =0 then
rear:=max;
end;

end;
Algorithm for qdelete()
The qdelete() is an operation in which an item is removed from a queue. Items are removed from
the end, opposite to the end used for addition. The end from which removals are made is the

46

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

front of the queue. Before one attempts to delete an item from the queue, it is essential to check
whether any item has been stored or not. If there is no item in the queue, it is an error to use the
qdelete() procedure and appropriate error message „queue empty‟ will be displayed
The following procedure shows how to realize qdelete () operation in a queue

procedure qstore(var q:queue; var item, front: integer;

max, rear :integer);
begin
if front <> rear then
begin
front:=front+1;
if front > max then
front:=1;
item:= q[front];
writeln(„value =‟,item)
end
else
writeln(„queue empty);
end;

(d) Linked Lists

Linked lists like stacks and queues are linear data structures in which the items are stored and
retrieved linearly in an organized manner like one item after another. A linked list is like a chain
of data items connected by pointers and each item contains a pointer to the address of the next
item.
There are several different kinds of linked structures
a) linear linked lists :In which the components are all linked together in some sequential
manner,
b) Linked list with multiple Pointers: Permitting forward and backward traversal thro‟ the
list.
c) Circular list: Linear list having no beginning and no ending.
d) Trees: in which the components are arranged in a hierarchical structure.

For example the following program segment illustrates how a linear linked list is declared and
connected with another list with the aid of pointer.
type
pointer=^list;
list=record
data:integer;

47

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

next:pointer;
end
var
a,b,c:pointer;
begin
a^.data:=10;
b^.data:=20;
c^.data:=30;
a^.next:=b
b^.next:=c;
c^.next:=nil;
end.

The graphical representation of the above structure is

a b c
10 20 30 nil
next next next
Linked lists are used for example in construction of compilers, operating systems and database
management systems.
Example of a program that demonstrates how a simple linear linked list is working
program selfglist(input,output);
type
pointer=^list;
list=record
data:integer;
next:pointer;
end
var
a,b,c:pointer;
x,y,,z:integer;
begin
a^.data:=10;
b^.data:=20;
c^.data:=30;
a^.next:=b

48

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

b^.next:=c;
c^.next:=nil;
writeln(„contents of the lits‟);
write(„value of „);
x:=a^data;
writeln(„a = „,x);
writeln(„a is linked to b‟);
y:=a^.next^.data;
writeln(„b = „,y);
writeln(„b is linked to c‟);
z:=a^.next^.data;
writeln(„c = „,z);
a^.next^.next^.next:=nil;
end.

Double linked Lists

A linked list that has two links in each of its nodes, with one link pointing to the preceding node
and the other pointing to the succeeding node is called a double linked list. In other words a
double linked list in a data structure has two pointer elements; one pointing to the next element
and the other pointer pointing to the previous element and can traverse the list in either direction.
The declaration of a double linked list structure is:

type
doubleptr=^node
node= record
llink:doubleptr;
value: integer;
rlink:doubleptr;
var
head,tail:doubleptr;

The graphical representation of the double linked list is shown below:

Data = 10

10

Prev next
49

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

Data = 20

20

Prev next

Data = 30

30

Prev next

(e) Binary trees

(i) Introduction
Data structures such as stacks, queues and linked lists are linear organization of data in which
items or components are arranged sequentially, one object after another. On the other hand,
components or items are arranged in hierarchical order then it is called a tree. Tree is more
flexible abstract data type than linear types.
A tree has a finite set of elements called nodes. A tree has a unique node called root. A binary
tree ia a tree whose elements have two nodes such as a left node and a right node. Each left node
contains a number less than the value in the preceding node. Each right node value is greater than
the value in the preceding node. Anode with no branch is called a leaf.
The advantage of a binary tree is that items can be placed in the tree in a sorted manner. Thus the
processes of inserting a node, deleting anode, searching for a node and retrieving information can
be accomplished in a more efficient manner than with a linear linked list. The node above a
given node in a tree is called a parent and the node below a given node in a tree is called a child.
The root is the unique node of a tree without a parent. The node with no child is called a leaf.
The link from a parent node to a child is called a branch. The tree that is part of another tree is
called a subtree.
The declaration of a binary tree is:
type
pointer=^node;
node=record
data:integer;
left:pointer;
right: pointer;
end;

50

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

Binary Tree Traversal

A binary tree is built and searched by moving downwards thro‟ the tree node by node, until an
empty child is reached or anode with a specific item is found. There are several ways to visit
elements of a binary tree. This include inoder, preorder and postorder.

(i) inorder
Inorder traversal is a process of a binary tree in which a node is visited between the traversal of
the node‟s left sub tree and the traversal of the node‟s right sub-tree.
Example
A

C
B
Diagram 1
In the example in ther inorder tree traverse, first the left sub-tree of the root is traversed(B). the
root is then visited(A). then the right sub tree is visited(C).

The following recursive procedure prints the contents of the binary tree in the inorder traversal
method.

Procedure inorder(ptr1:pointer);
(*inorder binary tree traverse*)
Begin
If ptr1<> nil then
Begin
Inorder(ptr1^.left);
Write(ptr1^.data:7);
Inorder(ptr1^.right);
End;
End;

(b) Preorder
In a preorder tree traverse a node is visited before its sub tree are traversed. It first visits the root
node(A), then traverse the left sub tree(B) and then the right sub tree(C).

The following recursive procedure prints the contents of the binary tree in the preorder traversal
method.

51

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

Procedure preorder(ptr1:pointer);
(*preorder binary tree traverse*)

Begin
If ptr1<> nil then
Begin
Write(ptr1^.data:7);
preorder(ptr1^.left);
preorder(ptr1^.right);
End;
End;

(c) postorder
When a postorder traversal on a tree is performed, both the left and the right sub tress are
traversed before the root node is visited. Using the previous diagram 1 the order will be B C A
The following recursive procedure prints the contents of the binary tree in the postorder traversal
method.

Procedure postorder(ptr1:pointer);
(*postorder binary tree traverse*)

Begin
If ptr1<> nil then
Begin
postorder(ptr1^.left);
postorder(ptr1^.right);
Write(ptr1^.data:7);
End;
End;
Example
A program to create a binary tree and to display the contents of the tree using the inorder tree
traversal methods
program binary(input,output);
type
pointer=^node;
node=record
data:integer;
left:pointer;

52

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

right: pointer;
end;
var root:pointer;
item:integer;
i,n:integer;

procedure inorder(ptr1:pointer);
(*inorder binary tree traverse*)
begin
if ptr1<> nil then
begin
inorder(ptr1^.left);
write(ptr1^.data:7);
inorder(ptr1^.right);
end;
end;

procedure buildtree(var bnode:pointer; value:integer);

begin
if bnode=nil then
begin
new(bnode);
bnode^.data:=value;
bnode^.left:=nil;
bnode^.right:=nil
end
else if value <=bnode^.data then
buildtree(bnode^.left,value)
else
buildtree(bnode^.right,value);
end;
begin (*main program*)
root:=nil;
writeln('homany elements ?');
readln(n);
i:=1;
while i<=n do

53

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

begin
writeln('enter a number');
readln(item);
buildtree(root,item);
i:=i+1;
end;
writeln;
writeln('output from the binary tree');
write('using inoreder algorithm');
inorder(root);
end.

RECORDS
A record can be defined as a group of fields made up of different data items. In pascal we refer a
record as a collection of heterogeneous (different) types of data grouped together.. the entire
collection is referred to as a record. The individual components which are called fields or
members can be accessed and processed separately.

a) Defining a record
The general form of a record variable decaration is:
Var record name= record
Field1;
Field2;
.
.
Fieldn
End;
Where field1 represents the first field declaration, field2 represents the second field and sos on.
Each field declaration is written in manner that is similar to an individual variable declaration i.e
field name: type
Where field name is an identifier that represents the name of the field and type is their data type
of the item that will occupy the field. Therefore full declaration would be

Var record name= record

Field name 1: type;
Field name 2: type;
.
.
Field name n: type;

54

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

End;
Example 1
Var customer= RECORD
Custno: integer;
Custtype: char;
Custbalance: real
end

records can also be declared using type definition as in the following example
general form is

type record name= record

Field name 1: type;
Field name 2: type;
.
.
Field name n: type;
End;

Example 2
type account= RECORD
Custno: integer;
Custtype: char;
Custbalance: real
end
var
customer: account;
Individual fields can be associated with user defined types as well as standard data types
Example
type status=(current, overdue, delinquent);
account= RECORD
Custno: integer;
Custtype: char;
Custstatus=status;
Custbalance: real
end
var
customer: account;
or

55

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

type status=(current, overdue, delinquent);

line= ARRAY[1..80] of char;
account= RECORD
custname: line;
Custno: integer;
Custtype: char;
Custstatus=status;
Custbalance: real
End;
var
customer: account;

Example 3
type status=(current, overdue, delinquent);
line= ARRAY[1..80] of char;
date = record
month:1..12;
day: 1..31;
yeay: 1900..2100;
end;
account= RECORD
custname: line;
lastpayment: date;
Custno: integer;
Custtype: char;
Custstatus=status;
Custbalance: real
End;
var
customer: account;

you can declare several records using the same type

e.g
VAR customer, regular: account;

56

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

b) Processing a record

It is possible to assign a record to another record in the course of working using the cost example
for
Customer:= regular;
When processing a field the general form is
[Link]
(Note the period between the two names)
Example 4
Writeln.(„enter the name‟);
Readln([Link]);
[Link] :=1942;

c) The with structure

It is tedious to keep on writing the field designator. If simply use the with structure general form
WITH record name DO statement.
Example 5
TYPE date= RECORD
Month: 1..12
Day: 1..31;
Year:1900..2100
END;
VAR birthday; date
BEGIN
Birthday:month:=5;
[Link]:=13;
[Link]:=1966;
END;
It is easier to write
WITH birthday DO
BEGIN
.Month :=5;.
.day:=13;.
year:=1996:
END;
Using read
WRITELN(„Enter the data‟)
WITH birthday DO
BEGIN

57

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

Read(month);
Read(day);
Read(year);
END;

d) Declaration of records using arrays

You can incorporate arrays in records so that data can be held to a large volume
Example
TYPE account = record
Custname: string;
Custnum: 1…9999;
Custbal :real
END
VAR customer: Array [1…100] of account
USING IN THE PROGRAM
FOR i := 1 to 100 DO
Begin
writeln („Enter the name‟);
Readln (customer[i].custname);
writeln („Enter the number);
Readln (customer[i].custnumb):
END;

USING THE WITH STRUCTURE

FOR i := 1 to 100 DO
Begin
WITH customer[i] do
Begin
writeln („Enter the name‟);
Readln (custname);
writeln („Enter the number);
Readln (custnumb):
End
END;
Example
program emplo(input,output);
(*program to demonstrate use of Type data and Records*)

58

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

type employee= record

name:string[15];
age:integer;
hrs:real;
rate:real;
gross: real;
end;
var empl1: array [1..10] of employee;
i:integer;
begin
for i := 1 to 10 do
writeln('Enter the Name,Age Hours Worked and The Rate');
begin
with empl1[i] do
readln(name,age,hrs,rate);
end;
for i:= 1to 10 do
begin
with empl1[i] do
write(name:15,age:5,hrs:5:0,rate:5:0);
writeln;
end;
end.

Assignment
Write a program that will accept 20 records with the following fields and output then on the
screen.

Name, Admno in a range of 199…12000, class dept and colleges

FILES

a) Introduction

Is a structured type like an array ( ie a collection of data items) unlike the array however, a file
can be stored on a auxiliary storage ( magnetic tape or disk). Thus the file structure allows us to
store information permanently and access that information whenever necessary.

There are two types of files, permanent files and temporary files. Permanent files are maintained
on auxiliary memory device and therefore preserved after the program has completed its

59

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

execution. The contents of such files can be accessed and or modified either by the same
program that creates or by some other program.

Temporary files on the other hand are stored within the computer main memory. A temporary
lost as soon as the program that created the file has completed its execution

b) Defining of a file

The simplest way to define a file is to include the file definition as part of the file- type variable
declaration. The general form is

VAR file name : FILE OF THE TYPE

Where file name is an identifier that represents the name of the file and type refer to the data
type the individual file components

Examples (Valid)
1) VAR symbols : FILE OF CHAR;
2) TYPE table = ARRAY (1..50,1..20) of Real;
VAR Data : FILE of table;
3) TYPE status = (current overdue, deliquescent);
account = RECORD
custname: string;
custno : interger;
custtype: status ;
custbal: real;
END;
VAR customers: file of account ;
4) Account= RECORD
Custname :string;
Custno: integer
Custbal: real
END;
Customer= FILE of account;
VAR oldcustomers, newcutomers : customers

c) Creating a file
The first step in creating a file is to prepare the file for writing. This is accomplished with
the standard procedure REWRITE. Thus we begin by writing
Rewrite(FileName)
If the specified file is being created for the first time the rewrite statement simply establishes the
beginning of the file. If the file already exists then the effect of rewrite statement is to erase all of

60

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

the information within the existing file and establish the beginning of the new file. After the
necessary data items have been assigned to a file buffer, this information is transferred to the file
by means of Write statement.
The WRITE statement is used to write a file component on to a file. The general
expression is
Write (file name,identifier);
Where identifier represents a variable or other identifiers whose value (or values incase of
structured type file buffer) is assigned to the file buffer.
Example
If the declaration of a file is as follows
PROGRAM CREATEFILE(INPUT,OUTPUT,CUSTOMERS);
TYPE ACCOUNT = RECORD
CUSTNAME: STRING;
CUSTNO: REAL;
CUSTBAL: REAL;
CUSTTPAY: REAL;
CUSTPAID: REAL;
END;
VAR CUSTOMERS: FILE OF ACCOUNT;
C:INTEGER;
CUSTREC:ACCOUNT;
Then writing the file customers will be a follows
WITH CUSTREC DO
BEGIN
WRITELN('ENTER CUSTOMER NAME');
READLN(CUSTNAME);
WRITELN('ENTER CUSTOMER NUMBER');
READLN(CUSTNO);
WRITELN('ENTER PAID ');
READLN(CUSTPAID);
CUSTTPAY:=15000;
CUSTBAL:= CUSTTPAY-CUSTPAID;

END;
WRITE(CUSTOMERS,CUSTREC);

61

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

d) Reading a file
The process of reading a file is essentially a mirror image of the process of creating a file. The
first step is to prepare the file foe reading by means of a standard procedure RESET. The general
form is
Reset(Filename)

If the file contains one or more components, the reset statement causes the value of the first file
component to be read and assigned to the file buffer. The read statement is used to read the file to
a buffer. Once a file component has been read and assigned to the file buffer , the buffer contents
may be processed as desired for example, the contents of the file buffer may be assigned to a
variable, printed to another file e.t.c. the Read statement has the following general expression.
Read(filename,variable name);
Using declaration for example on writing on the file then reading will be a follows
READ(CUSTOMERS,CUSTREC);

e) Updating a file
In Pascal it is not possible to read a file component, modify a file component and then write the
modified component back to the original file. This restriction tends to complicate the process of
updating an existing file. To update the old file we carryout the following steps for each
component within the file
Read the file component into the computer memory and determine whether
or not particular component must be updated
(a) If the current component does not require updating the
copy it directly to a new file.
(b) If updating is required, then new information is entered
from the input device and merged with the old
information in appropriate manner. The modified file
component is then written to a new file.
This scheme is repeated until the file components have been read from the
old file(i.e. until the end of the file has been reached.)
If additional file component must be appended to the original, then they are
entered from the input device at this time, in the proper order. Each new file
component is written to the new file at it is entered. For this scheme to work
properly, the new information must be entered sequentially from the input
device, in the correct order.
Example

PROGRAM CREATEFILE(INPUT,OUTPUT,CUSTOMERS,NEWCUST);
TYPE ACCOUNT = RECORD
CUSTNAME: STRING;
CUSTNO: REAL;
CUSTBAL: REAL ;

62

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

CUSTTPAY: REAL;
CUSTPAID:REAL;
END;
VAR CUSTOMERS,NEWCUST: FILE OF ACCOUNT;
NUM:INTEGER; ANS:CHAR;
CUSTREC,NEWREC:ACCOUNT;
PROCEDURE COPYRECORDS;
BEGIN
WHILE NOT EOF(CUSTOMERS) DO
BEGIN
READ(CUSTOMERS,CUSTREC);
NEWREC:=CUSTREC;
WRITE(NEWCUST,NEWREC);
END;
END;
PROCEDURE UPDATERECORDS;
BEGIN
REWRITE(CUSTOMERS);
RESET(NEWCUST);
REPEAT
IF NOT EOF(NEWCUST) THEN
BEGIN
READ(NEWCUST,NEWREC);
CUSTREC:=NEWREC;
END
ELSE
BEGIN
WITH CUSTREC DO
BEGIN
WRITE('ENTER THE CUSTOMER NAME=>');
READLN(CUSTNAME);
WRITE('ENTER CUSTOMER NUMBER=>');
READLN(CUSTNO);
WRITE('ENTER CUSTOMER PAYMENT');
READLN(CUSTPAID);
CUSTTPAY:= 15000;
CUSTBAL:=CUSTTPAY-CUSTPAID;

63

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

END;
END;
WRITE(CUSTOMERS,CUSTREC);
WRITELN('MORE RECORDS Y FOR YES AND N FOR NO =>');
READLN(ANS);
UNTIL (ANS='N') OR (ANS='n')
END;
PROCEDURE OUTPUT;
BEGIN
RESET(CUSTOMERS);
WHILE NOT EOF(CUSTOMERS) DO
BEGIN
WITH CUSTREC DO
BEGIN
READ(CUSTOMERS,CUSTREC);

WRITELN(CUSTNAME,' ',CUSTNO:6:0,'
',CUSTTPAY:6:0,' ',CUSTPAID:5:0,' ',CUSTBAL:5:0)
END;
END;
READLN;
END;
BEGIN
ASSIGN(CUSTOMERS,'FREDS');
ASSIGN(NEWCUST,'FREDS');
RESET(CUSTOMERS);
REWRITE(NEWCUST);
COPYRECORDS;
UPDATERECORDS;
OUTPUT;
END.

TEXT FILES
A stream of characters input via a keyboard and output to the screen of a monitor can be thought
of as the contents of text files being read from a keyboard or written to a screen. Indeed the
heading PROGRAM identifiers (INPUT, OUTPUT); essentially defines two system text files,
INPUT and OUTPUT. Text files, however are not confined to keyboard input and screen output,
they can be read from or written to secondary storage media or a disk.

64

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

The method of re-directing the input is through the program heading. The INPUT and OUTPUT
system file declaration are replaced by the explicit names of the text files being used. For
example
PROGRAM students(data,results);
Specifies two files data and results that are used in place of INPUT and OUTPUT. Thses two
files must be declared as variables of type TEXT for example
Var data, results: TEXT;
But this does not prohibit the use of INPUT and OUTPUT
PROGRAM students(INPUT, data OUTPUT, ,results);
In the above example the program reads data from both the keyboard and file data and writes
information to both the screen and file results.
There are two ways in which a text file may be created. The first is from within a program by
using Write and Writeln statements to direct output to magnetic disc or tape instead of the
screen. The second is by using the system editor in the way as a program is created(via keyboard
entry) and stored on magnetic tape or disk. A text file is a stream of ASCII characters, divided in
to lines, each with an end of line marker, and the end of file is appended by the system, with and
end of the file marker. Atext data is stored in the same format as a source program file.

(a) File processing

(i) Opening a file

Before a file can be used it must be opened. The two predefined procedure in pascal for
reading and writing are RESET and REWRITE.
RESET (data) opens the file data ready for reading and REWRITE (data) opens the file data
ready for writing (or overwriting existing lines)

(ii) Reading a text file.

The lines of a text file can be read by suing READ and READLN. However, the statement
are modified by including the name of the file to be read. Fro example
Read(data,value) where data is the name of the text file.

(iii) Detecting the of line

The function EOLN is used to detect the end of line. In most cases there is no need to use this
function if there is sufficient read statements to consume all data on one line of a text file. If
used the function EOLN is used as IF EOLN(data) THEN

(iv) Detecting the of a file

The function EOF is used to detect the end of a file. If this function is not used the READ
statements will attempt to read beyond the end of the file. This will results in a run time error
andd the program will be terminated by the operating system. The fuction EOF returns true if
the end of file is detected. For example
IF EOF(data) THEN

65

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

(v) Writing to file

The information is written to afile by use of write and writelin. The statements are modifiued
by including the name of the file. A file opened for writing by REWRITE is changed to
reading by RESET example
Writeln(results,value:6, articles);

(vi) Closing a file

There is no predefined procedure in standard Pascal to closer a file. The mode of use of a file
is changed by opening the file again (even though its is in effect still open). The RESET
statement could be used in effect to close the file. The close statement can be used to close a
filein most version of Pascal for example
Close (data)

Text files without Records

program textfiles(input,output);
var total,score1,score2,avg:real;
inp,out:text;
name:string[10];
begin
assign(inp,'[Link]');
assign(out,'[Link]');
reset(inp);
rewrite(out);
writeln('name score1 score2 total average');
while not eof(inp) do
begin
readln(inp,name,score1,score2);
total:=score1+score2;
avg:=total/2;
writeln(out,name:10, score1:4:2,' ',score2:4:2,'
',total:4:2,' ',avg:4:2);
writeln(score1:4:2,' ',score2:4:2,' ',total:4:2,'
',avg:4:2);
end;
close(inp);
close(out);
end.
Text Files With Records

66

Downloaded by Sylvance Otieno (syloti@[Link])

 lOMoARcPSD|4907642

program emplo(input,output);
type employee= record
name:string[15];
age:integer;
hrs:real;
rate:real;
gross: real;
end;
var empl1:employee;
inp,out:text;
begin
assign(inp, '[Link]');
assign(out,'[Link]');
reset(inp);
rewrite(out);
while not eof(inp) do
begin
with empl1 do
begin
readln(inp,name,age,hrs,rate);
gross:=hrs*rate;
writeln(out,
name:15,Age:3,hrs:10:1,rate:11:1,gross:11:2);
writeln(name:15,' ',age:4,' ',hrs:4,' ',rate:4,'
',gross:4:2);
end;
end;
close(inp);
close(out);
end.

67

Downloaded by Sylvance Otieno (syloti@[Link])