Sample Data Structures Questions Chapter 12 Searching

8. Suppose that I have the following record_type definition for a record in a hash table:

 struct record_type { int key; ... other stuff may also appear here ... }; 

The hash table uses open addressing with linear probing. The table size is a global constant called CAPACITY. Locations of the table that have NEVER been used will contain the key -1. Locations of the table that were once used but are now vacant will contain the key -2. All valid keys will be non-negative, and the hash function is:

 size_t hash(int key) { return (key % CAPACITY); } 

Complete the implementation of the following function. There is no need to check the precondition, but your code must be as efficient as possible.

bool key_occurs(const record_type data[ ], int search_key) // Precondition: data[0]...data[CAPACITY-1] is an open address hash table // as described above. // Postcondition: If search_key occurs as a key of a record in the table, then // the function returns true; otherwise the function returns false.