Jedním z typů datových struktur, které jsou přímým ztělesněním matematických entit v informatice, jsou sady. Operace s nimi často tvoří základ různých algoritmů. Různé programovací jazyky mají své vlastní prostředky pro popis množin.
Nezbytné
- - vývojové prostředí;
- - překladač z vybraného programovacího jazyka.
Instrukce
Krok 1
Popište sadu pomocí programovacího jazyka, pokud je k dispozici. Například v jazyce Pascal existuje konstrukt sady, který umožňuje deklarovat odpovídající typy. Je pravda, že objem těchto sad by neměl překročit 256 prvků. Příklad deklarací typu sady může vypadat takto:
typ
AZLetters = sada 'A'.. 'Z';
AllLetters = sada znaků;
Proměnné a konstanty typů, které jsou množinami, jsou deklarovány obvyklým způsobem. V tomto případě lze pro inicializaci použít setové literály. Například:
konst
LettersSet1: AZLetters = ['A', 'B', 'C'];
Krok 2
K popisu sad použijte funkce standardních knihoven nebo modulů. Knihovna šablon C ++, která by měla být dodána s kompilátorem, obsahuje šablonu pro třídu kontejneru sady, která implementuje funkce sad:
šablona <
klíč třídy, vlastnosti třídy = méně, třída Allocator = alokátor
sada tříd
Jak vidíte ze seznamu, argumenty šablony sady jsou: datový typ prvků sady, typ funkčního objektu k určení pořadí prvků v sadě a typ alokátoru paměti. V tomto případě je vyžadován pouze první argument (jako ostatní dva jsou standardně použity standardní binární predikáty méně a standardní alokátor).
Krok 3
Aplikujte třídy nebo šablony tříd používané při vývoji architektur, které implementují funkce práce se sadami, pokud existují. Příkladem takového nástroje je třída šablony QSet modulu QtCore knihovny Qt. Jeho funkce jsou podobné jako u kontejneru sady STL popsaného v předchozím kroku.
Krok 4
Popište sadu pomocí vlastních implementačních prostředků. Pro sady prvků jednoduchých typů a malých velikostí použijte bitové příznaky uložené v polích s pevnou délkou. Implementujte třídu sady kontejnerů pro komplexní datové typy. Jako základ můžete vzít funkčnost asociativních nebo hašovacích asociativních polí. Na druhé straně jej lze postavit na základě samovyvažovacích binárních vyhledávacích stromů (například červeno-černé stromy).
