Due: Tuesday, February 28th, 2012 9:10am
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.
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:
listing_number(), which takes a phone listing and returns its phone number.
Follow the design recipe from CS 1410-20, which means that listing_number() should be implemented with residential_listing_number() and business_listing_number().
compare_listing(), which takes two phone listing and determines whether they are the same (returns 0), the first should be ordered before the second (returns -1), or the second should be ordered before the first (returns 1).
All residential listings should precede business listings. Residential listings should be sorted first by last name then by first name. Business listings should be sorted by name. Phone numbers in the listings have no effect on the order.
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).
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:
r Marx Groucho 801-555-7777 b Rubber Chicken, Inc. 801-555-BIRD r Marx Zeppo 801-555-6161 r Marx Harpo 801-555-9000 b Exploding Cigars R Us 801-555-BOOM
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:
r Marx Zeppo
If a requested listing is not in the phone book, report not found.
| Last update: Monday, February 20th, 2012mflatt@cs.utah.edu |