Hi all,
So I'm trying to learn how to do a hash table with separate chaining, but it is giving me several issues. The hash table I'm trying to make will hold instances of a class named Person and uses Person's data member phonenumber for the key.
Currently, the main issue I am having is that I am unsure how to implement the array of linked lists, as this is a configuration I have never come across before. The functions that I have so far are limited by my current implementation of the array of linked lists, but they seem logical to me.
Thus, my question is: What should I change to make the array of linked lists? And how should I initialize it?
Here is what I have come up with to this point:
(note that the prepArray function does not work, but it was my attempt at initializing the head of each linked list to null)
#include <string>
#include <iostream>
//#include "ChainNode.h"
#include "person.h"
#define MAX 200
using namespace std;
class hashTable {
private:
struct hashNode
{
Person data;
bool filled;
hashNode * next;
};//end node
hashNode array[MAX];
public:
int hash(string);
void prepArray();
void tableInsert(Person p);
void tableDelete(string);
Person tableRetrieve(string);
};//end hashTable
Person hashTable::tableRetrieve(string p) {
int index = hash(p);
hashNode * hp = &(array[index]);
//hashNode * hp = array[index];
if(hp != NULL)
{
cout << "in if" << endl;
while((hp->data.getPhonenumber() != p) && (hp->next != NULL))
{
hp = hp->next;
}//end while
if(hp->data.getPhonenumber() == p)
{
return hp->data;
}//end if
else if(hp->next == NULL)
{
cout << "No such value" << endl;
}//end else if
//if this point in the funtion is reached, there is no member with that key
}//end if
cout << "No data found with said key" << endl;
exit(1);
}//end
void hashTable::tableDelete(string phonenumber)
{
int index = hash(phonenumber);
hashNode * hp = &(array[index]);
//hashNode * hp = array[index];
if(hp)
{
while((hp->data.getPhonenumber() != phonenumber) && (hp->next != NULL))
{
hp = hp->next;
}//end while
if(hp->next == NULL)
{
cout << "No such value" << endl;
return;
}//end if
else if(hp->data.getPhonenumber() == phonenumber)
{
hashNode * temp = hp;
hp = hp->next;
delete temp;
}//end else if
}//end if
else
{
cout << "No value with that phone number." << endl;
return;
}//end else
}
void hashTable::tableInsert(Person p)
{
int index = hash(p.getPhonenumber());
hashNode *hp = &(array[index]);//hashed position
//hashNode * hp = array[index];
//bool filled;
if(hp == NULL)
{
hp = new hashNode;
hp->data = p;
hp->next = NULL;
}
else if(hp !=NULL)
{
while(hp->next!=NULL)
{
hp = hp->next;
}//end while
//the first empty position has now been found
hp=hp->next;//move up to the null pointer
hp = new hashNode;
hp->data = p;
hp->filled = true;
hp->next = NULL;
}//end else if
}//end tableInsert
void hashTable::prepArray()
{
hashNode * head = new hashNode;
for(int i = 0; i < MAX; i++)
{
//array[i] = false;
array[i].data = NULL;
//head = array[i];
}//end for
//all the filled tags are now set to false
}//end prepArray
int hashTable::hash(string phonenumber)
{
//string str = p.getPhonenumber();
//int size = str.size();
int size = phonenumber.size();
int sum;
for(int i=0; i < size; i++)
{
sum += phonenumber[i];
}//end for
int h = sum % size;
return h;
}And here is my Person class, which provides the data type for the hashNode:
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <stdio.h>
#include <string>
using namespace std;
class Person{
private:
string name;
string phonenumber;
string GPA;
public:
Person();
Person(string name, string phonenumber);
string getName();
string getPhonenumber();
void setName(string newname);
void setPhonenumber(string newphonenumber);
void setGPA(string);
string getGPA();
};
Person::Person()
{
}
Person::Person(string newname, string newphonenumber)
{
name = newname;
phonenumber = newphonenumber;
}
string Person::getName() {
return name;
}
string Person::getPhonenumber() {
return phonenumber;
}
void Person::setName(string newname) {
name = newname;
}
void Person::setPhonenumber(string newphonenumber) {
phonenumber = newphonenumber;
}
string Person::getGPA() {
return GPA;
}//end
void Person::setGPA(string newGPA) {
GPA = newGPA;
}//endI hate to ask such an open-ended sort of question of you guys, but I am having a very difficult time finding an example of this situation actually written in C++ that is not immensely complex.
