Bc. Vojtěch Hordějčuk

„Píšu jak rozzuřený hokynář.” - J. Hurt

Domů » Wiki » Datové struktury » Množina (datová struktura)

Množina (datová struktura)

Množina je datová struktura, pomocí které lze v programech modelovat libovolně velkou kolekci vzájemně odlišitelných prvků, přičemž každý z prvků může být v množině zastoupen nejvýše jednou. Proto je třeba definovat funkci identity, která pro každou dvojici prvků určí, zda jsou identické, či nikoliv.

Prvky v množině nemají definované pořadí, takže by jej měla každá implementace „skrýt“ před vnějším pozorovatelem, např. vyšší vrstvou programu nebo uživatelem třídy.

Operace

  • JePrázdná() (empty) – zjisti, zda je množina prázdná
  • Vložit() (add) – vlož prvek do množiny, pokud se tam již nenachází
  • Odebrat() (remove) – odeber prvek do množiny, pokud se tam nachází
  • Obsahuje() (contains) – zjisti, zda množina obsahuje daný prvek

Implementace

Množinu lze implementovat jako obyčejné pole nebo seznam, ke kterému je nutné naimplementovat pomocnou funkci Obsahuje(). Nejjednodušší varianta této operace má lineární asymptotickou složitost (projdi všechny prvky a zkontroluj identitu hledaného prvku s každým z nich), ale použitím tzv. rozptylování (hashování) může asymptotická složitost klesnout až na konstantu.

Následující implementace je realizovaná v jazyce Java, využívá obousměrný seznam a generické typy, takže je univerzální. K provozu nevyžaduje žádné další knihovny.

/**
 * Implementace množiny s neomezenou velikostí.
 * Implementována pomocí obousměrně zřetězeného seznamu.
 * @param <E> třída elementu množiny
 * @author Vojtěch Hordějčuk
 */
public class Set<E>
{
  /**
   * Pomocná třída obalující jeden element množiny.
   * Jedná se o prvek obousměrně zřetězeného seznamu.
   * @param <E> třída elementu množiny
   */
  final protected class Element<E>
  {
    /**
     * přiřazený element
     */
    public E element = null;
    /**
     * předchozí prvek
     */
    public Element<E> prev = null;
    /**
     * následující prvek
     */
    public Element<E> next = null;
  }

  /**
   * ukazatel na první prvek seznamu
   */
  private Element<E> head;
  /**
   * ukazatel na poslední prvek seznamu
   */
  private Element<E> tail;

  /**
   * Vytvoří novou instanci množiny.
   */
  public Set ()
  {
    this.head = null;
    this.tail = null;
  }

  /**
   * Zjistí, zda množina obsahuje zadaný element.
   * @param element hledaný element
   * @return TRUE právě když se element nachází v množině
   */
  public boolean contains (E element)
  {
    // vyhledat prvek v seznamu

    Element<E> temp = this.head;

    while (temp != null)
    {
      // zkontrolovat identitu prvku
      // (prvky musí korektně implementovat metody "hashCode" a "equals")

      if (temp.element.hashCode () != element.hashCode ())
      {
        continue;
      }

      if (temp.element.equals (element))
      {
        return true;
      }

      // postoupit na další prvek

      temp = temp.next;
    }

    return false;
  }

  /**
   * Vloží element do množiny.
   * @param element vkládaný element
   */
  public void put (E element)
  {
    if ( ! this.contains (element))
    {
      // vytvořit novou položku seznamu

      final Element<E> fresh = new Element<E> ();

      fresh.element = element;
      fresh.prev = this.tail;
      fresh.next = null;

      // vložit položku na konec seznamu

      if (this.head == null)
      {
        // seznam je prázdný, nový prvek bude první i poslední

        this.head = fresh;
        this.tail = fresh;
      }
      else
      {
        // vložit na konec seznamu a posunout konec

        this.tail.next = fresh;
        this.tail = fresh;
      }
    }
  }

  /**
   * Odstraní element z množiny.
   * @param element odstraňovaný element
   */
  public void remove (E element)
  {
    // vyhledat prvek v seznamu

    Element<E> temp = this.head;

    while (temp != null)
    {
      // zkontrolovat identitu prvku
      // (prvky musí korektně implementovat metody "hashCode" a "equals")

      if (temp.element.hashCode () != element.hashCode ())
      {
        continue;
      }

      if (temp.element.equals (element))
      {
        // upravit ukazatele okolních prvků
        // (prvek bude vymazán JVM proto, že na něj nebude nic ukazovat)

        if (temp.prev == null)
        {
          if (temp.next == null)
          {
            // maže se jediný prvek

            this.head = null;
            this.tail = null;
          }
          else
          {
            // maže se první prvek

            temp.next.prev = null;
            this.head = temp.next;
          }
        }
        else
        {
          if (temp.next == null)
          {
            // maže se poslední prvek

            temp.prev.next = null;
            this.tail = temp.prev;
          }
          else
          {
            // maže se prostřední prvek

            temp.prev.next = temp.next;
            temp.next.prev = temp.prev;
          }
        }

        // operace dokončena

        return;
      }

      // postoupit na další prvek

      temp = temp.next;
    }
  }

  /**
   * Zjistí, zda je množina prázdná.
   * @return TRUE právě když je množina prázdná.
   */
  public boolean isEmpty ()
  {
    return (this.head == null);
  }

  @Override
  public String toString ()
  {
    // vytvořit textovou reprezentaci

    final StringBuffer buffer = new StringBuffer ();

    // projít seznam

    Element<E> temp = this.head;

    while (temp != null)
    {
      buffer.append (temp.element.toString () + " ");
      temp = temp.next;
    }

    // přidat závorky a vrátit výsledek

    return "{" + buffer.toString ().trim () + "}";
  }
}

zdrojový kód (Java) - zobrazit (4258 znaků)

Příklad

Operace Prvky množiny po jejím dokončení
Vložit(Pepa) {Pepa}
Vložit(Markéta) {Pepa, Markéta}
Vložit(Pepa) {Pepa, Markéta}
Odebrat(Igor) {Pepa, Markéta}
Odebrat(Markéta) {Pepa}