c++ - 计算哈希表中字符串出现的次数

Question

我正在用 C++ 编写自己的 HashTable 类，需要向用户输出表中每个字符串的出现次数。例如，如果这是输入:testing, 1, 2, testing，这是哈希表(通过链接和节点指针完成):

[0]->testing, testing
[1]->2
[2]->1

这将是给用户的输出(计数，后跟单词):

2 testing
1 2
1 1

我遇到的问题是如何跟踪哈希表中每个单词的数量，或者如何找到它。我从 this question 开始但无法在我的代码中实现另一个数组。

我也尝试了 this question 中的解决方案，但由于我使用了指针/链式哈希，所以它不起作用。

我的问题是，我是否需要使用一个单独的字符串数组来跟踪已经使用的内容，或者是否有一种简单的方法可以递归地遍历哈希表的每个索引并打印出出现的次数每个字符串？我认为我需要在我的 insert 函数或我的 printData 函数中完成此操作。

作为引用，这是我的代码:

HashTable.h:

#include <string>
#include <iostream>

using namespace std;

struct Entry {
    string word;
    Entry* next;
};

class HashTable {
public:
    HashTable();
    HashTable(int);
    int hash(string);
    void insert(string);
    void printData();
    int getCapacity() const;
private:
    //Member variables
    int CAPACITY; // The initial capacity of the HashTable
    Entry **data; // The array to store the data of strings (Entries)
};

哈希表.cpp:

#include "HashTable.h"

HashTable::HashTable()
{
    CAPACITY = 0;
    data = new Entry*[0]; 
}

HashTable::HashTable(int _cap)
{
    CAPACITY = _cap;
    data = new Entry*[_cap];

    for (int i = 0; i < CAPACITY; i++) {
        data[i] = new Entry;
        data[i]->word = "empty";
        data[i]->next = nullptr;
    }
}

int HashTable::hash(string key)
{
    int hash = 0;

    for (unsigned int i = 0; i < key.length(); i++) {
        hash = hash + (int)key[i];
    }

    return hash % CAPACITY;
}

void HashTable::insert(string entry)
{
    int index = hash(entry);

    if (data[index]->word == "empty") {
        data[index]->word = entry;
    } else {
        Entry* temp = data[index];
        Entry* e = new Entry;
        e->word = entry;
        e->next = nullptr;

        while (temp->next != nullptr) {
            temp = temp->next;
        }

        temp->next = e;
    }
}   

void HashTable::printData()
{
    for (int i = 0; i < CAPACITY; i++) {
        if (data[i]->next != nullptr) {
            while(data[i]->next != nullptr) {
                cout << data[i]->word << " -> ";
                data[i] = data[i]->next;
            }

            cout << data[i]->word << endl;
        } else {
            cout << data[i]->word << endl;
        }
    }
}

int HashTable::getCapacity() const
{
    return CAPACITY;
}

注意:我不能使用标准 C++ 库中的任何函数/数据结构。

Answer 1

这里只有两个选项

1. 遍历整个链表以计算出现次数。使用 map 来计算每个字符串的出现次数。

2. 您应该对链表进行排序。所以当你插入一个新节点时，你会把它插入到它的确切位置。您可以使用 strcmp 进行比较。通过这种方式，您可以在一次遍历中准确地计算每个单词，并且只使用一个整数变量，但是您的插入时间和复杂性会增加。