c++ - 搜索保存在文件中的哈希表

Question

我编写了一个程序，它创建了一个哈希表并将其保存到一个文件中。我应该编写第二个程序，允许用户输入一个 key ，在文件中搜索该 key ，并显示存储在与输入的 key 匹配的记录中的信息。

我的程序已正确创建哈希表并将其保存到正确的文件中，但是，我在搜索文件时遇到问题。当我输入一个我知道在哈希表中的 key 时，我收到“找不到此 key ”的消息。

这是我的代码:

我的头文件:

//prog8.h
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

class Hash {
private:
    static const int hashSize = 8;
    struct record {
        int key;
        string name;
        int code;
        double cost;
        record* next;
    };
    record* hashTable[hashSize];
public:
    Hash();
    int hash(int key);
    void addRecord(int key, string name, int code, double cost);
    int numInIndex(int index);
    void saveRecords();
    void saveRecordsInIndex(int index);
    void findRecord(int key);
};

我的 .cpp 文件包含方法的定义:

//prog8.cpp
#include "prog8.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

Hash::Hash() {
    for(int i = 0; i < hashSize; i++) {
        hashTable[i] = new record;
        hashTable[i]->key = 8;
        hashTable[i]->name = "blank";
        hashTable[i]->code = 0;
        hashTable[i]->cost = 0.0;
        hashTable[i]->next = NULL;
    }
}
void Hash::addRecord(int key, string name, int code, double cost) {
    int index = hash(key);
    if(hashTable[index]->key == 8) {
        hashTable[index]->key = key;
        hashTable[index]->name = name;
        hashTable[index]->code = code;
        hashTable[index]->cost = cost;
    }
    else {
        record* ptr = hashTable[index];
        record* newRecord = new record;
        newRecord->key = key;
        newRecord->name = name;
        newRecord->code = code;
        newRecord->cost = cost;
        newRecord->next = NULL;
        while(ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = newRecord;
    }
}
int Hash::numInIndex(int index) {
    int count = 0;
    if(hashTable[index]->key == 0) {
        return count;
    }
    else {
        count++;
        record* ptr = hashTable[index];
        while(ptr->next != NULL) {
            count++;
            ptr = ptr->next;
        }
    }
    return count;
}
int Hash::hash(int key) {
    int index = key % 5;
    return index;
}
void Hash::saveRecords() {
    ofstream recordsFile;
    recordsFile.open("records.dat");
    int number;
    for(int i = 0; i < hashSize; i++) {
        number = numInIndex(i);
        recordsFile << "-------------\n";
        recordsFile << "Index = " << i << endl;
        recordsFile << hashTable[i]->key << endl;
        recordsFile << hashTable[i]->name << endl;
        recordsFile << hashTable[i]->code << endl;
        recordsFile << hashTable[i]->cost << endl;
        recordsFile << "Number of items in index = " << number << endl;
        recordsFile << "-------------\n";
    }
}
void Hash::saveRecordsInIndex(int index) {
    ofstream recordsFile;
    recordsFile.open("records.dat");    
    record* ptr = hashTable[index];
    if(ptr->key == 0) {
        cout << "Index " << index << " is empty";
    }
    else {
        cout << "Index " << index << " contains the following records:\n";
        while(ptr != NULL) {
            recordsFile << "--------------\n";
            recordsFile << ptr->key << endl;
            recordsFile << "--------------\n";
            ptr = ptr->next;
            //index++;
        }
    }
}
void Hash::findRecord(int key) {
    ifstream recordsFile;
    recordsFile.open("records.dat");
    if(!recordsFile.is_open()) {
        cerr << "Error opening file" << endl;
    }
    int index = hash(key);
    bool wasFound = false;
    record* ptr = hashTable[index];
    while(ptr != NULL) {
        if(ptr->key == key) {
            wasFound = true;
            key = ptr->key;
        }
        ptr = ptr->next;
    }
    if(wasFound == true) {
        cout << key;
    }
    else {
        cout << "There was no record matching the key " << key << " found."
        << endl;
    }
    recordsFile.close();
}

我的第一个主文件:

//prog8main.cpp
#include "prog8.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
    ifstream file;
    file.open("prog8.dat");
    if(!file.is_open()) {
        cerr << "Error opening file" << endl;
    }
    int index;
    int key;
    string name;
    int code;
    double cost;
    Hash hashObj;
    if(key != 8) {
        while(file >> key && file >> name && file >> code && file >> cost) {
            hashObj.addRecord(key, name, code, cost);
            hashObj.saveRecords();
            //hashObj.saveRecordsInIndex(index);
        }
    }
    file.close();
    return 0;
}

我的主文件搜索输出文件:

//prog8search.cpp
#include "prog8.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
    int key;
    Hash hashObj;
    cout << "Please enter a key ";
    cin >> key;
    hashObj.Hash::findRecord(key);

    return 0;
}

这是我得到的输出示例，包含已创建的 records.dat 文件:

[cs331129@cs ~]$ g++ -o prog8 prog8.cpp prog8main.cpp
[cs331129@cs ~]$ prog8
[cs331129@cs ~]$ cat records.dat
-------------
Index = 0
12345
Item06
45
14.2
Number of items in index = 2
-------------
-------------
Index = 1
34186
Item25
18
17.75
Number of items in index = 2
-------------
-------------
Index = 2
12382
Item09
62
41.37
Number of items in index = 3
-------------
-------------
Index = 3
8
blank
0
0
Number of items in index = 1
-------------
-------------
Index = 4
12434
Item04
21
17.3
Number of items in index = 1
-------------
-------------
Index = 5
8
blank
0
0
Number of items in index = 1
-------------
-------------
Index = 6
8
blank
0
0
Number of items in index = 1
-------------
-------------
Index = 7
8
blank
0
0
Number of items in index = 1
-------------
[cs331129@cs ~]$ g++ -o prog8search prog8.cpp prog8search.cpp
[cs331129@cs ~]$ prog8search
Please enter a key 12345
There was no record matching the key 12345 found.

如有任何帮助，我们将不胜感激。

Answer 1

我发现您的代码存在许多问题:

1. 您的哈希索引大小是 8？那你为什么要修改 5？这意味着单元格 5、6 和 7 将始终为空，因为它们将被重定向到 0、1 和 2。

2. 为什么在 main() 中每次读取记录后都输出？为什么不在最后这样做呢？ (如果你不坚持那种糟糕的支撑风格，那么你在做什么会更清楚，尽管其他人在风格问题上会不同意我的看法)。

3. 您的代码当然会泄漏，不是常量正确的，通常可以通过更好的结构来完成。

4. “findRecord”对输入文件做了什么？我看不到它在读它。

5. 为什么要检查 key==0？那不是有效的 key 吗？