Question: I have the remove(int key); function working in tableChain_template.h. Except when i delete the item that was the head pointer. If i try to display
I have the remove(int key); function working in tableChain_template.h. Except when i delete the item that was the head pointer. If i try to display right after i remove it, there is a garbage value that is placed in the key and data field and an exception is thrown. I have included the same test program at the bottom so you are able to run it and see for yourself.
Here is the sample data to test.
After you try and delete key 3 or 811 call the 'D' for display and you'll see the garbage value placed there, and the exception thrown.
The problem is when you try to remove keys 811 and 3.
KEY
4058
VALUE
33.2
*******
KEY
2
VALUE
22.2
KEY
1
VALUE
11.4
KEY
811
VALUE
100
KEY
1623
VALUE
11.3
KEY
2435
VALUE
22.1
KEY
3245
VALUE
11.2
KEY
5678
VALUE
11.1
KEY
3
VALUE
33.1
**************tableChain_template.h************************
#include // Provides assert
#include // Provides size_t
#include "hashNode.h" // Provides the hashNode struct and toolkit
template
tableChain::tableChain()
// Library facilities used: cstdlib
{
size_t i;
total_records = 0;
for (i = 0; i < TABLE_SIZE; i++)
data[i] = nullptr;
}
template
tableChain::tableChain(const tableChain& source)
// Library facilities used: hashNode.h, cstdlib
{
size_t i;
hashNode* tail_ptr; // Needed for list_copy
for (i = 0; i < TABLE_SIZE; i++)
list_copy(source.data[i], data[i], tail_ptr);
total_records = source.total_records;
}
template
tableChain::~tableChain()
// Library facilities used: hashNode.h
{
size_t i;
total_records = 0;
for (i = 0; i < TABLE_SIZE; i++)
list_clear(data[i]);
}
template
void tableChain::insert(const RecordType& entry)
// Library facilities used: cassert, hashNode.h
{
hashNode* cursor; // set to point to existing hashNode with given key
assert(entry.key >= 0);
// Set cursor to point to existing hashNode with given key (if there is one)
cursor = find_node(entry.key);
if (cursor != nullptr)
{ // Add in existing spot
cursor->data = entry;
}
else
{ // Add in a new spot
list_head_insert(data[hash(entry.key)], entry);
total_records++;
}
}
template
void tableChain::remove(int key)
// Library facilities used: cassert, hashNode.h
{
hashNode
hashNode
size_t keyValue = hash(key);
cursor = data[keyValue];
if (cursor == nullptr)
return;
else
{
if (cursor->link == nullptr)
{
list_head_remove(cursor);
}
else
{
while (cursor->data.key != key)
{
prev = cursor;
cursor = cursor->link;
}
if (cursor->link == nullptr)
{
cursor = nullptr;
}
else
{
//we are removing from the inside of the linked list
list_remove(prev);
}
} //end else
} //end else
total_records--;
}
template
void tableChain::operator =(const tableChain& source)
// Library facilities used: hashNode.h, cstdlib
{
size_t i;
hashNode* tail_ptr; // Needed for list_copy
if (this == &source)
return; // Avoid self-assignment
for (i = 0; i < TABLE_SIZE; i++)
{
list_clear(data[i]);
list_copy(source.data[i], data[i], tail_ptr);
}
total_records = source.total_records;
}
template
bool tableChain::is_present(int key) const
// Library facilities used: cassert, cstdlib
{
assert(key >= 0);
return (find_node(key) != nullptr);
}
template
void tableChain::find(int key, bool& found, RecordType& result) const
// Library facilities used: cstdlib
{
hashNode *cursor;
cursor = find_node(key);
found = (cursor != nullptr);
if (found)
result = cursor->data;
}
template
size_t tableChain::hash(int key) const
// Library facilities used: cstdlib
{
return (key % TABLE_SIZE);
}
template
hashNode* tableChain::find_node(int key) const
// Postcondition: The return value is a pointer to the record with the
// specified key (if there is one). If there is no such hashNode, the return value
// is the nullptr pointer.
// Library facilities used: hashNode.h, cstdlib
{
hashNode* cursor;
cursor = data[hash(key)];
while ((cursor != nullptr) && ((cursor->data).key != key))
cursor = cursor->link;
return cursor;
}
//***DISPLAY MEMBER FUNCTION****
template
void tableChain::display_all()
{
cout << " ***DISPLAY ALL TABLE ENTRIES***" << endl;
//loop through each array element
for (size_t i = 0; i < TABLE_SIZE; i++)
{
//if an element is empty
if (data[i] != nullptr)
{
cout << "Index = " << i << endl;
//Display all values in the locatoin
for (hashNode* cursor = data[i]; cursor != nullptr; cursor = cursor->link)
{
cout << '\t' << cursor->data << endl;
}
}
}
}
***************************tableChain.h**************************
#ifndef tableChain_H
#define tableChain_H
#include // Provides size_t
#include "hashNode.h" // Provides the hashNode struct and toolkit
template
class tableChain
{
public:
// MEMBER CONSTANT -- See Appendix E if this fails to compile.
static const std::size_t TABLE_SIZE = 811;
// CONSTRUCTORS AND DESTRUCTOR
tableChain();
tableChain(const tableChain& source);
~tableChain();
// MODIFICATION MEMBER FUNCTIONS
void insert(const RecordType& entry);
void remove(int key);
void operator =(const tableChain& source);
// CONSTANT MEMBER FUNCTIONS
void find(int key, bool& found, RecordType& result) const;
bool is_present(int key) const;
std::size_t size() const { return total_records; }
//***DISPLAY MEMBER FUNCTION*********
void display_all();
private:
hashNode *data[TABLE_SIZE];
std::size_t total_records;
// HELPER MEMBER FUNCTION
std::size_t hash(int key) const;
hashNode* find_node(int key) const;
};
#include "tableChain_template.h" // Include the implementation
#endif
*************************hashNode.h******************************
#ifndef HASH_NODE_H
#define HASH_NODE_H
#include // Provides size_t
template
struct hashNode
{
Item data;
hashNode *link;
};
// FUNCTIONS for the linked list toolkit
template
size_t list_length(hashNode* head_ptr);
template
void list_head_insert(hashNode*& head_ptr, const Item& entry);
template
void list_insert(hashNode* previous_ptr, const Item& entry);
template
hashNode* list_search(hashNode* head_ptr, const Item& target);
template
hashNode* list_locate(hashNode* head_ptr, SizeType position);
template
void list_head_remove(hashNode*& head_ptr);
template
void list_remove(hashNode* previous_ptr);
template
void list_clear(hashNode*& head_ptr);
template
void list_copy
(hashNode* source_ptr, hashNode*& head_ptr, hashNode*& tail_ptr);
template
void list_piece
(hashNode* source_ptr, hashNode* end_ptr,
hashNode*& head_ptr, hashNode*& tail_ptr);
#include "hashNode_template.h" // Include the implementation
#endif
***********************hashNode_template.h*****************************
#include // Provides assert
#include // Provides nullptr and size_t
template
size_t list_length(hashNode* head_ptr)
// Library facilities used: stdlib.h
{
hashNode *cursor;
size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != nullptr; cursor = cursor->link)
answer++;
return answer;
}
template
void list_head_insert(hashNode*& head_ptr, const Item& new_item)
{
hashNode *insert_ptr;
insert_ptr = new hashNode;
insert_ptr->data = new_item;
insert_ptr->link = head_ptr;
head_ptr = insert_ptr;
}
template
void list_insert(hashNode* previous_ptr, const Item& new_item)
{
hashNode *insert_ptr;
insert_ptr = new hashNode;
insert_ptr->data = new_item;
insert_ptr->link = previous_ptr->link;
previous_ptr->link = insert_ptr;
}
template
hashNode* list_search(hashNode* head_ptr, const Item& target)
{
hashNode *cursor;
for (cursor = head_ptr; cursor != nullptr; cursor = cursor->link)
if (cursor->data == target)
return cursor;
return nullptr;
}
template
hashNode* list_locate(hashNode* head_ptr, SizeType position)
// Library facilities assert.h, stdlib.h
{
hashNode *cursor;
size_t i;
assert(position > 0);
cursor = head_ptr;
for (i = 1; (i != position) && (cursor != nullptr); i++)
cursor = cursor->link;
return cursor;
}
template
void list_head_remove(hashNode*& head_ptr)
{
hashNode *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link;
delete remove_ptr;
}
template
void list_remove(hashNode* previous_ptr)
{
hashNode *remove_ptr;
remove_ptr = previous_ptr->link;
previous_ptr->link = remove_ptr->link;
delete remove_ptr;
}
template
void list_clear(hashNode*& head_ptr)
// Library facilities used: stdlib.h
{
while (head_ptr != nullptr)
list_head_remove(head_ptr);
}
template
void list_copy
(hashNode* source_ptr, hashNode*& head_ptr, hashNode*& tail_ptr)
// Library facilities used: stdlib.h
{
head_ptr = nullptr;
tail_ptr = nullptr;
// Handle the case of the empty list
if (source_ptr == nullptr)
return;
// Make the head node for the newly created list, and put data in it
list_head_insert(head_ptr, source_ptr->data);
tail_ptr = head_ptr;
// Copy the rest of the nodes one at a time, adding at the tail of new list
for (source_ptr = source_ptr->link; source_ptr != nullptr; source_ptr = source_ptr->link)
{
list_insert(tail_ptr, source_ptr->data);
tail_ptr = tail_ptr->link;
}
}
template
void list_piece
(hashNode* start_ptr, hashNode* end_ptr, hashNode*& head_ptr, hashNode*& tail_ptr)
// Library facilities used: assert.h, stdlib.h
{
head_ptr = nullptr;
tail_ptr = nullptr;
// Handle the case of the empty list
if (start_ptr == nullptr)
return;
// Make the head node for the newly created list, and put data in it
list_head_insert(head_ptr, start_ptr->data);
tail_ptr = head_ptr;
if (start_ptr == end_ptr)
return;
// Copy the rest of the nodes one at a time, adding at the tail of new list
for (start_ptr = start_ptr->link; start_ptr != nullptr; start_ptr = start_ptr->link)
{
list_insert(tail_ptr, start_ptr->data);
tail_ptr = tail_ptr->link;
if (start_ptr == end_ptr)
return;
}
}
****************************tableChain_test.cxx******************************
#include // Provides toupper
#include // Provides EXIT_SUCCESS and size_t
#include // Provides cin, cout
#include "tableChain.h" // Provides the table class
using namespace std;
// Struct definition for the test_record_type, which has a key and a double.
struct test_record_type
{
int key;
double data;
};
//Overload binary insertion operator for test_record_type
ostream& operator << (ostream& outs, const test_record_type& source)
{
outs << "KEY: " << source.key << " DATA: " << source.data;
return outs;
}
// PROTOTYPES for functions used by this test program:
void print_menu( );
// Postcondition: A menu of choices for this program has been written to cout.
char get_user_command( );
// Postcondition: The user has been prompted to enter a one character command.
// The next character has been read (skipping blanks and newline characters),
// and this character has been returned.
test_record_type get_record( );
// Postcondition: The user has been prompted to enter data for a record. The
// key has been read, echoed to the screen, and returned by the function.
int get_key( );
// Postcondition: The user has been prompted to enter a key for a record. The
// items have been read, echoed to the screen, and returned by the function.
int main( )
{
tableChain test; // A table that we'll perform tests on
char choice; // A command character entered by the user
bool found; // Value returned by find function
test_record_type result; // Value returned by find function
cout << "I have initialized an empty table. Each record in the table ";
cout << "has an integer key and a real number as data." << endl;
do
{
print_menu( );
choice = toupper(get_user_command( ));
switch (choice)
{
case 'S': cout << "The table size is " << test.size( ) << endl;
break;
case 'I': test.insert(get_record( ));
cout << "The record has been inserted." << endl;
break;
case 'R': test.remove(get_key( ));
cout << "Remove has been called with that key." << endl;
break;
case '?': if (test.is_present(get_key( )))
cout << "That key is present." << endl;
else
cout << "That key is not present." << endl;
break;
case 'F': test.find(get_key( ), found, result);
if (found)
cout << "The key's data is: " << result.data << endl;
else
cout << "That key is not present." << endl;
break;
case 'D': test.display_all();
break;
case 'Q': cout << "Ridicule is the best test of truth." << endl;
break;
default: cout << choice << " is invalid. Sorry." << endl;
}
}
while ((choice != 'Q'));
return EXIT_SUCCESS;
}
void print_menu( )
// Library facilities used: iostream.h
{
cout << endl; // Print blank line before the menu
cout << "The following choices are available: " << endl;
cout << " S Print the result from the size( ) function" << endl;
cout << " I Insert a new record with the insert(...) function" << endl;
cout << " R Remove a record with the remove(...) function" << endl;
cout << " ? Check whether a particular key is present" << endl;
cout << " F Find the data associated with a specified key" << endl;
cout << " D Display all entries in hash table" << endl;
cout << " Q Quit this test program" << endl;
}
char get_user_command( )
// Library facilities used: iostream.h
{
char command;
cout << "Enter choice: ";
cin >> command; // Input of characters skips blanks and newline character
return command;
}
test_record_type get_record( )
// Library facilities used: iostream.h
{
test_record_type result;
cout << "Please enter a real number for a record's data: ";
cin >> result.data;
cout << result.data << " has been read." << endl;
result.key = get_key( );
return result;
}
int get_key( )
// Library facilities used: iostream.h
{
int key;
do
{
cout << "Please enter a non-negative integer for a key: ";
cin >> key;
}
while (key < 0);
cout << key << " has been read." << endl;
return key;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help