Having issues creating table using chain hashing (linked nodes).
The program compiles, but is crashing during execution.
I admit I don't really know what I'm doing since I havent really used inked lists in forever. A lot of this code I do not expect to work right away, such as the remove method, what I have written is a quick run-down of what I am actually expecting the code to do. Another set of eyes on this could really help. I just want to get this working so I have a firmer understanding of manipulating linked lists in time for exams after thanksgiving break.
Im listing the code here, but for convenience I am attaching the source as well.
Well I cant attach the .template files, but the headers are there.
****** table2.template, this is problem file
namespace main_savitch_12B
{
template <class RecordType>
const std::size_t table<RecordType>::TABLE_SIZE;
//CONSTRCUTORS AND DESTRUCTOR
template <class RecordType>
table<RecordType>::table( )
{
std::size_t i;
total_records = 0;
for (i = 0; i < TABLE_SIZE; ++i)
{
//set all pointers to NULL
data[i] = NULL;
}
}
template <class RecordType>
table<RecordType>::table(const table& source)
{
main_savitch_6B::node<RecordType> *tail_ptr;
std::size_t i;
for (i = 0; i < TABLE_SIZE; ++i)
{
list_copy(source.data[i], data[i], tail_ptr);
}
total_records = source.total_records;
}
template <class RecordType>
table<RecordType>::~table()
{
std::size_t i;
for (i = 0; i < TABLE_SIZE; ++i)
{
//use list_clear to empty all of the nodes in every element of data
list_clear(data[i]);
}
total_records = 0;
}
//MODIFICATION MEMBER FUNCTIONS
template <class RecordType>
void table<RecordType>::insert(const RecordType& entry)
{
assert(entry.key >= 0);
main_savitch_6B::node<RecordType> *cursor;
std::size_t hash_value = hash(entry.key);
cursor = data[hash_value];
if (cursor->link() == NULL)
{
cursor->set_data(entry);
}
else // start traversing the nodes at data[hash_value] for a NULL cursor
{
while (cursor->link() != NULL)
{
cursor = cursor->link();
}
// have arrived at a node that does not have a link to another, set data here.
cursor->set_data(entry);
}
total_records++;
}
template <class RecordType>
void table<RecordType>::remove(int key)
{
assert(key >= 0);
main_savitch_6B::node<RecordType> *cursor;
main_savitch_6B::node<RecordType> *precursor;
std::size_t hash_value = hash(key);
cursor = data[hash_value];
if(cursor == NULL)
return; //There is no record (node) with that key, do nothing
else
{
if (cursor->link() == NULL)
{
list_head_remove(cursor);
}
else
{
while (cursor->data().key != key)
{
precursor = cursor;
cursor = cursor->link();
}
if(cursor->link() == NULL)
{
cursor = NULL;
}
else
{
//we are removing from the inside of the linked list
list_remove(precursor);
}
} //end else
} //end else
total_records--;
}
template <class RecordType>
void table<RecordType>::operator =(const table& source)
{
if( this != &source)
{
data = source.data;
total_records = source.total_records;
}
return *this;
}
//CONSTANT MEMBER FUNCTIONS
template <class RecordType>
void table<RecordType>::find(int key, bool& found, RecordType& result) const
{
assert(key >= 0);
main_savitch_6B::node<RecordType> *cursor;
std::size_t hash_value;
hash_value = hash(key);
cursor = data[hash_value];
while ( cursor->link() != NULL && cursor->data().key != key)
{
std::cout<<cursor->data().data<<std::endl;
cursor = cursor->link();
if( cursor->data().key == key)
{
found = true;
result = cursor->data();
}
}
found = false;
}
template <class RecordType>
bool table<RecordType>::is_present(int key) const
{
assert(key >= 0);
bool found;
main_savitch_6B::node<RecordType> *cursor;
std::size_t hash_value;
hash_value = hash(key);
cursor = data[hash_value];
while (cursor->link() != NULL)
{
if (cursor->data().key == key)
return true;
cursor = cursor->link();
}
return false;
}
//HELPER MEMBER FUNCTION
template <class RecordType>
inline std::size_t table<RecordType>::hash(int key) const
{
return (key % TABLE_SIZE);
}
}***** table2.h, here is the header
// FILE: table2.h
// TEMPLATE CLASS PROVIDED: Table<RecordType>
// This class is a container template class for a Table of records.
// The template parameter, RecordType, is the data type of the records in the
// Table. It may any type with a default constructor, a copy constructor,
// an assignment operator, and an integer member variable called key.
//
// CONSTRUCTOR for the Table<RecordType> template class:
// Table( )
// Postcondition: The Table has been initialized as an empty Table.
//
// MODIFICATION MEMBER FUNCTIONS for the Table<RecordType> class:
// void insert(const RecordType& entry)
// Precondition: entry.key >= 0. Also if entry.key is not already a key in
// the table, then the Table has space for another record
// (i.e., size( ) < CAPACITY).
// Postcondition: If the table already had a record with a key equal to
// entry.key, then that record is replaced by entry. Otherwise, entry has
// been added as a new record of the Table.
//
// void remove(int key)
// Postcondition: If a record was in the Table with the specified key, then
// that record has been removed; otherwise the table is unchanged.
//
// CONSTANT MEMBER FUNCTIONS for the Table<RecordType> class:
// bool is_present(const Item& target) const
// Postcondition: The return value is true if there is a record in the
// Table with the specified key. Otherwise, the return value is false.
//
// void find(int key, bool& found, RecordType& result) const
// Postcondition: If a record is in the Table with the specified key, then
// found is true and result is set to a copy of the record with that key.
// Otherwise found is false and the result contains garbage.
//
// size_t size( ) const
// Postcondition: Return value is the total number of records in the
// Table.
//
// VALUE SEMANTICS for the Table<RecordType> template class:
// Assignments and the copy constructor may be used with Table objects.
//
// DYNAMIC MEMORY USAGE by the Table<RecordType> template class:
// If there is insufficient dynamic memory, then the following functions
// can call new_handler: the copy constructor, insert, the assignment
// operator.
#ifndef TABLE2_H
#define TABLE2_H
#include <cstdlib> // Provides size_t
#include "node2.h" // Provides the node type, from Figure 6.5 on page 306
namespace main_savitch_12B
{
template <class RecordType>
class table
{
public:
// MEMBER CONSTANT -- See Appendix E if this fails to compile.
static const std::size_t TABLE_SIZE = 811;
// CONSTRUCTORS AND DESTRUCTOR
table( );
table(const table& source);
~table( );
// MODIFICATION MEMBER FUNCTIONS
void insert(const RecordType& entry);
void remove(int key);
void operator =(const table& 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; }
private:
main_savitch_6B::node<RecordType> *data[TABLE_SIZE];
std::size_t total_records;
// HELPER MEMBER FUNCTION
std::size_t hash(int key) const;
};
}
#include "table2.template" // Include the implementation
#endif***** node2.h
// FILE: node2.h (part of the namespace main_savitch_6B)
// PROVIDES: A template class for a node in a linked list, and list manipulation
// functions. The template parameter is the type of the data in each node.
// This file also defines a template class: node_iterator<Item>.
// The node_iterator is a forward iterators with two constructors:
// (1) A constructor (with a node<Item>* parameter) that attaches the iterator
// to the specified node in a linked list, and (2) a default constructor that
// creates a special iterator that marks the position that is beyond the end of a
// linked list. There is also a const_node_iterator for use with
// const node<Item>* .
//
// TYPEDEF for the node<Item> template class:
// Each node of the list contains a piece of data and a pointer to the
// next node. The type of the data (node<Item>::value_type) is the Item type
// from the template parameter. The type may be any of the built-in C++ classes
// (int, char, ...) or a class with a default constructor, an assignment
// operator, and a test for equality (x == y).
// NOTE:
// Many compilers require the use of the new keyword typename before using
// the expression node<Item>::value_type. Otherwise
// the compiler doesn't have enough information to realize that it is the
// name of a data type.
//
// CONSTRUCTOR for the node<Item> class:
// node(
// const Item& init_data = Item(),
// node* init_link = NULL
// )
// Postcondition: The node contains the specified data and link.
// NOTE: The default value for the init_data is obtained from the default
// constructor of the Item. In the ANSI/ISO standard, this notation
// is also allowed for the built-in types, providing a default value of
// zero. The init_link has a default value of NULL.
//
// NOTE about two versions of some functions:
// The data function returns a reference to the data field of a node and
// the link function returns a copy of the link field of a node.
// Each of these functions comes in two versions: a const version and a
// non-const version. If the function is activated by a const node, then the
// compiler choses the const version (and the return value is const).
// If the function is activated by a non-const node, then the compiler choses
// the non-const version (and the return value will be non-const).
// EXAMPLES:
// const node<int> *c;
// c->link( ) activates the const version of link returning const node*
// c->data( ) activates the const version of data returning const Item&
// c->data( ) = 42; ... is forbidden
// node<int> *p;
// p->link( ) activates the non-const version of link returning node*
// p->data( ) activates the non-const version of data returning Item&
// p->data( ) = 42; ... actually changes the data in p's node
//
// MEMBER FUNCTIONS for the node<Item> class:
// const Item& data( ) const <----- const version
// and
// Item& data( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is a reference to the data from this node.
//
// const node* link( ) const <----- const version
// and
// node* link( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is the link from this node.
//
// void set_data(const Item& new_data)
// Postcondition: The node now contains the specified new data.
//
// void set_link(node* new_link)
// Postcondition: The node now contains the specified new link.
//
// FUNCTIONS in the linked list toolkit:
// template <class Item>
// void list_clear(node<Item>*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: All nodes of the list have been returned to the heap,
// and the head_ptr is now NULL.
//
// template <class Item>
// void list_copy
// (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr)
// Precondition: source_ptr is the head pointer of a linked list.
// Postcondition: head_ptr and tail_ptr are the head and tail pointers for
// a new list that contains the same items as the list pointed to by
// source_ptr. The original list is unaltered.
//
// template <class Item>
// void list_head_insert(node<Item>*& head_ptr, const Item& entry)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: A new node containing the given entry has been added at
// the head of the linked list; head_ptr now points to the head of the new,
// longer linked list.
//
// template <class Item>
// void list_head_remove(node<Item>*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list, with at
// least one node.
// Postcondition: The head node has been removed and returned to the heap;
// head_ptr is now the head pointer of the new, shorter linked list.
//
// template <class Item>
// void list_insert(node<Item>* previous_ptr, const Item& entry)
// Precondition: previous_ptr points to a node in a linked list.
// Postcondition: A new node containing the given entry has been added
// after the node that previous_ptr points to.
//
// template <class Item>
// size_t list_length(const node<Item>* head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The value returned is the number of nodes in the linked
// list.
//
// template <class NodePtr, class SizeType>
// NodePtr list_locate(NodePtr head_ptr, SizeType position)
// The NodePtr may be either node<Item>* or const node<Item>*
// Precondition: head_ptr is the head pointer of a linked list, and
// position > 0.
// Postcondition: The return value is a pointer that points to the node at
// the specified position in the list. (The head node is position 1, the
// next node is position 2, and so on). If there is no such position, then
// the null pointer is returned.
//
// template <class Item>
// void list_remove(node<Item>* previous_ptr)
// Precondition: previous_ptr points to a node in a linked list, and this
// is not the tail node of the list.
// Postcondition: The node after previous_ptr has been removed from the
// linked list.
//
// template <class NodePtr, class Item>
// NodePtr list_search
// (NodePtr head_ptr, const Item& target)
// The NodePtr may be either node<Item>* or const node<Item>*
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The return value is a pointer that points to the first
// node containing the specified target in its data member. If there is no
// such node, the null pointer is returned.
//
// DYNAMIC MEMORY usage by the toolkit:
// If there is insufficient dynamic memory, then the following functions throw
// bad_alloc: the constructor, list_head_insert, list_insert, list_copy.
#ifndef MAIN_SAVITCH_NODE2_H
#define MAIN_SAVITCH_NODE2_H
#include <cstdlib> // Provides NULL and size_t
#include <iterator> // Provides iterator and forward_iterator_tag
namespace main_savitch_6B
{
template <class Item>
class node
{
public:
// TYPEDEF
typedef Item value_type;
// CONSTRUCTOR
node(const Item& init_data=Item( ), node* init_link=NULL)
{ data_field = init_data; link_field = init_link; }
// MODIFICATION MEMBER FUNCTIONS
Item& data( ) { return data_field; }
node* link( ) { return link_field; }
void set_data(const Item& new_data) { data_field = new_data; }
void set_link(node* new_link) { link_field = new_link; }
// CONST MEMBER FUNCTIONS
const Item& data( ) const { return data_field; }
const node* link( ) const { return link_field; }
private:
Item data_field;
node *link_field;
};
// FUNCTIONS to manipulate a linked list:
template <class Item>
void list_clear(node<Item>*& head_ptr);
template <class Item>
void list_copy
(const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);
template <class Item>
void list_head_insert(node<Item>*& head_ptr, const Item& entry);
template <class Item>
void list_head_remove(node<Item>*& head_ptr);
template <class Item>
void list_insert(node<Item>* previous_ptr, const Item& entry);
template <class Item>
std::size_t list_length(const node<Item>* head_ptr);
template <class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position);
template <class Item>
void list_remove(node<Item>* previous_ptr);
template <class NodePtr, class Item>
NodePtr list_search(NodePtr head_ptr, const Item& target);
// FORWARD ITERATORS to step through the nodes of a linked list
// A node_iterator of can change the underlying linked list through the
// * operator, so it may not be used with a const node. The
// node_const_iterator cannot change the underlying linked list
// through the * operator, so it may be used with a const node.
// WARNING:
// This classes use std::iterator as its base class;
// Older compilers that do not support the std::iterator class can
// delete everything after the word iterator in the second line:
template <class Item>
class node_iterator
: public std::iterator<std::forward_iterator_tag, Item>
{
public:
node_iterator(node<Item>* initial = NULL)
{ current = initial; }
Item& operator *( ) const
{ return current->data( ); }
node_iterator& operator ++( ) // Prefix ++
{
current = current->link( );
return *this;
}
node_iterator operator ++(int) // Postfix ++
{
node_iterator original(current);
current = current->link( );
return original;
}
bool operator ==(const node_iterator other) const
{ return current == other.current; }
bool operator !=(const node_iterator other) const
{ return current != other.current; }
private:
node<Item>* current;
};
template <class Item>
class const_node_iterator
: public std::iterator<std::forward_iterator_tag, const Item>
{
public:
const_node_iterator(const node<Item>* initial = NULL)
{ current = initial; }
const Item& operator *( ) const
{ return current->data( ); }
const_node_iterator& operator ++( ) // Prefix ++
{
current = current->link( );
return *this;
}
const_node_iterator operator ++(int) // Postfix ++
{
const_node_iterator original(current);
current = current->link( );
return original;
}
bool operator ==(const const_node_iterator other) const
{ return current == other.current; }
bool operator !=(const const_node_iterator other) const
{ return current != other.current; }
private:
const node<Item>* current;
};
}
#include "node2.template"
#endif***** node2.template
// FILE: node2.template
// IMPLEMENTS: The functions of the node template class and the
// linked list toolkit (see node2.h for documentation).
//
// NOTE:
// Since node is a template class, this file is included in node2.h.
// Therefore, we should not put any using directives in this file.
//
// INVARIANT for the node class:
// The data of a node is stored in data_field, and the link in link_field.
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t
namespace main_savitch_6B
{
template <class Item>
void list_clear(node<Item>*& head_ptr)
// Library facilities used: cstdlib
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
template <class Item>
void list_copy(
const node<Item>* source_ptr,
node<Item>*& head_ptr,
node<Item>*& tail_ptr
)
// Library facilities used: cstdlib
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list
if (source_ptr == NULL)
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 rest of the nodes one at a time, adding at the tail of new list
source_ptr = source_ptr->link( );
while (source_ptr != NULL)
{
list_insert(tail_ptr, source_ptr->data( ));
tail_ptr = tail_ptr->link( );
source_ptr = source_ptr->link( );
}
}
template <class Item>
void list_head_insert(node<Item>*& head_ptr, const Item& entry)
{
head_ptr = new node<Item>(entry, head_ptr);
}
template <class Item>
void list_head_remove(node<Item>*& head_ptr)
{
node<Item> *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link( );
delete remove_ptr;
}
template <class Item>
void list_insert(node<Item>* previous_ptr, const Item& entry)
{
node<Item> *insert_ptr;
insert_ptr = new node<Item>(entry, previous_ptr->link( ));
previous_ptr->set_link(insert_ptr);
}
template <class Item>
std::size_t list_length(const node<Item>* head_ptr)
// Library facilities used: cstdlib
{
const node<Item> *cursor;
std::size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
++answer;
return answer;
}
template <class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position)
// Library facilities used: cassert, cstdlib
{
NodePtr cursor;
SizeType i;
assert(0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); ++i)
cursor = cursor->link( );
return cursor;
}
template <class Item>
void list_remove(node<Item>* previous_ptr)
{
node<Item> *remove_ptr;
remove_ptr = previous_ptr->link( );
previous_ptr->set_link(remove_ptr->link( ));
delete remove_ptr;
}
template <class NodePtr, class Item>
NodePtr list_search(NodePtr head_ptr, const Item& target)
// Library facilities used: cstdlib
{
NodePtr cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
if (target == cursor->data( ))
return cursor;
return NULL;
}
}***** here is the test program
#include <iostream>
#include <fstream>
#include <string>
#include "table2.h" // Provides the chained hash table class
using namespace std;
using namespace main_savitch_12B;
// **************************************************************************
// TableRecord type
// Each table will use the following data type for its entries, with
// keys ranging from 0 through MAX_KEY.
// **************************************************************************
struct TableRecord
{
int key;
double data;
};
const int MAX_KEY = 5000;
const int TABLE_SIZE = 811; // Knowing how table2 was implemented
int main(int argc, char *argv[])
{
cout << "*************************************";
cout << "\nChain hashing test";
cout << "*************************************";
// Create a table and add some values to it
table<TableRecord> testTable;
TableRecord testRecord;
// Add 100 records to our table to get started
for (int index = 0; index < 100; index++)
{
// Calculate a data value and a key for the record
testRecord.data = (double) index * 50;
testRecord.key = index * 50;
testTable.insert(testRecord);
}
// Add a record that has the same key as existing: shouldn't affect count
testRecord.data = 99.0;
testRecord.key = 300;
testTable.insert(testRecord);
// Add some records that should generate collisions, knowing how we calculate
// the hash code as key % TABLE_SIZE, with size set to 811
testRecord.data = 99.0;
testRecord.key = TABLE_SIZE;
testTable.insert(testRecord);
testRecord.data = 99.0;
testRecord.key = TABLE_SIZE * 2;
testTable.insert(testRecord);
testRecord.data = 99.0;
testRecord.key = TABLE_SIZE * 10;
testTable.insert(testRecord);
// Show the results of our insertions
cout << "\nAdded " << testTable.size() << " records to the test table" << endl;
cout << "*************************************";
// Try to remove some known key values, including some duplicates and some that collided
testTable.remove(100);
testTable.remove(150);
testTable.remove(1500);
testTable.remove(250);
testTable.remove(250);
testTable.remove(3750);
testTable.remove(4900);
testTable.remove(TABLE_SIZE * 2);
testTable.remove(TABLE_SIZE);
// Show the results after our removals
cout << "\nAfter removals there are " << testTable.size() << " records in the test table" << endl;
cout << "*************************************";
// Search for some values that should and should not be there
cout << "\nTry some searches for key values\n";
bool found = false;
for (int index = 0; index < MAX_KEY; index = index + 150)
{
testTable.find(index, found, testRecord);
if (found)
cout << "Found record with key value " << index << ", data = " << testRecord.data << endl;
else
cout << "Did not find record with key value " << index << endl;
}
// Find the collision record that should still be there using is_present
if (testTable.is_present(TABLE_SIZE * 10))
cout << "\nSuccessfully found record with key equal to " << TABLE_SIZE * 10 << endl;
else
cout << "\n?? Failed to find record with key equal to " << TABLE_SIZE * 10 << endl;
cout << "*************************************"<< endl;
cout << "End of Test" << endl;
cout << "*************************************" << endl;
system("Pause");
}