// htable.cpp by Leo Reyzin. CS112B1 Spring 2003 HW7. #include #include"htable.h" HashTable::HashTable() { table = NULL; tableSize = 0; } HashTable::~HashTable() { int location; HashNode *cur, *temp; if (table != NULL) { for (location = 0; location < tableSize; location++) { for (cur = table[location]; cur != NULL;) { temp = cur -> next; delete cur; cur = temp; } } delete [] table; } } // Initializes the table -- requires before any other operation. // Size is the desired table size. Returns true if successful, false // if out of memory. bool HashTable::Init(int size) { int location; if ((table = new (nothrow) HashNode* [size]) == NULL) return false; tableSize = size; for (location = 0; location < tableSize; location++) table[location] = NULL; return true; } // Inserts the data into the table, keyed by key. Returns true if successful, // false if out of memory. bool HashTable::Insert(string key, int data) { int location; HashNode * temp; location = Hash(key); temp = table[location]; table[location] = new (nothrow) HashNode (key, data, temp); if (table[location]==NULL) { table[location]=temp; return false; } return true; } // Returns true if key is in the table, false otherwise. Return the // associated data via parameter passed in by reference. bool HashTable::Find(string key, int & data) { ////////////////////////////////////////////////////////////////// // CODE GOES HERE ////////////////////////////////////////////////////////////////// } // Removes entry with key from the table if it exists. // Returns true if key is in the table, false otherwise. bool HashTable::Remove(string key) { ////////////////////////////////////////////////////////////////// // CODE GOES HERE ////////////////////////////////////////////////////////////////// } // Returns the hash value of the string. int HashTable::Hash(string key) { return (key[0]+key[key.length()-1]) % tableSize; } // Returns the number of entries in the table and the average seek time // (the average number of comparisons) required to find an entry // that is in the table. The two values are returned via // variables passed in by reference. void HashTable::GiveStats(int & numEntries, double & averageSeek) { ////////////////////////////////////////////////////////////////// // CODE GOES HERE ////////////////////////////////////////////////////////////////// } // Pretty prints the whole table -- good for debugging. void HashTable::Print() { int location; HashNode * cur; for (location = 0; location < tableSize; location++) { cout << location << ": "; for (cur = table[location]; cur != NULL; cur = cur->next) { cout << cur->key << ' ' << cur->data; if (cur->next!=NULL) { cout << ", "; } } cout << endl; } } // End of file