ingframin
05-01-2017, 09:56
Buon giorno gioventù,
Ho una domandina tecnica dovuta più che altro alla mai ignoranza (non avendo mai studaito algoritmi e strutture dati...).
Ho bisogno di fare una funzione che preso un carattere in ingresso, mi restituisca un intero che corrisponde ad un indice per prendere dei dati da un array.
Al momento quello che faccio è salvare i dati nell'array per come i caratteri sono posizionati nella stringa e poi faccio una ricerca lineare sulla stringa per recuperare l'indice in base al carattere.
La stringa purtroppo non posso garantire che sia ordinata :(
Al momento ho tre alternative in mente:
- un albero binario: in ogni nodo metto il carattere e i dati che mi servono
- una hash map ma non ho idea di come si costruisca una funzione di hash
- un array di 256 elementi in cui uso il carattere come indice, alla fine in C i char sono interi, ma questo comporta anche uno spreco di memoria notevole.
La buona notizia è che la stringa non può contenere duplicati, quindi in caso di hash map non ho bisogno di gestire collisioni.
Secondo voi qual'è la soluzione ottimale? Vale la pena sbattersi o ci sono librerie già pronte allo scopo?
Non posso usare C++, altrimenti avrei usato std::map e avrei risolto...
PS.
Non è un esercizio per scuola o università e più che codice mi serve un parere.
Ho una domandina tecnica dovuta più che altro alla mai ignoranza (non avendo mai studaito algoritmi e strutture dati...).
Ho bisogno di fare una funzione che preso un carattere in ingresso, mi restituisca un intero che corrisponde ad un indice per prendere dei dati da un array.
Al momento quello che faccio è salvare i dati nell'array per come i caratteri sono posizionati nella stringa e poi faccio una ricerca lineare sulla stringa per recuperare l'indice in base al carattere.
La stringa purtroppo non posso garantire che sia ordinata :(
Al momento ho tre alternative in mente:
- un albero binario: in ogni nodo metto il carattere e i dati che mi servono
- una hash map ma non ho idea di come si costruisca una funzione di hash
- un array di 256 elementi in cui uso il carattere come indice, alla fine in C i char sono interi, ma questo comporta anche uno spreco di memoria notevole.
La buona notizia è che la stringa non può contenere duplicati, quindi in caso di hash map non ho bisogno di gestire collisioni.
Secondo voi qual'è la soluzione ottimale? Vale la pena sbattersi o ci sono librerie già pronte allo scopo?
Non posso usare C++, altrimenti avrei usato std::map e avrei risolto...
PS.
Non è un esercizio per scuola o università e più che codice mi serve un parere.