Programmazione orientata agli oggetti in ANSI-C. Implementazione della superclasse – Name – 1

Cercare i simboli tramite il loro nome è un problema classico. Sfortunatamente, lo standard ANSI non definisce una funzione di libreria per risolvere il problema.

Bsearch() - ricerca binaria in una tabella ordinata – potrebbe essere un'idea per risolvere il problema, ma si deve comunque considerare che se inseriamo un nuovo simbolo dobbiamo andare a chiamare qsort() per sistemare l'ordinamento per le future ricerche. Di conseguenza si deve provvedere a fornire l'ordinamento per ogni volta che un nuovo elemento viene inserito nella tabella.

I sistemi UNIX forniscono funzioni per gestire tabelle i cui elementi crescono dinamicamente. Lsearch() - ricerca lineare di un array e se non trovato aggiunge l'elemento alla fine – non è completamente efficiente. Hsearch() - una tabella hash per strutture che consiste in un testo e un puntatore alle informazioni – mantiene una sola tabella di una dimensione fissata- tsearch() - un albero binario con confronti ed eliminazioni – è il tipo di ricerca più generale ma è discretamente inefficiente se i simboli iniziali sono installati rispettando l'ordinamento.

Su di un sistema UNIX, tsearch() è però il miglior compromesso. Il codice sorgente per una implementazione portabile con gli alberi binari può essere consultato in [Sch87]. Comunque, se questa funzione non è disponibile, oppure se non possiamo garantire che vi sia una inizializzazione random, dovremmo organizzarci per trovare un metodo più semplice da implementare. Ne consegue che un'attenta implementazione bsearch() può essere facilmente estesa per supportare anche l'inserimento in un array ordinato.

void * binary (const void * key,
void * _base, size_t * nelp, size_t width,
int (* cmp) (const void * key, const void * elt))
{ size_t nel = * nelp;
#define base (* (char **) & _base)
char * lim = base + nel * width, * high;
if (nel > 0)
{ for (high = lim — width; base <= high; nel >>= 1)
{ char * mid = base + (nel >> 1) * width;
int c = cmp(key, mid);
if (c < 0)
high = mid — width;
else if (c > 0)
base = mid + width, —— nel;
else
return (void *) mid;
}

Si tratta quindi di una ricerca binaria in un array arbitrario. key punta all'oggetto da trovare; base è inizialmente l'indirizzo di una tabella di *nelp elementi, ognuno dei quali è composto da width bytes; e cmp è una funzione per confrontare key con gli elementi di una tabella.

A questo punto abbiamo trovato un elemento di una tabella e abbiamo restituito il suo indirizzo e base è quindi l'indirizzo in cui key dovrebbe essere in una tabella. Continuiamo come segue:

memmove(base + width, base, lim — base);
}
++ *nelp;
return memcpy(base, key, width);
#undef base
}

memmove() sposta la fine dell'array e memcpy() inserisce la chiave. Se ipotizziamo che ci sia spazio oltre l'array e registraimo attraverso nelp che abbiamo aggiunto un elemento – binary() si comporta diversamente rispetto alla funzione standard bsearch() solo nel fatto che richiede l'indirizzo piuttosto che il varole della variabile contenente il numero di elementi nella tabella.

Scarica subito una copia gratis

Scrivi un commento

Send this to a friend