C++ ######################### Question ##################### Write a program to
ID: 3801272 • Letter: C
Question
C++
######################### Question #####################
Write a program to compute hash values of numbers given in file prog3_input.txt using hash function h(k) = k mod 10. If two numbers have the same hash value, then store the second number in the next free location. Write the computed hash values to a file named prog3_output.txt.
######################### Input File #####################
17
29
5
34
87
42
37
51
38
91
######################### Hints #####################
Algorithm:
Create an array A[10] and initialie all of its values to let's say -1
For each number you read from input file:
compute r= number%10
check if A[r] == -1 //this means the slot is available
then A[r] = number
else:
loop through indices of A starting from index r+1 until you find an empty slot. If reached index = 9 start searching from index 0
A[next available slot] = number
Walkthrough:
17 mod 10 = 7 => A[7] = 17
29 mod 10 = 9 => A[9] = 29
5 mod 10 = 5 => A[5] = 5
34 mod 10 = 4 => A[4] = 34
87 mod 10 = 7 => collision. A[7] is not empty. Next available A[8] = 87
42 mod 10 = 2 => A[2] = 42
37 mod 10 = 7 => collision A[7] not empty. A[8] not empty. A[9] not empty. A[0] = 37
51 mod 10 = 1 => A[1] = 51
38 mod 10 = 8 => collision. A[8] not empty. A[9], A[0], A[1], A[2] not empty. A[3] = 38
91 mod 10 = 1 => collision. A[1] not empty. A[2], A[3], A[4], A[5] not empty. A[6] = 91
Output file (resulting A array).
37
51
42
38
34
5
91
17
87
29
You can alternatively print only the hash values:
7
9
5
4
8
2
0
1
3
6
Explanation / Answer
PROGRAM CODE:
#include <iostream>
#include <fstream>
#include <sstream>
using namespace std;
//main function to read the file, calculate hash values and write to a file
int main() {
//read
ifstream in("prog3_input.txt");
string line;
int A[10] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int B[10], count = 0;
if(in.is_open())
{
//reading every line and getting the value
while(getline(in, line))
{
istringstream(line);
int number, r;
if(!(iss>>number))
{
cout<<"Something went wrong ";
exit(1);
}
//hash function
r = number%10;
if(A[r]==-1)
{
A[r] = number;
B[count++] = r;
}
else
{
int i = r+1;
while(A[i] != -1)
{
if(i==9)
i = 0;
else i++;
}
A[i] = number;
B[count++] = i;
}
}
}
ofstream out("prog3_output.txt");
for(int i=0; i<10; i++)
{
out<<B[i]<<endl;
}
return 0;
}
OUTPUT:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.