C++ Student Hashings Program ***************************************** First , c

Question

C++ Student 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

/******** Student.h *********/
// Structure for the Student
struct Student {
string ID;
string name;
};

/************************ HashTable.h **********************/
#ifndef HashTable_H
#define HashTable_H

using namespace std;
#include <string>
#include <stdlib.h>
#include "Student.h"

// Class for Hash table
class HashTable {
private:
// member variable that points to 100 student structures
struct Student array[100];

public:
// Constructor
HashTable ();
virtual ~HashTable ();

// insert function that takes ID and name as parameters
// and inserts the student with those details into the HashTable
void insert(string ID, string name);
string retrieve(string ID);
};

/*********************** HashTable.cpp ************************/
#include "HashTable.h"

// Implementation of HashTable Constructor.
HashTable::HashTable() {
for (int i = 0; i < 100; i++) {
array[i].id = NULL;
array[i].name = NULL;
}
}

// Implementation of insert function
// Uses linear probing incase of collisions
HashTable::insert(string ID, string name) {
// convert ID to int using atoi integer library function
int id = atoi(ID);
// get last 2 digits of ID using modulus operator
int pos = id % 100;

// check if the position is empty i.e, no collision and insert the student
if (array[pos].ID == NULL) {
array[pos].ID = ID;
array[pos].name = name;
return
}

// if there is a collision i.e, position is not empty
// check free position using linear probing
int i = 0;
while (i < 100 && array[i].ID == NULL) {
i++;
}

// Found empty location.
if (i < 100) {
array[i].ID = ID;
array[i].name = name;
}
}

string HashTable::retrieve(string ID) {
// convert ID to int using atoi integer library function
int id = atoi(ID);
// get last 2 digits of ID using modulus operator
int pos = id % 100;

// check if the position has the student with the ID
if (array[pos].ID == ID) {
return array[pos].name;
}

// otherwise there must have been a collision
// use linear probing to see where it was inserted
int i = 0;
while (i < 100 && array[i].ID != ID) {
i++;
}

// Found the ID. Return the name.
if (i < 100) {
return array[i].name;
} else { // ID not found. Return NULL
return NULL;
}
};

/******************** TestDriver.cpp ************************/
#include "HashTable.h"
#include <fstream>
#include "iostream"

class TestDriver {
int main(int argc, char const *argv[]) {
// Create an instance of the hash table class.
HashTable ht = new HashTable();
string ID, name;
int choice;
// Load the hash table from the text file, using the insert member function.
ifstream in ( "Students.txt" );
if ( !in ) return;
while ( !in.eof ) {
in >> ID;
in >> name;
ht.insert(ID, name);
}
// Close the file.
in.close();

// Display a menu options:
do
{
cout << "1. Find a student by ID." << endln;
cout << "2. Exit." << endln;
cin >> choice;

switch (choice)
{
case 1:
cout << "Enter a 4 digit ID: ";
cin >> ID
name = ht.retrieve(ID);
if (name != NULL) {
cout << "Name of the student: " << name;
} else {
cout << "No student has that ID";
}
break;
case 2:
break;
default:
cout << "Not a Valid Choice. "
break;
}
} while (choice != 5);
return 0;
}
};

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.