Software Design Using C++

Records (Structures)

Basics

A record, commonly called a structure in C++, is a collection of related data items. Unlike with an array, the data items in a record can be of different types. Also, with a record the data items are identified by field name, whereas with an array the data items are identified through the use of an index number.

For example, to create a simple record holding a part number and a price, we might use a typedef to create a record type (here called PartType) as follows:

typedef struct
   {
   int PartNumber;
   float Price;
   } PartType;

Another way to create the same type is the following:

struct PartType
   {
   int PartNumber;
   float Price;
   };

Dot notation is used to access a given field of a record. For example, the following assigns values to the two fields of a record named Part:

PartType Part;

Part.PartNumber = 123;
Part.Price = 9.95;

Similarly one would use the dot notation to look up the value in a field of a record. Thus we might use cout << Part.Price; to print the price contained in record Part.

One can picture a record as a box subdivided into sections for the various fields. The Part record above could be pictured as follows:

Note that it is possible to assign one record into another record variable of the same type. This merely copies all of the data from the fields of the record on the right hand side into the corresponding fields of the record variable on the left hand side. Thus we could use something like the following:

PartType Temp;
Temp = Part;

A Simple Working Example

We leave it to the reader to look at these three files and to try them out. Here we go on to a somewhat more complex version of the same program and describe it in detail.

A Somewhat More Involved Working Example

struct EmployeeType
   {
   char FirstName[NameMax];
   char LastName[NameMax];
   int ID;
   float WageRate;
   };

In the employee.cpp file are the functions that have been written for dealing with employee records of the type just shown. The ReadEmployee function is used to read data from the keyboard and place it in an employee record. The following shows the overall comments for this function. Note that the Employee formal parameter is a reference parameter. This is so that data can be sent back out of the function via this parameter. Also note that a return code is sent back in the function name. This code will be one of the constants which are set up in employee.h.

/* Given:  Nothing.
   Task:   To read from the keyboard data for one employee.
   Return: Employee   A structure containing the data just read.
           In the function name return FailFlag or OKFlag
           to indicate how input behaved.
*/
int ReadEmployee(EmployeeType & Employee)

In the actual code for the ReadEmployee function note that using something like cin >> Employee.LastName; is of limited usefulness in that it stops placing data in LastName at the first whitespace character. If this is a newline (from pressing the Enter key), great. However, it could be that the user of the program entered Barker III as the last name. In this case only Barker gets placed in the LastName field of the Employee record.

Also notice that the fail function is used after every data data entry command to see if the user pressed CTRL z to indicate end of data (EOF). If so, we immediately exit from the ReadEmployee function by doing return FailFlag. (Of course, in Linux CTRL d is used instead of CTRL z to indicate the end of data entry. If you accidentally use CTRL z in Linux, it will suspend your program. In such a case you can most likely bring your program back into the foreground with the command fg 1 and then continue to run your program.)

Another function in the same file is PrintEmployee. As you can see below it is passed a record of employee information and prints its data on the screen. Since the Employee parameter is only being used to send data into the function you might wonder why it is set up to be a reference parameter. The answer is that a record can contain a fairly large amount of data. It is time-consuming to copy all of it, and it takes extra space on the run-time stack for this copy. So for the sake of efficiency we typically make record parameters to be reference parameters. Note, however, that const is used in front of this parameter. This indicates that we will not change anything in the Employee parameter, so that no data is sent back in this parameter.

/* Given:  Employee   A structure containing info on one employee.
   Task:   To print the data from Employee on the screen.
   Return: Nothing.
*/
void PrintEmployee(const EmployeeType & Employee)

The oneemp.cpp file contains the main function. It is a simple test program that reads in data for one employee into a record and then prints the data out onto the screen. It should be fairly clear how it works.

Using an Array of Records

