Question

Instructions

Download the files towardsHashTables.cpp, and Queue.h.

This is the incomplete example from class last week, where we started implementing a hash table as a vector of queues.

In order for this example to work, the Queue struct needs 3 more functions to be implemented. A find function, which tells us it a given value appears in the queue, without being destructive. A function called print, which prints out the contents of the queue, again without being destructive. Finally, there is a need for a destructor. To implement it, you can just keep popping elements off the queue until there are no elements left.

Implement the 3 functions required in Queue.h and upload it here

Queue.h file

#ifndef Queue_h
#define Queue_h

#include <iostream>

struct Link {
    long data;
    Link* next;
    
    Link(){
        data = 0;
        next = NULL;
    }
    
    Link (long d){
        data = d;
        next = NULL;
    }
};

struct Queue {
    Link* front;
    Link* back;
    
    Queue (){
        front = NULL;
        back = NULL;
    }
    
    long peek () {
        return front->data;
    }
    
    void push(long value){
        if (isEmpty()){
            front = new Link(value);
            back = front;
        }
        else {
            back->next = new Link(value);
            back = back->next;
        }
    }
    
    bool find (long value){
        // Provide your code here

    }
    
    bool isEmpty(){
        return (front == NULL);
    }
    
    long pop(){
        long val = front->data;
        
        Link* oldFront = front;
        front = front->next;
        
        delete oldFront;
        
        return val;
    }
    
    void print() {
        // Provide your code here

    }
    
    ~Queue(){
        // Provide your code here

    }
};

#endif

hashtable.cpp

#include <iostream>
#include <vector>
#include "Queue.h"

using namespace std;

long k = 10;

long f (long x){
    return x % k;
}

int main() {
    
    // Declare a vector of Queue pointers
    vector<Queue*> hashtable;
    
    // Initialize the vector with k empty Queues
    for (long i = 0; i < k; i++) {
        hashtable.push_back(new Queue());
    }
    
    // This is the value I want to insert
    long value = 234;
    
    // Run it through the hash function to determine
    // to which queue we need to push it
    long index = f(value);
    
    // Push value to the index-th Queue
    hashtable[index]->push(value);
    
    // One more time
    value = 23;
    
    index = f(value);
    hashtable[index]->push(value);
    
    // One more time
    value = 23453;
    
    index = f(value);
    hashtable[index]->push(value);
    
    
    // Let's do some searching
    
    // This is what I am searching for
    value = 7;
    
    // Which queue should I be looking at
    index = f(value);
    
    // Look for it in the queue pointed to by index
    cout << hashtable[index]->find(value) << endl << endl;
    
    // Print contents of hash table
    for (long i = 0; i < k; i++) {
        Queue* current = hashtable[i];
        
        cout << i << ": ";
        
        current->print();
        cout << endl;
    }
    
    for (long i = 0; i < k; i++) {
        delete hashtable[i];
    }
    
    return 0;
}

Answer 1

#include <iostream>

#ifndef Queue_h
#define Queue_h
struct Link {
long data;
Link* next;
  
Link(){
data = 0;
next = NULL;
}
  
Link (long d){
data = d;
next = NULL;
}
};

struct Queue {
Link* front;
Link* back;
  
Queue (){
front = NULL;
back = NULL;
}
  
long peek () {
return front->data;
}
  
void push(long value){
if (isEmpty()){
front = new Link(value);
back = front;
}
else {
back->next = new Link(value);
back = back->next;
}
}
  
bool find (long value){
// Provide your code here
Link* curr = back;
while(curr != NULL){
  
if(curr->data==value)
return true;
  
curr = curr->next;
  
}
return false;

}
  
bool isEmpty(){
return (front == NULL);
}
  
long pop(){
long val = front->data;
  
Link* oldFront = front;
front = front->next;
  
delete oldFront;
  
return val;
}
  
void print() {
// Provide your code here
  
Link* curr = back;
while(curr != NULL){
  
cout<<curr->data<<" ";
curr = curr->next;
  
}
}
  
~Queue(){
// Provide your code here
Link* curr = back, *temp;
while(curr != NULL){
  
temp = curr;
curr = curr->next;
delete temp;
  
  
}
  

}
};

#endif

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

gcc version 4.6.3 share Files saved main.cpp 42 43 main.cpp back->next new Link (value); back back->next; 3: 23453 4: 234 45 46 bool find (long value)< 47- 48 49 50- 51 52 53 54 // Provide your code here Link* curr-back; while(curr != NULL){ 2- if ( curr->data-=value) return true; curr curr->next ; = 56 57 58 59 60 61 62 63 64 65 return false; bool isEmpty) return (frontNULL) long popO long val front->data; 67 68 69 Links oldFront front ; front- front->next; 70