This takehome is open book, open notes, and open computer. Do not consult with people other than yourself and Jeff Ondich.
0 1 2 3 4 5 6 7 8 9 --------------------- 0 | 0 1 0 0 2 0 0 5 0 0 1 | 1 0 1 0 0 0 0 0 0 0 2 | 0 1 0 2 0 2 0 0 0 0 3 | 0 0 2 0 0 0 1 0 0 1 4 | 2 0 0 0 0 1 0 0 0 0 5 | 0 0 2 0 1 0 3 0 0 0 6 | 0 0 0 1 0 3 0 2 1 0 7 | 5 0 0 0 0 0 2 0 0 0 8 | 0 0 0 0 0 0 1 0 0 2 9 | 0 0 0 1 0 0 0 0 2 0
Using the graph represented by this table, do the following.
SymbolTable myTable(5); myTable["emu"] = 7; myTable["ox"] = 9;
Draw a picture of myTable after this code has executed.
#include#include const int kMaxKeyLength = 20; struct STHashNode { char key[kMaxKeyLength]; int value; STHashNode *next; virtual ~STHashNode( void ); }; class SymbolTable { int nBuckets; STHashNode **hashTable; int HashFunction( char *key ); public: SymbolTable( int size ); virtual ~SymbolTable( void ); int& operator[]( char *key ); int IsIn( char *key ); int IsIn( char *key, int& ); }; static void LowerCaseCopy( char *destination, char *source ) { int i; for( i=0; source[i] != '\0'; i++ ) destination[i] = tolower( source[i] ); destination[i] = '\0'; } /////////////////////////////////////////////////////////////// // STHashNode::~STHashNode /////////////////////////////////////////////////////////////// STHashNode::~STHashNode( void ) { if( next ) delete next; } /////////////////////////////////////////////////////////////// // SymbolTable::HashFunction /////////////////////////////////////////////////////////////// int SymbolTable::HashFunction( char *key ) { char result = 0; for( int i=0; key[i] != '\0'; i++ ) result = result ^ key[i]; return( (int)(result) % nBuckets ); } /////////////////////////////////////////////////////////////// // SymbolTable::SymbolTable /////////////////////////////////////////////////////////////// SymbolTable::SymbolTable( int size ) { nBuckets = size; hashTable = new STHashNode* [size]; for( int i=0; i < nBuckets; i++ ) hashTable[i] = 0; } /////////////////////////////////////////////////////////////// // SymbolTable::~SymbolTable /////////////////////////////////////////////////////////////// SymbolTable::~SymbolTable( void ) { for( int i=0; i < nBuckets; i++ ) if( hashTable[i] ) delete hashTable[i]; delete [] hashTable; } /////////////////////////////////////////////////////////////// // SymbolTable::operator[] /////////////////////////////////////////////////////////////// int& SymbolTable::operator[]( char *key ) { char lowerCaseKey[kMaxKeyLength]; LowerCaseCopy( lowerCaseKey, key ); int index = HashFunction( lowerCaseKey ); STHashNode *current = hashTable[index]; while( current ) { if( strcmp( lowerCaseKey, current->key ) == 0 ) return( current->value ); current = current->next; } current = new STHashNode; current->next = hashTable[index]; hashTable[index] = current; strncpy( current->key, lowerCaseKey, kMaxKeyLength ); return( current->value ); } /////////////////////////////////////////////////////////////// // SymbolTable::IsIn /////////////////////////////////////////////////////////////// int SymbolTable::IsIn( char *key ) { char lowerCaseKey[kMaxKeyLength]; LowerCaseCopy( lowerCaseKey, key ); int index = HashFunction( lowerCaseKey ); STHashNode *current = hashTable[index]; while( current ) { if( strcmp( lowerCaseKey, current->key ) == 0 ) return( 1 ); current = current->next; } return( 0 ); } /////////////////////////////////////////////////////////////// // SymbolTable::IsIn /////////////////////////////////////////////////////////////// int SymbolTable::IsIn( char *key, int& value ) { char lowerCaseKey[kMaxKeyLength]; LowerCaseCopy( lowerCaseKey, key ); int index = HashFunction( lowerCaseKey ); STHashNode *current = hashTable[index]; while( current ) { if( strcmp( lowerCaseKey, current->key ) == 0 ) { value = current->value; return( 1 ); } current = current->next; } return( 0 ); }