Implementacije

Če želimo množico implementirati (zapisati) v računalniku, moramo najprej poiskati način za hranjenje njenih elementov. Elemente lahko hranimo kar v tabeli, a bomo videli, da to ni edina možnost. Nato se moramo vprašati, kaj bi radi z množico počeli. Ukvarjali se bomo predvsem z najosnovnejšimi operacijami: preverjanje prisotnosti podanega elementa, dodajanje posameznih elementov (pri tem moramo paziti, da se nam v množici ne pojavijo podvojeni elementi) in odstranjevanje posameznih elementov. Ogledali si bomo tri podatkovne strukture za implementacijo množice, ki se med seboj po učinkovitosti posameznih operacij kar precej razlikujejo. Četrto možno implementacijo – razpršilno tabelo – si bomo ogledali v naslednji učni enoti.

Operacije na množici bomo implementirali kot naslednje funkcije:

Ustvari(): Vrne prazno množico.
JePrisoten(mnozica, element): Če podani element pripada podani množici, vrne True, sicer pa vrne False.
Dodaj(mnozica, element): Doda podani element v podano množico.
Odstrani(mnozica, element): Odstrani podani element iz množice, če obstaja. V nasprotnem primeru se ne zgodi nič.
NizElementov(mnozica): Vrne niz, ki med zavitima oklepajema vsebuje elemente podane množice, ločene z vejicami. Na primer: '{1, 2, 3}'.

Implementacija s tabelo elementov

Množico lahko implementiramo tako, da njene elemente hranimo v tabeli. Ker vrstni red elementov v množici ni pomemben, lahko elemente v tabeli hranimo v poljubnem vrstnem redu. Prisotnost elementa preverimo tako, da se sprehodimo po tabeli in vrnemo True, če naletimo na iskani element. Dodajanje elementa v množico pa lahko implementiramo kar kot dodajanje na konec tabele, vendar pa moramo pred tem še preveriti, ali element v množici že obstaja. Zapišimo funkcije v modul mnozicaTabelaElementov.py (glej kodo na desni).

Implementacija množice s tabelo je enostavna, a neučinkovita. Zaradi sprehoda po tabeli imajo operacije JePrisoten, Dodaj in Odstrani časovno zahtevnost O(n), pri čemer je n število elementov v množici. Dodajanje elementa na konec tabele je sicer učinkovito, vendar pa operacija Dodaj zaradi predhodnega preverjanja prisotnosti ni nič manj časovno neučinkovita od funkcije JePrisoten.

# Implementacija množice s tabelo elementov # Vrne prazno množico. def Ustvari(): return [] # Vrne True, če je podani element prisoten v # podani množici, sicer pa vrne False. def JePrisoten(mnozica, element): for x in mnozica: if x == element: return True return False # Doda podani element v podano množico. def Dodaj(mnozica, element): if not JePrisoten(mnozica, element): mnozica.append(element) # Odstrani podani element iz podane množice. def Odstrani(mnozica, element): if JePrisoten(mnozica, element): mnozica.remove(element) # Vrne niz, ki predstavlja podano množico; # npr. '{1, 2, 3}' za množico, ki vsebuje # elemente 1, 2 in 3. def NizElementov(mnozica): # Med sprehodom po tabeli elemente pretvarjamo # v nize in nastale nize dodajamo v tabelo. izpis = [] for element in mnozica: izpis.append(str(element)) # Združimo nize iz tabele # (npr. ['a', 'b', 'c'] --> '{a, b, c}'). return ('{' + ', '.join(izpis) + '}') # Ta funkcija se pokliče, če modul uporabimo # kot samostojen program. Funkcija preizkusi # delovanje posameznih funkcij modula. def main(): t = [5, 2, 5, 5, 1, 6, 8, 3, 2, 3] print('Ustvarjam prazno množico m ...') m = Ustvari() for element in t: print('Dodajam element: ' + str(element)) Dodaj(m, element) print('Množica m: ' + NizElementov(m)) print('JePrisoten(m, 3): ' + str(JePrisoten(m, 3))) print('JePrisoten(m, 5): ' + str(JePrisoten(m, 5))) print('JePrisoten(m, 6): ' + str(JePrisoten(m, 6))) print('JePrisoten(m, 7): ' + str(JePrisoten(m, 7))) print('Odstranjujem element: 3') Odstrani(m, 3) print('JePrisoten(m, 3): ' + str(JePrisoten(m, 3))) print('Množica m: ' + NizElementov(m)) # Spomnimo se: s spodnjima vrsticama dosežemo, # da lahko modul uporabljamo tudi kot samostojen # program. if __name__ == '__main__': main()

Izvedi Počisti