ok, working book "data structures , other objects using c++ 4th ed". making hash table accepts keys , hashes them correct spots using open addressing resolve collisions. code below have.
the header file
#ifndef table1_h #define table1_h #include <cstdlib> // provides size_t { template <class recordtype> class table { public: // member constant -- see appendix e if fails compile. static const std::size_t capacity = 811; // constructor table( ); // modification member functions void insert(const recordtype& entry); void remove(int key); // constant member functions bool is_present(int key) const; void find(int key, bool& found, recordtype& result) const; std::size_t size( ) const { return used; } private: // member constants -- these used in key field of special records. static const int never_used = -1; static const int previously_used = -2; // member variables recordtype data[capacity]; std::size_t used; // helper functions std::size_t hash(int key) const; std::size_t next_index(std::size_t index) const; void find_index(int key, bool& found, std::size_t& index) const; bool never_used(std::size_t index) const; bool is_vacant(std::size_t index) const; }; } #include "table1.template" // include implementation. #endif and template class
template <class recordtype> const std::size_t table<recordtype>::capacity; template <class recordtype> const int table<recordtype>::never_used; template <class recordtype> const int table<recordtype>::previously_used; template <class recordtype> table<recordtype>::table( ) { std::size_t i; used = 0; (i = 0; < capacity; ++i) data[i].key = never_used; // indicates spot that's never been used. } template <class recordtype> void table<recordtype>::insert(const recordtype& entry) // library facilities used: cassert { bool already_present; // true if entry.key in table std::size_t index; // data[index] location new entry assert(entry.key >= 0); // set index data[index] spot place new entry. find_index(entry.key, already_present, index); // if key wasn't there, find location new entry. if (!already_present) { assert(size( ) < capacity); index = hash(entry.key); while (!is_vacant(index)) index = next_index(index); ++used; } data[index] = entry; } template <class recordtype> void table<recordtype>::remove(int key) // library facilities used: cassert { bool found; // true if key occurs somewhere in table std::size_t index; // spot data[index].key == key assert(key >= 0); find_index(key, found, index); if (found) { // key found, remove record , reduce used 1. data[index].key = previously_used; // indicates spot that's no longer in use. --used; } } template <class recordtype> bool table<recordtype>::is_present(int key) const // library facilities used: assert.h { bool found; std::size_t index; assert(key >= 0); find_index(key, found, index); return found; } template <class recordtype> void table<recordtype>::find(int key, bool& found, recordtype& result) const // library facilities used: cassert.h { std::size_t index; assert(key >= 0); find_index(key, found, index); if (found) result = data[index]; } template <class recordtype> inline std::size_t table<recordtype>::hash(int key) const { return (key % capacity); } template <class recordtype> inline std::size_t table<recordtype>::next_index(std::size_t index) const // library facilities used: cstdlib { return ((index+1) % capacity); } template <class recordtype> void table<recordtype>::find_index(int key, bool& found, std::size_t& i) const // library facilities used: cstdlib { std::size_t count; // number of entries have been examined count = 0; = hash(key); while((count < capacity) && (data[i].key != never_used) && (data[i].key != key)) { ++count; = next_index(i); } found = (data[i].key == key); // tried adding counter = counter +1. // failed, reason in comments. } template <class recordtype> inline bool table<recordtype>::never_used(std::size_t index) const { return (data[index].key == never_used); } template <class recordtype> inline bool table<recordtype>::is_vacant(std::size_t index) const { return (data[index].key == never_used) || (data[index].key == previously_used); } my question hoping is, how keep track of number of comparisons made find each value in table?
so far, tried making private member variable , increasing each iteration through find_index loop, didn't work. overall goal graph average number of comparisons vs. table density.
you should create table stores amount of comparisons each call find_index. value key , amount of comparisons value.
Comments
Post a Comment