I am asked to Create a data structure that consists of an array of studentLists

Question

 I am asked to Create a data structure that consists of an array of studentLists  (see ‘speedTable’ below). When a new student is inserted, the student will be added to one of the lists within the array. When a student is searched for by ID number. My best guess is to implement a hash table function

 I cannot  Implement the ‘speedTable’ hash function, which is essentially an array of studentLists. I would appreciate some help in implementing it.


class speedTable

{

private:

studentList * table; //an array of studentLists

int tableSize; //size of the array



public:

//constructor which will allocate a new array of studentLists of size ‘size’

speedTable(int size);



//be sure to free all dynamically allocated memory!

~speedTable();



//add student s to data structure

void add(student s);



//remove student with given id from data structure

void remove(int id);



//locate and return the student with given id from the data structure

student getStudent(int id);

}

Explanation / Answer

#include #include #include #include using namespace std; class student { private: int id; public: student(const int); const int getId() const; void setId(const int); }; ostream& operator<<(ostream& os, student s) { os << "student: {id: " << s.getId() << "}"; return os; } student::student(const int id) { setId(id); } void student::setId(const int id) { this->id = id; } const int student::getId() const { return id; } class speedtable { private: vector > table; const int compute_hash(const int) const; public: speedtable(const int); void add(const student); void remove(const int); const student getStudent(const int) const; friend ostream& operator<<(ostream&, speedtable); }; ostream& operator<<(ostream& os, speedtable st) { os << "[ "; for (unsigned int i = 0; i < st.table.size(); i++) { if (st.table.at(i).size() > 0) { os << i << ": "; for (unsigned int j = 0; j < st.table.at(i).size(); j++) { os << st.table.at(i).at(j) << ", "; } os << " "; } } os << "]"; return os; } const int speedtable::compute_hash(const int id) const { return id % table.size(); } speedtable::speedtable(const int size) { for (int i = 0; i < size; i++) { table.push_back(vector()); } } void speedtable::add(const student s) { const int hash = compute_hash(s.getId()); vector* bucket = &table.at(hash); bucket->push_back(s); } void speedtable::remove(const int id) { const int hash = compute_hash(id); vector* bucket = &table.at(hash); for (unsigned int i = 0; i < bucket->size(); i++) { if (bucket->at(i).getId() == id) { bucket->erase(bucket->begin() + i); } } } const student speedtable::getStudent(const int id) const { const int hash = compute_hash(id); vector bucket = table.at(hash); for (unsigned int i = 0; i < bucket.size(); i++) { if (bucket.at(i).getId() == id) { return bucket.at(i); } } stringstream ss; ss << "ID " << id << " does not exist in the speed table"; throw runtime_error(ss.str()); } int main() { cout << "Create speedtable..." << endl; speedtable students(50); cout << students << " " << endl; cout << "Populate speedtable with data..." << endl; students.add(student(47)); students.add(student(447)); students.add(student(100)); students.add(student(105)); students.add(student(205)); students.add(student(305)); cout << students << " " << endl; cout << "Remove student ID 305..." << endl; students.remove(305); cout << students << " " << endl; cout << "Get student ID 47..." << endl; cout << students.getStudent(47) << " " << endl;; cout << "Get non-existent student ID 99 (should throw error)..." << endl; try { cout << students.getStudent(99) << endl; } catch (exception& e) { cerr << " ::: runtime_exception caught: " << e.what() << endl; cout << "Worked successfully" << endl; } cout << "All done" << endl; return 0; }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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