Huffman 4: build Huffman tree
Learning goals
You should learn:
- Practice using linked lists and trees.
- Combining linked lists with trees
- 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.
- HW11: Implement priority queue for future use
- HW12: Calculate character frequencies from a file
- HW13: Create a priority queue of trees from the character frequencies in a file.
- HW14: Build a single Huffman tree. ◀◀◀ this homework
- HW15: Implement functions to write arbitrary bits to a file, for future use.
- HW16: Write the Huffman Tree to the disk.
- HW17: Write the encoded file contents to the disk.
- HW18: 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 HW13 into a single Huffman tree. The algorithm is described in the article (originally linked from HW12), 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.
- Read the Huffman walkthrough and make sure you understand the algorithm for building the Huffman tree.
- Create a directory for HW14 and change into it.
you@ecegrid-thin1 ~ $
mkdir hw14
you@ecegrid-thin1 ~ $
cd hw14
-
Copy all of your files from HW13 into your
HW14 directory.
you@ecegrid-thin1 ~/hw14 $
cp ../hw13/{*.[ch],Makefile} -t ./
See the Q&A for an explanation of thiscp
command. -
Update your Makefile with the new
ASG_NICKNAME
.This should require chaning only a single line. You should now have this:you@ecegrid-thin1 ~/hw14 $
vim Makefile
ASG_NICKNAME=HW14
-
Edit your huffman.h to add the declarations for
make_huffman_tree(…)
anddestroy_huffman_tree(…)
. No other edits are necessary.you@ecegrid-thin1 ~/hw14 $
vim huffman.h
Requirements
- Your submission must contain each of the following files, as specified:
file contents huffman.c functions make huffman tree(Node✶ head)
→ return type: TreeNode✶Create a tree from the given priority queue.- Follow the algorithm given in the article and Huffman walkthrough .
-
Set the
.character
field of each newly created cluster (non-leaf) node to'\0'
. - All
Node
objects in the priority queue must be freed. -
Use your
pq_enqueue(…)
andpq_dequeue(…)
. -
If the priority queue is empty
(i.e.,
head==NULL
), return an empty Huffman tree (i.e.,NULL
). -
The parameter to this function may be called
head
orpq
.
destroy huffman tree(TreeNode✶✶ a root)
→ return type: voidDestroy a Huffman tree that was created usingmake_huffman_tree(…)
.-
*a_root
refers to the root of a Huffman tree created bymake_huffman_tree(…)
. -
Set
*a_root
toNULL
.
huffman.h types All types from HW13. declarations All declarations from HW13, plus those added for HW14 (specified above). test_huffman.c functions main(int argc, char✶ argv[])
→ return type: int- 100% code coverage is required for huffman.c.
- Direct testing of frequencies.c and priority_queue.c is optional for HW14.
- Use your miniunit.h.
- Submissions must meet the code quality standards and other course policies on homework.
Submit
To submit HW14 from within your hw14 directory, type
make submit
That should result in the following command:
264submit HW14 huffman.c huffman.h frequencies.c frequencies.h priority_queue.c priority_queue.h test_huffman.c miniunit.h clog.h Makefile
Pre-tester ●
The pre-tester for HW14 has been released and is ready to use.
Q&A
What is the weird syntax in the
cp
command?That command copies all files ending with “.c” or “.h” and your Makefile from your hw13 directory into your into your hw14 directory.
It is equivalent to the following three commands, but shorter and more error-resistant.
$
cp hw13/*.c hw14/
$
cp hw13/*.h hw14/
There are a few things going on here.$
cp hw13/Makefile hw14/
-
cp files… -t target_directory
means to copy files… to target_directory.It is equivalent to
Thecp files… target_directory
.-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
~/hw14
, (hw14 directory within your home directory),..
means your home directory, and../hw13
means the hw13 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,hw13/{*.[ch],Makefile}
meanshw13/*.[ch]
andhw13/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,
hw13/*.[ch]
meanshw13/*.c
and/orhw13/*.h
.
-
How much work is this?
The instructor's solution uses 16 sloc for
make_huffman_tree(…)
and 8 sloc fordestroy_huffman_tree(…)
.Note:
destroy_huffman_tree(…)
is extremely similar to the destroy function you already wrote for tree_sort.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 reuseshead -> next
as a cluster node, to avoid freeing oneNode
and then malloc'ing space for anotherNode
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
4/16/2020 | Added destroy_huffman_tree(…) and details about test_huffman.c. |
4/17/2020 |
Fixed a few issues…
|