CS152 W17 Warmup 7

Goals for this Warmup

• Practice binary search tree operations
Practice data representation

For this lab, you are welcome to get technical help from another student on how to use or install any of the tools involved. You may also get syntax help on C. You may not, however, get help on the algorithmic portion of the exercise outside of office hours or piazza questions to TAs or instructors.

• Set up
• Problems
• Testing
• Submit

Set up

Remember to create a new directory in your repository for this lab.

$ cd CNET-cs152-win-17
$ mkdir hw7
$ svn add hw7
$ cd hw7

Problems:

In this warm up, we will build the appropriate functions that we will be using to create and operate on our data structures that together implement our compression technique. The files we will be working with are:

• llist.h, llist.c
• heap.h, heap.c
• bst.h, bst.c
• word.h, word.c
• compress.h, compress.c

Provided here are the header files. We will be creating the *.c files from scratch for llist.c, heap.c, and compress.c, and we will be re-using bst.c and word.c from last week's work.

Problem 1: Linked List

We already have completed the functions contained in word.c, and most of those in bst.c. Now, to complete bst.c, we will be implementing the iterator function. In order to do this effectively, we will be using a linked list once again. However, there is some flexibility in the specific implementation. Provided for us is a header file llist.h, and this file contains several different access methods. It is up to you to choose specifically how you want to utilize this linked list, which effectively is deciding which of the access and insertion functions you wish to choose.

Once you come up with a set that you are planning on using, add a note to the top of your llist.h file indicating which functions you chose and why. Choose wisely!

The functions you can choose from are:

• insert_head
• remove_head
• insert_tail
• remove_tail

A functional data structure built around our linked list will require one insert function and one remove function. Our choice of these functions will allow us to use the linked list as either a stack or a queue, depending upon whether we wish to access in a first-in-first-out (FIFO) fashion, or as a last-in-first-out (LIFO) fashion. Think carefully about the advantages of each mechanism, and how both of these map to your ultimate goal: implementing an inorder traversal of your binary search tree.

Problem 2: Iterate

Once this is completed, we will use these functions to implement our iterator defined in bst.h:

• void* iterate(bst* tree);

This function is an iterator that accesses items in the binary search tree in an in-order traversal. Recall that an inorder traversal requires that all left-subtrees are visited, followed by the root, followed by right subtrees, in that sequence. This is the location where we will leverage our choice of linked-list access mechanism.

An example of an in-order traversal is shown below:



(source: https://en.wikipedia.org/wiki/Tree_traversal#In-order)

Problem 3: Heap Functions

In heap.c, we will be implementing two heap functions: insert and remove, along with create() and free(). The creation and free functions are very similar to those for the bst data structure that you implemented in bst.h

• heap_insert
Heap insert acts slightly differently than that of the typical binary search tree insert function. The process is defined in the header file, and consists of first inserting an element into the bottom of the heap. The element is then compared with its parent utilizing a compare function that we have already written in word.c, and if they are in the proper order (according to a compare function), then the function returns. Otherwise, the element and its parent swap places in the heap, and the function goes back to the second step.
• void* heap_remove
This function is operates similarly to the heap_insert function, in that first the root element is removed and replaced by the element in the last level. The new element is then compared with its children, and if they are properly ordered the function returns. Otherwise, the function swaps the new root with one of its children, and goes back to step two.

Testing

At this point we have done the following:

Implemented a linked list and an appropriate access method (LIFO, FIFO)

Used this to implement an inorder traversal iterator in bst.c.

Implemented a new heap data structure, along with access functions

Now we can begin using these tools to build our compression mechanism!

To test for correctness, we can run our set of functions against various input text files. A good testing procedure should include building and printing out a binary search tree sorted alphabetically (printing out via the inorder traversal that we have now implemented), and building a second binary search tree sorted instead by word frequency, and printing out the words again utilizing our new iterator, in descending order by frequency. Next, we can build a min-heap of the words in our text file, and print those out again ordering by frequency count. These should agree with one another!

Submit

At this point, you should have done the following:

• Checked out your repository
• Created a folder named hw7 in your repository and run svn add hw7
  

  $ svn add hw7

• Created , added, and filled in four files (with their corresponding header files): bst.c, heap.c, llist.c, word.c and Makefile inside your hw7 directory.
• If you participated in Duet Programming, make sure you svn update your duet repository, then copy over the files into your personal repository. The cp command copies files.

  mkdir CNET-cs152-win-17/hw7
  cp cs152-win-17-duet-0x/hw7/* CNET-cs152-win-17/hw7/*
  cd CNET-cs152-win-17
  svn add hw7
  

• $ svn add *.h *.c Makefile

• Compiled your executable manually and with the Makefile
• Executed your code to make sure it runs properly and inspected the results.

• $ svn commit -m "hw7 warmup complete"

Now you're ready to move on to hw7!! Remember that the homework is completed individually.