// my size is not decreasing when I erase a record. //dvr_hwch.cpp #include <ios
ID: 3568842 • Letter: #
Question
// my size is not decreasing when I erase a record.
//dvr_hwch.cpp
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
#include "hash_chn.h"
void print_menu( );
int main( )
{
//List test; // A List to perform tests on
char choice; // Command entered by the user
Table dataTable;
RecordType rec;
int key;
bool found;
int size;
do
{
print_menu( );
cout << "Enter choice: ";
cin >> choice;
cout << endl;
choice = toupper(choice);
switch (choice)
{
case 'I': // insert
cout << "Enter key (int >= 0) for record: ";
cin >> rec.key;
cout << "Enter data (int) for record: ";
cin >> rec.data;
dataTable.insert( rec );
cout << "Record was inserted in table" << endl << endl;
break;
case 'F': // find
cout << "Enter key (int >= 0) to search for: ";
cin >> key;
dataTable.find( key, found, rec );
if ( found )
{
cout << "Record was found." << endl;
cout << " key = " << setw(8)
<< rec.key << endl;
cout << " data = " << setw(8)
<< rec.data << endl;
}
else
cout << "Record with key " << key << " not found."
<< endl << endl;
break;
case 'E': // erase
cout << "Enter key (int >= 0) to erase: ";
cin >> key;
if ( dataTable.erase( key ) )
cout << "Record was erased from table" << endl << endl;
else
cout << "Record with key " << key << " not found."
<< endl << endl;
break;
case 'S': // size
size = dataTable.size( );
cout << "There are " << size << " records in the table."
<< endl;
// cout << "There are " << (CAPACITY - size)
// << " empty slots left in the table." << endl << endl;
break;
case 'Q': cout << "Test program ended." << endl;
break;
default: cout << choice << " is invalid." << endl;
}
}
while ((choice != 'Q'));
return EXIT_SUCCESS;
}
void print_menu( )
{
cout << endl;
cout << "The following choices are available: " << endl;
cout << " I Insert a new record or update existing record" << endl;
cout << " F Find a record" << endl;
cout << " E Erase a record" << endl;
cout << " S Get the number of records" << endl;
cout << " Q Quit this test program" << endl << endl;
}
//--------------------------------------------------------
//hash_chn.cpp
#include <cassert>
#include <cstdlib>
using namespace std;
#include "hash_chn.h"
Table::Table( )
{
used = 0;
for ( int i = 0; i < CAPACITY; i++ )
table[i] = NULL;
}
void Table::insert( const RecordType& entry )
{
bool alreadyThere;
Node* nodePtr;
assert( entry.key >= 0 );
findPtr( entry.key, alreadyThere, nodePtr );
if( !alreadyThere )
{
int i = hash( entry.key ); // get index of "bucket" where entry belongs
// insert at beginning of list
Node* temp = new Node;
temp->rec = entry; // copy record
temp->next = table[i];
table[i] = temp;
used++;
}
else
{
// nodePtr points to existing record that should be updated
nodePtr->rec = entry;
}
}
int Table::hash( int key ) const
{
return key % CAPACITY;
}
int Table::size( ) const
{
return used;
}
// findPtr function
// void findPtr( int key, bool& found, Node*& nodePtr ) const;
// Preconditions: key >= 0
// Postconditions: If a record with the indicated key is in the table,
// then found is true and nodePtr is set to point to that record.
// Otherwise, found is false and nodePtr contains garbage.
void Table::findPtr( int key, bool& found, Node*& nodePtr ) const
{
int i;
Node* ptr;
i = hash( key );
ptr = table[i];
found = false;
while ( !found && ptr != NULL )
{
if ( key == ptr->rec.key )
{
found = true;
nodePtr = ptr;
}
ptr = ptr->next;
}
if ( !found )
nodePtr = NULL;
}
void Table::find( int key, bool& found, RecordType& result ) const
{
Node* nodePtr;
assert( key >= 0 );
findPtr( key, found, nodePtr );
if ( found )
{
result = nodePtr->rec;
}
}
bool Table::erase( int key )
{
assert( key >= 0 );
// first try to find the item
Node* nodePtr;
bool found;
findPtr( key, found, nodePtr );
if ( found )
{
int i = hash( key );
// the item found, erase it now
Node* headNode = table[i];
if (nodePtr != headNode)
{
// copy the data from the head node into the node to be deleted
nodePtr->rec = headNode->rec;
}
// then delete the head node.
table[i] = headNode->next;
delete headNode;
}
return found;
}
//---------------------------------------------------------------------
//hash_chn.h
typedef int ItemType;
const int CAPACITY = 31;
struct RecordType
{
int key;
ItemType data;
};
struct Node
{
RecordType rec;
Node* next;
};
class Table
{
public:
Table( );
void insert( const RecordType& entry );
void find( int key, bool& found, RecordType& result ) const;
bool erase( int key );
int size( ) const;
private:
int hash( int key ) const;
void findPtr( int key, bool& found, Node*& ptr ) const;
Node* table[CAPACITY];
int used;
};
//-------------------------------------------------------------------------
Explanation / Answer
//You have to update the used variable when you erase a record
bool Table::erase( int key )
{
assert( key >= 0 );
// first try to find the item
Node* nodePtr;
bool found;
findPtr( key, found, nodePtr );
if ( found )
{
int i = hash( key );
// the item found, erase it now
Node* headNode = table[i];
if (nodePtr != headNode)
{
// copy the data from the head node into the node to be deleted
nodePtr->rec = headNode->rec;
}
// then delete the head node.
table[i] = headNode->next;
delete headNode;
//update the used variable
used--;
}
return found;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.