Cesko.wiki Množina (datová struktura)
Author
Albert FloresMnož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ř. +more 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á. +more * 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ů. +more * 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. +more * 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. +more Implementace popsané jako "běžné použití" typicky usilují o optimalizaci operací element_of, add a delete.