A slight modification to the program book_shelf would allow us to search through the array ~for a value, in this case we could search for either the author or the title. The element of a data structure for which we search, is called the key field. In this case the key field will be the author. In the above program the subscript identifier number was used to write out the element of an array. We used a counter variable I to control a loop. When searching through an array we need a value to search for as well as a loop counter. First of all we read in the value we wish to search for, then inspect the first element of the array to see if it matches this value, using the loop counter as the subscript. If this value doesn't match, we increment the loop counter by one, and inspect the next element. In the simplest form, this requires a fragment of code like this below. The variable number_of_data_items contains the number of array elements which contain data, and is similar to number_of_books in the previous program.
WRITE('Enter the name to search for : '); READLN(the_name); I := 1; WHILE (the_name <> the_array[I].name) AND (I <= number_of_data_items) DO I := I + 1;
This simple piece of code will work its way through the array, inspecting every element and comparing the_name with the field the_array[I].name. The program will exit the loop if the_name is found or when I reaches the same value as number_of_data_items. The loop counter I will then be equal to one of three values
(the_name found in element 1)
number_of_data_items + 1 (the_name not found in array)
A value between 1 and number_of_data_items (the_name found at that value)
We can simplify the search by keeping the element the_array[MAX].name empty so if I becomes equal to MAX you know that the value that you are searching for is not contained in the array, but this entails the search going the entire way through the array. This idea is what is behind this next bit of code.
IF (I = MAX) THEN WRITELN('The name is not in the data-base') ELSE WRITELN('The name is held in element : ',I);
so only if I is less than MAX will the value of I be written out. This can easily be used to write out the other fields of the record, because you know that the value of I points to the array element which contains the searched for value. Searching through arrays almost always causes problems for the beginner programmer, because they find difficulty in dealing with the first element and the last element of the array, what happens most is that the program tries to access an element past the end of the array as will occur when the loop counter becomes equal to MAX + 1. This causes a run-time error and the program crashes without explaining very clearly why. Normally it is best to search through an array using a WHILE loop, because the program can exit from the search as soon as a matching value is found. In the next program I use a FOR loop because I want to search right through the entire array. This is because in a library data-base search, you would want to write out all titles by the author, not just the first one to be found. This next program is just a modified version of the one above. It uses the same data file to read in the data, and the same datastructure to store it. The assignment statements are a little different, in this example the read in data is assigned directly to the field in the array, without the use of dummy variables which hold the data values temporarily. As I said before, if you need to use apostrophes in your text, you need to put in two of them together as in the line from the next program:
WRITE('Please enter authors name : ');
Program 2
PROGRAM book_shelf_two(INPUT,OUTPUT,booklist); { this program is a library catalogue, it asks for the name of an author, then lists all titles by that author } CONST MAX = 15; TYPE AUTHOR_NAME = STRING[20]; BOOK_TITLE = STRING[50]; BOOK = RECORD author : AUTHOR_NAME; title : BOOK_TITLE; END; BOOK_SHELF = ARRAY[1..MAX] OF BOOK; VAR I, { loop counter } number_of_books, number : INTEGER; booklist : TEXT; { file name } my_book_shelf : BOOK_SHELF; an_author : AUTHOR_NAME; found : boolean; BEGIN number_of_books := 0; WRITELN; RESET(booklist); { reset file for reading } WHILE (number_of_books <= MAX) AND (NOT EOF(booklist)) DO WITH my_book_shelf[I] DO { read in from file } BEGIN number_of_books := number_of_books + 1; READLN(booklist,title); { assign data to array } READLN(booklist,author); END; CLOSE(booklist); { all file data in array } WRITE('Please enter authors name : '); READLN(an_author); WRITELN; found := FALSE; WRITE('The author ',an_author,' has these titles'); WRITELN(' in the library'); WRITELN; FOR I := 1 TO number_of_books DO { search through array } IF my_book_shelf[I].author = an_author THEN BEGIN found := TRUE; WRITELN(my_book_shelf[I].title); END; IF NOT(found) THEN WRITELN('Nothing by ',an_author,' was found'); WRITELN; WRITELN(' ~~~~~~~~~~~~~~~~'); WRITELN(' Search completed'); END. { program book_shelf_two }
Some of the authors in the file will only have one title by them in the data base, but because we have chosen to use a FOR loop, the program is forced to search through the entire array before it can quit. In this example there was a very good reason for this, but some times, there is only one element that will satisfy the test, and to search any further would be both pointless, and a waste of processor time. Now, let us suppose that we had a very large array, one which was used to store the same details as those in a telephone book: name, address, phone number. Both the phone number and the address are likely to be unique, so they both could be used as key fields, and since they are unique, once a match was found, the search could be terminated. For this kind of search a WHILE loop is best suited. For this example we will need a three field RECORD, and an upper limit designated by the CONST MAX.
Program 3
PROGRAM phone_book(INPUT,OUTPUT,phone_book_file); { this program performs a linear search on an array loaded from a file. It searches for a matching phone number and returns the name and address of the person to whom that number is registered } CONST MAX = 20; { all the elements need not be filled } TYPE A_PHONE_NUMBER = STRING[10]; A_NAME = STRING[20]; AN_ADDRESS = STRING[50]; DETAILS = RECORD phone_number : A_PHONE_NUMBER; name : A_NAME; address : AN_ADDRESS; END; PHONE_BOOK = ARRAY[1..MAX] OF DETAILS; VAR number_of_entries, I : INTEGER; area_phone_book : PHONE_BOOK; found : BOOLEAN; customer_number : A_PHONE_NUMBER; phone_book_file : TEXT; BEGIN I := 1; found := FALSE; RESET(phone_book_file); WHILE (I <= MAX) AND (NOT EOF(phone_book_file)) DO WITH area_phone_book[number_of_entries] DO BEGIN READLN(phone_book_file,phone_number); READLN(phone_book_file,name); READLN(phone_book_file,address); I := I + 1; END; number_of_entries := I - 1; { last increment of "I" set it 1 past number of records in the file } CLOSE(phone_book_file); WRITE('Enter customer phone number : '); READLN(customer_number); I := 1; { reset the value of "I" to 1 } WHILE NOT found AND (I <= number_of_entries) DO WITH area_phone_book[I] DO BEGIN found := phone_number = customer_number; I := I+1; END; IF found THEN WITH area_phone_book[I-1] DO BEGIN WRITE('The customer is '); WRITELN(name,' of ',address); END ELSE BEGIN WRITE('There is no entry for '); WRITELN(customer_number); END; END. { program phone_book }
You will have noticed again that there are no assignment statements as such in the file reading section of the program. The method used to load the array is by directly reading the values into their correct fields in one line. The first WHILE loop, is the one used to do this. The use of the with, means that the line,
But they both do the same thing, that is read the next data item from the file, and place it into the appropriate field of the array ~element, that the current value of I indicates. The file required by the above program should be of the form:
123456 John Smith 42 Hill St, Dunblane 654321 Henry Alexander 21 Braeside, Alva . . . 837462 Peter Wood Riverview Dr, Edinburgh 284574 Jim Iggnatowski 1 Dinnet Row, Portree
There is no need to have exactly the same number of entries in a file as there are elements in the array. In fact you need not have more than three or four, just enough to test it with. In order to test the program, you could directly assign values to the fields of the array, and leave the file handling to later. To assign values into these fields would require code similar to,
WITH area_phone_book[1] DO BEGIN phone_number := '123456'; name := 'John Smith'; address := '42 Hill St, Dunblane'; END;
You can of course repeat this for any element number in the array.
