Abstraktna podatkovna struktura množica (set)

Abstraktna podatkovna struktura množica (set)

Avtor: Tjaša Dragar

Opis podatkovne strukture

Množica je abstraktna podatkovna struktura (v nadaljevanju APS), ki lahko hrani podatke različnih tipov in ima dve osnovni lastnosti:

  • elementi množice so neurejeni (vrstni red elementov ni pomemben) in
  • ne vsebuje podvojenih elementov (vsak element se lahko v množici pojavi 0 ali 1-krat).

Primer množice:


Primeri uporabe množic:

  • seznam prijavljenih študentov na izpitu
  • seznam mojih prijateljev na socialnem omrežju Facebook
  • ponujene destinacije neke agencije za absolventski izlet...

Lastnosti APS množica ustrezajo matematični definiciji končne množice. Formalno je množica S končna, če za neko naravno število n obstaja bijektiva preslikava f: ->

Število n predstavlja moč množice S (število elementov v tej množici). Prazna množica, torej množica, ki ne vsebuje nobenega elementa, je končna množica, katere moč množice je enaka 0.

Primeri končnih množic:



(http://www2.nauk.si/files/335/venn.jpg)

Operacije

Za APS definiramo naslednje operacije:

  • naredi prazno množico
  • dodaj element v množico
  • odstrani element iz množice
  • velikost množice (št. elementov v njej)
  • množica vsebuje element

Opis osnovnih operacij

  • prazna: 0-> množica
    Naredimo novo, prazno množico.
  • dodaj: (množica, element) -> množica
    Že obstoječi množici dodamo element. Pri tem zaradi lastnosti množice ne dovoljujemo vstaviti element, ki je že v množici.
  • odstrani: (množica, element) -> množica
    Iz že obstoječe množice element odstranimo. Pri tem lahko naletimo na 2 težavi:
    -odstraniti želimo element, ki v množici sploh ne obstaja
    -množica je prazna
  • velikost: množica -> celo število (int)
    Dobimo celo število, ki predstavlja velikost množice (število elementov v njej).
  • vsebuje: (množica,element) -> {True, False}
    Dobimo bool vrednost True ali False, ki nam pove, ali je dani element v množici ali ne.

Implementacija

Obstaja veliko različnih implementacij APS množica. Najprej si bomo pogledali implementacijo s seznamom in prej definiranimi osnovnimi operacijami v programskem jeziku Python. (V Pythonu sicer obstaja tudi vgrajeni tip SET, ki se mu bomo posvetili kasneje.)

class Mnozica:

    def __init__(self):
        #konstruktor, ki ustvari novo (prazno) množico
        self.mnozica = []
    def velikost(self):
        #metoda vrne število elementov v množici
        return len(self.mnozica)
    def vsebuje (self,x):
        #metoda vrne True, če dani element v množici obstaja in False sicer
        if self.mnozica.count(x) == 0:
            return False
        else:
            return True
    def dodaj (self,x):
        #metoda doda element v množico (pod pogojem, da tega elementa še ni v množici)
        if self.vsebuje(x):
            raise ValueError('Podvajanje elementov ni mogoče.')
        self.mnozica.append(x)
    def odstrani (self,x):
        #metoda odstrani element iz množice
        if self.velikost() == 0:
            raise ValueError('Množica je prazna.')
        elif self.vsebuje(x) == False :
            raise ValueError('Tega elementa ni v množici.')
        else:
            self.mnozica.remove(x)

Program, ki vsebuje razred Mnozica s podrobnimi komentarji in testiranje ustreznosti implementacije: mnozica.py

Gradnja strukture

S pomočjo prej definirane implementacije strukture (ponovni ogled) , bomo zgradili primer APS množice, v kateri želimo, da so naslednji elementi: {1,3,5,7,9,...,49}.

V množico želimo dodati kar precej elementov, zaradi česar bi bilo nesmiselno, da bi za vsako dodajanje elementa napisali svoj ukaz. Namesto tega raje spišemo kratek python program, ki bo to naredil namesto nas:

from mnozica import *
#uvoz razreda mnozica, kjer de implementacija APS
mn = Mnozica()
#ustvarimo novo prazno množico
i=1
while i < 50:
    mn.dodaj(i)
    #dodajamo elemente
    i+=2

print(mn)
#izpis množice

Dobimo naslednji izpis:

{1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49}

Na tej množici izvedemo še ostale operacije:

velikost=mn.velikost()
print(velikost)
>>> 25
mn.odstrani(3)
print(mn)
>>>{1,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49}
mn.dodaj(51)
print(mn)
>>>1,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51}
b=mn.vsebuje(50)
print(b)
>>>False

