CS
APA - Lesson
25 - Structures
INTRODUCTION:
A structure is an organizational tool which
allows for grouping of related values that describe an
object.
An array permits quick random access of
large amounts of data, but it is restricted to storing
one data type. A
structure will allow us to group together different
types of data. By
combining an array's random access abilities with a
structure's ability to store different data types, we
can build very powerful data structures.
The key topics for this lesson are:
A. Structures
B. Overloading the Output Operator (<<) with Structures
C. Structures vs. Classes
D. An Array of Structures
VOCABULARY: STRUCTURE STRUCT
HETEROGENEOUS AGGREGATE
DISCUSSION: A. Structures
1. A structure is a user-defined data type which organizes collections of values having the same or different data types. A structure is characterized as a heterogeneous aggregate.
heterogeneous - of different types
aggregate - a collection of pieces into a mass or sum
2. A structure will be used to model objects which require multiple values, usually of different data types. An example is the information printed on a driver's license. Most of the data types are strings, but weight is stored as an integer, and your birthday could be stored using a date class.
3. Here is a different example to store information about a person.
struct infoType
{
apstring name;
int height; // inches
int weight; // lbs
}; // <--- notice the semicolon
4. The above definition does not allocate any variables; it defines a new data type called infoType. The definition must end with a semicolon after the closing brace (}).
5. We can now use this new data type to declare structures.
infoType player1;
The variable player1 looks like this in memory:
6. The data members in a structure are by default public. They can be accessed using the same dot notations as used with classes. To assign the values shown above requires this type of syntax:
player1.name = "Michael Jordan";
player1.height = 78;
player1.weight = 200;
7. Assignments can be made between two structures having the same type. In this example, all three data members are transferred in one line of code:
player2 = player1;
B. Overloading the Output Operator (<<) with Structures
1. It is useful to overload the output operator (<<) to print data members of a struct. For example, using the struct from above Section A-3, we could print out each data member using individual cout statements.
cout << player1.lastName << " ";
cout << player1.firstName << " ";
cout << player1.height << endl;
2. But it would be very convenient to be able to write statements like
cout << player1 << endl;
You might recall that the above statement is processed from left to right.
(cout << player1) << endl;
The result of the (cout << player1) statement is the ostream cout, which allows the next statement to be chained, cout << endl.
3. It is possible to overload an existing operator in C++ to handle new data types. We need the output operator to be ready to process an ostream and an infoType struct. Here's the code:
ostream & operator<< (ostream & Out, const infoType &temp)
{
Out << temp.lastName << " " << temp.firstName << " ";
Out << temp.height;
return Out;
}
4. When the statement cout << player1 << endl; is processed, the first statement (cout << player1) is executed. Within the function call of operator<<, Out becomes an alias for cout, and temp becomes an alias for player1. The three fields of player1 are printed to Out (cout), and the function returns Out (cout) to allow for chaining.
C. Structures vs. Classes
1. Classes are used in C++ to implement abstract data types in which the inner workings and data of the abstract data type (ADT) are kept hidden from the user. Any manipulations of the object's data must be done through a tightly defined interface.
2. A structure is similar to a class, but is used mainly to organize related data. The data members in structures are public by default and usually do not include any member functions.
3. Whereas a class encapsulates both data and behaviors together, a structure is typically used to organize data only.
4. Working with structures is easier, but the use of a specific structure is typically limited to one program. A class is used to implement an abstract data type which is used in multiple programs.
5. Structures can have constructors and member functions. Struct constructors will be very useful when working with linked lists and binary trees.
D. An Array of Structures
1. A very useful combination of data structure tools is an array of structures.
|
See Handout H.A.25.1, ages.cpp. |
2. The handout H.A.25.1, ages.cpp, contains the source code of an example program using an array of structures. The definitions at the top of the program are repeated here: |
struct student
{
apstring lastName;
apstring firstName;
int age;
};
struct listType
{
int number; // how many people are in the list
apvector <student> list;
};
3. The structure student contains 3 values: 2 strings and an integer. The larger structure listType contains an array of student and an integer number. Notice the semicolons which complete each structure definition. At this point no variables have been declared, only definitions. The data structure will be declared in function main as data. Here is a diagram of the variable data.
4. This program keeps track of the first and last names of people and their ages. When the structure data is declared in function main the size of the array list is 0. The first function called is loadFile which loads a text file called names.txt. For the sake of discussion assume names.txt has this content:
"names.txt"
4
Smith
Tom 25
Jones
Susan 58
Lee
Cindy 33
White
John 18
5. The function loadFile will initialize data with information from disk.
a. The function receives the pathway to the text file on disk as an apstring. The apstring needs to be converted to a C-style string to work with the open command. The ifstream inFile is an alias for the text file "names.txt."
b. The structure temp consists of two data members, number and list. The statement,
inFile
>> temp.number;
reads the 4 from the first line in names.txt and stores it in temp.number.
The variable temp.list is an apvector which supports the resize command. The statement
temp.list.resize (temp.number);
resizes the array to hold 4 student structures.
inFile
>> temp.list[k].lastName;
reads a string and stores it in the kth position of the array list, in the data member lastName of the student structure stored in temp.list[k].
6. Adding new people to the list is accomplished by the use of two functions, doAddStudent and addStudent. Inside of doAddStudent a local student is declared and filled from the keyboard. This function in turn calls addStudent, which resizes the array and adds the new data into the data structure. At all times during the life of the program, the structure data (declared in function main) and any alias version of it will know and keep track of the number of students within its array.
7.
The quickSort
and swap functions were modified to work with a
new data type called student.
The list of people in the data
structure will be ordered in ascending order based on
the last name. Notice
in the original call of quickSort
in function main,
the parameter call is
quickSort (people.list, 0, data.number-1);
which sends the index values 0 and data.number-1
as the boundaries of the array.
8. Finally the structure is saved again to disk including any additional data added to the structure. Saving is the exact opposite of loading the text file from disk.
SUMMARY/REVIEW: The strategy of nesting structures inside arrays which in turn are nested inside other structures is a powerful organization tool. Combinations of arrays, classes, and structures provide excellent tools for organizing and manipulating data.
ASSIGNMENT:
Lab Exercise, L.A.25.1, Store