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 similar set of problems to what you did in the warmup. These will be used in next week's two-week project.

Set Up

There is no additional setup - you should have your files from the warm-up.

Exercises

Problem 1: word struct and functions

You will implement the second comparison function for words: compare_counts

Problem 2: binary search tree

You are writing several binary search tree functions (bst) to add to what you implemented in the warm-up:

  • void free_bst(bst* tree); // free all of the nodes of a bst
  • void do_to_all(bst*, void (*f)(void*)); // perform a function on all nodes of a bst
  • void print_bst(bst *tree, void (*print_item)(void*)); // print all nodes of a bst

Problem 3: 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 constructs a binary search tree consisting of the words in the file. It then increments the count each time it sees the word again.

Note that this function has a lot going on within it - and it will be hard to get partial credit if it doesn't work. Partial credit is from implementing the other functions in the warm-up and hw. However, to get credit for this problem, you need to finish it.

Submit

At this point, you should have done the following:
  • Created and filled in several files associated with this project: bst.h bst.c word.h word.c hw6.h hw6.c hw6_main.c Created test files with words in them 
  • $ svn add *.c *.h Makefile testwords1.txt testwords2.txt
  • Compiled your executable manually and with the Makefile
  • Implemented your test cases
  • Executed your code
  • Debugged your code 
  • $ svn commit -m "hw6 complete"