I'm having trouble with these functions made for a C++ hash table...any and all pointers in the right direction would be greatly appreciated! EDIT: table.h is the problem file, but I included node.h just in case!

// FILE: table.h

#ifndef TABLE_H
#define TABLE_H

#include <cstdlib>    // Provides size_t
#include <string>     // Provides string
#include <sstream>    // Provides stringstream
#include "node.h"     // Provides the node type as used previously

template <class RecordType>
class table {

    public:
        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; }
        std::string toString( ) const;

    private:
        node<RecordType> *data[TABLE_SIZE];
        std::size_t total_records;
        // HELPER MEMBER FUNCTION
        std::size_t hash(int key) const;
};

// NONMEMBER FUNCTION for the table class
template <class RecordType>
std::ostream& operator<<(std::ostream& outs, const table<RecordType>& seq);


// INVARIANT for the table ADT:
//      STUDENT: Provide a solid and complete invariant for this implementation
#include <stdexcept>  // Provides exceptions
#include <cstdlib>    // Provides size_t
#include <iostream>   // Provides <<
#include <sstream>    // Provides stringstream
#include <string>     // Provides string


template <class RecordType>
const std::size_t table<RecordType>::TABLE_SIZE;


// STUDENT -- implement ALL methods of the table class starting with 
//            constructors, destructor, etc.

template <class RecordType>
table<RecordType>::table( ) {
    std::size_t index;

    // STUDENT code here
    total_records = 0;
    for (index = 0; index < TABLE_SIZE; index++){
        data[index] = NULL;
    }
}

template <class RecordType>
table<RecordType>::table( const table& source ) {
    std:size_t index;
    // STUDENT code here
    node<RecordType>* end;
    for (index = 0; index < TABLE_SIZE; ++index){
        list_copy(source.data[index], data[index], end);
    }
    total_records = source.total_records;

}

template <class RecordType>
table<RecordType>::~table( ) {
    std::size_t index;

    // STUDENT code here
    /*
    node<RecordType>* ptr = new node<RecordType>;
    node<RecordType>* del = new node<RecordType>;
    while(index < TABLE_SIZE){
        ptr = data[index];
        while(ptr != NULL){
            del = ptr;
            ptr = ptr->link();
            delete del;
            del = NULL;
        }
        data[index] =  NULL;
        ++index;
        }
        */
    } 


template <class RecordType>
void table<RecordType>::insert(const RecordType& entry) {

    std::size_t index = hash(entry.key);

    // STUDENT code here
    bool present = false;
    node<RecordType>* cursor = data[index];
    while(cursor != NULL && !present){

        if (cursor->data().key == entry.key){
            cursor->data() = entry;
            present = true;
        } else 
            cursor = cursor->link();

    }
    if(!present){
        node<RecordType>* add = new node<RecordType>(entry, data[index]);
        data[index] = add;
    }
    total_records++;


}

template <class RecordType>
void table<RecordType>::remove(int key) {
    //std::cout << "Entering remove with key = " << key << "\n";
    std::size_t index = hash(key);

    // STUDENT code here
    /*
    node<RecordType>* precursor = data[index];
    node<RecordType>* cursor = precursor->link;
    */


}


template <class RecordType>
void table<RecordType>::operator =( const table& source ) {

    size_t index;
    // STUDENT code here
    if (this != &source){
        total_records = source.total_records;
        for (index =0; index < TABLE_SIZE; index++){
            data[index] = source.data[index];
        }
    }

}

template <class RecordType>
void table<RecordType>::find(int key, bool& found, RecordType& result) const {

    std::size_t index = hash(key);
    // STUDENT code here
    /*
    node<RecordType> *cursor = data[index];
    found = false;
    while (cursor->link() != NULL && cursor->data().key != key){
        cursor = cursor->link();
        if (cursor->data().key == key){
            found = true;

        }
    }
    */


}

template <class RecordType>
bool table<RecordType>::is_present(int key) const {

    size_t index = hash(key);
    bool found = false;
    node<RecordType>* ptr = data[index];

    // STUDENT code here

    return found;
}

