Número de recuentos de ocurrencias de una cadena en una tabla de hash - c ++, tabla hash

Estoy escribiendo mi propia clase HashTable en C ++ y necesito mostrarle al usuario el número de ocurrencias de cada cadena en la tabla. Por ejemplo, si esta es la entrada: testing, 1, 2, testing, y esta es la tabla hash (hecha con el encadenamiento y los punteros de nodo):

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

este sería el resultado para el usuario (el recuento, seguido de la palabra):

2 testing
1 2
1 1

El problema que tengo es cómo hacer un seguimiento de cuántas de cada palabra hay en la tabla de hash o cómo encontrarla. Comencé con esta pregunta pero no pude implementar otra matriz en mi código.

También probé la solución en esta pregunta, pero no funcionó debido a mi uso de punteros / hash encadenado.

Mi pregunta es, ¿necesito usar una matriz separada?de cadenas para realizar un seguimiento de lo que ya se ha utilizado, o hay una manera fácil de revisar cada índice de la tabla de hash e imprimir el número de ocurrencias de cada cadena? Creo que necesito lograr esto en cualquiera de mis insert función o mi printData función.

Para referencia, aquí está mi código:

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

NOTA: No puedo usar ninguna función / estructura de datos de la biblioteca estándar de C ++.

Respuestas

Solo veo dos opciones aquí

1. Recorrer toda la lista enlazada para contar ocurrencias. Use un mapa <string, int> para contar las ocurrencias de cada string.

2. Usted debe hacer su lista de enlaces ordenados. Entonces, cuando inserte un nuevo nodo, lo insertará en su lugar exacto. Puede utilizar strcmp para la comparación. De esta manera, puede contar cada palabra exactamente en una cruz y usar solo una variable entera, pero su tiempo y complejidad de inserción aumentarán.