Počítanie počtu výskytov reťazca v tabuľke Hash - c ++, hashtable

Píšem vlastnú triedu HashTable v C ++ a potrebujem na výstup užívateľovi počet výskytov každého reťazca v tabuľke. Ak je to napríklad vstup: testing, 1, 2, testing, a toto je hash tabuľka (vykonaná s reťazením a ukazovateľmi uzlov):

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

toto by bol výstup pre používateľa (počet, za ktorým nasleduje slovo):

2 testing
1 2
1 1

Problém, ktorý mám, je ako sledovať, koľko z každého slova je v tabuľke Hash, alebo ako ho nájsť. táto otázka ale nebol schopný implementovať ďalšie pole v mojom kóde.

Tiež som sa snažil riešenie v táto otázka, ale to nefungovalo, pretože som použil ukazovatele / reťazené hash.

Moja otázka je, musím použiť samostatné polereťazcov na sledovanie toho, čo už bolo použité, alebo existuje jednoduchý spôsob, ako rekurzívne prejsť každým indexom tabuľky hash a vytlačiť počet výskytov jednotlivých reťazcov? insert alebo moja printData Funkcie.

Tu je môj kód:

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

POZNÁMKA: Nemôžem použiť žiadnu štruktúru funkcií / údajov zo štandardnej knižnice C ++.

odpovede:

Vidím tu iba dve možnosti

1. Presunúť celý prepojený zoznam počítať výskytov. Použite mapu <string, int> na počítanie výskytov pre každý reťazec.

2. Váš prepojený zoznam by ste mali zoradiť. Takže keď vložíte nový uzol, vložíte ho na svoje presné miesto. Na porovnanie môžete použiť strcmp. Týmto spôsobom môžete počítať každé slovo presne v jednom ťahu a používať len jednu celočíselnú premennú, ale čas vloženia a zložitosť sa zvýši.