Uno dei tipi di strutture dati che sono l'incarnazione diretta delle entità matematiche nell'informatica sono gli insiemi. Le operazioni con loro abbastanza spesso sono alla base di vari algoritmi. Diversi linguaggi di programmazione hanno i propri mezzi per descrivere gli insiemi.
Necessario
- - sviluppo dell'ambiente;
- - traduttore dal linguaggio di programmazione selezionato.
Istruzioni
Passo 1
Descrivere l'apparecchio utilizzando il linguaggio di programmazione, se disponibile. Ad esempio, nel linguaggio Pascal esiste un costrutto set che permette di dichiarare i tipi corrispondenti. È vero, il volume di tali set non deve superare i 256 elementi. Un esempio di dichiarazioni di tipo set potrebbe essere simile a questo:
genere
AZLetters = insieme di 'A'.. 'Z';
AllLetters = insieme di caratteri;
Le variabili e le costanti dei tipi che sono insiemi vengono dichiarate nel modo consueto. In questo caso, è possibile utilizzare valori letterali per l'inizializzazione. Per esempio:
cost
LettersSet1: AZLetters = ['A', 'B', 'C'];
Passo 2
Usa le capacità delle librerie standard o dei moduli per descrivere i set. Quindi, la libreria di modelli C ++, che dovrebbe essere fornita con il compilatore, include un modello per la classe contenitore set che implementa la funzionalità dei set:
modello <
chiave di classe, Tratti di classe = meno, allocatore di classe = allocatore
set di classe
Come puoi vedere dal listato, gli argomenti del set template sono: il tipo di dati degli elementi dell'insieme, il tipo dell'oggetto funzionale per determinare l'ordine degli elementi nell'insieme e il tipo di allocatore di memoria. In questo caso, è richiesto solo il primo argomento (poiché gli altri due, il predicato binario standard less e l'allocatore standard vengono utilizzati per impostazione predefinita).
Passaggio 3
Applicare classi o modelli di classe utilizzati nello sviluppo di framework che implementano la funzionalità di lavorare con i set, se presenti. Un esempio di tale strumento è la classe template QSet del modulo QtCore della libreria Qt. Le sue capacità sono simili a quelle del contenitore del set STL descritto nel passaggio precedente.
Passaggio 4
Descrivi il set utilizzando i tuoi mezzi di implementazione. Utilizzare flag di bit, archiviati in array a lunghezza fissa, per insiemi di elementi di tipi semplici e dimensioni ridotte. Implementare una classe contenitore set per tipi di dati complessi. Come base, puoi prendere la funzionalità di array associativi associativi o di hashing. A sua volta, può essere costruito sulla base di alberi binari di ricerca autobilanciati (ad esempio alberi rosso-nero).
