We have already come across arrays in a few places in earlier programs - for example, we used an array of integers in stats.pas, and every time we use a string we are using an array of characters. In this section we look in more depth at the structure of arrays, and operating with arrays, and we also look at some of the more popular data structures used in Pascal. A complete discussion of all data structures used would be impossible, but we will implement some basic structures and discuss some of the more complex ones.
Arrays
An Array is a grouped set of data elements of the same characteristics. It is an n-dimensional collection of elements where each element can be populated or referenced separately. An example of an array declaration is :
var studentresults : array[1..10,1..5] of real;
Here a two dimensional array of size (10 * 5), with a total of fifty elements, each of which is of data type real, is declared. In this case, the array might be used to store exam results for 10 students in 5 subjects. The array is called studentresults and is referenced by addressing the element of the array required. For example to get the result that the eighth student achieved in the third subject, the result is accessed using
result = studentresult[8,3]
As mentioned above, a string is an array of characters, thus the declaration
Var name : string[30];
declares an array of 30 character fields which is referred to as name. A character array can also be multidimensional, for example the array
var studentname : array[1..10,1..30] of char;
could be used to store the names of 10 students, with each name a maximum of 30 characters long, corresponding in order to the first dimension of the array studentresult above. A more conventional, and perhaps easier way of understanding a multidimensionl string array would be to declare the array we have just declared above as :
var studentname : array[1..10] of string[30];
The array
var subjects : array[1..5] of string[30];
could be used to store the names of 5 subjects, each subject name up to 30 characters, corresponding to the second dimension of the array studentresults above.
To place a value in an element of an array, use subscripts to reference the element of the array into which you wish to place a value, e.g.
studentresults[7,2] := 14.75;
places the value 14.75 in the array element for the eighth student in the third subject.
In the case of a character array, a string can be placed into an element of an array of strings using direct assignment, e.g. ;
Studentname[3] := 'Mary';
places the name "Mary" in the first four characters of array element 3. Even though the array element is 30 characters long, the word "Mary" in the array is terminated at the end of the assigned value, and if we writeln(name), the result will be "Mary". The array is still 30 characters long, but deemed to terminate at the null character.
To change an individual element of a character array, a similar access method to that used for numerical arrays is used, e.g.
studentname[3,4] := 'k';
writeln(name);
will result in "Mark" being printed to the screen.
Example
In the following example, we populate two arrays - the first is an array of names of a sample of the population, and the second an array showing their height, weight and age. We then calculate the average and standard deviation of the heights, weights and ages of the sample, and allow the user to enquire on the height or weight of an individual member of the sample. The program uses a number of techniques we have developed in previous sections.
program samplestats;
const maxsample = 100;
type stats = array[1..maxsample, 1..3] of real;
var heightweightage : stats;
var people : array[1..maxsample] of string[30];
var name : string[30];
var samplesize, i : integer;
var height, weight, age : real;
{ }
{ populate_people procedure = gets names of people in sample }
{ }
procedure populate_people;
begin
for i:= 1 to samplesize do
begin
write ('Enter name of candidate ',i,' : ');
readln (name);
people[i] := name;
end;
writeln (i,' names stored ');
writeln;
end;
{ }
{ populate_stats procedure = populates array of statistics }
{ }
procedure populate_stats;
begin
for i:= 1 to samplesize do
begin
write ('Enter height, weight and age for ',people[i],' separated by spaces : ');
readln (height, weight, age);
heightweightage[i,1] := height;
heightweightage[i,2] := weight;
heightweightage[i,3] := age;
end;
writeln ('Finished storing statistics ');
writeln;
end;
{ }
{ procedure calculate_stats = calculates averages, standard deviations }
{ etc. of numbers stored in heightweightage array }
{ }
procedure calculate_stats;
var totalheight, totalweight, totalage : real;
var sdheight, sdweight, sdage : real;
var avheight, avweight, avage : real;
var stdvheight, stdvweight, stdvage : real;
var diffheight, diffweight, diffage : real;
begin
totalheight := 0; totalweight := 0; totalage := 0;
sdheight := 0; sdweight :=0; sdage :=0;
avheight := 0; avweight :=0; avage :=0;
stdvheight := 0; stdvweight :=0; stdvage :=0;
diffheight := 0; diffweight :=0; diffage :=0;
{ calculate averages }
for i:= 1 to samplesize do
begin
totalheight := totalheight + heightweightage[i,1];
totalweight := totalweight + heightweightage[i,2];
totalage := totalage + heightweightage[i,3];
end;
avheight := totalheight / samplesize;
avweight := totalweight / samplesize;
avage := totalage / samplesize;
{ calculate standard deviations }
for i := 1 to samplesize do
begin
diffheight := heightweightage[i,1] - avheight;
diffweight := heightweightage[i,2] - avweight;
diffage := heightweightage[i,3] - avage;
sdheight := sdheight + (diffheight * diffheight);
sdweight := sdweight + (diffweight * diffweight);
sdage := sdage + (diffage * diffage);
end;
stdvheight := sqrt (sdheight / samplesize);
stdvweight := sqrt (sdweight / samplesize);
stdvage := sqrt (sdage / samplesize);
writeln ('Summary of statistics :');
writeln (' Average St.Dev');
writeln ('Height ',avheight:7:3, stdvheight:7:3);
writeln ('Weight ',avweight:7:3, stdvweight:7:3);
writeln ('Age ',avage:7:3, stdvage:7:3);
end;
{ }
{ candidate enquiry - allow user to enquire on individual }
{ statistics for a named candidate }
{ }
procedure candidate_enquiry;
var quit : boolean;
begin;
writeln;
writeln ('Enquire on statistics for an individual candidate ');
writeln ('Enter name of candidate required, type EXIT to quit search ');
readln (name);
quit := name = 'EXIT';
while (not(quit)) do
begin
for i:= 1 to samplesize do
begin
if (people[i] = name) then
begin
writeln ('Statistics for ',name);
writeln ( 'Height ',heightweightage[i,1]:7:3,
' Weight ',heightweightage[i,2]:7:3,
' Age ',heightweightage[i,3]:7:3);
end; { end of if people[i] = name then... }
end; { end of i := 1 to samplesize }
writeln ('Enter name of candidate required, type EXIT to quit search ');
readln (name);
quit := name = 'EXIT';
end; { end of while not(quit)) }
end;
begin
write ('Enter sample size : ');
readln (samplesize);
populate_people;
populate_stats;
calculate_stats;
candidate_enquiry;
end.
There are some features of this program we have not used before :
Firstly the code is divided into procedures. Looking at the main body of code (between the begin and end., there are four main sections to the program - getting the names of the people, getting the statistics for each individual, calculating the statistics for the sample, and enquiring on individuals within the sample. These functions are divided up and written separately, and then invoked from within the main body of the program. The individual procedures are divided up and written exactly the same as a self contained program, with some small differences. The procedure is defined by the reserved word "procedure", after which comes the definition of the parameters to the procedure in brackets. Then follows a section for declaration of variables local to the procedure, followed by the body of the procedure code itself, delimited by an opening begin and end;. It is important that the name of the function to be invoked is identified to the compiler before the function is called in the program.
Variable Scope : There are a number of variables which are declared at the start of the program, such as samplesize, i, and age. These variables are declared outside any individual function and are global to all functions within the program, that is any function can reference or amend these variables. When one of these variables is amended within a function, it's amended value is then available to any of the other functions to use. However, within the calculate_stats function, a number of variables are defined which are local to that function, e.g. totalheight and avage. That is, memory is allocated to these variables when the function is invoked, and the variables are destroyed when the function is exited. Once calculate_stats returns control to the main program, none of the variables declared local to that function are available for reference or amendment. If a variable were declared locally within calculate_stats with the same name as a variable with global scope, the local variable would be independent of the global variable, would be destroyed on exiting the function, and the global variable would retain the value it had before the function were invoked after the function was exited.
Structures
A structure is a collection of data items of different attributes linked together for organisational purposes. We have already come across structures in the programs to write to and read from the contacts file. Here the structure was a record of four sets of character fields, a name, address, email address and a telephone number. Equally a structure could contain other data types, e.g. integers and real numbers. type vartypename = record is usually used to group data into records which are either to be stored in memory or on file. Below is a modified version of the structure used in the contacts file programs to show its use :
type record_struc = record
name : string[30];
address : string[30];
email_address : string[30];
telno : string[20];
zip_code : string[8];
age : integer;
salary : real;
end;
To declare a variable whose type is that of a defined structure, once the structure has been defined using the type command as above, an instance of that type must be created, as follows :
var rec : record_struc;
This declares a variable rec which is a structure of type record_struc. The individual components of rec are referenced and dereferenced using the syntax rec.fieldname, e.g. rec.name, rec.address etc. For examples of the application of structures, see writeadd.pas, writead2.pas, readaddr.pas, findaddr.pas and searchad.pas.
Other Structures
It is beyond the scope of this course to cover in detail the considerable range of data structures that are popular to Pascal programmers. However, there are two popular structures used regularly, stacks and linked lists. Here we show the programming behind the stack structure and briefly outline the principles behind the operation of a linked list.
Stacks
A stack is a Last-In-First-Out (LIFO) data structure. It is used where a piece of well defined data will be put into a sequential system of data. Data can then be placed into the system, or removed from the system, using the rule that the last piece of data into the system is always the first piece of data out of the system. There are four basic operations used on a stack :
push (data), pop()
empty(), top()
The push() operation places data on the top of the stack and increments the top_of _stack indicator by one to indicate there is another piece of data on the stack.
The pop() operation removes the top (last in) piece of data from the stack and decrements the top_of_stack indicator by one to indicate that there is one less piece of data on the stack.
The empty() operation is an indicator flagging whether or not the stack contains any data.
The top() operation indicates where the top of the stack is, and therefore where the most recently placed piece of data is.
If a stack has a finite size, and is not too large to hold in memory, an array structure can be used to maintain the stack. Alternatively, a structure is defined containing both the data which a stack element is to hold and a pointer. The pointer will be to another instance of the structure. As new elements are added to the stack, a new instance of the structure is allocated in memory. The pointer in the previous 'top-of-the stack' element is pointed at the new instance of the structure and the new instance becomes the top of the stack. The pointer in the top-of-the-stack element will always point to NULL to indicate that it is the top of the stack. The following structure definition might be appropriate to define the element structure for a linked stack :
type stack_element = record
pointer : ^stack_element;
element_name char[20];
element_num int;
};
where ^stack_element indicates a pointer to an address in memory where a variable of type stack_element is stored. This pointer can then be dereferenced to access the next instance of the stack_element variable.
Below we show a trivial implementation of a stack. The program allows the user to select any of the stack operations : top, push, pop, and empty and then returns the appropriate value based on the operation requested. This stack stores strings, e.g. to model a LIFO customer queue, and uses an array which stores a maximum of 100 customers :
program stack;
const maxcust = 100;
type cust_array = array[1..maxcust] of string[30];
var customers : cust_array;
var top, i : integer;
var option : char;
var quit : boolean;
function intro : char;
var option : char;
var valid : boolean;
begin
writeln;
writeln ('Enter one of the following options :');
writeln ('A Push a new customer onto the stack ');
writeln ('B Pop the most recent customer from the stack ');
writeln ('C Display the top element of the stack ');
writeln ('D Enquire as to whether the stack is empty ');
writeln ('E Traverse the whole stack ');
writeln ('X Exit the stack program ');
repeat
readln (option);
until option in ['A'..'E', 'X', 'a'..'e','x'];
if option in ['a'..'e','x'] then option := upcase (option);
intro := option;
end;
procedure push;
var custname : string[30];
begin
write ('Enter next customer name : ');
readln (custname);
customers[top] := custname;
top := top + 1;
writeln ('Customer added to top of stack');
end;
procedure pop;
begin
writeln ('Top customer on stack : ',customers[top - 1]);
top := top - 1;
writeln ('This customer has now been popped, there are ',top-1,
' customers remaining on the stack');
end;
begin
top := 1;
quit := FALSE;
while (not(quit)) do
begin
option := intro;
case option of
'A' : begin
writeln ('Push new customer onto stack ');
push;
end;
'B' : begin
writeln ('Pop last customer from stack');
if (top = 1) then writeln ('No customers on stack to pop')
else pop;
end;
'C' : begin
writeln ('Display top of stack');
if (top = 1) then writeln ('Stack is empty')
else begin
writeln ('Variable top has value ',top,
' => there are ',top-1,' elements in the stack');
writeln ('The value of the top element is ',customers[top - 1]);
end;
end;
'D' : begin
writeln ('Enquire as to whether stack is empty');
{ stack is empty if top = 1 }
if (top = 1) then writeln ('The stack is empty')
else writeln ('The stack is not empty, it contains ',top-1,' elements');
end;
'E' : begin
writeln ('Traverse the whole stack');
{ stack is empty if top = 1}
if (top = 1) then writeln ('The stack is empty - no elements to traverse ')
else for i := 1 to top-1 do
writeln ('Value of stack element ',i,' : ',customers[i]);
end;
'X' : quit := TRUE;
end; { end of case }
end; { end of while }
end.
There is only one aspect of this program that we have not used before - the function intro is very similar to the procedures we used in the program previously. The difference between a function and a procedure is that a function returns a value to the invoking program. To accommodate this, the data type of the returned variable is declared in the function declaration, and the value returned is assigned to a variable in the course of the function, the variable name is the same as the function name. Other than this a function will work in the same way as a Pascal procedure.
Also, we have seen the upcase command for the first time - this converts the character passed to it as a parameter to upper case.
Linked Lists
A linked list is very similar to a stack but it has important distinctions both in its implementation and in its operation. A linked list has a header, which is a pointer to its first element. Each element then contains two items, its data item (or items) and a pointer item which points to the next element in the linked list. One of the differences between a stack and a linked list that an item can be inserted at any point, or deleted from any point in the list (as opposed to a stack, which can only add or delete from the top of the list), so a linked list can maintain an arbitrarily defined order.
A variation on the linked list is a doubly linked list, where each element not only points to its successor but also to its predecessor, allowing the linked list to be traversed both forwards and backwards. Even greater levels of linking between elements can occur, though this is much more unusual.