CISC220 F2014 Lab4

Lab #4

A List is a dynamic, linear data structure that allows insertion and removal at arbitary locations, including both ends. The full ADT for an STL List is defined here.

• A Stack can be implemented as a List which uses push_back() for push() and pop_back() for pop()
• A Queue can be implemented as a List which uses push_back() for enqueue() and pop_front() for dequeue()

Here is starter code for a List class implemented using a doubly-linked list. push_back(), pop_front() (which doesn't return anything), and front() and back() (which give access to the ends of the list without removing them) have been written for you.

1. C++ programming exercises

• (1 point) Complete the push_front() and pop_back() functions in the doubly-linked list List class. Copy char_test() and string_test() in main.cpp to reverse_char_test() and reverse_string_test() and modify them to test your functions.
• (4 points) Write the insert_ordered() function (see comments in dll_list.hh for explanation) and make a new function ordering_test() in main.cpp to call it. This test function should declare a MyList<string> variable, read words from a text file specified on the command line (as with wordbyword), insert each of them into the list, and then print every element in the list from first to last. The result should be all of the words in alphabetical order.
  • In case it's not clear, your insert_ordered() function will need to traverse the list to find the correct spot to make a new node with the data
  • Please remove punctuation, make everything lower-case, etc. before running insert_ordered(). Here is a program to do this called filecleaner. Given a file "foo.txt" on the command line, it writes a new file called "cleaned_foo.txt".

2. Submission

• Include a PDF file <Your Name>_README.pdf which contains the inputs and outputs of your program, etc. For insert_ordered(), try several different input files (such as the ones included with filecleaner), but only include outputs of shorter files.
• Create a single tar/zip/rar file out of the top-level and all subdirectories. This archive file should be named <Your Last Name>_Lab4.tar (or .zip or .rar, etc.).
• Submit it in Sakai by midnight at the end of Thursday, September 25