Project 2: CISC181, Spring 2006

Required Reading/Concepts:

• Chapters 1-5 in Savitch, including
  • control structures: if, if/else, switch, while, for
  • functions
  • arrays, including sorting
  • pointers
• Basic concepts of building linked lists (covered in lecture notes)
• Reading from files with ifstream, including reading until eof()
• Writing to files with ofstream
• Using cin.getline()
• C strings, in particular: strtok, strncpy, strcmp

This assignment does not require the use of classes. Classes will be covered in project 3.

Reminders:

• Work independently on this programming project.
• Do not work with another student in the class. If you need help, see your instructor or TA during office hours, or make an appointment if those hours are not convenient.
• Don't wait until the day before the assignment is due to start working. If you wait until then, you'll have no time to go in for help if you get stuck. This assignment is designed so you can pace yourself over several days.

Assignment Description

The original version of this assignment involved developing a program that edits a file of NCAA football teams. However, in order to make the assignment more interesting and personal, I am going to ask each of you to choose his/her own "topic" for the assignment.

You will be writing a menu-driven program that manipulates a file of data related to a given topic. You'll be able to add, delete and lookup items in that list, as well as read the list from a file, and write the list to a file.

Part 0: Understand the assignment, and choose a topic
(Filename: proj2data.txt, 9% of total points, 9% complete when done)

In this part of the project, your job is to understand the big picture of what you are trying to accomplish, choose a topic, and post some general information about that topic on the web. I have put together sample scripts of a completed project involving the topic "NCAA teams." Your job is to review some sample output so that you know what you are aiming to accomplish.

Understanding the Sample Scripts

The program provides the user with a menu of options for maniuplating the file. The menu allows the user to

1. add a team
2. delete a team
3. search for the information for a particular team
4. modify the information for a team,
5. list the teams
6. read the list from a file, and
7. write the list to a file.

