Courses/CS 2114/Lab Manual/Structures

From A-State Computer Science Wiki
< Courses‎ | CS 2114‎ | Lab Manual
Revision as of 17:07, 17 April 2019 by Gidget (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Structures

Introduction

A structure is a collection of data of different types contained in an aggregate unit; compare this to the vector, which is a collection of data of the same type. This lab will examine the utility of structures and how they can be used to replace the parallel vectors containing associated data.

Topics Covered in this Lab:
  • definition of structure types
  • instantiation of structure variables
  • manipulation of the data in a structure
  • passing structures to functions
  • vectors of structures
Questions Answered in this Lab:
  • What is a struct and how is it useful?
  • How are the data members of a structure accessed?
  • What kinds of data members can a structure contain?
  • What is the best way to pass a structure to a function? Why?
Demonstrable Skills Acquired in this Lab:
  • ability to define new structures
  • ability to access and manipulate structure data
  • passing structures to functions by reference and by constant reference

Parallel Vectors

Download the spParallelVectors.cpp program file from the course's Class Assignments section on Blackboard.

Consider the information to be stored: names, identification numbers, and exam scores, all of which are provided as input to the program, as well as average and grade, which are to be calculated, are to be stored for each student taking a course. Place the following example data in file spStudentData.txt (or download the file from the course's Class Assignments section on Blackboard).

Green    11111111   61 62 64
Fox      22222222    0 20 34
Ebert    33333333   71 72 74
Downs    44444444   91 92 94
Charles  55555555   51 52 54
Harris   88888888   41 42 44
Baker    66666666  100 99 94
Able     77777777   81 82 84
zzz

Parallel vectors will be required for names, identification numbers, and scores; additional parallel vectors will store averages (computed from the scores in the data file) and letter grades (computed in turn from the averages, based on a 90-80-70-60 scale). The resulting set of parallel vectors defined in function main:.

Verbatimcode.pngCode Illustration
   vector<string>      names;
   vector<int>         idNumbers;
   vector<vector<int>> scores;  
   vector<double>      averages;
   vector<char>        grades;

The following prototypes define the interfaces of the functions that will be used in the program. Note the use of const to designate parameters which will not be altered by their functions.

Verbatimcode.pngCode Illustration
void readAndCalculate
        (istream& infile, vector<string>& names, vector<int>& idNumbers,
         vector<vector<int>>& scores, vector<double>& averages,
         vector<char>& grades);
void write
        (ostream& outfile, string description, const vector<string>& names,
         const vector<int>& idNumbers, const vector<vector<int>>& scores,
         const vector<double>& averages, const vector<char>& grades);
void bubbleSortByName
        (vector<string>& names, vector<int>& idNumbers,
         vector<vector<int>>& scores, vector<double>& averages,
         vector<char>& grades);
void bubbleSortByAverage
        (vector<string>& names, vector<int>& idNumbers,
         vector<vector<int>>& scores, vector<double>& averages,
         vector<char>& grades);

Function main will call function write to copy the data to a file after each of the other functions performs its task.

Note that function readAndCalculate is responsible for retrieving names, identification numbers, and scores from the input file, as well as determining averages and grades. The student information is read and stored in the appropriate vector. Once the scores have been stored, the average and letter grade are calculated and stored as well.

Function write must display seven separate columns of data: a name, an identification number, three separate scores, an average, and a letter grade.

Two bubble sorts (one which sorts by name, the other by average) must handle all of the data for each student. Note that swap functions are now used here for each of the data types to be interchanged. Function bubbleSortByAverage is identical to bubbleSortByName other than the condition of the if statement, which should compare averages rather than names.


Execute the program and inspect file spParallelVectorsOutput.txt to verify that each function is working correctly.

Consider further additions to the data set; examples might include student classification (FR/SO/JR/SR), major (CS/MATH/etc.), cumulative hours, and/or mailing address, among others. How would function readAndCalculate, function write and the bubble sorts need to be changed? The parameter lists for each would grow, functions readAndCalculate and write would have to process the additional data, and the bubble sorts would have more swaps to implement.

The C++ struct

A vector is composed of elements of the same type, such as integers, floating-point values, or characters. A C++ structure is composed of elements of different types; the elements all relate in some manner to a single entity. The elements of a structure are referred to as data members or fields. A structure may contain any number of data members, and these may be any combination of predefined or previously user-defined types. Keyword struct is used to define a structure as in the following example.

Start a program in file spStructuresT.cpp with the following assortment of #include directives, global constant declaration and structure definition.

Verbatimcode.pngCode Illustration
#include <iostream>
   using std::cin;
   using std::cout;
   using std::endl;
   using std::istream;
   using std::ostream;
#include <fstream>
   using std::ofstream;
   using std::ifstream;
#include <iomanip>
   using std::setw;
   using std::setprecision;
   using std::fixed;
   using std::left;
   using std::right;
#include <string>
   using std::string;
#include <vector>
   using std::vector;
#include <algorithm>
   using std::swap;
#include <numeric>

const int NUMBER_OF_SCORES = 3;

struct Student
{
   string      name;
   int         idNumber;
   vector<int> scores;
   double      average;
   char        grade;
};

The struct statement does not set aside any memory for variables; rather, it provides the definition for a new user-defined type (which can subsequently be used itself to set aside memory). The location of the definition of the new type Student is important. It is defined globally at the beginning of the program and so can be seen throughout the remaining code; from this point forward in the program it may be used like the built-in types int, float, double, char, and bool. Note that the structure definition should precede the function prototypes. (It is also possible to define structures within functions for local use only, although this is done infrequently.)

Note the leading upper case ‘S’ of the newly-defined type, used to distinguish Student from a variable identifier, for which convention dictates that the first character is usually in lower case. The identifiers name, idNumber, scores, average, and grade specify the data members of the structure.

Variables of type Student may now be defined and used in any function. Whereas individual members of an array as well as a vector are specified using the array subscript ‘‘[ ]’’ operator, individual members of a structure are specified using the member select ‘‘.’’ operator. Add the following to function main.

Verbatimcode.pngCode Illustration
   Student s1;
   s1.name      = "Smith";
   s1.idNumber  = 12345678;
   s1.scores.push_back(90);
   s1.scores.push_back(91);
   s1.scores.push_back(92);
   s1.average   = (s1.scores[0] + s1.scores[1] + s1.scores[2]) / 3.0;
   s1.grade     = 'A';
   cout << s1.name << ' ' << s1.grade << endl;

The variable s1 contains seven separate pieces of information: a name, an identification number, three exam scores, an average, and a letter grade; in some ways, all of these pieces of information may be treated as one. Add the following to function main.

Verbatimcode.pngCode Illustration
   Student s2 = s1;  // member-wise copy
   cout << s2.name << ' ' << s2.idNumber << ' '
        << s2.scores[0] << ' ' << s2.scores[1] << ' ' << s2.scores[2] << ' '
        << s2.average << ' ' << s2.grade << endl;

The cout statement illustrates that all seven component pieces of data are copied from structure s1 to s2 in what is referred to as a member-wise copy. This aspect of structures makes them well suited to simplify programs that would otherwise use parallel arrays or vectors.


A Vector of Structures

Add the following declaration to function main.

Verbatimcode.pngCode Illustration
   vector<Student> cs2183;

Recall that a vector definition does not reserve storage, it only establishes the type of data that the vector will store. The identifier cs2183 will be used to access multiple Student structures. The vector cs2183 will hold information for all of the students in the course.

Four functions were developed to handle parallel vectors: readAndCalculate, write, bubbleSortByName and bubbleSortByAverage. New versions of these functions will be developed to work with a vector of structures rather than a collection of parallel vectors. Add prototypes for the new functions following the definition of structure type Student.

Verbatimcode.pngCode Illustration
void readAndCalculate(ifstream& infile, vector<Student>& csCourse);
void write(ostream& outfile, string description, const vector<Student>& csCourse);
void bubbleSortByName(vector<Student>& csCourse);
void bubbleSortByAverage(vector<Student>& csCourse);

Add the following function main. Note that the new same-purpose functions are invoked in the same order as that used for parallel vectors, so the expected output should be the same, too.

Verbatimcode.pngCode Illustration
int main()
{
   ifstream infile("spStudentData.txt");
   if(!infile)
      cout << "Error opening input file." << endl;
   else
   {
      vector<Student> cs2183;
      readAndCalculate (infile, cs2183);
      infile.close();
   
      ofstream outfile("spStructuresOutput.txt");
   	write (outfile, "Pre-Sorting w/ Structures", cs2183);

      bubbleSortByName (cs2183);
      write (outfile, "Structures Sorted by Name", cs2183);

      bubbleSortByAverage (cs2183);
      write (outfile, "Structures Sorted by Average", cs2183);	
   }
   	
   return 0;
}

Function readAndCalculate is the first to be modified to work with structures rather than parallel vectors. The body of this function will be identical in length and form to that used with parallel vectors; note that the header of this function has traded the five parallel array entries for one vector of structures. Complete this new function now.

Pseudocode.pngPseudocode
void readAndCalculate(ifstream& infile, vector<Student>& csCourse)
{
   string name;
   infile >> name;
   while (name != "zzz")
   {
      // create a single instance of the Student structure
      // store student's name in the single Student structure
      // get id number and store in the single Student structure
      // get individual scores & sum them; store the individual scores in the single Student structure
      // calculate the average and store in the single Student structure
      // assign letter grade based on average
      // add this single Student structure to the vector csCourse
      // get the next name
   }  
}

The changes to function write are similar to those made to function readAndCalculate. Make them now.

Verbatimcode.pngCode Illustration
void write(ostream& outfile, string description, const vector<Student>& csCourse)
{
   outfile << description << endl;
   for each student in the csCourse vector
   {
      /* output the student's name left aligned in a column of width 10
         followed by the student's id number, each of the individual 
         exam scores (each score in a column of width 4), the
         average of the scores (with a single decimal place in a column of width 7)
         and the letter grade based on the tradition 90 - 100 A scale
   }  
   outfile << endl;
}

Unlike functions readAndCalculate and write, the two bubble sort functions are considerably shorter for a vector of structures than they would be for a set of parallel vectors. The reduced length stems from the ability to assign structures to one another in C++; the tedious swap of elements in each of the individual parallel vectors can be avoided in favor of a single swap of structures. Create the new function bubbleSortByName now.

Pseudocode.pngPseudocode
void bubbleSortByName(vector<Student>& csCourse)
{
   vector<Student>::size_type pass = 0, // the data has not been examined yet
                              numberOfStudents = csCourse.size();
   bool swapOccurred;
   do
   {
      swapOccurred = false;
      for // pair = 0 to one less than numberOfStudents-1-pass
         if // current student's name > next student's name
         {
            // swap the student structures;
            swapOccurred = true;
         }  
      ++pass;
   } while (swapOccurred);
}

The new function bubbleSortByAverage is identical in all places but the comparison. Add it as well.

Note that is possible to send a single structure to a function such as in the swap function call. Since even a single structure could possibly hold a large amount of data, structures should be passed by reference. When writing a function that accepts a structure as a reference, the const keyword should be used when the function should not be able to alter the data stored in the structure.

Execute the program and verify that the results obtained using an array of structures are identical to those obtained using parallel vectors.

Adding to the Data Set

It should be apparent at this point that structures can greatly simplify certain aspects of dealing with large amounts of data. To emphasize this point, create a new data set in file spExtendedStudentData.txt as follows (or download the file from the course's Class Assignments section on Blackboard).

Green     11111111 FR  28.0  61  62  64 CR
Fox       22222222 SO  40.5   0  20  34 CR
Ebert     33333333 SO  35.0  71  72  74 AU
Downs     44444444 FR  16.5  91  92  94 CR
Harris    88888888 JR  72.0  41  42  44 CR
Baker     66666666 SR 120.0 100  99  94 CR
Able      77777777 JR  69.5  81  82  84 PF
Charles   55555555 FR  29.0  51  52  54 AU
zzz

The additional data consists of a class ranking (FR/SO/JR/SR), a floating point number of credit hours, and a grade option (CR=credit/AU=audit/PF=pass-fail); the class ranking will follow the identification number, the credit hours will follow the class ranking, and the grade option will end the record. Revise both the parallel vectors program and the vector of structures program to accommodate this additional data. In so doing, observe that the functions for reading and writing are similar in all but their parameter lists; on the other hand, while each bubble sort for parallel vectors must increase its parameter list and number of swaps, each bubble sort for a vector of structures is literally unchanged.