An array of records is useful for temporarily storing a sequence of records. The two multiple source file projects below use just such an array to hold the employee data read in for a sequence of employees. Each program then finds and prints the average wage rate for the employees and uses the stored data to print the employee records for those employees who earned above the average. As above we show a simple version first and then a somewhat more complex one.

The Simpler Array of Records Example

As before we let the reader examine the code in this example and proceed to the more complex example, where we take a closer look.

The More Complex Array of Records Example

The first two files listed above are the same as the files by the same name used in the project whose main function was in oneemp.cpp. The new files include emparray.h, a header file containing a constant for the maximum number of employees that the array will be able to contain as well as a typedef setting up EmpArrayType as a type for such an array of records.

const int EmpMax = 50;   // Max number of employees
typedef EmployeeType EmpArrayType[EmpMax];

An array of type EmpArrayType, perhaps named EmpArray, can be pictured as a numbered sequence of records as shown in the picture below. This picture assumes that the array has been filled with data, but in some cases we might only fill part of it. To keep track of how much data we have in the array is, of course, the purpose of the EmpCount variable that you see in the main function of this program. For example, if EmpCount = 6, then you know that EmpArray has data at indices 0 through 5.

In the emparray.cpp file is found the code for the following LoadArray function. Note that it returns data via both parameters and that it sends an integer code back in the function name.

/* Given:  Nothing.
   Task:   To read a sequence of employee data from the keyboard,
           storing it in EmpArray.
   Return: EmpArray   The array of employee data.
           EmpCount   The number of employees just entered.
           In the function name return OKFlag or 
           TooMuchDataFlag to indicate how this function ended.
*/
int LoadArray(EmpArrayType EmpArray, int & EmpCount)

Internally, the LoadArray function calls our existing ReadEmployee function each time that it needs to read in the data for one employee. Note that the usual while loop pattern is used in placing this data into the array, with care taken to be sure that we do not run off of the end of the array (a common source of run-time errors). When this loop ends an if is used to decide how it ended. If ReadEmployee was unable to read data (undoubtedly because the user entered CTRL z to quit, or CTRL d in Linux), we use cin.clear() to clear the internal flags that are tested by the fail function. If we did not use this clear function we would be unable to get further input from the keyboard. This would be because we have already told the program that we are at the end of the data (EOF) by pressing CTRL z. (To see that we do actually do further input, check the main function in the aboveavg.cpp file.)

The AverageRate function is also found in the emparray.cpp file. It gets data from its two parameters, EmpArray and EmpCount, and uses these to find the average wage rate, which it returns in the function name.

/* Given:  EmpArray  Array of employee data from index 0 to Count-1.
           EmpCount  Number of records of data stored in EmpArray.
   Task:   To find the average wage rate for the employees in EmpArray.
   Return: In the funtion name, the average wage rate.
*/
float AverageRate(EmpArrayType EmpArray, int EmpCount)

At the start of this function you see that we have used the statement assert(EmpCount > 0); as a way to ensure that EmpCount is positive. We do not want to ever go on and divide by zero, giving a run-time error! The assert statement checks whether the condition inside is true and if so allows the program to continue. If the condition is not true, the program is aborted with a message that this condition failed to be true. Although this is one way to avoid crashing a program by dividing by zero, it might be more gracious to print our own customized error message and then to exit the program. Assert statements are more commonly used in the debugging stage of program development. Once one is sure that things are working fine, those asserts are then removed.

In the same file one also finds the PrintAboveAvg function whose job is to print the data for all employee records with a wage rate above the average. There is one new feature used inside the for loop in the code, shown below in simplified form. This is the comma operator. You already know that the three parts of the for line are separated by semicolons. Thus the initialization step consists of k = 0, NumPrinted = 0. The comma can be used to separate a sequence of commands. If a return value is needed from the combined command, the return value from the final statement is used. As we are not using any return value here, the effect is just to combine two initializations into one. Since both variables are being initialized to the same value, another way to achieve this would be to use k = NumPrinted = 0.

