Množina

Množina (set) je abstraktní datová struktura, která obsahuje hodnoty, aniž by garatovala jejich pořadí. Jelikož se jedná se o implementaci matematického termínu množina, tak tato struktura obsahuje každý prvek vždy maximálně jednou. Podobnou strukturou, která však smí obsahovat daný prvek vícekrát, je multimnožina. Pro implementaci systému navzájem se nepřekrývajících podmnožin používáme datovou strukturu disjoint-set.

Implementace

Nejjednodušším způsobem implementace množiny je použít seznam, zapomenout na pořadí prvků a při vkládání vždy hlídat, aby se daný prvek neobjevil v množině vícekrát. Ač je tento postup přímočarý, tak je velice neefektivní, protože je pro vyhledání prvku nutné v krajním případě projít celou množinu (tj. asymptotická složitost O(n) ). Z tohoto důvodu se pro ukládání dat do množiny používá většinou hashovací tabulka (hash table), která zajistí přístup k jednotlivým prvkům průměrně v konstantním čase.

Kód

Java

 /**
  * Mnozina implementovana jako list
  * @author Pavel Micka
  * @param <ENTITY> typovy parametr obsahu
  */
 public class Set<ENTITY> {
     private List<ENTITY> list;
     /**
      * Konstruktor
      * @param initialCapacity kapacita, se kterou je inicializovan podrizeny seznam
      */
     public Set(int initialCapacity) {
         list = new ArrayList<ENTITY>(initialCapacity);
     }
 
     /**
      * Vlozi entitu do mnoziny
      * @param e entita
      * @return true - pokud probehne vlozeni uspesne, false pokud jiz mnozina
      * danou entitu obsahuje (dle equals())
      */
     public boolean put(ENTITY e) {
         if (list.contains(e)) return false;
         list.add(e);
         return true;
     }
 
     /**
      * Vrati nejaky prvek z mnoziny (a z mnoziny jej take odstrani)
      * @return prvek, null pokud je mnozina prazdna
      */
     public ENTITY pick() {
         if(list.size() == 0) return null;
         return list.remove(list.size() - 1);
     }
 
     /**
      * Odstrani z mnoziny danou entitu
      * @param e entita
      * @return true - pokud mnozina obsahovala danou entitu, false - pokud nikoliv
      */
     public boolean remove(ENTITY e) {
         return list.remove(e);
     }
 
     /**
      *
      * Dotaz na pritomnost dane entity
      * @param e entita
      * @return true - pokud jej mnozina obsahuje, false - pokud nikoliv
      */
     public boolean contains(ENTITY e) {
         return list.contains(e);
     }
     /**
      * Dotaz na velikost mnoziny
      * @return pocet prvku
      */
     public int size() {
         return list.size();
     }
 }

Implementace

Kód

Doporučujeme