Množina je v informatice abstraktní datový typ, který je schopen uložit určité hodnoty bez jakéhokoliv pořadí a bez opakujících se hodnot. Je to počítačová implementace matematického konceptu konečné množiny. Na rozdíl od jiných datových struktur se množina používá spíše pro testování, zdali se konkrétní hodnota nachází v množině dat, nežli pro získávání specifických prvků z množiny.
Některé množiny jsou navrženy jako statické a s jejich vytvořením se žádné prvky už dále nepřidávají ani neodebírají. Statické množiny umožňují pouze operace dotazů na jejich prvky (např. zjištění, zdali se nachází daná hodnota v množině nebo pro výčet hodnot v libovolném pořadí). Jinou variantou množin mohou být množiny dynamické, které oproti statickým umožňují i operace vkládání a odebírání prvků.
Operace
Statické množiny Typické operace, které mohou být prováděny se statickou množinou S, jsou: is_element_of(x,S): Zkontroluje, zdali je hodnota x v množině S. is_empty(S): Zkontroluje, zdali je množina S prázdná. size(S) or cardinality(S): Vrátí počet prvků množiny S. iterate(S): Vrátí funkci, která vrátí další hodnotu množiny S při každém volání a to v libovolném pořadí. enumerate(S): Provede výčet hodnot množiny S v libovolném pořádí. build(x1,x2,...,xn): Vytvoří množinu s hodnotami x1,x2,…,xn. create_from(collection): Vytvoří novou množinu obsahující všechny prvky dané kolekce.
Dynamické množiny Dynamické množiny navíc typicky obsahují: create(): Vytvoří novou a prázdnou množinu. create_with_capacity(n): Vytvoří novou množinu se schopností uchovat n prvků. add(S,x): Přidá prvek x do S, pokud ještě neexistuje. remove(S, x): odebere prvek x z S, pokud existuje. capacity(S): Vrátí číslo reprezentující maximální počet prvků, které je schopna množina uchovat.
Logické operace s množinami Je možné provádět s množinami základní logické operace. union(S,T): Vrátí sjednocenou množinu S a T. intersection(S,T): Vrátí průnik množin S a T. difference(S,T): Vrátí rozdíl množin S a T. subset(S,T): Testuje, zda je množina S podmnožinou množiny T.
Implementace Množiny mohou být implementovány pomocí nejrůznějších datových struktur, které poskytují kompromis mezi časem (rychlost provádění operací) a místem (paměťová náročnost). Některé implementace jsou navrženy tak, aby zajistily efektivitu při vykonávání speciálních operací, jako jsou například nearest nebo union. Implementace popsané jako "běžné použití" typicky usilují o optimalizaci operací element_of, add a delete.
Odkazy
Reference
Související články Zásobník (datová struktura) Fronta (datová struktura)
Kategorie:Datové struktury