Posted By

DrPepper on 11/11/11


Tagged


Versions (?)

[CISP 430] HASH TABLE FROM TEXT BOOK EXAMPLE (table1.h)


 / Published in: C++
 

  1. // FILE: table1.h (part of the namespace main_savitch_12A)
  2. // TEMPLATE CLASS PROVIDED: table<RecordType> (a table of records with keys).
  3. // This class is a container template class for a table of records.
  4. // The template parameter, RecordType, is the data type of the records in the
  5. // table. It may be any of the bulit-in C++ types (int, char, etc.), or a
  6. // class with a default constructor, an assignment operator, and an integer
  7. // member variable called key.
  8. //
  9. // MEMBER CONSTANT for the table<RecordType> class:
  10. // static const size_type CAPACITY = ________
  11. // table<RecordType>::CAPACITY is the maximum number of records held by a table.
  12. //
  13. // CONSTRUCTOR for the table<RecordType> template class:
  14. // table( )
  15. // Postcondition: The table has been initialized as an empty table.
  16. //
  17. // MODIFICATION MEMBER FUNCTIONS for the table<RecordType> class:
  18. // void insert(const RecordType& entry)
  19. // Precondition: entry.key >= 0. Also if entry.key is not already a key in
  20. // the table, then the table has space for another record
  21. // (i.e., size( ) < CAPACITY).
  22. // Postcondition: If the table already had a record with a key equal to
  23. // entry.key, then that record is replaced by entry. Otherwise, entry has
  24. // been added as a new record of the table.
  25. //
  26. // void remove(int key)
  27. // Postcondition: If a record was in the table with the specified key, then
  28. // that record has been removed; otherwise the table is unchanged.
  29. //
  30. // CONSTANT MEMBER FUNCTIONS for the table<RecordType> class:
  31. // bool is_present(const Item& target) const
  32. // Postcondition: The return value is true if there is a record in the
  33. // table with the specified key. Otherwise, the return value is false.
  34. //
  35. // void find(int key, bool& found, RecordType& result) const
  36. // Postcondition: If a record is in the table with the specified key, then
  37. // found is true and result is set to a copy of the record with that key.
  38. // Otherwise found is false and the result contains garbage.
  39. //
  40. // size_type size( ) const
  41. // Postcondition: Return value is the total number of records in the
  42. // table.
  43. //
  44. // VALUE SEMANTICS for the table<RecordType> template class:
  45. // Assignments and the copy constructor may be used with table objects.
  46.  
  47. #ifndef TABLE1_H
  48. #define TABLE1_H
  49. #include <cstdlib> // Provides size_t
  50.  
  51. namespace main_savitch_12A
  52. {
  53. template <class RecordType>
  54. class table
  55. {
  56. public:
  57. // MEMBER CONSTANT -- See Appendix E if this fails to compile.
  58. static const std::size_t CAPACITY = 811;
  59. // CONSTRUCTOR
  60. table( );
  61. // MODIFICATION MEMBER FUNCTIONS
  62. void insert(const RecordType& entry);
  63. void remove(int key);
  64. // CONSTANT MEMBER FUNCTIONS
  65. bool is_present(int key) const;
  66. void find(int key, bool& found, RecordType& result) const;
  67. std::size_t size( ) const { return used; }
  68. private:
  69. // MEMBER CONSTANTS -- These are used in the key field of special records.
  70. static const int NEVER_USED = -1;
  71. static const int PREVIOUSLY_USED = -2;
  72. // MEMBER VARIABLES
  73. RecordType data[CAPACITY];
  74. std::size_t used;
  75. // HELPER FUNCTIONS
  76. std::size_t hash(int key) const;
  77. std::size_t next_index(std::size_t index) const;
  78. void find_index(int key, bool& found, std::size_t& index) const;
  79. bool never_used(std::size_t index) const;
  80. bool is_vacant(std::size_t index) const;
  81. };
  82. }
  83. #include "table1.template" // Include the implementation.
  84. #endif

Report this snippet  

You need to login to post a comment.