template <class RecordType>
std::string table<RecordType>::toString( ) const {
// Library facilities used string, sstream, node.h
    std::stringstream outs;
    outs << "Table: number records " << total_records << "\n";
    outs << "[\n";
    if ( total_records == 0 ) {
        outs << "]";
        return outs.str();
    }

    size_t index;
    for ( index = 0; index < TABLE_SIZE; ++index ) {
        if ( data[index] != NULL ) {
            outs << "Slot " << index << ": ";
            const node<RecordType>* ptr = data[index];
            while ( ptr->link() != NULL ) {
                outs << "(" << ptr->data().key << "," << ptr->data().data << ") ";
                ptr = ptr->link();
            }
            outs << "(" << ptr->data().key << "," << ptr->data().data << ")\n";
        }
    }
    outs << "]\n";
    return outs.str();
}

template <class RecordType>
std::ostream& operator<<(std::ostream& outs, const table<RecordType>& tbl) {
//Library facilities used:  iostream
    outs << tbl.toString();
    return outs;
}

template <class RecordType>
inline std::size_t table<RecordType>::hash(int key) const {
    // returns value in range 0 <= retValue < TABLE_SIZE
    return key % TABLE_SIZE;
}

#endif

======================================

// FILE: node.h 
// 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 iterator 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_piece(
//     const node* start_ptr, const node* end_ptr, 
//     node*& head_ptr, node*& tail_ptr
//   )
//    Precondition: start_ptr and end_ptr are pointers to nodes on the same
//    linked list, with the start_ptr node at or before the end_ptr node
//    Postcondition: head_ptr and tail_ptr are the head and tail pointers for a
//    new list that contains the items from start_ptr up to and including 
//    end_ptr.  The end_ptr may NOT be NULL.
//
//   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 NODE_H  
#define NODE_H
#include <cstdlib>   // Provides NULL and size_t
#include <iterator>  // Provides iterator and forward_iterator_tag

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<Item> *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_piece (const node<Item>* start_ptr,
                 const node<Item>* end_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 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 class uses 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) { 
            cursor = initial; 
        }

        Item& operator *( ) const { 
            return cursor->data( ); 
        }

        node_iterator& operator ++( ) /* Prefix ++ */{ 
            cursor = cursor->link( );
            return *this;
        }

        node_iterator operator ++(int) /* Postfix ++*/ {
            node_iterator original(cursor);
            cursor = cursor->link( );
            return original;            
        }

        bool operator ==(const node_iterator other) const { 
            return cursor == other.cursor; 
        }

        bool operator !=(const node_iterator other) const { 
            return cursor != other.cursor; 
        }

    private:
        node<Item>* cursor;
};

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) { 
            cursor = initial; 
        }

        const Item& operator *( ) const { 
            return cursor->data( ); 
        }

        const_node_iterator& operator ++( ) /* Prefix ++ */ {
            cursor = cursor->link( );
            return *this;
        }

        const_node_iterator operator ++(int) /* Postfix ++ */ {
            const_node_iterator original(cursor);
            cursor = cursor->link( );
            return original;
        }

        bool operator ==(const const_node_iterator other) const { 
            return cursor == other.cursor; 
        }

        bool operator !=(const const_node_iterator other) const { 
            return cursor != other.cursor; 
        }

    private:
        const node<Item>* cursor;
};


// INVARIANT for the node class:
//   The data of a node is stored in data_field, and the link in link_field.

#include <cstdlib>    // Provides NULL and size_t
#include <stdexcept>  // Provides exception classes

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_piece( const node<Item>* start_ptr, const node<Item>* end_ptr, 
                 node<Item>*& head_ptr, node<Item>*& tail_ptr   ) {
    // Library facilities used: cstdlib
    head_ptr = tail_ptr = NULL;

    if ( start_ptr == NULL || end_ptr == NULL ) 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;

    // Copy the nodes one at a time, adding to the tail of new list
    start_ptr = start_ptr->link();
    while ( start_ptr != end_ptr->link() ) {
        list_insert( tail_ptr, start_ptr->data( ) );
        tail_ptr = tail_ptr->link( );
        start_ptr = start_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: stdexcept, cstdlib
    NodePtr cursor;
    SizeType i;

    if (position < 1)
        throw std::invalid_argument("position must be >= 1");
    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;
}


#endif

Recommended Answers

The remove code doesn't do anything except get the index.

The insert code overwrites the insertion point instead of inserting into the table.

Jump to Post

All 2 Replies

That's over 500 lines so it's best if you call out what fails and what lines you feel need a closer look.

commented: Completely understandable! I think the main problem is in in the remove and insert functions, everything else tends to stem from those two functions? +0

The remove code doesn't do anything except get the index.

The insert code overwrites the insertion point instead of inserting into the table.

commented: Thank you for your help! Do you know what I could do to re-write the insert method as intended? +0
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.