Question

Can someone please write me a header file in c++ using the quadratic probing hash method that will work with this program?

#include "hash.h"
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <list>
using namespace std;

const size_t KEYS_COUNT = 1000; // Number of keys to generate for testing

string random_key();

class HashCheck {
private:
        size_t count;
        Hash hash;
public:
        HashCheck(Hash& h) { count = 0; hash = h; }
        void operator() (const string key) {
                if (hash[key] != ++count)
                        cout << "Key " << key << " does not match value " << count << endl;
        }
};

int main() {

        Hash hash; // Hash table for testing
        list<string> keys; // Keys added to hash table

        srand(time((time_t)0)); // Init RNG

        // Add 1000 unique entries to the table
        size_t count = 0;
        while (count < KEYS_COUNT) {
                string key = random_key();
                if (find(keys.begin(), keys.end(), key) == keys.end()) {
                        //cout << key << endl; // Uncomment to see keys generated
                        keys.push_back(key);
                        hash[key] = ++count;
                }
        }

        // Verify that all keys map to their original values
        for_each(keys.begin(), keys.end(), HashCheck(hash));

#ifdef _MSC_VER
        system("pause");
#endif
        return 0;
}

string random_key() {
        // Generate a random string of length 1 through 40
        size_t len = rand() % 40 + 1;
        string key;
        for (size_t i = 0; i < len; i++)
                key += 'a' + rand() % 26;
        return key;
}

Answer 1

The header file is a heap which is using a template file. For reasons that escape me the insert and remove functions cannot be "seen" in the main file. I am getting an error message: 

