Previous: 10.3 Binary Search
Up: 10 Sorting and Searching
Next: 10.5 Polymorphic Data Type
Previous Page: 10.3 Binary Search
Next Page: 10.5 Polymorphic Data Type
Previous: 10.3 Binary Search
Up: 10 Sorting and Searching
Next: 10.5 Polymorphic Data Type
Previous Page: 10.3 Binary Search
Next Page: 10.5 Polymorphic Data Type
So far, in the previous sections, we have seen how to search and sort an array of integers. In this section we apply the sort and search methods to our database of payroll records. The data items in a payroll record are id number, hours worked, rate of pay, regular and overtime pay. Our task is to write an interactive program which displays the pay record for a given individual.
We saw how we could implement such a database in Chapter .
There, the data record for a specific id is stored at the same index in
several different arrays as shown in Figure 10.16.
In our application, we will search the database to find the payroll record
given a specific id number as the key.
Therefore, we will need to sort the database by the id number field.
When we search for the key, we will get the index for the element, if any,
which matches the sought after id.
With that index in id number array, we can access the remaining information
for that data record.
As we saw in the previous section, when we sort an array, we rearrange the positions of the array elements. When we sort data records, we must rearrange the positions of all fields of the data records; i.e. if a data record is spread over several arrays, we must rearrange the elements of all of these arrays in an identical manner. In this way, we will still be able to access a data record using the index determined by a key. To sort the database, we can use either selection sort or bubble sort for our task. We will assume that the input data is mostly sorted, requiring little rearrangement, and therefore will choose to use bubble sort. This is a reasonable assumption since records are usually kept in a file in sorted order. Only new records entered may be out of place. We will modify bubblesort() of the last section to handle data records.
The input data record is spread over three arrays; namely, , hrs[], and rate[]. Since we are sorting records by id numbers, the decision whether to swap records is determined by the elements of the id[] array; however, if we swap elements of id[], we must also swap corresponding elements of the other two arrays.
The code for the modified sort function, called sortdata(),
that sorts input payroll records is shown in Figure 10.17.
We write the code in the file payutil.c and add its prototype
in payutil.h.
These files have other payroll functions and prototypes developed in
Chapter , including:
which reads the input data,
which calculates regular and overtime pay,
and printdata() which
prints the pay records in a table.
We also use the file tfdef.h that defines
TRUE and FALSE.
We can now use the above function in a payroll program that sorts the input data before processing it. The main purpose of this program is to test the operation of creating a sorted database of records before later modifications to the program. The driver is very simple and consists of functions that get data, sort data, calculate pay, and print data as seen in Figure 10.18. Notice we have performed the calculate pay step after the database has been sorted, as the arrays containing this data are not rearranged by our sort function. The sample session is shown below.
Sample Session:
The program file, paysrt.c, containing the driver, and the source file, payutil.c, with the new function, sortdata() added, must be compiled and linked. Observe that the input is almost sorted by id number; only the last record is out of place. Bubble sort can sort this data in one pass.
Having observed that the database is correctly sorted, we can now complete the task to search for a specific record to display. We will use binary search on the data in sorted order. The search for an id number in the array, id[], returns an index if it is found, and returns -1 otherwise. If the index is non-negative, the same index is used to access the rest of the data record spread over the other arrays. We modify the above test program to read the data records and calculate the pay, then repeatedly call binsrch() to return the index of a data record for a specified id number. If a data record exists, it is printed by printrec(). We have already implemented the function binsrch() and included it in the file, sortsrch.c. We will soon write printrec(). The program that implements our task is shown in Figure 10.19.
The first part of the program reads data, sorts data, and calculates pay. The second part of the program reads an id number and calls binsrch() to locate its index in the array. If the index is non-negative, the program uses a function, , to print a data record at that index. If the index is negative, the program prints an error message. The function, printrec(), is shown in Figure 10.20 and added to the file, payutil.c.
A sample session for the search part of the program is shown below. The input data is assumed identical to that in the sample session for the previous program paysrt.c.
