I have a linkedList class and I need to convert it into a hash table through an
ID: 3638621 • Letter: I
Question
I have a linkedList class and I need to convert it into a hash table through an array.
these are the functions I need to implement:
class speedTable
{
private:
studentList * table; //an array of studentLists
int tableSize; //size of the array
public:
speedTable(int size);
~speedTable();
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);
//Create a new array of size newsize and rehash
//all items in the old table into the new table.
//Free (delete) the old array and point the table
//variable at the new array.
void resize(int newsize);
}
this is my linkedList code:
#include <string>
#include <iostream>
#include <vector>
#include <iomanip>
#include <cassert>
#include "student.h"
using namespace std;
//student list is a doubly linked list of students.
template <class Type>
class linkedList
{
public:
template<class Type>
class node
{
public:
Type data;
node<Type> * next;
node<Type> * prev;
node(Type x)
{
data = x;
next = NULL;
prev = NULL;
}
};
node<Type> * head, *first;
friend ostream& operator<<<Type>(ostream& os, const linkedList<Type>& x);
public:
~linkedList();
linkedList();
bool empty();//return true if the list is empty, false if not.
void push(Type s);//insert student s into the front of the linked list
Type pop();//remove and return the student at the front of the list
bool removeStudent(int id);//locate and remove the student with given ID number
Type getStudent(int id);//locate and return a copy of the student with given ID number
//arrange students into increasing based on either ID or name. If
//variable 'field' has value "id", sort into increasing order by id.
//If 'field' has value "name", sort into alphabetical order by name.
void sort(string field);
//a test function to simply display the list of students to the screen
//in the order they appear in the list.
void display();
int returnCount();
Type *list;
};
template <class Type>
linkedList<Type>::linkedList()
{
head = NULL;
}
template <class Type>
linkedList<Type>::~linkedList()
{
}
template <class Type>
int linkedList<Type>::returnCount()
{
if (head == NULL)
return 0;
else
{
int count = 0;
node<Type> * current = head;
while( current != NULL )
{
count++;
current = current->next;
}
return count;
}
}
template<class Type>
void linkedList<Type>::push(Type s)
{
node<Type> * somenode = new node<Type>(s);
somenode->next = head;
if( head != NULL )
head->prev = somenode;
head = somenode;
}
//remove and return front item from list
template <class Type>
Type linkedList<Type>:: pop()
{
if( head == NULL )
{
cout<<"Cannot pop item from empty list"<<endl;
}
else if( head->next == NULL )
{
Type output = head->data;
delete head;
head = NULL;
return output;
}
else
{
node<Type> * temp = head;
head = head->next;
head->prev = NULL;
Type output = temp->data;
delete temp;
return output;
}
}
template <class Type>
bool linkedList<Type>::empty()// Function to check if the list is empty
{
int empty=returnCount();
if(empty == 0)
{
cout<< " The list is empty "<<endl;
return true;
}
else return false;
}
template <class Type>
void linkedList<Type>::display()
{
node<Type> * current = head;
while( current != NULL )
{
cout<< current->data <<endl;
current = current->next;
}
}
template <class Type>
Type linkedList<Type>::getStudent(int id)
{
node<Type> *current; //ptr to current node
current = head; //point to first
while (current!= NULL)
{
if (current->data.getId() == id)
return current->data;
else //otherwise move to the next node
current = current->next;
}
}
template <class Type>
bool linkedList<Type>::removeStudent(int id)
{
node<Type> *current; //ptr to current node
current = head; //point to first
while (current!= NULL)
{
if (current->data.getId() == id)
{
//found it, let it equal temp
node<Type> * temp = current;
if (temp->prev == NULL)
{
head = head->next;
head->prev = NULL;
delete temp;
return true;
}
else
{
node<Type> * previous, * next;
previous=temp->prev;
next = temp->next;
previous->next=next;
next->prev=previous;
delete temp;
return true;
}
}
else //otherwise move to the next node
current = current->next;
}
return false;
}
template<class Type>
void linkedList<Type>::sort(string field)
{
int c = returnCount();
//create an array of size returnCount.
Type studentArray[100];
node<Type> * current = head;
for(int i = 0; i < c; i++)
{
studentArray[i] = current->data;
current = current->next;
}
int k, j, count;
Type tmp;
bool flag;
count = c;
for (k = 0; k< count; k++)
{
flag = false;
for (j = 0; j< count - k - 1; j++) //bubble the i-th largest element to the right position
{
//swap list[j] and list[j+1] if they are out of order
if ( field.compare("id") ==0)
{
if (studentArray[j].getId() > studentArray[j+1].getId())
{
tmp = studentArray[j];
studentArray[j] = studentArray[j+1];
studentArray[j+1] = tmp;
flag = true;
}
}
else if ( field.compare("name") == 0)
{
string n = studentArray[j].getName();
string m = studentArray[j+1].getName();
if (n.compare(m) > 0)
{
tmp = studentArray[j];
studentArray[j] = studentArray[j+1];
studentArray[j+1] = tmp;
flag = true;
}
}
}
if (!flag) //if swapping, then the list is sorted
break;
}
current = head;
for(int i = 0; i < c; i++)
{
current->data = studentArray[i];
current = current->next;
}
}
#endif
Explanation / Answer
class speedTable { private: studentList * table; //an array of studentLists int tableSize; //size of the array public: speedTable(int size); ~speedTable(); 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); //Create a new array of size newsize and rehash //all items in the old table into the new table. //Free (delete) the old array and point the table //variable at the new array. void resize(int newsize); } this is my linkedList code: #include #include #include #include #include #include "student.h" using namespace std; //student list is a doubly linked list of students. template class linkedList { public: template class node { public: Type data; node * next; node * prev; node(Type x) { data = x; next = NULL; prev = NULL; } }; node * head, *first; friend ostream& operatornext = head; if( head != NULL ) head->prev = somenode; head = somenode; } //remove and return front item from list template Type linkedList:: pop() { if( head == NULL ) { coutprev = NULL; Type output = temp->data; delete temp; return output; } } template bool linkedList::empty()// Function to check if the list is empty { int empty=returnCount(); if(empty == 0) { coutprev == NULL) { head = head->next; head->prev = NULL; delete temp; return true; } else { node * previous, * next; previous=temp->prev; next = temp->next; previous->next=next; next->prev=previous; delete temp; return true; } } else //otherwise move to the next node current = current->next; } return false; } template void linkedList::sort(string field) { int c = returnCount(); //create an array of size returnCount. Type studentArray[100]; node * current = head; for(int i = 0; i data; current = current->next; } int k, j, count; Type tmp; bool flag; count = c; for (k = 0; k 0) { tmp = studentArray[j]; studentArray[j] = studentArray[j+1]; studentArray[j+1] = tmp; flag = true; } } } if (!flag) //if swapping, then the list is sorted break; } current = head; for(int i = 0; i data = studentArray[i]; current = current->next; } }Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.