[C] Struttura dati per memoria associativa

[ingframin]

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.

[wingman87]

Io propendo per la terza soluzione che di fatto è una mappa. L'albero, a meno che la stringa sia particolarmente corta, non ti darebbe un grande vantaggio di memoria.

[ingframin]

Originariamente inviato da wingman87

Io propendo per la terza soluzione che di fatto è una mappa. L'albero, a meno che la stringa sia particolarmente corta, non ti darebbe un grande vantaggio di memoria.

La stringa è di soli 72 caratteri...
Sto pensando di tenermi la ricerca lineare onestamente

[wingman87]

72 non è poi così corta. Alla fine del tuo array di 255 spazi ne usi il 28% e lo spreco di memoria si limita a 183 riferimenti null.
Usando un albero binario, contando 2 riferimenti per valore avresti 144 riferimenti, la metà null. Ma sarebbe più complicato e meno efficiente nell'accesso e nella scrittura.
Con la ricerca lineare impieghi 72*73/2 passi (2628) per trovare tutti gli indici.

[cdimauro]

Concordo sull'array: soluzione semplice, pratica veloce.

@ingframin: perché dici che consuma troppo memoria? Potresti scendere un po' nel dettaglio, SE possibile?

[ingframin]

Originariamente inviato da cdimauro

Concordo sull'array: soluzione semplice, pratica veloce.

@ingframin: perché dici che consuma troppo memoria? Potresti scendere un po' nel dettaglio, SE possibile?

Più che altro devo allocare 128 byte per usarne solo 72... Mi pare uno spreco.
Poi vabbé, ho 32GB di ram sul pc, quindi crepi l'avarizia, è solo che non pensavo fosse una buona soluzione.

[cdimauro]

La soluzione buona è quella che ti permette di risolvere rapidamente il tuo problema.