Com S 228 --- Introduction to Data Structures

			     HOMEWORK 8:
			C++ structs and unions
		 (File $Date: 95/03/09 21:01:44 $)

Due: problem 2, at the beginning of your discussion section week of March 23

In this homework, you will learn about C++ structs and unions.

PLEASE NOTE: For each programming problem, hand in a printout of
your code files, and your transcript of testing.
Your code must only use standard features of C++,
and your transcript must demonstrate that it would work on the Com S machines.
We recommend testing on the Com S department machines to ensure this
(use the Unix command ``script'').
Your transcript and each file you print should have the file name
and your information (your ~/.me file as in HW0) at the top as comments.
You must use comments as we are doing in class
(see /home/cs228/public/assertion-notation.txt for details).
We are grading on these comments now.

For additional practice, we suggest that for at least some of the problems,
you write out a solution on paper first.  This is more like what the test
will be.  When you are happy with your paper version, try it on the
computer.  (Note that you must hand in a printout and a transcript, however.)


HEADINGTON & RILEY: 5
(Supplementary reading from DEITEL & DEITEL: 16.2-4, 18.12)

1. (suggested practice)
   Do some of the exercises in Headington and Riley's book for chapter 5
   (pp. 230-235).  I suggest at least exercises 5.1(a,c,e,h,j), 5.2(a,c,e),
   5.3(a,c,f,i), 5.4(a,c).  Do what parts seem useful to you,
   then look at the answers, which are at the end of the book,
   in pages A-176 to A-177 for these problems.

2. (50 points)
   Do programming project 5.4 on pages 235-6 of Headington and Riley's book.
   The phonebk.h file is in /home/cs228/public/HR; you'll need to supply
   the files phonebk.pri and phonebk.C for the implementation,
   as well as a test harness.  You may copy phonebk.h and modify it if needed.
   The file "bool.h" included by this file is in /home/cs228/public/include.
   (So as in previous homeworks, you can
   compile with the flag -I/home/cs228/public/include to get the header files.)

   Hand in a printout of your testing and the program files.

   In your discussion section, you'll discuss your solution
   with another class member, and will have an opportunity
   to ask questions and discuss solutions with the class as a whole.
   So be sure to write your code clearly, and pay particular attention to
   the specification comments.  We won't check the details
   of your work, as that will be the subject of the discussion.
   So don't worry (too much) if it isn't exactly right.
   We will check that what you hand in has the right parts
   (a printout of each file, labeled correctly with comments at the top,
   and a transcript).

3. (40 points extra credit)
   Do programming project 5.2 on page 234.

4. (50 points extra credit)
   Variant records are still somewhat unsafe, because clients can ignore the
   tag (or type) field and access fields that aren't really there.
   Show how to use what you already know about C++ to enforce
   restrictions on variants, so that clients can only access fields that
   are supposed to be there, based on the tag field.  Code an example
   of your solution, and a test harness.

Unix MANUAL PAGE FOR gprof

5. (30 points extra credit)
   Finish the selection sort program in /home/cs228/public/examples/selsort.
   Be sure to use lots of functions. Then compile your program it with the
   flag:
	-pg
   to allow profiling.  When you run your program you will get a file gmon.out
   written in the directory where the program resides.  Use grof to
   get the profile output from the function:
	gprof selsort.exe >profile-output.txt
   Hand in: a printout of the makefile you used, the profile-output.txt output,
   and an answer to the question: where does the program spend most of its
   time?