Learning goals

You should learn:

1. Practice using linked lists and trees.
2. Combining linked lists with trees
3. Learning objectives: structures and dynamic structures

Overview

This is part 4 in an 8-part series in which you are implementing the Huffman Coding algorithm to compress files.

1. huffman_1: Implement priority queue for future use
2. HW16: Calculate character frequencies from a file
3. HW17: Create a priority queue of trees from the character frequencies in a file.
4. HW18: Build a single Huffman tree. ◀◀◀ this homework
5. HW19: Implement functions to write arbitrary bits to a file, for future use.
6. HW20: Write the Huffman Tree to the disk.
7. HW21: Write the encoded file contents to the disk.
8. huffman_8: Create a command-line interface for compressing files.

Your task in this homework is to transform the priority queue of tree nodes that you generated in HW17 into a single Huffman tree. The algorithm is described in the article (originally linked from HW16), as well as this Huffman walkthrough .

Input

The input to your code will be a priority queue like this:

Output

The output to your code will be a tree like this. Note that this is a Huffman tree, not a binary search tree (BST).

Getting Started

There is no starter code. However, we recommend creating a new directory for each step of the Huffman series.

1. Read the Huffman walkthrough and make sure you understand the algorithm for building the Huffman tree.
2. Create a directory for HW18 and change into it.
   you@ecegrid-thin1 ~ $ mkdir hw18
   you@ecegrid-thin1 ~ $ cd hw18
3. Copy all of your files from HW17 into your HW18 directory.
   you@ecegrid-thin1 ~/hw18 $ cp ../hw17/{*.[ch],Makefile} -t ./
   See the Q&A for an explanation of this cp command.
4. Update your Makefile with the new ASG_NICKNAME.
   you@ecegrid-thin1 ~/hw18 $ vim Makefile
   This should require chaning only a single line. You should now have this: ASG_NICKNAME=HW18
5. Edit your huffman.h to add the declarations for make_huffman_tree(…) and destroy_huffman_tree(…). No other edits are necessary.
   you@ecegrid-thin1 ~/hw18 $ vim huffman.h

Requirements

Submit

To submit HW18 from within your hw18 directory, type

make submit

That should result in the following command: 264submit HW18 huffman.c huffman.h frequencies.c frequencies.h priority_queue.c priority_queue.h test_huffman.c miniunit.h log_macros.h Makefile

Pre-tester ●

The pre-tester for HW18 has been released and is ready to use.

Q&A

1. What is the weird syntax in the cp command?

   That command copies all files ending with “.c” or “.h” and your Makefile from your hw17 directory into your into your hw18 directory.

   It is equivalent to the following three commands, but shorter and more error-resistant.

   you@ecegrid-thin1 ~/hw18 $ cp hw17/*.c hw18/
   you@ecegrid-thin1 ~/hw18 $ cp hw17/*.h hw18/
   you@ecegrid-thin1 ~/hw18 $ cp hw17/Makefile hw18/
   There are a few things going on here.

   • cp files… -t target_directory means to copy files… to target_directory.

     It is equivalent to cp files… target_directory.

     The -t makes it explicit that the thing after it is the target directory. That prevents some errors people sometimes make when you mistype something and end up copying one file over another—and losing the second file. With -t the thing after it must be a directory.

   • .. means the parent directory, relative to your current directory.

     Since you are currently in ~/hw18, (hw18 directory within your home directory), .. means your home directory, and ../hw17 means the hw17 directory within your home directory.

   • ./ means the current directory.

     The slash at the end is optional, but prevent errors. Without it, you might forget the dot (.). Also, adding a slash to the end of something explicitly states that it is a directory, so you don't accidentally mix up a file and a directory.

   • {♥,♦,♣} means ♥, ♦, and ♣. Thus, hw17/{*.[ch],Makefile} means hw17/*.[ch] and hw17/Makefile.

   • [♥♦♣] is a character class, and is equivalent to ♥, ♦, and/or ♣. Unlike the pattern with curly braces, in a character class, ♥, ♦, and ♣ must be single characters.

     Thus, hw17/*.[ch] means hw17/*.c and/or hw17/*.h.

2. How much work is this?

   The instructor's solution uses 16 sloc for make_huffman_tree(…) and 8 sloc for destroy_huffman_tree(…).

   Note: destroy_huffman_tree(…) is extremely similar to the destroy function you already wrote for tree_sort.

   

3. The instructor's solution seems awfully short. Is it legit?

   That solution is compliant with our code quality standards, but does take one shortcut: It reuses head -> next as a cluster node, to avoid freeing one Node and then malloc'ing space for another Node as the cluster. That's not exactly the way we described the algorithm in lecture, but it's equivalent. Also, some unnecessary #include's have been removed.

Updates

There are no updates to HW18 so far.