Link back to syllabus

  1. In the spirit of the llist abstract type and the dlist abstract type, write a map type backed by a binary search tree built of tree_nodes. This type stores a mapping from strings to numbers, similar to a HashMap<String, Integer> in Java. The header file is here.

    You will want to write several helper functions in order to recursively process the tree structure. Additionally, when inserting a new node, you are given a string. You should allocate fresh memory to store this string in your map, and then free this memory in map_free.

  2. Write a program, frequencies, that uses your map to report how many time words appear in a file. For example, if I say frequencies < palindrome.txt, where palindrome.txt contains a man a plan a canal Panama, then I will see

    Panama: 1
a: 3
canal: 1
man: 1
plan: 1

    This is because a appears 3 times, while the other words each appear once.

    You may assume that each word is at most 20 characters long. Accordingly, you can declare a char word[21] and read in the words using scanf("%20s", word). As scanf returns the number of things it has read, you can usefully use it in a while condition:

    char word[21];
while(scanf("%20s", word) == 1)
{
    ...
}

    This loop will keep reading words until the file is fully read (or the user types Ctrl+D on an empty line.)