[an error occurred while processing this directive]
CS 2000 -
Program Design in C
[an error occurred while processing this directive]
Programming Assignment #10
[an error occurred while processing this directive] Linked lists
[an error occurred while processing this directive] Due Friday, December 9 at 5:00 PM
Plan about 5-8 hours of work
This assignment is worth 100 points and is due on Friday, December 9 by electronic handin. Any assignment electronically handed in on Friday before 5:00 PM is on-time. Late assignments will be accepted over the weekend. The late penalty is one point. The handin directory will close at 12:01 AM on Wednesday, December 14. No assignments may be handed in after this time.
Note: TA hours are limited during finals week.
Expectations for grading, comments (including title comments), and function contracts remain in place. If you need to see the requirements again, please review assignment #1 and assignment #4.
Finally, you must write and submit only your own code for this assignment. You may study with other students, but you may not copy their work, download solutions, or turn in team solutions. All portions of this assignment (including anything from your assignment #8 solution) must be your own independent work, or code that I provide. Please, I don't have time to prosecute any more plagiarism cases this semester, but I will if I have to... :(
The goal of this assignment is to give you further practice in
building classes and to expose you to linked data structures.
You will complete several classes and test applications for this
assignment. For each class, create a
.h file with
the class declaration and a
.cpp file with the
definitions. For information about working with multiple files,
please review assignment #8 and lab #8.
This assignment will utilize your solution to assignment #8. If you did not finish assignment #8, do so now. I recommend creating a new directory for assignment #10 so that you don't overwrite your work from assignment #8.
You will also need to download these files from the linked list example in class:
Finally, recall that a linked list is created by linking
Node objects together. A node contains a data element and a pointer to the next node in the list:
In the linked list class, we maintain a head and a tail pointer that point to the first and last nodes in the list:
LinkedListDouble class above represents a list of
doubles. It is very similar to the
example that you may have modified for assignment #8. The list
of doubles may grow or shrink, and the class is used through these
void add (double value); // Adds to the end of the list void remove (int pos); // Removes element at given pos double get (int pos); // Returns element at that pos void set (int pos, double value); // Sets a position in list int size (); // The number of elements stored in the list
Add another public function to the
class that prints out the list to the console by traversing the links
and printing out the data values in each node. Here is the
/* Prints out to the console the data elements in this list * by traversing the links in the linked list. This function * is used to debug linked lists. The output will begin and * end with square braces, and will show the data elements within * the braces. Examples * * A list containing 2, 7.3, and 5: [ 2 7.3 5 ] * An empty list: [ ] * * This function does not call any other function in this class. */ void LinkedListDouble::print_forward ()
As specified in the contract, this function must not call any other
function within the linked list class. Also, do not use or
access the size of the list in this function. Write statements
and a single
while loop that traverses the list using
pointers and print out the data values found in each node. (Keep
it simple - exact formatting is unimportant so long as the list data
values are clear.)
The purpose of this part is to give you practice traversing the list, and to give you a great tool for debugging linked lists. (Following links and printing out data is one way that programmers debug these lists.)
Briefly test this function (using some
before moving on.
remove function in the linked list class is not
complete. Write the remove function so that it properly removes
the specified item from the linked list. The item is specified
by position. Make sure you consider the following issues:
deletekeyword on a pointer to the node.
Common problems that students will have are not updating the list size properly, not updating head or tail properly, not deleting the node, deleting too many nodes, or not updating the pointers in the list properly.
Write a tester to thoroughly test the linked list class. Your
tester should have a
main function that repeatedly adds,
removes, gets, and sets elements in the linked list. You may
design this any way you like, but it should be clear from the output
that the linked list is working properly. I recommend output
The list: [ ] Size: 0 Adding 4 to the list: The list: [ 4 ] Size: 1 Adding 6 to the list: The list: [ 4 6 ] Size: 2 Adding 6 to the list: The list: [ 4 6 ] Size: 2 Removing element at position 0: The list: [ 6 ] Size: 1 ... etc ...
Test all of the list functions, and make sure you try to break the list class with challenging tests. For example, instead of just removing one element, try removing the first element, removing a middle element, and removing the last element in a list. Try removing all the elements in a list, then add a few more. Exploring a variety of cases will be more likely to reveal errors in your work, and this is the goal of a test program.
Note: Do not test illegal conditions -- these are undefined for our list. For example, do not try to set the element at position -1, and do not remove the 5th element from a four element list.
In assignment #8, you created a class called
that used arrays to implement a set of strings. Copy your
solution from assignment #8 (including the
class files, the data file, and the
program), then rename the class to be
ArrayStringSet. Rename the files, change the type
names in the files, and make sure your count_words program still
This step is just a renaming step. If it takes more than a few minutes, you might be doing something wrong -- please ask for help.
count_words.cpp, you create an
ArrayStringSet object. Most students will
create the object by just creating a variable like this:
(Your variable name will probably be different.) This creates an object in a local variable. Change this line of code so that the object is dynamically allocated in heap memory:
ArrayStringSet *s = new ArrayStringSet();
Your variable will now be a pointer to a new object (instead of just being the object). Change all of your usages of the object to follow, or dereference, the pointer. To help, assume you had this line of code that used the object:
Since you're now using a pointer to an
ArrayStringSet, you'd need to dereference it:
I prefer this form of following the pointer:
Change your solution so that you only use pointers to
ArrayStringSet objects. You should only be creating
one of these objects, so this change shouldn't take too
long. Test your revised
count_words.cpp before moving on.
Create another class called
mimics the functionality of the
class. Use a linked list to implement this set. Finally,
count_words.cpp to use this
LinkedStringSet class instead of the array-based set
This part may seem tough, but it can be broken down into simple steps:
LinkedListDoubleclass. Just make sure that you do not change any of the
count_words.cppprogram, change it to use a
LinkedStringSet. Since the function headers are identical between the string set classes, this should be a trivial change.
Once you have the changes in place, debug them. The
functionality of the
count_words.cpp program should not
change. (You may add additional functions for debugging.)
Extra credit option #1: If you complete parts 1 through 6 with a good or excellent score, you can earn 50% extra credit on this assignment by completing this part. The extra credit will be applied to your overall homework grade after all letter grades for other students have been determined. It is due with your assignment, but may also be late if the assignment is late. Hand in this extra credit with your assignment (incorporated into your assignment solution).
LinkedStringSet class and the
ArrayStringSet class share a common 'interface', as well
as a bit of functionality. Create a common superclass called
StringSet that declares this common functionality.
ArrayStringSet classes to inherit from this base
class. Test your changes by changing the tester to only
declare variable pointers to the
StringSet class, not to
either subclass. (You'll still create new subclass objects, but
you will store the pointer in a
This step parallels the example from class on Wednesday, November 30. The base class should declare (as virtual) all the functions found in both subclasses. In addition, you may want to declare a count variable and provide an implementation for the size function. (When you put common functionality in the base class, you'll want to remove it from the subclasses.)
Extra credit option #2: If you complete parts 1
through 7 with an excellent score, you can earn a full assignment's
worth of extra credit. The extra credit will be applied to your
overall homework grade after all letter grades for other
students have been determined. It is due on Wednesday, December
14 at 5:00 PM, no late work accepted. Electronically hand in your work to the
LinkedStringSet class so that it uses a
doubly-linked list instead of a singly-linked list. You will
need to change any function that adds or removes elements to/from the
list so that doubly-linked lists are properly used. In addition,
make sure the
print_forward function is correct, and add
print_reverse function for debugging the links
pointing backwards through the list. Finally, create another
test application for testing the functionality of this revised
LinkedStringSet class. Make sure that you print out
the list in both directions (from the head and tail) at every step in
your test program.
Submit all of your code for this assignment, along with the new testing application. Your solution to this assignment (parts 1 through 7) must still work.
Here are a few diagrams to help you get started. This is the structure of a node in a doubly-linked list:
This is an empty doubly-linked list:
This is a doubly-linked list with four elements in it:
Before handing in your program, make sure that any debugging output is removed.
Follow this link for instructions for handing in your files.
Page updated Saturday December 10, 2011 at 06:38:17.