Zgled uporabe

Dana je podatkovna struktura množica. Definiraj naslednji funkciji:

  • presek, ki za dani množici vrne novo množico, ki vsebuje elemente, ki so v obeh množicah
  • unija, ki za dani množici vrne novo množico, ki vsebuje elemente, ki so v vsaj eni izmed množic

1. korak

Če bomo želeli dostopati do posameznih elementov v množici, bomo najprej nekoliko spremenili prej definirano implementacijo množice. In sicer bomo dodali metodo vrniElement, ki bo vrnila element na nekem položaju. Rekli smo, da položaj elementa v množici ni pomemben, vendar ga bomo vseeno definirali, da bomo omogočili dostop do elementov.

     def vrniElement(self,p):
        #metoda vrne element, ki je na položaju p
        if p>= self.velikost():
            raise IndexError('Tega položaja ni v množici.')
        #v kolikor vnesemo prevelik položaj, se sproži napaka
        return self.mnozica[p]
        #sicer, pa vrnemo element množice na tem položaju
        #ker smo naredili implementacijo s seznamom, to naredimo s pomočjo indeksa elementa



Popravljen razred Mnozica:

mnozica.py

Zgled uporabe

2. korak

Funkcija presek:

  • za parameter dobi dve množici, vrne tudi množico - presek
  • najprej pogledamo velikosti obeh množic
  • izberemo manjšo od obeh množic in to pregledamo po elementih
  • za vsak element 1. množice, pa potem s pomočjo pred definirane metode vsebuje() preverimo še, če je tudi element 2. množice
  • v kolikor je zgornja trditev resnična, ta element dodamo v novo množico presek

Funkcija unija:

  • za parameter dobi dve množici, vrne tudi množico - unijo
  • najprej v unijo zapišemo kar vse elemente 1. množice
  • nato po elementih pregledamo 2. množico in v unijo dodamo le elemente, ki tam še niso
from mnozica import*

def presek (mn1, mn2):
    v1=mn1.velikost()
    v2=mn2.velikost()
    presek=Mnozica()

    if v1<v2:
        for i in range(v1):
            el=mn1.vrniElement(i)
            if mn2.vsebuje(el):
                presek.dodaj(el)

    else:
        for i in range(v2):
            el=mn2.vrniElement(i)
            if mn1.vsebuje(el):
                presek.dodaj(el)

    return presek

def unija (mn1,mn2):
    v1=mn1.velikost()
    v2=mn2.velikost()
    unija=Mnozica()

    for i in range(v1):
        el=mn1.vrniElement(i)
        unija.dodaj(el)

    for i in range(v2):
        el=mn2.vrniElement(i)
        if not unija.vsebuje(el):
            unija.dodaj(el)

    return unija


Koda za zgled uporabe

Implementacija v Python-u : SET

V Pythonu obstaja implementacija množice in sicer je to modul Set.
Le-ta omogoča ustvarjanje neurejenih zbirk unikatnih podatkov, kar pa sta ravno prej omenjeni lastnosti APS množice. Najpogosteje se uporablja za:

  • testiranje ali nek element je v zbirki podatkov
  • odstranjevanje podvojenih vnosov
  • matematične opracije na množicah: presek, unija, razlika in simetrična razlika

Ustvarjanje množice
V tej implementaciji ustvarjanje množice ni ločeno od dodajanja elementov, kar pomeni, da nam ni potrebno najprej ustvariti prazne množice, ampak jo lahko direktno napolnimo z elementi.

1. način: zaviti oklepaji

>>> mn = {1,2,3,7}
>>> print(mn)
{1, 2, 3, 7}

Kaj se zgodi, če želimo v množico dodati več enakih elementov?

>>> m={1,2,3,3,5,2}
>>> print(m)
{1, 2, 3, 5}

Podvojenih elementov v množici ni.

2. način: set()

>>> mn1=set('Računalništvo')
>>> print(mn1)
{'R', 'o', 't', 'u', 'v', 'i', 'l', 'č', 'n', 'š', 'a'}
>>> mn2=set([1,5,6,8,8])
>>> print(mn2)
{8, 1, 5, 6}

