Jedným z typov dátových štruktúr, ktoré sú priamym stelesnením matematických entít v informatike, sú množiny. Operácie s nimi často tvoria základ rôznych algoritmov. Rôzne programovacie jazyky majú svoje vlastné prostriedky na opis množín.
Nevyhnutné
- - vývojové prostredie;
- - prekladateľ z vybraného programovacieho jazyka.
Inštrukcie
Krok 1
Popíšte súpravu pomocou programovacieho jazyka, ak je k dispozícii. Napríklad v jazyku Pascal existuje množinová zostava, ktorá umožňuje deklarovať zodpovedajúce typy. Je pravda, že objem takýchto sád by nemal presiahnuť 256 prvkov. Príklad deklarácií typov môže vyzerať takto:
typu
AZLetters = množina 'A'.. 'Z';
AllLetters = sada znakov;
Premenné a konštanty typov, ktoré sú množinami, sú deklarované obvyklým spôsobom. V takom prípade je možné na inicializáciu použiť množinové literály. Napríklad:
konšt
LettersSet1: AZLetters = ['A', 'B', 'C'];
Krok 2
Na opísanie množín použite možnosti štandardných knižníc alebo modulov. Takže knižnica šablón C ++, ktorá by mala byť dodaná s kompilátorom, obsahuje šablónu pre triedu kontajnera množiny, ktorá implementuje funkčnosť množín:
šablóna <
kľúč triedy, vlastnosti triedy = menej, trieda Allocator = alokátor
triedna sada
Ako je zrejmé z výpisu, argumenty šablóny množiny sú: údajový typ prvkov množiny, typ funkčného objektu na určenie poradia prvkov v množine a typ alokátora pamäte.. V tomto prípade je potrebný iba prvý argument (ako ďalšie dva sa štandardne používa štandardný binárny predikát menej a štandardný alokátor).
Krok 3
Použite triedy alebo šablóny tried použité pri vývoji rámcov, ktoré implementujú funkčnosť práce so sadami, ak existujú. Príkladom takého nástroja je trieda šablón QSet modulu QtCore knižnice Qt. Jeho schopnosti sú podobné schopnostiam kontajnera súpravy STL opísaného v predchádzajúcom kroku.
Krok 4
Popíšte súpravu pomocou vlastných implementačných prostriedkov. Pre sady prvkov jednoduchých typov a malých veľkostí používajte bitové príznaky uložené v poliach s pevnou dĺžkou. Implementujte nastavenú triedu kontajnera pre komplexné dátové typy. Ako základ môžete vziať funkčnosť asociatívnych alebo hašovacích asociatívnych polí. Môže byť zase postavený na základe samovyvažujúcich binárnych vyhľadávacích stromov (napríklad červeno-čierne stromy).
