项目介绍
-
本项目实现一个简单的哈希表。
-
txt文件包含一个整数值序列。读取它们并使用链接构造一个哈希表。
-
程序应该依次读取每个整数,并使用mod 100作为哈希函数计算其哈希值。因此,如果键是k,那么哈希值h(k) =kmod 100。(最简单的哈希函数)
-
完成计算后打印:
- 哈希表中空条目的数量。
- 最长链的长度。
-
不使用STL或等价的库。
哈希表示例图如下:
读取的文件示例:
代码实现
#include <iostream>
#include <fstream>
using namespace std;
const int MAXNUM = 100;
int Lchaining = 0;
int tool = 0;
int key[MAXNUM];
struct Node {
int value;
Node* next;
Node(int value) :value(value), next(0) {};
};
Node* Table[MAXNUM] = { 0 };
int hashfunction(int value);
void insert(int Key, int Value);
void chaincount(Node* node);
void insert(int Key, int Value) {
Node* newNode = new Node(Value);
int a = 1;
if (Table[Key] == NULL) {
Table[Key] = newNode;
}
else {
Node* currentNode = Table[Key];
while (currentNode->next != NULL) {
a++;
currentNode = currentNode->next;
}
if (a > Lchaining) {
Lchaining = a;
}
currentNode->next = newNode;
}
}
int main() {
ifstream read;
int key, value;
string a;
cout << "Please enter the filename: " << endl;
cin >>a;
read.open(a.c_str());
if (!read)
{
cout << "Can't open file" << endl;
exit(1);
}
while (read >> value) {
key = hashfunction(value);
insert(key, value);
}
int y = 0;
while (y < 100) {
y++;
if (Table[y] == NULL) {
tool++;
}
}
cout << "The number of empty entries in the hash table: " << tool << endl;
cout << "The length of the longest chain: " << Lchaining << endl;
return 0;
}
int hashfunction(int value) {
return value % 100;
}
输出结果如下图: