hash.cpp

数据结构与程序设计教材源码 数据结构与程序设计教材源码

Hash_table::Hash_table()
{
}
 
void Hash_table::clear()
{
   Key null;
   null.make_blank();

   for (int i = 0; i < hash_size; i++) 
      table[i].initialize(null);
}
 
Error_code Hash_table::insert(const Record &new_entry)
/* 
Post: If the Hash_table is full, a code of overflow is returned.
If the table already contains an item with the key of new_entry
a code of duplicate_error is returned.  Otherwise: The Record new_entry
is inserted into the Hash_table and success is returned.
Uses: Methods for classes Key, and Record.
The function hash.
*/
{
   Error_code result = success;
   int probe_count,           //  Counter to be sure that table is not full.
       increment,             //  Increment used for quadratic probing.
       probe;                 //  Position currently probed in the hash table.
   Key null;                  //  Null key for comparison purposes.
   null.make_blank();

   probe = hash(new_entry);
   probe_count = 0;
   increment = 1;
 
   while ((Key) table[probe] != null           //   Is the location empty?
     && (Key) table[probe] != (Key) new_entry  //   Duplicate key?
     && probe_count < (hash_size + 1) / 2) {   //   Has overflow occurred?
      probe_count++;
      probe = (probe + increment) % hash_size;
      increment += 2;         //     Prepare increment for next iteration.
   }
   if ((Key) table[probe] == null) 
      table[probe] = new_entry; //   Insert new entry.
   else if ((Key) table[probe] == (Key) new_entry) 
            result = duplicate_error;
   else result =  overflow;                  //   The table is full.
   return result;
}
 
Error_code Hash_table::retrieve(const Key &target, Record &found) const
{
   int probe_count,           //   counter to be sure that table is not full
      increment,              //   increment used for quadratic probing
      probe;                  //   position currently probed in the hash table
   Key null;                  //   null key for comparison purposes
   null.make_blank();

   probe = hash(target);
   probe_count = 0;
   increment = 1;
   while ((Key) table[probe] != null &&      //   Is the location empty?
     (Key) table[probe] != target            //   Search Successful?
     && probe_count < (hash_size + 1) / 2) { //   Full table?
      probe_count++;
      probe = (probe + increment) % hash_size;
      increment += 2;       //     Prepare increment for next iteration
   }
   if ((Key) table[probe] == target) {
      found = table[probe];
      return success;
   }
   else return not_present;
}