Come implementare un set?

Question

Voglio implementare un Set in C. È corretto usare un elenco collegato, quando si crea il SET, o dovrei usare un altro approccio?

Come di solito implementare il proprio set (se necessario).

NOTA: Se io uso l'approccio lista concatenata, io probabilmente hanno le seguenti complessità per impostare il mio operazioni:

• init: O (1);
• destroy: O (n);
• inserire: O (n);
• rimuovere: O (n);
• unione: O (n * m);
• intersezione: O (n * m);
• differenza: O (n * m);
• nome: O (n);
• issubset: O (n * m);
• setisequal: O (n * m);

O (n * m) sembra essere un po 'troppo grande soprattutto per i dati enormi ... C'è un modo per implementare il mio set più efficiente?

Answer 1

Ho usato alberi rosso-nero in passato per creare serie.

Ecco le complessità temporali dall'articolo di Wikipedia.

Spazio O (n)
Ricerca O (log n)
Inserire O (log n)
Delete O (log n)

Answer 2

std::set è spesso implementata come un albero nero rosso: http://en.wikipedia.org/wiki/Red-black_tree

Questo approccio vi darà molto meglio la complessità su tutte le operazioni elencate.

Answer 3

Ci sono molti modi per impostare l'implementazione. Here sono alcuni di loro. Oltre allo MSDN c'è un ottimo articolo su di esso.

Answer 4

Dal momento che si dispone già di una lista concatenata implementato, il più semplice è a skip list. Se si desidera utilizzare alberi bilanciati, il più semplice a mio parere è un treap. Si tratta di strutture dati randomizzate, ma generalmente sono altrettanto efficienti delle loro controparti deterministiche, se non di più (e una lista skip può essere resa deterministica).

Answer 5

Gli insiemi vengono in genere implementati come alberi red-black (che richiede che gli elementi abbiano un ordine totale) o come un hashtable che ridimensiona automaticamente (che richiede una funzione hash).

Quest'ultimo viene in genere implementato avendo la dimensione doppia di hash e reinserendo tutti gli elementi quando viene superata una determinata soglia di capacità (il 75% funziona bene). Ciò significa che le operazioni di inserimento inidividuali possono essere O (n), ma quando sono ammortizzate su molte operazioni, in realtà è O (1).