Lab 5: CPS100e: Pointers, Searching, Animals

Introduction

Change into your cps100e directory and create a lab5 subdirectory. Then change into this and copy files by typing what's below (don't forget the trailing dot).

      cp ~ola/cps100e/lab5/* .

If you type "ls" you should see the following files: Makefile, dophone.cc, cdread.cc, and animals.cc.

First make a link to several text data files. To do this type

    ln -s ~ola/data data

Then you'll be able to use the directory data to access several big text and data files.

Searching Phone lists

Use the emacs commands C-x C-f to find/load the file dophone.cc. Then compile this command using C-x c and type make dophone in the minibuffer. You'll be prompted for the name of a file. Enter data/phone.dat and the program will load a list of 5,961 1-800 phone numbers in North Carolina. You'll then be prompted for a number of searches. Enter 1500 searches. This will cause the program to search for the first number, the second, the third, etc., using two different searching methods: sequential and binary search. Run the program again and make 2500 searches.

How long does it take for 2500 searches using sequential search? _____________________? Using binary search __________________________?

The for loops in main that control the searches run from 0 to limit. Change these loops so that they run from count downto limit. Run the program again for 2,500 searches. Do the times change (significantly) from what you noted before? How do you account for this?

Pointer Stuff

Now load the file cdread.cc, compile it, and run it. This reads the same kind of information about CD's that was used in another program. All the struct and class definitions are included in one file rather than in a .h and .cc file.

When prompted for the name of an input file, enter data/minicd.dat. This file contains information for 2006 CD's. The lines for printing the CD's are currently commented out. The program reads CD information, and, during the reading, stores each CD into the proper position according to title. This is done by ``sliding'' CD info to the right until the correct location for the CD is found. Selection sort is used to sort the CD's by group name. How long does it take to read the file of 2006 CD's ___________________? How long does it take to sort the file _____________________? Can you think of a reason for this difference?

Copy the file cdread.cc to a file cdread2.cc. To do this use the Unix cp command:

    cp cdread.cc cdread2.cc

Now load the file cdread2.cc into emacs. You'll change the definition of the Vector defined in the Collection struct so that is stores pointers to CDinfo objects rather than CDinfo objects themselves. Make this change to the definition:

       Vector<CDinfo *> myList;        // array of CD information

by adding an asterisk as shown so that list is a vector of pointers.

Try to compile the program. You'll get an error message like the one below.

cdread2.cc:89: request for member `title' in `this->Vector<CDinfo
*>::operator [](int)((k - 1))', which is of non-aggregate type `CDinfo *'

To get to the line with the error on it, type C-x ` (that's the back-quote mark). You can also type C-x g and then the number of a line, to go to a specific line.

This means that CDinfo * is a non-aggregate or non-struct type. Rather than use a dot to access a field of the struct, you must use an arrow -> to get to the struct that is pointed to by myList[k-1]

      0 < k && title < myList[k]->title;

Make this change. Type C-x ` to go to the next error (something about cannot convert CDinfo...). Here you'll need to create memory for the pointer to reference. Add the word new as shown below.

     myList[k] = new CDinfo(atoi(num),title,atof(price),group);

Type C-x ` to go to the next error ( request for member `group' ...). You'll need to change the "." used to access the group field to an arrow -> for the pointer to work.

Type C-x ` to go to the next error. This error is due to the improper definition of temp. Change the definition so that temp is a pointer:

    CDinfo * temp;

Then recompile the program. It should compile successfully; if not, ask for help or make the changes needed to make it compile. Run the program using data/minicd.dat as data. How long does it take to read the data now ______________________? to sort the data _____________________________? (If you print the CD information it won't print properly. You'll need to change the myList[k] in the Collection::Print function to *myList[k] --- don't worry about this for now.)

Try to provide a reason for the change in time when pointers are used.

Indirect indexing and pointers

In the current program, the list is read in and kept sorted by title, then re-sorted by group (losing the sorting by title). For this part of lab you'll make it possible to keep the list of CDs sorted both by title and by group. Add a new field to the Collection struct

     Vector<CDinfo *> myGroups;        // indirect group pointers

to construct myGroups you'll need to add something in the the Collection constructor to construct the Vector myGroups as shown below.

Collection::Collection(int size) : myList(size), myGroups(size)

The idea here is to use the pointers in myGroups to indirectly reference the CD info. The pointers stored in myList will NOT change when the list is sorted, instead the pointers stored in myGroups will change. To do this you'll need to do three things.

Initialize the pointers in myGroups . Do this as the last thing in Collection::Read , use a loop to set myGroups[k] = myList[k] for all elements in myList . Now there are two pointers pointing to each CD info struct.
Change the code in SortGroup so that instead of using myList it uses myGroups . This is just a text change of all occurrences of myList to myGroups in the member function SortGroup.
Add another loop in the member function Collection::Print. Print all the CDs using *myList[k] (as is done in the version provided but you must add the *). Then write another loop to print using *myGroups . Add a line of output before printing the sorted-by-group list, something like "list sorted by group follows". You might want to test the program using data/smallcd.dat which has only 22 CDs in it, this will make it easier to see that both "sorts" work.

Extra Credit: Animals

Load the program animals.cc into emacs, compile it and run it. The program will print something different each time it is run (it uses the Dice class). This program uses the concept of inheritance to create new kinds of students. There is a default, normal student and a geeky student. To earn extra credit, create a new class that represents some other kind of student. Name the class appropriately and model it after the Geek class shown in the program. The member function Behavior should ``act differently'' for the new student, as should the function Fun. You'll need to add another if statement in main to account for the new kind of student --- based on the roll of the dice object you'll want to create an object (that will be pointed to) of your new class type.

Submission

To turn in programs: When your modified programs works, you can submit it, along with a README describing how long it took you and what your impressions of the lab are. Type (where N is your section number: 1, 2, or 3):

      submit100e lab5secN README cdread2.cc animals.cc

The README file should include your name, how long you worked on the program, and anyone you received significant help from. You should also include any comments you have about the lab.

You should receive a message telling you that the programs were submitted correctly.