|
My program must do the following:
You are to write a C++ program that utilizes a Hash Table class that will store string values as the data. The class has the following public methods available:
// constructor that includes the size of the table and pointers
// to the hash and rehash functions to be used
HASHTABLE (const int tableSizeIn,
const FunctionTypeHash& hashIn, const FunctionTypeRehash& rehashIn);
~HASHTABLE(); // destructor
// insert the specified item in the hash table, returning a boolean
// value indicating whether it successfully stored the item in the
// table, and also return the number of collisions that occured
// while placing the item in the table
bool insertItem (const HashItemType& item, int& numCollisions);
// retrieve the specified item in the hash table, returning a boolean
// value indicating whether or not the value was found in the table
bool retrieveItem (HashItemType& item);
// delete the specified item in the hash table, returning a boolean
// value indicating whether or not the value was successfully deleted
bool deleteItem (const HashItemType& item);
// return an integer indicating the current number of items in the table
int itemsInTable (void);
// return an integer indicating the total number of collisions that have
// occurred during the processing of all the insertItem() calls
int totalCollisions (void);
// returning a float value indicating the average number of collisions
// based on the number of items currently in the table
float averageCollisions (void);
// return a integer (in the range of 0-100) that indicates the
// hash table's percentage full (current number of values in the
// table divided by the total number of table positions)
int percentFull (void);
// display a version of the hash table, showing a number indicating the
// current position in the table, and the data (if any) that is in
// that position
void display (void);
The string values are to be stored in the private area of the class in a dynamically-allocated array based on the first parameter passed to the class' constructor. You are free to include any other private data elements as necessary to implement the public methods.
To specify the appearance of the empty items in the table, as well as the deleted items in the table, the following global declarations should be used:
typedef string HashItemType;
const HashItemType emptyItem = "";
const HashItemType deletedItem = "** Deleted **";
// define prototypes for hash and rehash functions
typedef int (*FunctionTypeHash)(const HashItemType& item, const int tableSize);
typedef int (*FunctionTypeRehash)(const int rehashKey, const int tableSize);
The FunctionTypeHash and FunctionTypeRehash are prototypes that define the appearance of the two functions you will pass to the constructor for the Hash Table. Here are two examples of what the actual functions might look like:
int hashExample (HashItemType& item, const int tableSize) {
// the code that determines the hash code for
// the specified item goes here
}
int rehashExample (const int rehashKey, const int tableSize) {
// the code that determines the rehash code based
// on the rehash key goes here
}
// to define an instantiation of the HashTable class, the
// call to the constructor might look like:
HASHTABLE hashTableExample(31,hashExample,rehashExample);
For an additional code example showing the use of function parameters, go here.
The main() function of your program is to define several instantiations of the HashTable class, and then utilize hash and rehash functions that you devise. The intent is to provide a series of insertions, deletions, and retrievals of data from the hash table, with the intent of determining how efficient (in terms of collisions) your selection of hash and rehash functions were.
To simplify the process of defining the data for this exercise, you are to create a data file that contains a series of commands that will perform various operations on the hash table. The commands are:
add string_to_add
delete string_to_delete
retrieve string_to_retrieve
items
percent
display
The items command will display the current number of items in the hash table. The percent command will display the current percent full for the hash table. The display command will display the current contents of the hash table (basically a call to the display() method). The add, delete and retrieve commands should display a message indicating the success of their operation (add should also include the number of collisions that occurred during the add).
The following is a short example of a command sequence on a hash table that has 23 positions in the table:
add cow
add horse
add sheep
delete horse
add cat
retrieve spider
add chicken
percent
items
display
The output produced by this data sequence:
Added 'cow' after 0 collisions
Added 'horse' after 0 collisions
Added 'sheep' after 0 collisions
Successfully deleted 'horse'
Added 'cat' after 0 collisions
Did not retrieve 'spider'
Added 'chicken' after 0 collisions
The table is 17% full
There are 4 items in table
0:
1:
2:
3:
4: sheep
5:
6:
7: cow
8:
9:
10:
11:
12: chicken
13: cat
14:
15:
16: ** Deleted **
17:
18:
19:
20:
21:
22:
Note that a portion of the assignment grade will be based on how thoroughly you tested your code, and convince the instructor that it will work in all situations. As shown on the assignment submission page, you are to include a set of two of the test data files you used. Also be sure to answer the three questions on the assignment page.
As always, clear source code documentation and formatting will also factor into the final assignment grade.
Reading a datafile in C++
To read a datafile, you can define an input stream (similar to cin) and read from it just like you read from cin. To declare the new file-based input stream and then open it for reading, the C++ commands would be:
ifstream input;
input.open("datafilename",ios::in);
For example, to read the input file named "test.dat" as a sequence of words (similar to one of our previous programs), the sequence would be:
string word;
ifstream input;
input.open("test.dat",ios::in);
while (input >> word)
cout << word << endl;
input.close();
So far, this is what I have:
You are to write a C++ program that utilizes a Hash Table class that will store string values as the data. The class has the following public methods available:
// constructor that includes the size of the table and pointers
// to the hash and rehash functions to be used
HASHTABLE (const int tableSizeIn,
const FunctionTypeHash& hashIn, const FunctionTypeRehash& rehashIn);
~HASHTABLE(); // destructor
// insert the specified item in the hash table, returning a boolean
// value indicating whether it successfully stored the item in the
// table, and also return the number of collisions that occured
// while placing the item in the table
bool insertItem (const HashItemType& item, int& numCollisions);
// retrieve the specified item in the hash table, returning a boolean
// value indicating whether or not the value was found in the table
bool retrieveItem (HashItemType& item);
// delete the specified item in the hash table, returning a boolean
// value indicating whether or not the value was successfully deleted
bool deleteItem (const HashItemType& item);
// return an integer indicating the current number of items in the table
int itemsInTable (void);
// return an integer indicating the total number of collisions that have
// occurred during the processing of all the insertItem() calls
int totalCollisions (void);
// returning a float value indicating the average number of collisions
// based on the number of items currently in the table
float averageCollisions (void);
// return a integer (in the range of 0-100) that indicates the
// hash table's percentage full (current number of values in the
// table divided by the total number of table positions)
int percentFull (void);
// display a version of the hash table, showing a number indicating the
// current position in the table, and the data (if any) that is in
// that position
void display (void);
The string values are to be stored in the private area of the class in a dynamically-allocated array based on the first parameter passed to the class' constructor. You are free to include any other private data elements as necessary to implement the public methods.
To specify the appearance of the empty items in the table, as well as the deleted items in the table, the following global declarations should be used:
typedef string HashItemType;
const HashItemType emptyItem = "";
const HashItemType deletedItem = "** Deleted **";
// define prototypes for hash and rehash functions
typedef int (*FunctionTypeHash)(const HashItemType& item, const int tableSize);
typedef int (*FunctionTypeRehash)(const int rehashKey, const int tableSize);
The FunctionTypeHash and FunctionTypeRehash are prototypes that define the appearance of the two functions you will pass to the constructor for the Hash Table. Here are two examples of what the actual functions might look like:
int hashExample (HashItemType& item, const int tableSize) {
// the code that determines the hash code for
// the specified item goes here
}
int rehashExample (const int rehashKey, const int tableSize) {
// the code that determines the rehash code based
// on the rehash key goes here
}
// to define an instantiation of the HashTable class, the
// call to the constructor might look like:
HASHTABLE hashTableExample(31,hashExample,rehashExample);
For an additional code example showing the use of function parameters, go here.
The main() function of your program is to define several instantiations of the HashTable class, and then utilize hash and rehash functions that you devise. The intent is to provide a series of insertions, deletions, and retrievals of data from the hash table, with the intent of determining how efficient (in terms of collisions) your selection of hash and rehash functions were.
To simplify the process of defining the data for this exercise, you are to create a data file that contains a series of commands that will perform various operations on the hash table. The commands are:
add string_to_add
delete string_to_delete
retrieve string_to_retrieve
items
percent
display
The items command will display the current number of items in the hash table. The percent command will display the current percent full for the hash table. The display command will display the current contents of the hash table (basically a call to the display() method). The add, delete and retrieve commands should display a message indicating the success of their operation (add should also include the number of collisions that occurred during the add).
The following is a short example of a command sequence on a hash table that has 23 positions in the table:
add cow
add horse
add sheep
delete horse
add cat
retrieve spider
add chicken
percent
items
display
The output produced by this data sequence:
Added 'cow' after 0 collisions
Added 'horse' after 0 collisions
Added 'sheep' after 0 collisions
Successfully deleted 'horse'
Added 'cat' after 0 collisions
Did not retrieve 'spider'
Added 'chicken' after 0 collisions
The table is 17% full
There are 4 items in table
0:
1:
2:
3:
4: sheep
5:
6:
7: cow
8:
9:
10:
11:
12: chicken
13: cat
14:
15:
16: ** Deleted **
17:
18:
19:
20:
21:
22:
Note that a portion of the assignment grade will be based on how thoroughly you tested your code, and convince the instructor that it will work in all situations. As shown on the assignment submission page, you are to include a set of two of the test data files you used. Also be sure to answer the three questions on the assignment page.
As always, clear source code documentation and formatting will also factor into the final assignment grade.
Reading a datafile in C++
To read a datafile, you can define an input stream (similar to cin) and read from it just like you read from cin. To declare the new file-based input stream and then open it for reading, the C++ commands would be:
ifstream input;
input.open("datafilename",ios::in);
For example, to read the input file named "test.dat" as a sequence of words (similar to one of our previous programs), the sequence would be:
string word;
ifstream input;
input.open("test.dat",ios::in);
while (input >> word)
cout << word << endl;
input.close();
Can someone please point me in the direction as to where I go from here and clean up what I have, b/c I'm lost. I would really appreciate it.
|
| 