Ustvarjanje prazne množice je mogoče samo z 2. načinom in sicer: set(). Z ukazom {} pa bi dobili prazen slovar.

Implementacija v Python-u : SET

Testiranje ali nek element je v množici

Ukaza: x in mnozica, x not in mnozica

>>> studenti={'Sara','Miha','Nik','Anja'}
>>> 'Sara' in studenti
True
>>> 'Tjasa' in studenti
False

Unija množic

mnozica1| mnozica2 ALI mnozica1.union(mnozica2)

>>> mn2={7,9,11}
>>> mn1=set()
>>> unija=mn1|mn2
>>> print(unija)
{9, 11, 7}


>>> mn3=set('Zima')
>>> mn4=set('Poletje')
>>> mn3.union(mn4)
{'Z', 'P', 't', 'i', 'j', 'l', 'm', 'o', 'a', 'e'}

Presek množic

mnozica1& mnozica2 ALI mnozica1.intersection(mnozica2)

>>> mn1={1,3,5,7,8}
>>> mn2={1,2,3,4,5}
>>> mn1.intersection(mn2)
{1, 3, 5}
>>> mn1 & mn2
{1, 3, 5}

Implementacija v Python-u : SET

Razlika množic
Razlika dveh množic je množica, ki vsebuje elemente iz prve množice, ki niso v drugi množici.

mnozica1 - mnozica2 ALI mnozica1.difference(mnozica2)

>>> mn1={1,2,3,4,5,6,7,8,9,10}
>>> mn2={2,4,6,8,10}
>>> mn1-mn2
{1, 3, 9, 5, 7}

Simetrična razlika množic
Simetrična razlika dveh množic je množica, ki vsebuje elemente iz prve ali druge množice, vendar ti elementi niso v preseku obeh množic.

mnozica1 ^ mnozica2 ALI mnozica1.symetric_difference(mnozica2)

>>> mn1={1,2,3,4,5,6,7,8,9}
>>> mn2={2,4,5,6,7}
>>> mn1^mn2
{1, 3, 8, 9}

Ali drugače: to so elementi, ki so v uniji in niso v preseku, kar pomeni, da so to elementi razlike unije in preseka obeh množic.

>>> mn1={1,2,3,4,5,6,7,8,9,10}
>>> mn2={1,2,3,7,8,9,11,12,13}
>>> unija=mn1.union(mn2)
>>> presek=mn1.intersection(mn2)
>>> unija.difference(presek)
{4, 5, 6, 10, 11, 12, 13}
>>> mn1.symmetric_difference(mn2)
{4, 5, 6, 10, 11, 12, 13}

Implementacija v Python-u : SET

Ostale operacije:

  • len(s): vrne moč množice oz. število elementov v množici

    >>> mn=set()
    >>> len(mn)
    0
  • s.issubset(t) ali s <= t: ali je s podmnožica množice t, kar pomeni, da so vsi elementi množice s tudi v množici t

    >>> mn=set()
    >>> m={1,2}
    >>> mn.issubset(m)
    True
    >>> m.issubset(mn)
    False
  • s.copy():naredi kopijo množice s
  • s.update(t) ali s |= t: množici s smo dodali elemente iz t

    >>> a={1,3,5}
    >>> b={2,4,6}
    >>> a.update(b)
    >>> a
    {1, 2, 3, 4, 5, 6}
  • s.add(x): v množico s dodamo element x
  • s.remove(x):iz množice s odstranimo element x oz. sprožimo napako KeyError, če tega elementa ni
  • s.discard(x):iz množice s odstranimo element x, v kolikor je le-ta v množici s
  • s.pop():odstranimo in vrnemo nek element iz množice s. Če je množica prazna sprožimo napako.

    >>> m={1,2,3,4,5,6,7,8}
    >>> m.pop()
    1
    >>> m
    {2, 3, 4, 5, 6, 7, 8}
  • s.clear():odstranimo vse elemente iz množice s

Viri

Tiskani viri

Kononenko I., Robnik Šikonja M.: Algoritmi in podatkovne strukture I, Založba FE in FRI, Ljubljana 2003.

Spletni viri

http://en.wikipedia.org/wiki/Finite_set

http://web.cs.wpi.edu/~cs2102/common/kathi-notes/sets.html

http://en.wikipedia.org/wiki/Set_(computer_science)

http://docs.python.org/2/library/sets.html

0%
0%