Description
In this assignment you will use C++ linked lists to implement a data structure we have studied in this class: a hash table. This hash table will be encapsulated inside a class called Table (what you know as a map). To make it more interesting, we’re going to test our class in two different programs: one is a command-based test driver you will write (a program to maintain student names and scores), and the other is a C++ version of the concordance program we wrote in lab 10. We wrote the concordance program for you.
Note that there is a very short time-line on this assignment: there’s a little more than a week to complete it. We recommend you start immediately. To help you complete the program successfully and on time we have included some development hints and a suggested milestone later in this document (with recommended completion time of this Sunday).
As we have mentioned previously, we recommend you do all your C++ development for this course on Vocareum. If you choose not to do this, please leave yourself at least a few days to port your code (i.e., start testing it on Vocareum a few days before it’s due so you have time to fix any bugs.) The Vocareum g++ compiler and environment is the one we will be using for grading your assignment.
To be able to use a C++ class in multiple programs, but not end up with multiple versions of your Table class code, these are going to be multi-file programs that use separate compilation and a Makefile. We will be discussing these topics more in lecture soon. However, we wrote the Makefile for you, and put all the necessary include statements in the source files so as to make this aspect of the assignment as painless as possible for you. Note: it will not work to use the regular g++ command to compile this program. There are more specifics about this in the File Organization section below.
The assignment files
The files in bold below are ones you modify and submit. The ones not in bold are ones that you will use, but not modify.
Table . h Header file for the Table class. This contains the Table class definition (but not the method implementations). More about this in the section on the Table class.
Table . cpp Implementation file for the Table class. This contains Table method definitions.
More about this in the section on the Table class.
listFuncs . h Header file for linked list module. Contains Node struct definition and prototypes for functions on linked lists. More about this in the section on the linked list functions.
pa5list . cpp
functions.
2020/12/4 PA5 CS 455
listFuncs . cpp Implementation file for the Node struct and list functions. Contains Node constructors and definitions of functions to operate on a linked list. More about this in the section on the linked list functions.
(this one you modify, but do not submit) A test program for your list
grades . cpp Test program for our Table class. We gave you a skeleton version that does the command-line argument handling, you’ll be writing the rest of this program. More about this in the section on the grades program.
concord.cpp A second program to try out your Table class with. More about this in the sections on the Table interface, and testing with the concord program. melville.txt and poe.txt Some text files to test the concordance program on.
Makefile A file with rules for the “make” command. This Makefile has rules for compiling the source code to make the executables. There are comments at the top of the file telling you how to use it.
README See section on Submitting your program for what to put in it. Before you start the assignment please read the following statement which you will be “signing” in the README:
“I certify that the work submitted for this assignment does not violate USC’s student conduct code. In particular, the work is my own, not a collaboration, and does not involve code created by other people, with the exception of the resources explicitly mentioned in the CS 455 Course Syllabus. And I did not share my solution or parts of it with other students in the course.”
File organization and compiling multi-file programs in C++
Separately compiled programs in C++ usually have two files per class:
The header file (suffix .h) contains the class definition. It also has some preprocessor directives (start with #). We’ve already given you a partially completed header file, Table.h, for the Table class; this header file specifies the class interface via the class definition and associated comments. Any additions you need to make to the class definition go in this file: in particular, you will need to add the private data and the headers for any private methods here — as with other classes we have specified for you this semester, you are not allowed to make any changes to the public section of this class definition.
The implementation file (suffix .cpp) contains the implementation of the methods. That is, the complete method definitions for all the methods, public and private. This file needs to #include the class header file (i.e., Table.h). We started your Table.cpp, and put the necessary #include in it.
This program is going to also contain a second separately-compiled module, although that one does not have a class in it. It’s going to be a module with our Node struct and all the functions for operating on a linked list of that node type. This module is needed for the chaining in your hash table. That module will also have a header file plus an implementation file. It is described in more detail in the section on linked list functions. Since this module is only used in the Table implementation the #include statement for its header file is only in
longest chain: 0
cmd>
Once this start-up happens the program repeatedly reads and executes commands from the user, printing out the command prompt (cmd>) after it finishes the previous command, until the user enters the quit command.
Here are the commands for the program (in the following a name will always be a single word):
insert name score
Insert this name and score in the grade table. If this name was already present, print a message to that effect, and don’t do the insert.
change name newscore
Change the score for name. Print an appropriate message if this name isn’t present.
lookup name
Lookup the name, and print out his or her score, or a message indicating that student is not in the table.
remove name
Remove this student. If this student wasn’t in the grade table, print a message to that effect.
Print out all names and scores in the table.
size
Print out the number of entries in the table.
stats
Print out statistics about the hash table at this point. (Calls hashStats() method)
help
Print out a brief command summary.
quit
Exit the program.
The only error-checking required for this program is for you to print out “ERROR: invalid command”, and the command summary (see ‘help’ command) if a user give an invalid command name. Once you print the message your program should then display another command prompt.
So, for example, you do not have to check whether the user has entered the correct number of arguments or the correct type of arguments for a command (i.e., the graders will not test your program on those conditions).
Note: this program enables you to test all of the Table methods.
Using the concord program to test Table
Once you are convinced your Table class works with the grades program you should use concord.cpp program along with the .txt files that came with the assignment to test your Table class with a larger amount of data. This program does not use all of the Table methods, so is not suitable as a complete test of your Table class. See comments in concord.cpp for how to run it.
Program development and milestone
Here’s a suggested development plan to help you succeed on this assignment:
-
Think through what exact operations you will need on a single chain to implement the various Table methods. Define the exact interface of functions to do these operations on a single linked list. These kinds of operations were discussed here.
-
By Sunday 11/8 have all of your linked list functions written and tested. Because they don’t depend on the private data of the hash table class (just the Node class) you can write a separate program to test these thoroughly, before you tackle any of code dealing with a dynamic array, etc. See the next section for more details about this milestone.
-
Once you are convinced that your list code works, you can start working on the Table class that uses these functions. Implement the constructors, insert and printAll methods of Table, and test them with a partially written grades.cpp.
-
Add other Table methods and the corresponding grades.cpp code that tests those methods to your program, one at a time, testing them as you go, until you have a completely working grades program.
-
Test your Table class with concord.cpp running on the two story files given.
Milestone
For each of the operations on the Table class, figure out what corresponding operations you will need on a single chain to help complete the operation. You will need pretty much one chain (i.e., linked list) operation per Table operation: there may be one or two situations where you can reuse an operation in multiple places.
Note: besides the stuff mentioned in the previous paragraph, this milestone is about code that operates on a single linked list, not about hash tables. Put another way, it doesn’t involve the Table class, but it involves building functions that operate on ListType (a.k.a., Node*). These functions will be useful tools that will make implementing the table class easier.
To complete this milestone, you are going to write a test-program called pa5list.cpp that will contain code to test all of your linked list functions. The linked list functions themselves will be in the file listFuncs.cpp, and the prototypes for those functions (as well as the Node definition) will be in listFuncs.h We provided starter versions for all three of these files.
The Makefile for this assignment already contains a rule to create the executable pa5list from these files. (I.e., do the Linux command “make pa5list” to compile it.)
These functions you create to operate on a linked list will be regular functions (not methods) that pass data in and out via explicit parameters and return values (like the linked list functions we have written in lecture and in last week’s lab). Each of them involves a parameter of type ListType passed by value or by reference. This was discussed further, with an example header give in the section of the assignment on linked list functions. As mentioned there, once you have thoroughly tested them, you will be able to use them in your code for the Table class.
To get the lab credit, you’ll need to design your test driver (pa5list.cpp) to work on hard-coded data, as we have done for other unit tests we have written for this course.
Note: you are not required to submit pa5list.cpp as part of pa5. You are, however, required to put all of your linked list code for the assignment in listFuncs.h and listFuncs.cpp
Grading criteria
This program will be graded approximately 70% on correctness, 30% on style and documentation (where the list module requirement is part of that style score). As usual we will be using the style guidelines published for the class.
README file / Submitting your program
Your README file must document known bugs in your program, contain the signed certification shown near the top of this document, and contain any special instructions or information for the grader.
The submit script will check if all the necessary files are present, and if so, will attempt to compile grades and concord using the provided Makefile. Then it checks that you used the correct output format for the hashStats and printAll Table methods. Note: see the method comments for these two methods for details of the required format.
https://bytes.usc.edu/cs455/curr/assgts/pa5/pa5.html 9/9
