Due Wednesday, May 11th, 11:59pm

Goals for this homework

  • Practice implementing with trees
  • Exercise algorithm development using trees
  • Solidify the notion of an iterator - both implementation and use
  • Practice using static variables

You are expected to complete this assignment individually. If you need help, you are invited to come to office hours and/or ask questions on piazza. Clarification questions about the assignments may be asked publicly. Once you have specific bugs related to your code, make the posts private.

This homework has a single problem that builds on your work from the warmup.

You should submit many files for this assignment ( llist.h, llist.c, queue.c, queue.h, bst.c, bst.h, hw6.h, hw6.c, test_hw6.c and Makefile) in your subversion repository as directed below.

Set Up

You should already have your hw6 directory. If you participated in duet programming, make sure you copy over the files from the warm-up NOW.

Problem 1: word count

You will write a function with the following interface: 
bst* get_counts(char *filename);

This function takes in a filename. It reads in the file and splits the file into words. Words are broken by whitespace and punctuation of any kind. For simplicity, can't will be considered two words: "can" and "t". I suggest using fgets to read in the lines and strtok to divide the line into words.

Here is an example of a line of text and the words resulting from it:

hello, how are you? Welcome to CS152 today. We will study trees - bst's.
"hello" "how" "are" "you" "Wecome" "to" "CS152" "today" "We" "will" "study" "trees" "bst" "s"

This function counts how many occurrences there are of each word. It then places them in a binary tree that is sorted by count so that the user can take that bst and print it out in order.

The important thing to remember is that the tree you use to count the words is different from the tree you return to the user. When you count the words, you look them up by word. When you return a tree to the user, the words need to be indexed by count, not word.

You also need to make a few files as input to show the grader that you tested this on good test cases. Name those files test1.txt, test2.txt, etc.

Submit

At this point, you should have done the following:
  • Created and filled in several files associated with this project: queue.h queue.c llist.h llist.c bst.h bst.c word.h word.c hw6.h hw6.c test_hw6.c
  • Copied over the files from your warmup if you are participating in duet programming. 
  • $ svn add *.c *.h Makefile
  • Compiled your executable manually and with the Makefile
  • Implemented your test cases
  • Executed your code
  • Debugged your code 
  • $ svn commit -m "hw6 complete"