1. apply separate chaining to address collision but each chain cannot hold more than 2 nodes. Always insert new students to the end of the chain.
2. when a chain already holds two nodes and we need to insert another collided student, apply linear probing to look for the next empty slot to build a new chain (which can, again, hold no more than 2 nodes)
3. The link array stores the address of the next chain (like that in coalesced chaining), with all elements initialized to –1.
4. When a node is removed from a chain, no need to update anything else.

Example of the Design

Insert 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

H(1) = 1. Student 1 goes to slot 1. (1st node in the chain at slot 1)
H(2) = 0. Student 2 goes to slot 0. (1st node in the chain at slot 0)
H(3) = 1. Student 3 goes to slot 1. (2nd node in the chain at slot 1)
H(4) = 0. Student 4 goes to slot 0. (2nd node in the chain at slot 0)

Now look at the link array “link”. All elements are initialized to -1. No update so far.

H(5) = 1. Student 5 cannot go to slot 1 (chain is full — you need to design a mechanism to check if a chain is full). Check “link[1] = -1”, meaning that no new chain is built for students collided at slot 1. Thus, we need to find an empty slot to build a new chain. Do linear probing and find slot 2, insert student 5. (1st node in the chain at slot 2). Update “link[1] = 2”, meaning that the next chain for collided students is at slot 2.

H(6) = 0. Student 6 cannot go to slot 0 (chain is full). Check “link[0]= -1”, meaning that no new chain is built for students collided at slot 0. Thus, we need to find an empty slot to build a new chain. Do linear probing and find slot 3, insert student 6. (1st node in the chain at slot 3). I[date “link[0] = 3”, meaning that the next chain for collided students is at slot 3.

H(7) = 1. Student 7 cannot go to slot 1 (chain is full). Check “link[1] = 2”. So go to slot 2. Its chain is not full yet, insert 7 to the chain. (now the chain is full)

H(8) = 0. Student 8 cannot go to slot 0 (chain is full). Check “link[0] = 3”. So go to slot 3. Its chain is not full yet, insert 8 to the chain. (now the chain is full)

H(9) = 1. Student 9 cannot go to slot 1 (chain is full). Check “link[1] = 2”. So go to slot 2. Its chain is also full; in this case, check “link[2] = -1”, meaning no more new chain has been built for the collided students. So apply linear probing (starting from slot 2) to find an empty slot. Find slot 4. Insert student 9 (1st node in the chain at slot 4). Update “link[2] = 4”.

H(10) = 0. Student 9 cannot go to slot 0 (chain is full). Check “link[0] = 3”. So go to slot 3. Its chain is also full. Then check “link[3] = -1”, meaning no more new chain has been built for the collided students. So apply linear probing (from slot 3) to find an empty slot. Cannot find an empty slot (until probing sequence returns to slot 3), return insertion fail.

The resulted hash table looks like below. (red numbers indicate the order of inserted nodes)

Here is the rubrics for the assignment3.
Enumerate( ) method – 0 points
Search ( ) – 30 points
Insert( ) – 40 points
Remove( ) – 20 points
Documentation – 10 points

Here is a sample input and expected output for each case: (This is only for your reference: not used for testing)

1. Example for Enumerate() method (choice ? 1)
   Input:
   1 3.5 2 3.2 3 4.0 4 3.6 5 2.8 6 3.1 7 2.5 8 3.7 9 3.9 10 2.6
   1 5 3
   Output:
   2 4 3
   1 3 2
   5 7 4
   6 8 -1
   9 -1
2. Example for the Search () method (choice ? 2)
   Input:
   1 3.5 2 3.2 3 4.0 4 3.6 5 2.8 6 3.1 7 2.5 8 3.7 9 3.9 10 2.6
   2 5 3
   Output:
   2.8
3. Examples for the Remove () method (choice ? 3)
   Input:
   1 3.5 2 3.2 3 4.0 4 3.6 5 2.8 6 3.1 7 2.5 8 3.7 9 3.9 10 2.6
   3 5 3
   Output:
   2 4 3
   1 2
   5 7 4
   6 8 -1
   9 -1

NOTE: Please save the file as “HW3_CS2413.cpp” ONLY.
● Please do not modify existing codes in the template, especially the input / output formats. Only add your implementations to it. (You can add new variables to the existing classes, functions, etc)
● The auto-grader only recognizes the formats in this template.
● The main function has been written for you. It will test your member functions. You can also use it to debug the code. (See examples above.)

Provided cpp:

include

using namespace std;
class Student {
public:
int SID = 0;
float GPA = 0;
Student* ptr = NULL;
};
class HashTable {
public:
int Insert(Student* y); // insert a student x based on x.SID
// return 1 if insertion is successful
// return -1 if insertion fails (e.g. table full)
float Search(int key); // search for a student with SID=key in the table
// return GPA if student is found
// return -1 if student is not found
int Remove(int key); // remove a student with SID=key from the table
// return 1 if student is found and removed
// return -1 if student is not found
void Enumerate(); // enumerate all numbers, already implemented for you
private:
Student* x[5] = {NULL, NULL, NULL, NULL, NULL}; // array of student pointers
int link[5] = {-1,-1,-1,-1,-1}; // link array, all initialized to -1
int Counter[5] = {0, 0, 0, 0, 0};
int hash(int key); // hash function, already implemented for you
};
int HashTable::hash(int key) {
return key % 2;
}
void HashTable::Enumerate() {
Student* temp;
for (int i = 0; i < 5; i++) {

temp = x[i];
while (temp != NULL) { // print the chain

cout << temp->SID << ‘ ‘; temp = temp->ptr;
}
cout << link[i] << ‘\n’; // last number is the corresponding link value,
then change line
// so, basically, each line for one chain +
corresponding link
}

}
int main()
{
HashTable table;
for (int i = 0; i < 10; i++) { Student* x = new Student; cin >> x->SID >> x->GPA;
x->ptr = NULL;
table.Insert(x);
}
int operationChoice, SearchKey, RemoveKey;
cin >> operationChoice >> SearchKey >> RemoveKey;
if (operationChoice == 1) {

table.Enumerate();
}
else if (operationChoice == 2) {

cout << table.Search(SearchKey);
}
else if (operationChoice == 3) {

table.Remove(RemoveKey);
table.Enumerate();
}
else {

cout << “Enter a valid choice”;
}
return 0;
}

Sample Solution