MCX2                                                                                                                 Math Department
Mr. Gary Jaye                                                                                                       Danny Jaye, A.P.S.

                                          1997 APCS AB Exam: Question 4

This question concerns the design of a hash table to be used to store names.
Assume that a class Name has been declared as shown below. 

class Name
{
  public:
    Name();                       // constructor
    Name(const apstring & s);     // construct from string

    // accessor functions

    int length()                 const;  // returns # characters in name
    char operator [](int k)      const;  // return k-th character of name
    bool Equal(const Name & rhs) const;  // check equality
    
  private:
    // declarations here
};

// commented prototypes
// int Name::length() const;
// postcondition: returns # characters in self

// char Name::operator[](int k) const;
// postcondition: if 0 <= k < length(), returns k-th character 
//                otherwise returns space

// bool Name::Equal(const Name & rhs) const;
// postcondition: returns true if rhs == self, otherwise returns false

bool operator == (const Name & lhs, const Name & rhs)
// postcondition: returns true if lhs == rhs, otherwise returns false    
{
    return lhs.Equal(rhs);
}

Also assume the following global constant has been declared 

   const int SIZE = some positive integer;

Part A 
Write function Hash, whose header is given below. Hash returns the hash value
of its parameter nn. The hash value is an integer in the range 0..SIZE-1,
computed as follows: 

  1.Compute the sum of the first and last characters of the given name
    (treat the characters as ints). 

  2.Convert the sum to an integer in the range 0..SIZE-1 by finding the
    remainder when sum is divided by SIZE 

For example, if SIZE = 5: 

Complete the function Hash below the following header. In writing Hash you
may call member functions of the class Name (Name::length, Name::operator[],
Name::Equal) and the overloaded operator == . You will not receive full
credit if your code relies on a particular implementation of Name. Assume
that function Hash is called only with parameters that satisfy its precondition. 

  int Hash(const Name & nn)
  // preconditon: 0 < nn.length()
  // postcondition: returns hash value of nn

Part B 
Assume that the hash table will be implemented using an apvector of linked
lists, indexed from 0 to SIZE-1. The list in the kth element of the vector
will hold all names with hash value k that have been inserted into the hash
table. If no inserted name has hash value k, then the kth element of the
vector will be NULL/0. For example, if SIZE is 5 and the names Ken, Susan,
Mark, Cary, Don, and X have been inserted into the hash table, then the
vector will be as shown below.

   

Assume that nodes for the linked list have been declared as follows: 

    struct Node
    {
        Name info;    
        Node * next;
    };

Write function Lookup, whose header is given below. Lookup should return
true if the parameter nn is in the hash table table; otherwise it should
return false. Lookup should use the hash value of nn to identify the list
that might contain nn; then it should search for nn in the list. For example,
if variable Table represents the hash table shown on the previous page: 

In writing Lookup you may call member functions of the class Name and the
overloaded operator == for Name values. You will not receive full credit if
your code relies on a particular implementation of Name. You may also call
the function Hash of part (a). Assume that Hash works as specified,
regardless of what you wrote in part (a). Assume that function Lookup is
called only with parameters that satisfy its precondition. 

Complete function Lookup below the following header. 

bool Lookup(const apvector<Node *> & table, const Name & nn)
// precondition: for all 0 <= k < SIZE, either table[k] == NULL/0    
//               or table[k] is a pointer to a linked list of names
//               all of which have hash value k
// postcondition: returns true if nn is in table;
//                otherwise returns false