Com S 228 --- Introduction to Data Structures

			     HOMEWORK 9:
		      Pointers and Dynamic Data
		 (File $Date: 1995/03/28 19:32:27 $)

Due: problems 3-5, at the beginning of lecture, March 28
     problem 8, at the beginning of your discussion section week of March 30
     problem 9, at the beginning of lecture, April 3

In this homework, you will learn about pointers and dynamic data

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.)


DEITEL & DEITEL:  5.1-3, 5.5, 5.7-12

I'm suggesting reading from the DD book first, because it's more low-level,
and so may help you get over the C++ details before going on to what Headington
and Riley are trying to use them for.  However, only read the DD material
if you have time to read both it and the readings from the HR book.
Note however, that DD are not as careful as I am about distinguishing the
concepts of "pointer" and "pointer variable".  Also, don't get bogged down
in the details they present.

1. (suggested practice)
   Do some of the exercises in the self-review sections on pages 321-323
   of Deitel & Deitel's book.  I suggest working exercises 5.1-7
   on paper.  Do what parts seem useful to you, then look at the answers,
   which follow the self review sections on pages 323-324.


HEADINGTON & RILEY: 7.1-5

2. (suggested practice)
   Do some of the exercises in Headington and Riley's book for chapter 7
   (pp. 335-338).  I suggest *at least* exercises 7.1, 7.2(a,c,e,h),
   7.3(a), 7.4(a,b), and 7.8.  Do what parts seem useful to you,
   then look at the answers, which are at the end of the book,
   in pages A-178 to A-179 for these problems.

3. (20 points) 
   On paper, do exercise 7.3, parts b and c on page 336 of Headington
   and Riley's book.  Clearly label each part.

4. (10 points)
   Do exercise 7.4 on page 336 of Headington and Riley's book,
   and write a test harness for it.  This is to be done (ultimately)
   on the computer.  That is, put the function call in a main program.
   Hand in a printout of the main program (with the rewritten function call),
   the rewritten function Divide, and your test output.

5. (40 points)
   Implement the strcmp function as specified on page A-128 of HR appendix G,
   without using the strcmp (or strncmp!) functions of the <string.h> library.
   You are to write this function in two ways:
   (a) treating the formal parameter as an array and using array notation
       (see Figure 7.9, alternative 1),
   (b) treating the formal parameter as a pointer and using * and pointer
       arithmetic (see Figure 7.9, alternative 2 or 3).

   Now do the same for the strstr function as specified on page A-130 of HR
   appendix G, without using the strstr functions of the <string.h> library.
   However, the prototype listed there is wrong, and should be altered
   to have a const before the first char, so that it reads:
	const char* strstr(const char *str, const char subStr)
   Again, you are to write this function in two ways:
   (c) treating the formal parameter as an array and using array notation
   (d) treating the formal parameter as a pointer and using pointer arithmetic.

   If you have trouble understanding the specifications, try using the real
   functions from <string.h> in your test harness, or
   use them as a test oracle.  See also appendix B.12 of the DD book.

   As usual, hand in a printout of your code, test harness, and test output. 

6. (50 points; extra credit only)
   Do exercise 5.35 on page 339 of Deitel and Deitel's book (pig latin).

HEADINGTON & RILEY: 7.3

7. (50 points; extra credit only)
   Do programming project 7.4 on pages 338-340 of Headington and Riley's book.
   This project shows you how to deal with command-line arguments in Unix
   (and other operating systems).

HEADINGTON & RILEY: 7.6-7.8

8. (50 points)
   For this problem you will implement some of the module specified
   in the file String.h, found in the directory /home/cs228/public/include.
   You'll need to supply the files String.pri and String.C
   for the implementation, as well as a test harness.
   (You can copy the file String.h and modify it slightly if you need to,
   but I don't think you will need to do that.)
   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.)

   For this problem, you are to implement and test the following
   constructors, member functions, and functions:
	String();
	String(char c);
	String(const char* s);
	String(const String& str);  // copy constructor
	~String();
	int Length() const;
	char operator [](int i) const;
	void SetChar(int i, char c) const;
	ostream& operator << (ostream& out, const String& str);

   *Don't* provide implementations for or test the following:
	String& operator = (const String& str);
	String Substring (int start, int end) const;
	int Find(const String& str);
	Boolean operator < (const String& str2) const;
	Boolean operator > (const String& str2) const;
	Boolean operator >= (const String& str2) const;
	Boolean operator <= (const String& str2) const;
	Boolean operator == (const String& str2) const;
	Boolean operator != (const String& str2) const;
	String operator + (const String& str2) const;
	char * ToCppString() const;
        void AddChar(char ch);
   (Please *don't* bring them to class, because they are part of the
   next problem.)

   Although it is possible to implement the String class using an object
   of a modified version of IntVec class as the only data member,
   don't do that for this problem, as it won't provide as good practice
   with pointers and dynamic data.  Instead, one of your private
   data members should be a pointer variable.

   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 abstraction map comment and the class invariant that go in String.pri,
   and to the concrete pre- and postcondition comments in String.C.
   (See /home/cs228/public/docs/assertion-notation.txt and HR appendix D
   for details.)  As usual, we won't check the details of your work,
   because that will be the subject of the discussion.
   So don't worry (too much) if it isn't exactly right (see problem 9).
   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).

   (Note: you are allowed to discuss coding details with class members
   in more detail than the course policies would normally allow,
   but only during your discussion section time.  Outside of that time,
   exchanging such code details is considered cheating.)

9. (100 points)
   For this problem you are to complete the implementation of the module
   specified in the file String.h, found in the directory
   /home/cs228/public/include.
   You'll need to complete the files String.pri and String.C
   for the implementation, as well as a full test harness.

   What you hand in should be a *complete* implementation with complete
   testing of the String module.  It should include all the necessary
   specification comments.  In other words, build on the work you
   did in the previous problem, but hand in everything, even what you handed
   in before.  (This gives you a chance to correct errors.)

10. (suggested practice)
   Implement String using a modified version of the IntVec class.
   You'll have to modify IntVec to something like CharVec, so that it stores
   characters.  This implementation would have just one data member,
   of the class CharVec.  You might want to review HR section 3.4 for this.

11. (suggested practice)
   Specify and implement an overload of operator >> for Strings.

12. (40 points extra credit)
    Do exercise 5.35 on page 339 of Deitel and Deitel's book (pig latin),
    as a *client* of your String class.  Don't add any more member functions
    to your class for this.  You'll need to implement something like strtok
    as a client of your String class.

13. (50 points extra credit)
    The String class specified in String.h requires the implementation to
    check for subscript errors.  Of course, a client of this class is also
    going to try to program the class so that such errors never occur,
    which may lead to duplication of checking at runtime.
    (a) Why is this problem worse if your implementation of String is
    using CharVec as in problem 10?
    (b) Specify and implement a class UncheckedString that is like String,
    but does no error checking at runtime.  The specification is very important
    in this problem, be sure it's different and doesn't specify run-time
    checking.
    (c) Reimplement String using a single data member of type UncheckedString.

14. (100 points extra credit)
    Read about inheritance, and implement String as a class privately derived
    from UncheckedString.  Write the minimum amount of new code in the
    implementation of String.  You'll have to change the String.h file
    for this.