Conteggio del numero di occorrenze di una stringa in una tabella hash - c ++, hashtable

Sto scrivendo la mia classe HashTable in C ++ e ho bisogno di fornire all'utente il numero di occorrenze di ogni stringa nella tabella. Ad esempio, se questo è l'input: testing, 1, 2, testinge questa è la tabella hash (eseguita con concatenamento e puntatori di nodi):

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

questo sarebbe l'output per l'utente (il conteggio, seguito dalla parola):

2 testing
1 2
1 1

Il problema che sto avendo è come tenere traccia del numero di ogni parola nella tabella hash o di come trovarlo. questa domanda ma non è stato in grado di implementare un altro array nel mio codice.

Ho anche provato la soluzione in questa domanda, ma non ha funzionato a causa del mio uso di puntatori / hashing incatenato.

La mia domanda è, ho bisogno di utilizzare un array separatodi stringhe per tenere traccia di ciò che è già stato utilizzato, o c'è un modo semplice per scorrere in modo ricorsivo ogni indice della tabella hash e stampare il numero di occorrenze di ogni stringa? Penso che ho bisogno di realizzare questo in entrambi i miei insert funzione o mio printData funzione.

Per riferimento, ecco il mio codice:

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: Non posso usare alcuna funzione / struttura dati dalla libreria standard C ++.

risposte:

Vedo solo due opzioni qui

1. Attraversa l'intero elenco collegato per contare le occorrenze. Usa una mappa <string, int> per contare le occorrenze per ogni stringa.

2. Dovresti rendere ordinato il tuo elenco collegato. Quindi quando inserisci un nuovo nodo, lo inserirai nella sua esatta posizione. È possibile utilizzare strcmp per il confronto. In questo modo puoi contare ogni parola esattamente in una traversa e usando solo una variabile intera, ma il tempo e la complessità dell'insegnamento aumenteranno.