|
|
Si supponga che gli elementi dell’insieme siano identificabili univocamente con i numeri compresi tra 0 ed n-1. Un insieme A allora può essere rappresentato con un vettore booleano di n posizioni, in cui la k-esima posizione vale 1 (condizione vera) se k appartiene ad A, 0 (condizione falsa) altrimenti. Nell’implementazione proposta, in linguaggio C, supponiamo che gli insiemi A e B abbiano la stessa dimensione:
La funzione “appartiene” verifica l’ appartenenza di un elemento x in un insieme A. Nella funzione “inserisci” la k-esima posizione vale viene posta a true (1), quando inseriamo un elemento in tale posizione. Le operazioni di unione e intersezione di due insiemi si realizzano facilmente con operazioni logiche. Infatti, per l ‘unione basta porre a vero tutti i bit che sono veri in almeno uno dei due vettori (con un’ operazione OR), per l ‘ intersezione tutti quelli veri in entrambi i vettori (con un and). Gli operatori “appartiene”, “inserisci” hanno complessità O(1) gli altri operatori invece sono O(n). Di conseguenza questa realizzazione è efficace solo per strutture statiche, ovvero quando non vengono usati operatori tipo unione ecc. In generale quindi, questa realizzazione non è efficiente, anche perché viene sprecato dello spazio in memoria.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.