You will develop the program as a menu driven program, and you are strongly encouraged to develop it in seven stages. (In fact, when I wrote the program, I wrote it in exactly the stages that I am recommending to you. It took me 3.5 hours to write it from start to finish, so I strongly encourage you not to wait until the day before to start, but rather, to start now, and try to do one stage per day until you are finished. If you keep pace with me, you can do each stage in about 30 minutes; more likely, it may take you a couple of hours for each stage.

So that you can get an idea of what the program is supposed to do, I have put an example script file for each stage in the following directory on strauss:

/www/htdocs/CIS/181/pconrad/06S/work/proj/proj2/sampleScripts

http://www.udel.edu/CIS/181/pconrad/06S/work/proj/proj2/sampleScripts

Understanding the Sample Linked List Code

There is also some sample code in the directory:

/www/htdocs/CIS/181/pconrad/06S/work/proj/proj2/structExample

http://www.udel.edu/CIS/181/pconrad/06S/work/proj/proj2/structExample

Describing a "table of data" related to your topic

To finish part 0 of the project, you are going to describe a table of data related to the "topic" that you have chosen. Rather than give a detailed description of what I'm looking for, it is probably more effective to just show you several examples first.

Some examples

Here are a few example tables for various topics. What you need in each case is at least two "fields" (i.e. two columns) that contain character array data, at least one with integer numberic data, and at least one with floating-point numeric data.

Pizzas with Side Salads (as in the inputExamples programs)

Hiking Trails

Once you've come up with the "columns" for your table, and at least three sample "rows" for your table, you are ready to do the part that you are going to submit for credit.

The first thing you need to do is register your topic on WebCT. So log on to WebCT, go to the CISC 181 honors page, click on Discussions, and go to Project 2 topic registration. FIRST make sure no one else is doing your topic, and then submit a post where you briefly state what your topic is (e.g. "Pizza and Salad orders"). Now you have reserved your topic and are ready to begin the project

First, use the mkdir command to make a new subdirectory under your cisc181 homepage called "proj2". The path of this directory will be something like ~/public_html/cisc181/proj2.

Next, go to your cisc181 homepage html file and make a link to this new directory with something like <a href=proj2>Project 2 files</a>

Now make a new file in the proj2 directory called "proj2data.txt". Inside the file proj2data.txt, you want to document the columns in your table. Here are a couple of examples. The way I've formatted things here isn't the "only" way or the "right" way—this is a file written in English, not computer code, and it will be read by human beings, not a computer program. So format things however you like, as long as the way you write it is clear.

When you are finished writing up your proj2data.txt file, use a web browser and see if you can access your new file from your cisc181 homepage. If not, you might have to use the chmod command make it readable on the web, something like:

chmod a+x ~
chmod a+rx ~/public_html/proj2
chmod -R a+rx ~/public_html/cisc181

Your TA will grade this file based on what is there after you've submitted the other part of your project.

P. Conrad, cisc181 Section 22, proj2data.txt

Topic: Hiking Trails


column 1: hiking trail name
type of data: character
maximum length: 20
can contain blanks: yes


column 2: location
type of data: character
maximum length: 30
can contain blanks: yes




column 3: lengthOfTrail
type of data: float
minimum value: 0
maximum value: 9999.9
units: miles
decimal places to show: 1
calculation: show length of trail in km as well.
decision: if trail is < 5 miles print short, otherwise print long.

column 4: state
type of data: character
maximum length: 2
can contain blanks: no
comments: I'll either avoid trails that are in multiple states,
or I'll divide up multi-state trails (such as the Appalachian Trail)
into segments, one per state.

column 5: timesHiked
type of data: int
minimum value: 0
maximum value: 9999

P. Conrad, cisc181 Section 22, proj2data.txt

Topic: Supreme Court Justices


column 1: justiceName
type of data: character
maximum length: 30
can contain blanks: yes


column 2: appointedBy
type of data: character
maximum length: 30
can contain blanks: yes

column 3: yearAppointed
type of data: int
minimum value: 1776
maximum value: 9999
units: years

column 4: yearBorn
type of data: int
minimum value: 0
maximum value: 9999
units: years

P. Conrad, cisc181 Section 22, proj2data.txt


 Topic: Digital Cameras
 column 1: brand
   type of data: character
   maximum length: 20
   can contain blanks: yes
 column 2: model
   type of data: character
   maximum length: 20
   can contain blanks: yes
 column 3: megapixels
   type of data: float
   minimum value: 0
   maximum value: 99.9
   units: megapixels
   decimal places to show: 1
 column 4: price
   type of data: double
   minimum value: 0
   maximum value: 9999.99
   units: dollars
   notes: print dollars and cents separately, separated by .

      

General Advice on Succeeding with this project

Consult the sample scripts for advice on what to test. You are encouraged to test each stage of the program as you develop, rather than trying to develop the whole thing at once.

At each stage, you should have a working complete program that you could script and turn in for partial credit. However, in the end you should only turn in one program.

It is best to read over the entire assignment before starting to code part 1, so you have some idea of where we are going. But don't let the size or complexity overwhelm you; working step by step, one step per day, you'll have no trouble finishing on time if you start NOW. With that said, let's begin.

Important Note

For the remainder of the project, the term "record" will refer to one line of data. For example, for the hiking trails, a record would be one trail, with the name, the location, the length, the state, and the number of times hiked. For generality, I will use function names like addRecordToList. But you should feel free to change these names to something specific to your project, for instance addTrailToList if you did the hiking trails thing. In fact, changing the names in such a way would make your code easier to read and understand, and thus would earn you style points. You should definitely add such changes to any user input/output, e.g. in the menu system.

Step 1: Write a basic menu driven program
(Filename: p2s1, 9% of total points,
36% complete when done (9% step 0, 9% step 1, 18% for overall submission) )

 Main Menu: 
    a: add record to list 
    l: list records 
    q: quit program   
    s: summarize list  

Each of these options will call a function that will perform some task. (Even the 'q' option might perform some task before finally quitting.) For example, the 'a' option will call a function called something like:

void addRecordToList(Record **recordListHeadPtr, Record **recordListTailPtr);

• create a new node
• ask the user to enter the data for the record (e.g. for hiking the name of the trail, length of the trail, state, etc.) and store that data in the node.
• add that node into the linked list

Each node in the linked list will be a struct that you define to represent a single record. For instance, struct Trail or, for this generalization, struct Record. (Note: C++ programmers generally capitalize user-defined types such as Trail or Record so that they can be easily distinguished from variables and functions.)

The linked list will consist of struct Record nodes. All the fields of your data record (e.g. cost of pizza, topping, salad dressing) will be in the stuct in addition to a pointer of type Record* to the next node, called "next". You should declare variables in your main program to point to the head and tail of a list of teams, such as the following:

  Record *recordListHead;
  Record *recordListTail;

You will pass these variables (the ones for head and tail of the record list) into the function readRecordFile. You should pass these variables by pointer; that is, you will pass the address of these variables, as follows:

     ...
     switch (menuOption)
     {
        case 'a':
            addRecordToList(&recordListHead, &recordListTail);
            break;
     ...

void addRecordToList (Record **recordListHeadPtr, Record **recordListTailPtr)
{

   ... 
    
    Record *p;
    
    p = new Record; // allocate a new node
    
    // set fields inside p based on values read from user
    // For example, if one of your fields is a character array called name:

    char userInput[100]; // To hold the user's input
    // read in userInput
    p->name = new char[ x ];
    // Replace x with an appropriate value determined from the user input
    // Use the function strlen, and don't forget about the terminating null character.

    // set the rest of the fields similarly.  You only have to use new to
    // allocate memory for character array fields.  The rest of your fields
    // should just be simple data types (not arrays), so you can just set those
    // directly without calling new.

    if ((*recordListHeadPtr) == NULL)  // if first node in list
      (*recordListHeadPtr) = p;      // set the head of the list
    else
      (*recordListTailPtr)->next  = p; // link new node to end of the list
    (*recordListTailPtr) = p;          // update the tail pointer

    ...
}

Note the use of the new memory allocation operator above. We use new to allocate memory that can't really be determined from the start of the program, such as the number of nodes in the list or the size of the user-input character arrays for a field. That is why the node above and the character array field are allocated using new. This means we can essentially have as many nodes as we want, etc.

However, using new also means we have to deallocate that memory manually. We do this with the deallocation operator delete. Delete takes a pointer (same thing returned by new) and deallocates the associated memory chunk on the heap. For this step, you need to make a quit function that deallocates all the memory that you created using new, prints a message, and then quits. This function will be accessed with the "q" option from the menu.

To do this, go through each node in the linked list (starting with the one pointed to by recordListHead), and do the following (in order):

1. Deallocate each character array field in the current node with something like delete currentRecord->nameField;.
2. Save the pointer to the next node (i.e. currentRecord->next). A sensible place to save this would just be recordListHead.
3. Delete the node itself (i.e. delete currentRecord).
4. Move on to the next node (you saved a pointer to it in step 2), as long as there is a next node.

• "s": Print a summary of the list. Simply print a count of how many records are in the list.
• "l": List all the records in the linked list in some neat format (see script files for examples.)

So after this step you have four menu options: a (add), q (quit), s (summary), and l (list).

Partial Credit: If this step is as far as you get, it is worth up to 40% partial credit (you start with a grade of 40%, and additional deductions may be taken from there). If you stop here, script this program. Be sure you test all the options that are present at this stage (see the script file p2s1.txt for ideas.

Your script file should also be called p2s1.txt if you stop at this stage.

If you are continuing on with the remaining parts, you do NOT need to submit a script or C++ program for this step.

Step 2: Add the "f" option (50%)
(Filename: p2s2.cc, 9% of total points, 45% complete when done)

Add one additional option to the program.

The "f" option "finds" a record in the list. You are required to have two character array fields in your data type. The search will be on one of these (e.g. for hiking, probably the name of the trail). Prompt the user for a search string, then search the list for all teams that match that domain name. To compare the user-entered c-string with the one in each record, you will have to use the function strncmp in the header file called "cstring". For help on how to use this function, type man strncmp from strauss, or look it up in your textbook. Note that it is possible for the list to contain duplicate entries. See the script file p2s2.txt for example output.

Start by making a copy of your p2s1.cc or p2s1.cc program with, for example:

cp p2s1.cc p2s2.cc

Then add the necessary code to implement the new option.

Partial Credit: If this step is as far as you get, it is worth up to 50% partial credit (you start with a grade of 50%, and additional deductions may be taken from there). If you stop here, script this program. Be sure you test all the options that are present at this stage (see the script file p2s2.txt for ideas.

Your script file should also be called p2s2.txt if you stop at this stage.

If you are continuing on with the remaining parts, you do NOT need to submit a script or C++ program for this step.

Step 3: Add the "d" option (delete)
(Filename: p2s3.cc, 9% of total points, 54% complete when done)

Add one additional option to the program:

The "d" option deletes a team from the list. It will prompt the user to enter a search string (should use the same character array field in the record that you used for the "f" option). It will then search the list for the first node that matches that domain name, and delete that node from the list. Be sure to use the delete operator here to de-allocate everything for this node, as in step 1, and to update all pointers so that the list is still in-tact after the delete.

From here on out the drill is the same for each additional step (except the last one)... for each step, you add one additional option to the program, and get a bit more credit. At each step, copy your file with a command such as:

cp p2s2.cc p2s3.cc

Then add the necessary code to implement the new options. (This is the last step where I'll spell out these specific instructions

Partial Credit: If this step is as far as you get, it is worth up to 60% partial credit (you start with a grade of 60%, and additional deductions may be taken from there). If you stop here, script this program. Be sure you test all the options that are present at this stage (see the script file p2s3.txt for ideas.)

(From here on out, you'll be expected to just follow the pattern; I'll just say "this step is worth x% partial credit, and the script file should be called p2sn.txt, where n is the step number.

If you are continuing on with the remaining parts, you do NOT need to submit a script or C++ program for this step. Only submit the script for the step at which you finish.

Step 4: The "u" option (update)
(Filename: p2s4.cc, 9% of total points, 63% complete when done)

Suggestion: You should read the values into a character array (using cin.getline()) and before assigning the new value, check if the string entered is blank (using strlen()). If the length of the string is 0, that means the string is empty. Ask your TA if you are not sure how to do this.

If a character array field is updated, you have to delete the old array and use new to create the new one.

See previous stages 1-3 for guidance on how to name your program, script file, etc. and what to turn in if you stop at this step.

Step 5: The "r" option (read from file)
(Filename: p2s5.cc, 9% of total points, 72% complete when done)

In this step, you will add an option to allow the user to read records into the linked list from a file.

The file will have the same format as the files in the directory proj2, which contains several files teams1.txt, teams2.txt, etc., all of which contain fields separated by ":". For your project, you may use comma separated data, or : separated data; it is your choice.

Hints on the strtok() stuff

For hints on how to use strtok to read colon or comma separated data, follow the example code from the strtokExample subdirectory, which reads a file separated by commas. To use colons insetad, simply change "," in the second parameter of strtok to ":"

~pconrad/public_html/cisc181/05F/work/proj/proj2/strtokExample

http://copland.udel.edu/~pconrad/cisc181/05F/work/proj/proj2/strtokExample

What this step must do

After you've figured out how to handle the strtok part, add the "r" option to your program. This option prompts the user to enter a file name.

It then opens that file as an ifstream; if the file can't be opened, just print an error message and return from the function to the main menu (don't exit the program.)

If the file is opened successfully, read all records from the file (which contains colon separated values, similar to the files teams.txt, and udel.txt; these can be found in the proj/proj2 directory cited above). For each line you read from the file, allocate a new node. Read each line from the file into a single character array, then use strtok() to break up the fields and store each one in its proper place in the new node. Then, add that new node into the linked list. Remember to use new to allocate each node and to allocate each character array field in each node.

Creating your data file

You'll need to create a data file or two. I suggest you create at least three data files:

• one with a single line of data
• one with exactly two lines of data
• a third with at least 5 lines of data

Name your data files after your theme, e.g.

• hiking1.txt, hiking2.txt and hiking3.txt
• resorts1.txt, resorts2.txt, resorts3.txt
• videogames1.txt, videogames2.txt, videogames3.txt

Some sample data files for the NCAA team project (in colon separated format) are in:

http://copland.udel.edu/~pconrad/cisc181/05F/work/proj/proj2/sampleData/

Finishing and submitting

See previous stages 1-3 for guidance on how to name your program, script file, etc. and what to turn in if you stop at this step.

Step 6: The "w" option (write to file)
(Filename: p2s6.cc, 9% of total points, 81% complete when done)

It then opens that file as an ofstream; if the file can't be opened, just print an error message and return from the function to the main menu (don't exit the program.)

If the file is opened successfully, write all the records from the linked list into an output file, separated by colons or commas, in the same format as the input files teams.txt, and udel.txt; these can be found in the proj/proj2 directory cited above).

The idea is that the output file you create should be able to be read back into the program as an input file with the r option on the same run, or a later run. You should test this in your script.

See previous stages 1-3 for guidance on how to name your program, script file, etc. and what to turn in if you stop at this step.

Step 7: A smarter quit option
(Filename: p2s7.cc, 9% of total points, 90% complete when done)

When the user types quit, print a message warning the user if there are any unsaved changes. If there are NOT unsaved changes, the message should not be printed. If there are unsaved changes, ask the user if they really want to quit without saving. If the answer is yes, go ahead and quit. If the answer is no, return to the main menu.

Hint: Add a variable in your main program that keeps track of whether or not the list has been modified since the last time it was written to a file. Start the variable as false. Every time the user invokes an option that modifies the list, set the variable to true. Every time the user writes the file out to the disk, set the variable to false. Then pass this variable into the quit option.

See previous stages 1-3 for guidance on how to name your program, script file, etc. and what to turn in if you stop at this step.

Step 8: Making the list sorted (to get an "A" grade)
(Filename: proj2.cc, 10% of total points, 100% complete when done)

For this step, you will need to make sure that your list remains sorted in alphabetical order according to the "key" value (the same character array field that you search for in steps 2, 3, etc.). For this, you will want to either use strcmp() or strcasecmp() from the cstring library. These are the same except that strcasecmp ignores upper/lower case. You decide for your choice of data which function is more appropriate

The primary function here that will need changing is "a" (add). This will need to insert each new node into the list at the proper place. Also, update will need to call remove and then add if the "key" field is changed. Additionally, you can not assume that input files are pre-sorted; therefore, your function that reads from a file may have to be modified, depending on how you chose to implement it. Finally, there is some minor improvement that can be made to the find function.

For information on how to use strcmp, type man strcmp from Strauss, or look on page 376 in Savitch. Or, ask your TA for help.

For this stage, be sure your script tests all the options involved in the program. Also, if you reach this stage, name your program and your script file proj2.cc and proj2.txt.

Finishing and Submitting (contains important instructions!)

You do not need to create a Makefile or a tar file to submit this assignment; all your code will be in one C++ source file.

To get full credit for your scripts

• When scripting, follow the example script for your stage from the proj2 directory on the website (http://www.udel.edu/CIS/181/pconrad/06S/work/proj/proj2/sampleScripts)
• When working with data files, remember to cat any data files you read or create, and to do an ls command before and after you create.
• If your program writes out a data file, the ls command should show that the file does not exist before you run the program, and does exist afterwards.

Submit three files to WebCT

1. source file
2. at least one sample data file (the one with at least five lines of data in it)
3. your script file

Also, print your script file for your TA.

Grading

(end of project 2)