for (k = 0, NumPrinted = 0; k < EmpCount; k++)
   if (EmpArray[k].WageRate > AvgRate)
      {
      PrintEmployee(EmpArray[k]);
      NumPrinted++;
      }

It is left to the reader to study the rest of this program example.

A Program to Look Up Records in an Array

A Software Engineering Example

Analysis

In the first step of the software development cycle we need to get a clear idea of what the program should do. This is usually done by specifying the inputs, processing, and outputs.

In our case we do need to say more precisely what the input data is. The data entered at the keyboard for each employee, let's say, consists of the employee's first and last name, ID number, and wage rate, exactly as we did in the two previous programs. (One reason to do this is so that we can reuse code from those programs. In particular, we would expect to be able to reuse EmployeeType from employee.h and perhaps other things from employee.h, employee.cpp, emparray.h, and emparray.cpp).

The processing seems to be fairly clear. We want the user to interactively enter the data for a series of employees and then be able to repeatedly look up employee data by entering the first and last name of each desired employee. Let's fill this out by deciding that the user is to use CTRL z to end the lookups (or CTRL d under Linux).

The output is also fairly clear. Other than simple prompts that ask the user to enter data, the program needs to present, for each lookup, all of the data on the employee (if a match is found). This data, of course, consists of the first and last names, ID number, and wage rate.

Design

Let's start by considering the data and what we need to hold the data. For data we have a series of employee records that we need to keep around while the user looks up individual records. Thus, this seems to be another problem in which to use an array of employee records. That should also allow us to reuse more code from the previous problem, such as the function to load the array with employee records and the function to print an employee record.

Next, let's design the functions that we hope to use. Suppose we initially decide to divide the problem up into functions as shown in the following structure chart:

Some of the functions shown in this chart have already been written for use in the previous two problems. Thus we simply reuse the functions LoadArray, ReadEmployee, and PrintEmployee. For the other two functions, let's try the following design:

/* Given:   EmpArray  Array of employee records, already in order.
            EmpCount  Number of employee records in EmpArray.
   Task:    To allow the user to do repeated lookups for the data on
            an employee by entering the person's name.
   Return:  Nothing.
*/
void Lookups(EmpArrayType EmpArray, int EmpCount)

/* Given:   EmpArray   Array of employee records.
            Low        The low index of the range to search.
            High       The top index of the range to search.
            Target     Record containing name for which to search.
   Task:    To do a binary search for Target in the specified range of
            EmpArray.
   Return:  In the function name, return the index of where Target was
            found or -1 if it was not found.
*/
int BinarySearch(EmpArrayType EmpArray, int Low, int High,
   const EmployeeType & Target)

Note that we have decided to put the first and last names together into the Target record, as that is easier than having two separate parameters. That also brings to mind a problem: Even though we have written a binary search function before, it was not designed to handle records. How will we have the binary search compare two records to decide if they are equal (according to the last name and first name), if the first record is less than the second (alphabetically by the two names), etc? A good way to do this is to have an EmpCompare function to do this for us. Thus we decide to add the following function. Since it has to do with individual records we will place it in employee.h.

/* Given:   First   An employee record.
            Second  Another employee record.
   Task:    To decide if, based on last name then first name, First
            is less than, equal to, or greater than Second.
   Return:  In the function name return:
               -1 if First < Second
               0  if First == Seond
               1  if First > Second
*/
int EmpCompare(const EmployeeType & First, const EmployeeType & Second)

Prototyping

Instead of proceeding to code the whole project, let's first build a prototype. However, since a number of the helping functions have already been written, our prototype may be more complete than would normally be the case. Thus we can use the existing LoadArray and PrintEmployee functions. Let's assume that we do not yet write the code for the BinarySearch and EmpCompare functions, though if you look in our old employee.cpp and emparray.cpp files you will see that these two functions were already there.