Main.cpp: /** * Insert a few elements into a heap and the remove them * one by one and see if we get them in the right. */ #include "priority_queue_heap.h" #include "heap.h" #include <iostream> #include <ctime> using namespace std; int test1() { heap<int> hp; hp.insert(1); hp.insert(2); hp.insert(3); hp.insert(4); hp.insert(5); hp.check_heap(); int x = hp.remove(); cout << "removed " << x << endl; x = hp.remove(); cout << "removed " << x << endl; x = hp.remove(); cout << "removed " << x << endl; x = hp.remove(); cout << "removed " << x << endl; x = hp.remove(); cout << "removed " << x << endl; cout << "empty? " << hp.is_empty() << endl; } void test2() { srand(time(NULL)); heap<int> hp; for(int i = 0; i < 30; i++ ) { hp.insert(rand()); } while(!hp.is_empty()) { int x = hp.remove(); cout << x << endl; } } int main() { /*test1(); test2();*/ priority_queue_heap<int> enter1(); enter1.insert(135); enter1.insert(909); enter1.insert(203); cout<<endl; cout<< "values to be removed" << endl; cout << enter1.remove() << endl; } heap.h: #ifndef HEAP_H #define HEAP_H /** * This class implements a heap as described in the text. * We will treat it as a priority queue. */ template <class T> class heap { public: static const int CAPACITY = 10; heap() { size = 0; } bool is_empty() const { return size == 0;} bool is_full() const { return size == CAPACITY; } /** * Remove the largest value from this heap and return it. * * Precondition: heap is not empty. */ T remove(); /** * Inserts the 'value' into the heap. * * Precondition: heap is not full */ void insert(const T& value); /** * Check if the heap is valid. * Prints out each parent and its children (for all nodes with children) * Stops when a parent is less than one or both of its children * Prints 'check' for each parent that is greater than or equal to its children */ bool check_heap(); private: T data[CAPACITY]; int size; }; #include "heap.template" #endif // HEAP_H heap.template: #include <cassert> #include <cstdlib> #include <iostream> #include <iomanip> /* * parent index is p, children are at indices 2*p+1 and 2*p+2 * You must check that those are in range * * child index is c, parent index is (c-1)/2 (integer division) */ /** * Inserts the 'value' into the heap. * * Precondition: heap is not full */ template <class T> void heap<T>::insert(const T& value) { assert(!is_full()); //std::cout << size << std::endl; // add the value to a new node in proper position data[size] = value; size++; // move the value up the tree as needed int child = size-1; // index of the new 'node' int parent = (child-1)/2; // index of the parent while((child > 0) && (data[parent] < data[child])) { // swap parent and child values T tmp = data[parent]; data[parent] = data[child]; data[child] = tmp; // update parent and child child = parent; // this is where new value is! parent = (child-1)/2; } // it's a heap! } /** * Remove the largest value from this heap and return it. * * Precondition: heap is not empty. */ template <class T> T heap<T>::remove() { assert(!is_empty()); // grab first element, save it for return later T save = data[0]; // copy last value in list to the beginning // decrement size data[0] = data[size-1]; size--; // size--; // data[0] = data[size]; // sift the new first element down until it finds its place int parent = 0; int left_child = 2*parent+1; int right_child = 2*parent+2; bool still_working = true; while(still_working && left_child < size) { // while the parent has at least one child if(right_child >= size) { // only the left child to worry about if(data[parent] < data[left_child]) { // out of order, so swap them T t = data[parent]; data[parent] = data[left_child]; data[left_child] = t; parent = left_child; still_working = false; // we must be done! } else { still_working = false; } } else { // two children if(data[left_child] > data[right_child]) { //left child larger if(data[parent] < data[left_child]) { // out of order, so swap them T t = data[parent]; data[parent] = data[left_child]; data[left_child] = t; parent = left_child; } else { still_working = false; } } else { // right child larger if(data[parent] < data[right_child]) { // out of order, so swap them T t = data[parent]; data[parent] = data[right_child]; data[right_child] = t; parent = right_child; } else { still_working = false; } } left_child = 2*parent + 1; right_child = 2*parent + 2; } } return save; } /** * Check if the heap is valid. * Prints out each parent and its children (for all nodes with children) * Stops when a parent is less than one or both of its children * Prints 'check' for each parent that is greater than or equal to its children */ template <class T> bool heap<T>::check_heap() { for(int p = 0; p < size; p++ ) { int cl = 2*p+1; int cr = 2*p+2; std::cout << std::setw(5) << p << std::setw(10) << data[p]; if(cl < size) { // p has a left child? std::cout << std::setw(10) << data[cl]; if(data[p] < data[cl]) { std:exit(1); } } if(cr < size) { // p has a right child? std::cout << std::setw(10) << data[cr]; if(data[p] < data[cr]) std::exit(1); } std::cout << std::endl; } return true; } priority_queue_simple.template: #include <cassert> /** * Remove the largest value from this priority queue and return it. * * Precondition: priority queue is not empty. */ template <class T> T priority_queue_simple<T>::remove() { assert(size > 0); int imax = 0; for(int i = 1; i < size; i++ ) { if(data[i] > data[imax]) imax = i; } T tmp = data[imax]; data[imax] = data[size-1]; size--; return tmp; } /** * Inserts the 'value' into the priority queue. * * Precondition: priority queue is not full */ template <class T> void priority_queue_simple<T>::insert(const T& value) { assert(size < CAPACITY); size++; data[size-1] = value; } priority_queue_heap.h: #ifndef PRIORITY_QUEUE_HEAP_H #define PRIORITY_QUEUE_HEAP_H //#include "heap.h" template <class T> class priority_queue_heap { priority_queue_heap(); bool is_empty() const; bool is_full() const; /** * Remove the largest value from this priority queue and return it. * * Precondition: priority queue is not empty. */ T remove(); /** * Inserts the 'value' into the priority queue. * * Precondition: priority queue is not full */ void insert(const T& value); private: heap<T> pri_que; }; #include "priority_queue_heap.template" #endif // PRIORITY_QUEUE_HEAP_H template <class T> T priority_queue_heap<T>::remove() { return pri_que.remove(); } priority_queue_heap.template: template <class T> T priority_queue_heap<T>::remove() { return pri_que.remove(); } template <class T> void priority_queue_heap<T>::insert(const T& value) { pri_que.insert(value); } priority_queue_simple.h: #ifndef PRIORITY_QUEUE_SIMPLE_H #define PRIORITY_QUEUE_SIMPLE_H /** * This class implements a priority queue using a very simple strategy: * Store the values in an array. * Add new values at the end. * When asked to remove a value, search for the largest (linear search) * */ template <class T> class priority_queue_simple { public: static const int CAPACITY = 30; priority_queue_simple() { size = 0; } bool is_empty() const { return size == 0; } bool is_full() const { return size == CAPACITY; } /** * Remove the largest value from this priority queue and return it. * * Precondition: priority queue is not empty. */ T remove(); /** * Inserts the 'value' into the priority queue. * * Precondition: priority queue is not full */ void insert(const T& value); private: T data[CAPACITY]; int size; }; #include "priority_queue_simple.template" #endif // PRIORITY_QUEUE_SIMPLE_H 

You should remove the "()" characters after enter1 at line 51 of main.cpp ... Otherwise c++ sees that as a function, it does not call the constructor.