Using structs to solve problems

Let's first work through some of the problems at the end of these notes and feel a little bit more comfortable with using structs to get things done in programs.

It's worth noting that structs and bottom-up programming are a natural fit. You want to write a program that's going to have to deal with 2D points? So you implement a nice 2D point struct with all sorts of helpful funtions to read, write, add and compare points. Later you can go and use all this nice functionality to solve whatever particular problem you had to solve.

Structs that contain arrays

Suppose we have a file namedgrades.txt, which contains student grade information. The file looks like this:
11 students
10 homeworks
Adams	58	96	65	72	93	67	59	74	95	56
Brown	96	67	56	74	94	100	98	68	95	65
 ...  
telling us initially how many students we have, how many homework scores for each student, and then listing all the student names followed by their homework scores.

Now, I'd like to write a program that works as follows:

Now, assuming there are Ns students and Nh homeworks, the natural way for us to think of this is to say "I'd like to have an array of Ns objects of type Student." We know how to construct a struct Student, so that's no problem, but what data members would we need to store this student data? We'd need a string to store the name, and we'd need ... well, we'd need an array of Nh ints to store the homework grades. In other words, we'd need a data member of type int*.


struct Sudent
{
  string name;
  int* hw;
};

Packaged up this way, an object of type Student representing the student "Brown" from above would look like the picture above. Now, the question is, if variable S is the Student object from the picture, what expression would give me the value of the homework assignment with index 2? Well, S.hw is the name of the pointer to the array of grades, so I just need to subscript it with a 2: S.hw[2]! I might be tempted at this point to look back at my original problem and say that I'll create my storage for all this student/grade data with:
Student* stu = new Student[Ns];
Quick check

Consider the code on the left.

  1. What is the type of stu?
  2. What is the type of stu[j]?
  3. What is the type of stu[j].hw?
  4. What is the type of stu[j].hw[0]?
Answers are given below (drag your mouse):
1. Student*  2. Student  3. int*  4. int
It's true that stu is now an array containing Ns object of type Student, but remember that each Student object has data member hw, which is just an uninitialized pointer at this juncture. We need to go back and allocate homework-grade arrays for each Student object in the array. So creating our storage really looks like this:

Student* stu = new Student[Ns];
for(int j = 0; j < Ns; j++)
  stu[j].hw = new int[Nh];
At this point, writing the program is not very new for us: Here's my solution. All I did was use the top-down design that we've seen so many times. I simply wrote the main function the way I wished I could, and created the structs and functions that made writing main that way possible.

What assignment and pass-by-value mean with structs

If A and B are objects of type Foo, where Foo is a struct. The assignment statement
A = B;
results in what's called "member-wise assignment". This means that the assignment proceeds by going through each data-member of A and assigning that data member the value of the same data-member in B. So, if A and B are objects of type Student from the above example,
A = B;   is the same as     A.name = B.name; A.hw = B.hw;
You have to think about the consequences of this. After A = B, the pointers A.hw and B.hw have the same value ... that means they both point to the same array! This may not be what you expect. Because of this, for example, the line
A.hw[5] = 100;
results in both A and B having 100 for the index 5 value of their hw data member.

The same holds true for pass-by-value with structs: you get member-wise copy. So, when you have structs with data members that are pointers, the pointers get copied but the actual array pointed to stays the same. Think carefully of the consequences of this!

Composition of structs

Imagine a scenario in which we are performing experiments with cockroaches. We'll suppose we get data readings for other roaches that give us a time in [hh:mm:ss] format, and a position in (x,y) coordinates. For example, trial.txt. We want the user to be able to enter a time in [hh:mm:ss] format and we'll tell him where the roach is (i.e. en route between which two points).

We've dealt with points before, and we will again, so let's go ahead and give the basic struct definition & function prototypes for points:


//--- POINT ---------------------------------//
struct point
{
  double x, y;
};
void read(point &p, istream &IN);
void write(point p, ostream &OUT);
Now, while we may not have dealt with times in hh:mm:ss for a while, it is not unlikely we'll have to deal with such things again. Therefore, it is natural to give a struct definition and some prototypes for an hhmmss struct:

//--- TIME IN HH:MM:SS ----------------------//
struct hhmmss
{
  int h,m,s;
};
void read(hhmmss &T, istream &IN);
bool before(hhmmss a, hhmmss b);
Now, a data reading consists of a time and a position, so it might be nice to have a datum struct that records a single data reading. It'd look something like this

struct datum
{
  point position;
  hhmmss time;
};
... and I'd probably want a function void read(datum &D, istream &IN); to read in such objects.

With all of this (and with all these functions defined!) writing my main function is not too difficult:

// Read and store data readings
datum* A = new datum[N];
for(int i = 0; i < N; i++)
  read(A[i],IN);

// Get the query time from the user
hhmmss T;
cout << "Enter a time: ";
read(T,cin);

// Find the first sighting at or after given time
int k;
for(k = 0; k < N; k++)
{
  if( before(A[k].time,T) == false )
    break;
}
Then it would just remain to write out the information to the user. Take a look at this complete program. There are several important things to look at here:
  1. I used bottom up design to solve this problem. I started off with the pieces (structs and functions) that I knew I could define easily, and that I knew would come in handy here and probably in other programs as well. Then I started to put these pieces together to create a program.
  2. My datum struct contains as data members two other structs I defined --- point and hhmmss. This is called composition of data types. We've already been doing this, of course, in having data members that are of type string.

Problems

  1. Be the bank! Write a program that manages account information for a simple bank. You have the file BankAccts.txt, which lists all your bank account information at the beginning of the year. You also have the file Transactions.txt, which lists all the deposit transactions for the year, each transaction consisting of a line giving the date, the account number, and the $'s deposited. Your program should print out an end of the year report that lists all the accounts with their account numbers, owner name, and end of year balance in exactly the same format as used in the input file Here's my solution.
  2. In HTML, colors are specified by a "number". for example, yellow is specified by the "number" #FFFF00. And you can color words using this. For example, if I want to Write "Hello", in HTML (i.e. Hello with a yellow H on the front), I use the following HTML:
    <font color="#FFFF00">H</font>ello
    The file colors.txt contains a list of number/names. Write a program that reads in this file, allows the user to enter colors and words, and finally produces an HTML file that writes those words in those colors. Example:
    Enter color and word, or quit: Blue  Somewhere
    Enter color and word, or quit: Green over
    Enter color and word, or quit: Aquamarine the
    Enter color and word, or quit: Gold rainbow
    Enter color and word, or quit: quit 
    With this, your program should create an html file like this.
  3. Write a program that reads in points from the file points.txt and writes out the lower left and upper right coordinates of the smallest rectangle containing all the points from the file. Here's My Solution.