Take a look at the prototype, recfind.cpp. In the Lookups function note that the call to BinarySearch has been commented off, since we are assuming that this function has not yet been written. Instead, we just give Result the arbitrary value of 0, so that the program will print out the record at index zero for every lookup. This isn't correct, of course, but it allows us to see that significant portions of the program are in working order. It also allows the user to try out the software to see if it appears that (when finished) it will do what is desired. Although the data input is rather clumsy for the target employee (as one has to enter a last name before being allowed to use CTRL z to halt), the program seems to work OK. Thus we move on to the coding phase.

Coding

Because of the clumsy data input noted above, let's decide to code a separate function to handle getting the first and last names for an employee to look up. Thus, we are cycling back to the design stage and modifying the design. The new function is outlined as follows:

/* Given:   Nothing.
   Task:    To prompt the user to enter the last and first name of an
            employee.
   Return:  Employee   Record containing these names, other fields unused.
            In the function name, return EOFFlag if CTRL z was entered,
            OKFlag otherwise.
*/
int GetTarget(EmployeeType & Employee)

The code for this function is found in our new recfind.cpp file. Of course, some of the Lookups function had to be modified to accommodate the GetTarget function. We now code the remaining functions as shown below:

int EmpCompare(const EmployeeType & First, const EmployeeType & Second)
   {
   int Value;

   Value = strcmp(First.LastName, Second.LastName);
   if (Value < 0)
      return -1;
   if (Value > 0)
      return 1;

   // If reach this line, LastNames are the same.
   Value = strcmp(First.FirstName, Second.FirstName);
   if (Value < 0)
      return -1;
   if (Value > 0)
      return 1;

   // If reach this line, both first and last names are same.
   return 0;
   }

If you are not familiar with the strcmp function, be sure to look it up by using either the Visual C++ compiler's help system or a good reference book. This function is very useful in comparing strings that are arrays of characters ending in a NULL character.

int BinarySearch(EmpArrayType EmpArray, int Low, int High,
   const EmployeeType & Target)
   {
   int Mid, Diff;

   while (Low <= High)
      {
      Mid = (Low + High) / 2;
      Diff = EmpCompare(EmpArray[Mid], Target);

      if (Diff == 0)
         return Mid;
      else if (Diff < 0)
         Low = Mid + 1;
      else
         High = Mid - 1;
      }

   return -1;   // If reach here, Target was not found.
   }

Testing and Debugging

As a first test we might try entering simple data such as the following, where each line shows a last name, first name, ID, and wage rate:

When we try to search for the employee with first and last name one, everything seems to work fine. Unfortunately, when we try to search for the employee with first and last name three that employee is reported as not found. What went wrong? You might want to try the debugger to trace what is happening as binary search tries to locate this employee. You might also draw the array of four records and try to trace the binary search by hand. Probably you now see the problem: The data is not in ascending order! Binary search requires this. Thus we realize that we made a mistake in the design phase: We need to sort the array of data by last name (and secondarily by first name).

We cycle back to the design phase to fix this. Let's use a SelectionSort routine. It can use the EmpCompare function to compare two records based on their names. At this point we redraw our structure chart to show all of the changes made since the original structure chart. Note that EmpCompare is shown twice in the chart since it gets called from two different functions. Do not try to draw a line from these two functions to a single box for EmpCompare as structure charts are commonly drawn as trees.

We then have to code the SelectionSort function as well. This results in a completed program that appears to be error-free when we run additional tests. See the following files for the details:

Maintenance

If this program were actually put into real use at a company or sold as a product, there would undoubtedly be calls for maintenance. Perhaps what we thought to be an error-free program is not so at all, so that newly-discovered errors have to be fixed. Users might also call for new features, such as the ability to save the data between separate uses of the program. (This would require the use of files.)

Documentation

We have created a fair amount of documentation above. Look at all that has been written down in the above stages, as well as the structure charts that were drawn. Plus there is the internal documentation, the comments included in the code itself. This material would all be saved to assist the maintenance programmers who might work on this project. For a larger program a user's manual and/or a reference manual might also be written.