#include

using namespace std;

string ltrim(const string &);

string rtrim(const string &);

/*

Each "person" is defined by their name, zipcode, and their pet's name.

Persons are hashed by their zipcode.

*/

//----------------------------------------------------------------------------

/* define a "person"

--------------------*/

class person{

public:

// variables that define a person

string name;

int zipcode;

string petsname;

// constructor

person(string nm="", int zc=0, string pn=""){

name = nm;

zipcode = zc;

petsname = pn;

}

// print a person

void print(){

cout

}

};

//----------------------------------------------------------------------------

/* define a Linked List (LL)

/*

/* a linked list consists of a series of nodes. Each node consists of a data

/* value (type "person") and a pointer to another node

/*

/* The constructor and push functions have been created for you but the

/* find function needs to be written

----------------------------------------------------------------------------*/

class LL{

public:

//---------------------------

/* embedded class to defined the nodes for this linked list

---------------------------*/

class node{

public:

person val;

node *next;

node(person newVal,node *n){

val = newVal;

next = n;

}

};

node *head;

// constructor

LL(){

head = NULL;

}

// push a new person to the list

void push(person newval){

head = new node(newval,head);

}

// check the linked list to see if there is any node that contains

// a person with the zipcode "zipQuery".

// If so, use the person 'print' function to print the person.

// Otherwise print that the zipQuery was not found.

void find(int zipQuery){

// YOUR CODE HERE

}

};

//----------------------------------------------------------------------------

/* define the hashed table

/*

/* The hashed table consists of an array of Linked Lists. To add a new person

/* to the hashed table, we compute their key (from their zip code) and then

/* "push" them onto the linked list at buffer[key].

/*

/* The constructor, compute_key, and push functions have been written,

/* but you will need to write "find"

----------------------------------------------------------------------------*/

class hashed_table{

public:

int BUFFLEN;

LL *buffer;

// constructor

hashed_table(){

BUFFLEN = 10;

buffer = new LL[BUFFLEN];

}

// compute the key

int computeKey(int input){

return input % BUFFLEN;

}

// add a new person to the table by finding their key

// and then pushing into the corresponding linked list

void push(person newPerson){

int key = computeKey(newPerson.zipcode);

buffer[key].push(newPerson);

}

// find a person by computing the key and then running "find" in the

// corresponding linked list.

void find(int zipQuery){

// YOUR CODE HERE

}

};

void test_buffer(int zip) {

hashed_table myTable;

myTable.push( person("alice",19122,"hoot") );

myTable.push( person("bob",12193,"rover") );

myTable.push( person("charlie",27707,"lady") );

myTable.push( person("dan",90210,"bubbles") );

myTable.push( person("elise",20904,"marbles") );

myTable.push( person("fran",86753,"moose") );

myTable.find(zip);

}

int main()

1. Hash Tables - C++ This problem closely mimics the hash table example we've worked in class using Python, with two key differences. First: the code is in C++, not Python. Secondly, instead of a buffer of "students", I'm using a buffer of linked lists. When a new person gets added to the hash table, their key is computed and then they're added to the linked list matching to the specific key. See the code for more details. Your job is to write the two "find" functions to look for a particular person in their respective linked list. Everything else has been written for you - the only place you need to write code is the "find" method in the "LL" class and the "find" method of the "hashed_table" class. The basics are the same as we've seen in class: I have created a buffer of linked lists. A hash key is created for each new person (according to their zipcode) and the person is added to the linked list located at buffer[key]. Don't make any changes to the push method or anything to do with the buffer or person class. When it's time to look someone up, we take their zip code, determine the hash key, and then look to see where that zipcode is present in buffer[key]. We do that by traversing down the list and checking each node. We return either print the person or an error message if they aren't found