Zliczanie liczby wystąpień ciągu znaków w tabeli skrótów - c ++, hashtable

Piszę własną klasę HashTable w C ++ i muszę przekazać użytkownikowi liczbę wystąpień każdego łańcucha w tabeli. Na przykład, jeśli to jest dane wejściowe: testing, 1, 2, testing, a to jest tablica skrótów (zrobiona z łańcuchem i wskaźnikami węzłów):

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

będzie to wynik dla użytkownika (liczba, po której następuje słowo):

2 testing
1 2
1 1

Problem, który mam, polega na tym, jak śledzić, ile każdego słowa znajduje się w tabeli skrótów lub jak je znaleźć. Zacząłem od to pytanie ale nie mogłem zaimplementować innej tablicy w moim kodzie.

Próbowałem również w to pytanie, ale to nie działało z powodu mojego użycia wskaźników / mieszania łańcuchowego.

Moje pytanie brzmi: czy muszę użyć osobnej tablicyciągów, aby śledzić, co już zostało użyte, czy też istnieje prosty sposób rekurencyjnie przejrzeć każdy indeks tabeli Hash i wydrukować liczbę wystąpień każdego ciągu? Myślę, że muszę to zrobić w moim insert funkcja lub moja printData funkcjonować.

Dla odniesienia, oto mój kod:

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)
};

HashTable.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;
}

UWAGA: Nie mogę używać żadnej funkcji / struktury danych ze standardowej biblioteki C ++.

Odpowiedzi:

Widzę tu tylko dwie opcje

1. Przejrzyj całą połączoną listę, aby policzyć wystąpienia. Użyj mapy <ciąg, int>, aby policzyć wystąpienia dla każdego ciągu.

2. Powinieneś posortować połączoną listę. Kiedy wstawisz nowy węzeł, wstawisz go dokładnie w tym miejscu. Możesz użyć strcmp do porównania. W ten sposób możesz policzyć każde słowo dokładnie w jednym przejściu i używając tylko jednej zmiennej całkowitej, ale Twój czas wstawiania i złożoność wzrosną.