CS 2420-20 Homework 11

Due: Tuesday, February 28th, 2012 9:10am

Part 1 – General AVL Trees

Generalize the AVL tree implementation of avl.c from bst.zip so that it works on any kind of pointer as a value. A comparison function should be provided when creating a new AVL tree, just like hash.c accepts hashing and equality functions when creating a hash table.

Change btsearch() so that it returns a value found in the tree or NULL if the value is not already in the tree.

Your new AVL-tree implementation should be in new avl.c and avl.h files so that it can be linked with multiple programs.

Part 2 – Phone Listings

Define a new datatype of phone listsings, which come in two variants. A residential listing consists of a last name, a first name, and a phone number. A business listing consists of a name and a phone number.

Implement two functions on phone listings:

Part 3 – Phone Book

Combine your AVL and phone-listing implementations to implement a phone book, where entries can be added to the phone book and looked up.

Looking up a phone number relies on the fact that listing comparisons ignore the phone number. You can create a “dummy” residential or business listing (with an dummy phone number), look for an existing value in the AVL tree that is equal to the dummy listing, and then extract the number from the existing listing (if any).

Part 4 – Phone Book Program

Make your program accept a phone-book file as a command line argument. A phone book file is a sequence of lines, where groups of lines correspond to residential and business entries. If a line starting a group is "r", then the next line is a residential last name, the second line afterward is a first name, and the third line afterward is a phone number. If a line starting a group is "b", then the next line contains a business name, and the second line afterward is a phone number.

For example, the following phone-book file content has five listings:

  Rubber Chicken, Inc.
  Exploding Cigars R Us

After the program loads a phone book from the give file, read lines from stdin and look up the request numbers. The request has the same shape as a group of lines in the phone-book file, but without the phone number.

For example, the following lines on stdin request a residential phone number for Zeppo Marx:


If a requested listing is not in the phone book, report not found.

Last update: Monday, February 20th, 2012