You are a script writer for your favorite TV show and you want to write a C++ program to make your job easier. To this end you decide to write a hierarchy of classes (with abstract class Character being the top most class) that contains all of the roles in your show. Then you create a data structure (a list is fine) of characters that contains one or more static variables that measure the "state" of the room in which the dialog takes place. You then repeatedly iterate through the list of characters having each deliver a line of dialog specific to them (use virtual functions for this). The line of dialog they deliver is, of course, dependent upon the "state" of the room. When a character delivers a line this changes the "state" of the room by modifying the one or more variables in the room (stored in the list class). Using this model you can create flowing dialog of about the same intelligence as many TV shows.
As an example, if you are a Star Trek fan you might have characters Scotty, Bones and Kirk (each instances of a subclass of Character). You might also have static variables Indignation and Pressure. You might then have dialog that looks like the following:
You must create at least three characters and at least three subclasses of Character. Your "world" must have at least two state variables. You must produce at least 8 coherent lines of dialog. The iteration should terminate when some "state" condition is met. Further the list node must use REFERENCES to characters and not pointers to characters. Note that it is not hard to create cycles of dialog - try it! Also - try different initializations for the state variables and see how this changes the dialog.
Finally, you must write a dynamic data structure for this (no arrays). An interesting thing to try is to write code so that if a character gets angry enough or some such thing that he exits the conversation by deleting himself from the list (how do you do this?).
A hash table is a dynamic data structure that stores information by taking a value and computing a hash index for it by using the value as an argument to a hash function. It then inserts the value in the list of an array of lists with that index. (For example, if I were storing integers in a hash table I might have an array of lists of integers of some fixed size (say 27). As a hash function I might just use modulo. Then if I wanted to store 29 in the hash table I would compute the index as 2 (29%27 = 2) and store 29 at the head of the third list (indexed from 0). If I then wanted to know if 29 was in the list I would have to compute the index for 29 (in this case 2) and then search the contents of this list.
Using templates write a generic hash table class that takes at least a type and a hash function as template parameters. Note that the hash function must also be templatized to the type of data that it is hashing. It is your responsibility to make sure that the hash function does not return values that are larger than the size of the array (you can throw an exception in this case). You may want to use additional template parameters to prevent or detect this (throw an excpetion). For this question you may use the library template list class if you so desire or you can write your own (you may not use the library hash table class).
The hash data structure must support Insertion (without duplication), Deletion, Query and Clear operations. Write sample code to test your hash table class with at least two distinct instantiations. It must also not leak memory (you must have proper destructors). You do not need to write an assignment operator or a copy constructor for this class. Also, at least one of the hash functions you use must be a template class that is specialized in at least one interesting way.
Note that your grade on each of these problems will be based in large part on your proper usage of the facilities of the C++ language and not strictly on functionality.
Last Updated: Tuesday, December 14, 2004 12:17:55 PM