CPS 100, Fall 2002, Week #3

The questions here are based, in part, on the code in readlist.cpp which shows how to insert nodes into a linked list, both at the front of the list and at the back of the list.

Questions

1. First, assume that the program will be modified to store words and the count of how many times each word occurs. The definition of the struct Node is partially shown below. What changes (if any) should be made to the constructor so that no other code in the current version of the program changes. struct Node { string word; int count; // # occurrences Node * next; // points to next node in list Node (const string& s, Node * link) : word(s), next(link) { } };
2. How does the function print change to print both a word and its count on the same line? How does the node-counting function count change?

3. Modify readAndAddToFront so that when a word is read, it's only added to the front if it doesn't already occur in the list. If it does occur, bump the number of occurrences by one. You should do this by adding as few lines as possible to readAndAddToFront, most of the work should be/can be done in a new function you write and call.

4. Can you use the same function/code from the previous problem in modifying readAndAddToBack? Why/How?

5. Write a function that cuts a linked-list into two equal new sub-lists (or lists whose size differs by one). Here's the prototype and specification (draw a picture to help).

     Node * cutInTwo(Node * list)
     // pre: list is NULL/0 terminated, contains n nodes
     // post: list contains first n/2 nodes, and a pointer
     //       to the first node of the second n/2 nodes is returned
     //       so that effectively the list is cut in two.