This question has already been solved
You
Have something to say? Contribute New Article Reply to this Article
Hash Chaining Issues
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");
}My assignments on line 57 and 66 seem to be causing the crash, they go away when I comment them out. I'm trying to resolve them but I'm having no luck.
Update:
This is embarrassing, found I was comparing without first making the data subscript cursor was pointing to a node, which has no link() pointer...
Changed
if (cursor->link() == NULL)
{
cursor->set_data(entry);
}to
if (cursor == NULL)
{
cursor = new main_savitch_6B::node<RecordType>;
cursor->set_data(entry);
}
Still might not be correct but im getting somewhere.
also, I am not even using my found boolean in the is_present function, so im making that change. there is a problem with is_present and find functions still but I am working on those.
You
© 2012 DaniWeb® LLC
