CS 113: Introduction to Computer Science II with Introduction to C

Steve Homer---Spring 1999

Homework 5---due Tuesday, April 13

Reading: Standish, Chapter 9, pages 337-375 and Chapter 10, pages 405-428

The files you must submit for this homework are exactly: h5acct.c, h5tree.h, h5tree.c, and h5.scr.

In this assignment you will implement a binary search tree. This will include implementing functions to create a tree, destroy it, add an element to the tree, delete an element, find an element in the tree and print out the elements of the tree.

You will use your binary search tree to build and manipulate a small account database. The account numbers will serve as the keys for your binary search tree. You will read the initial data for the account from a datafile, write functions which operate on the database once the initial tree has been built, and write out the changed database to an output file.

An Implementation of Binary Search Trees

You will implement a Tree Data Structure that holds information about credit card accounts. For each account you will store:

So, an account's info may look like "24365 Smith 355".

Your tree module must have the following interface: 

typedef ?? treeKeyT;

typedef ?? treeValueT;

typedef struct {
  treeKeyT key;
  treeValueT value;
} treeElementT;

typedef struct treeCDT *treeADT;

treeADT TreeCreate(void);
void TreeDestroy(treeADT tree);
void TreeAdd(treeADT tree, treeElementT element);
treeElementT TreeDelete(treeADT tree, treeKeyT key);
treeElementT *TreeFind(treeADT tree, treeKeyT key);
void TreePrint(treeADT tree, FILE *outfileP);

Note that our elements now have 2 distinct parts. The key is the account number, the rest of the fields for an account (name and balance) form the value, which is the other part of a tree element. Your tree implementation can access the key and value, but may not access fields inside of those parts (since that would make the code less generic).

The interface must also contain the prototype for one more function: 

/*
 * PrintElement is not defined here in the tree module,
 * it is only prototyped here.
 */
void PrintElement(treeElementT element, FILE *outfileP);

However, this last function must be defined in the main program h5acct.c, not in the implementation file. In other words, the fact the the tree module only has a prototype for PrintElement() says that this function must be defined in a main program in order to use the module.

The implementation file will need 2 types of its own: 

typedef struct treeNodeTag {
  ...
} treeNodeT;

typedef struct treeCDT {
  ...
} treeCDT;

Each treeNodeT will hold one element in the tree (linked) representation. The type treeCDT should hold the field(s) you need to keep track of a tree.

Only generic tree code should go in this tree module. Code specific to the accounts (except for the type of things stored in each account, which goes in h5tree.h) should go in the main program h5acct.c.

You must submit files h5tree.h, containing the interface, and h5tree.c, containing the implementation.

A simple test program, /cs/course/cs113/current/hw5/h5treetest.c, is available for you to test your tree module. We strongly suggest that you compile and run your tree module with this code to help ensure your code works properly and that it is generic (i.e., note that the test program uses a different kind of key and value).

An Account Database

Using your implementation of a binary search tree, implement a simple account database program.

When the program starts, it should read in the initial set of accounts from the data file /cs/course/cs113/current/hw5/accounts.in. It should do this by opening the file with fopen(). reading from it, etc. Examine that file to determine the format of account data (there is one account per line).

Once the initial accounts are read in, you should repeatedly prompted the user, allowing them to enter commands to:

Your program should print prompts and label its output.

You may assume that fields will be entered correctly, i.e., account numbers and balances will only have digits in them.

Remember that the function PrintElement, which must take an account (i.e., an element) and print out its fields in a reasonable manner, must be defined in this main program.

Add the following types to your main program (after you include h5tree.h): 

typedef treeElementT accountT;

typedef treeKeyT acctNumT;

That way you can declare account variables with more descriptive types in the main program. I.e., you can do: 

accountT acct1;
acctNumT acct_num;

acct1.key = 4567;
strcpy(acct1.value.name, name);
acct1.value.balance = 789;
acct_num = acct1.key;

You must submit a file named h5acct.c that contains this main program.

How the Main Program Uses the Tree

All accounts are stored in a tree, so the main program must call tree functions to add accounts, remove accounts, etc.

Here is how each tree function should operate and how it will be used in the main program: