[an error occurred while processing this directive] CS 2000 - (none)

CS 2000 - Program Design in C
Fall 2011

[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 assignment

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:

Part 1

The LinkedListDouble class above represents a list of doubles.  It is very similar to the ArrayList example that you may have modified for assignment #8.  The list of doubles may grow or shrink, and the class is used through these five functions:

    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 LinkedListDouble 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 function contract:

/* 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 main function) before moving on.

Part 2

The 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:

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.

Part 3

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 like this:

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.

Part 4

In assignment #8, you created a class called StringSet that used arrays to implement a set of strings.  Copy your solution from assignment #8 (including the StringSet class files, the data file, and the count_words.cpp 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 works.

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.

Part 5

In your count_words.cpp, you create an ArrayStringSet object.  Most students will create the object by just creating a variable like this:

  ArrayStringSet s;

(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:

  s.add (word);

Since you're now using a pointer to an ArrayStringSet, you'd need to dereference it:

  (*s).add (word);

I prefer this form of following the pointer:

  s->add (word);

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.

Part 6

Create another class called LinkedStringSet that mimics the functionality of the ArrayStringSet class.  Use a linked list to implement this set.  Finally, change your count_words.cpp to use this LinkedStringSet class instead of the array-based set class.

This part may seem tough, but it can be broken down into simple steps:

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

Part 7

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

The 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.  Change your LinkedStringSet and 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 StringSet pointer variable.)

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

Part 8

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 extracredit02 directory.

Change 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 a similar 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:

Handing in your files

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.