Laboratory 10 Solutions

CSCI 132 Data Structures--Spring 2014

Laboratory 10 Solutions
Solution to Hash_table function code:
/*******************************************************************
 * Name: Brenda Student
 * Date: 4/21/14
 * Course: CSCI 132 Section 01
 * Assignment: Lab 10
 * Instructor: Royden
 * Program: hash.cc
 * Purpose: Implementation of functions for the Hash_table class.
 ***************************************************************************/
Error_code Hash_table::insert(Cell *new_entry)
{
  int probe, location;
  probe = hash(new_entry->row, new_entry->col);
  if (sequential_search(table[probe], new_entry->row, new_entry->col,
                                        location) == not_present) {
    return (table[probe].insert(0, new_entry));
  }else
    return (duplicate_error);
}

bool Hash_table::retrieve(int row, int col)const
{
  int probe, location;
  probe = hash(row, col);
  if (sequential_search(table[probe], row, col, location)== success) {
    return true;
  } else 
    return false;
}


int hash(int row, int col)
/* Post: The function returns the hashed valued between 0 and hash_size - 1 that
corresponds to the given Cell parameter. */
{
  int value;
  value = row + factor * col;
  value %= hash_size;
  if (value < 0) return value + hash_size;
  else return value;
}

Error_code sequential_search(const List<Cell *> &search_list, int my_row, int my_col, 
                                           int &location) {
  Cell *found;
  location = -1;
  for (int i = 0; i < search_list.size(); i++ ) {
    if(search_list.retrieve(i, found) != success ) {
    	cout << "Error retrieving item from chained list."  << endl;
    }
    if ((found -> row == my_row) && (found -> col == my_col)) {
      location = i;
      return success;
    }
  }
  return not_present;
}