Lab 14

Lab assignment: Linked Lists and Word Counts

I've given you a list of words from a document, and their word counts.  I want you to write an insert function for this list, which takes in a Node *, and either increments one of the existing word counts, or adds a new Node to the end of the list.

• • Stage 1-2 (1 point each):

            insert should do 2 things.

            1. If the word appears in the list, increment numAppearances for word in that list.

            2. If the word doesn't appear in the list, add a new Node to the end of the list, with that word and a numAppearances of 1.

            Each of these things are worth a point, and you can complete them in either order.

• • Stage 3 (Extra Credit) (1 point):

  • For a point of extra credit, make it so that the list remains in descending order of number of appearances.  After each insert, if the numAppearances of the node is greater than that of the node before it, you swap the two in the list.

  • Note that since the list is singly linked, you may need to check for the word ahead of where your pointer is in the list, in order to do the swap.  This means more special cases for the beginning and end of the list.

Notes:

• • Keep in mind that this is a team effort so you should agree with your partner on what you are going to do before you start typing. The partner who is typing is the "driver" and the partner watching is the "navigator."  Be sure to switch roles every 10 to 15 minutes, to foster a deep understanding of the code for both partners.    The navigator should be watching for syntax errors and verifying the correctness of the code you're writing.  

• It will speed things up for you if you keep a window open for editing and have a separate window open for compiling and running your program.  Remember that windows are resizeable!

Submission:

1. You should work with a partner for this (and all the remaining) lab(s).  Only one of you need to submit the program to Blackboard, though you should be certain that both of your names be present in a comment at the top of the .c or .cpp source file.

1.5 If you work alone, include just your name in a comment at the top so that I know you worked alone, and not have to guess.

2. You should turn in to Blackboard by the END OF THE LAB (8:50 for the 8-9 lab session, 9:50 for the 9-10 lab session).  I know it's tempting to keep working on it, but other classes come in, and it's not fair to the students who are limited to that particular time span if you go over.  Which isn't to say that you can't work on it later, to check your solution against the one I post for your own understanding.  But what you submit for a grade should be before the next hour begins.

3. If you wish, you may submit your lab by 11 am on Thursday for a 1 point penalty.  If you can't finish up the second point by the end of lab, you can still earn the score by completing all three steps and submitting your code by the day after.