C++ Hashings Program ***************************************** First , create a
ID: 3833318 • Letter: C
Question
C++ Hashings Program
*****************************************
First, create a structure (named Student) that will describe each of the students. The structure contains the following member variables:
An ID consisting of 4 digits. The data type should be a string or c-string instead of an int.
A name, which may have embedded spaces (like "John Smith"). The data type is a string or c-string.
*****************************************
Second, See the below text file which contains all the students information.
*****************************************
Third, create a hash table class (using .h and .cpp files preferably) whose one member variable points to an array of 100 student structures. The placement of a student structure within the array is based on the last 2 digits of a student's ID. So a student with an ID ending in 45 will go in the 45th subscript ([45]) of the array, unless there's a collision. The hash table class also would include the following member functions:
Constructor - Assigns to each element of the array the value NULL for the ID and the name. (Those values are how you determine if a slot is "empty".
Destructor - If you're using dynamic memory allocation. Otherwise probably not necessary.
insert - Has 2 parameters, representing ID and name, which are assigned to the member variables of the structure instance Assigns a student's information (ID and name) to the proper element of the array. Important: Uses hashing to determine the proper array element, and resolves collisions.
retrieve - Has 1 parameter, the ID, and returns the student's name, or NULL if no student with that ID exists.Important: Uses hashing to find that student in the array, and deals with collisions.
*****************************************
Fourth, create a driver or test file. This code will:
Create an instance of the hash table class.
Load the hash table from the text file, using the insert member function.
Display a menu options:
1. Find a student by ID. If chosen, the user is prompted to enter a 4 digit ID (no input validation necessary). Using the retrieve member function, the program either will output the name of the student associated with that ID, or report that no student has that ID.
2. Exit. If chosen, the program will end.
*****************************************
//Students.txt File
6631 John Smith
2333 Alex May
7722 Julio Hernandez
1234 Jeff Jack
4436 Sara Lores
3624 Talya Nunez
8903 Frank Lertes
6782 Cara Peters
4567 Dean Jacobs
6654 Vanessa Ruiz
2368 Lenny Kravitz
7123 Gabriel Berto
3670 Kevin James
5460 Robin Telez
1267 Bruce Wayne
7629 Herb Walker
4538 Denise Richards
3568 Lori Rodriguez
2341 Colin Yates
3459 Anna Yang
8532 Phillip Valdez
3279 Christina Tovar
7619 Tori Gates
4378 Rick Grimes
4350 John Snow
Explanation / Answer
#include<iostream.h>
#include<string>
using namespace std;
struct Student {
string ID;
string name;
};
class HashEntry
{
public:
int key;
struct Student value;
HashEntry *next;
HashEntry(int key, struct Student value)
{
this->key = key;
this->value = value;
next = NULL;
}
};
class Hashtable
{
private:
HashEntry table[100];
public:
Hashtable()
{
for (int i = 0; i< 100; i++)
{
table[i].value.ID = "NULL";
table[i].value.name = "NULL"
}
}
/*
* Hash Function
*/
int HashFunc(string key)
{
return stoi(key.substr(2, 2));
}
/*
* Insert Element at a key
*/
void Insert(int key, struct Student value)
{
int hash = HashFunc(key);
HashEntry *p;
if (table[hash].value.ID == "NULL")
{
table[hash].value = value;
}
else
{
p = &table[hash];
while (p->next != NULL)
{
if (p->value.ID == key)
{
cout << "Duplicate Entry" << endl;
return;
}
p = p->next;
}
p->next = new HashEntry(key, value);
}
}
/*
* Search Element at a key
*/
HashEntry * Search(int key)
{
int hash = HashFunc(key);
HashEntry *p, *q;
q = NULL;
if (table[hash].value.ID == "NULL")
return NULL;
else
{
p = &table[hash];
while (p ! = NULL)
{
if (p->value.ID == key)
{
q = p;
break;
}
p = p->next;
}
}
return q;
}
/*
* Remove Element at a key
*/
void Remove(int key)
{
int hash = HashFunc(key);
HashEntry *p, *q;
int f
if (table[hash].value.ID = "NULL")
cout<<"No Element found at key "<<key<<endl;
else
{
p = &table[hash];
q = p->next;
while (p !=NULL){
if (p->value.ID == key)
{
q = p->next;
if (q != NULL)
{
p->value = q->value;
cout << "Element deleted" << endl;
}
else
{
q = &table[hash];
while (q->next != p)
q = q->next;
q-next = NULL;
cout << "Element deleted" << endl;
}
break;
}
p = p->next;
}
}
}
}
void main()
{
Hashtable ht = new Hashtable();
ifstream infile;
infile.open("Students.txt"
string id,firstname,lastname;
string name;
struct Student value;
char ch;
HashEntry *he;
while (infile >> id >> firstname >> lastname)
{
name = firstname + " " + lastname;
value.name = name;
value.ID = id;
ht.Insert(id, value);
}
ch = '3'
while (ch != '2')
{
cout << "1.Find a Student by ID" << endl;
cout << "2.Exit" << endl;
cin >> ch;
if (ch == '1')
{
cout << "Enter Student ID" << endl;
cin >> id;
he = Search(id);
if (he == NULL)
{
cout << "No student has that ID" << endl;
}
else
{
cout << he->value.name << endl;
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.