Homework SoursePreliminary task Using c Write a program that creates a list
Preliminary task:
Using c++, Write a program that creates a list that can be searched quickly. To do so, create a hashed list (an array of size 13) using a modulo-division hash function with a linear probe to resolve collisions (Utilize the Hashing implementation on page 521 or create your own class).
Use the input from lab7.dat file and search data from lab7srch.dat file.
lab7.dat
5876
1314
5343
2735
7222
6248
9901
lab7srch.dat
5876
6248
4477
7451
2818
9901
1000
9999
4567
8398
Direct the output to the external file YourIslandIDlab7.out.
Sample Output:
HASH METHOD: modulo-division
COLLISION RESOLUTION: linear probe
HASHED LIST:
SUB KEY
0 5876
1 1314
2 5343
3 -1
4 -1
5 2735
6 -1
7 7222
8 6248
9 9901
10 -1
11 -1
12 -1
HASHED LIST SEARCH RESULTS:
KEY FOUND HOME ADDRESS #COLLISIONS
5876 YES 0 0
6248 YES 8 0
4477 NO 5 1
7451 NO 2 1
2818 NO 10 0
9901 YES 9 1
1000 NO 12 0
9999 NO 2 1
4567 NO 4 0
8398 NO 0 3
Total Number of Collisions: 7
Postliminary task:
Format your output so that the user of your program understands the values that were input and what was output for each calculation. Your program should have a user-friendly interface.
Make sure your program is properly documented and good programming standards are followed. You are required to follow C++ Style guide, which is available on Blackboard.
Try your program with a variety of input values, to determine it works properly.
Solution
#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
const int HTSIZE = 13;
int hashFunction(string , int );
int main() {
string hashTable[HTSIZE];
string line;
fstream dataIn;
int sub = 0;
int index = 0;
bool found;
int collision = 0;
dataIn.open(\"lab6.dat\");
cout << \"HASH METHOD: modulo-division\" << endl
<< \"COLLISION RESOLUTION: linear probe\" << endl
<< \"HASHED LIST\" << endl << endl
<< \"SUB\" << setw(5) << \"KEY\" << endl;
while(dataIn)
{
getline(dataIn, line);
index = hashFunction(line, line.length());
hashTable[index] = line;
}
for(index = 0; index < HTSIZE; index++)
{
if(hashTable[index] == \"\")
{
hashTable[index] = \"-1\";
}
cout << left << setw(5) << index << hashTable[index] << endl;
}
dataIn.close();
dataIn.open(\"lab6srch.dat\");
while(dataIn)
{
getline(dataIn, line);
sub = hashFunction(line, line.length());
found = false;
while(hashTable[sub] != \"-1\" && !found)
{
if(hashTable[sub] == line)
found = true;
}
else
sub = (sub + 1) % HTSIZE;
}
if(found)
{
cout <<\"Yes\" << endl;
}
else
{
hashTable[sub] = line;
}
}
dataIn.close();
for( index = 0; index < HTSIZE; index++)
{
cout << setw(5) << hashTable[index] << endl;
}
return 0;
}
int hashFunction(string insertKey, int keyLength)
{
int sum = 0;
for (int index = 0; index < keyLength; index++)
sum = sum + static_cast<int>(insertKey[index]);
return (sum % HTSIZE);
}
