Č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}'
.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
.