- Enostavni enojno povezani VS
- Enojno povezani VS z začetkom in koncem
- Dvojno povezani VS z začetkom
- Dvojno povezani VS z začetkom in koncem
Verižni seznam kot PS
Verižni seznam kot PS
Matija Lokar
Več različnih PS
Seznami – enostavni VS
Enostavni verižni seznam
- Poznamo le kazalec na prvi element
Enojno povezan z začetkom in koncem
- Poznamo kazalec na prvi in zadnji element
Dvojno povezani VS
- Vozel ima reference naprej in nazaj
- Poznamo kazalec na prvi element
Dvojno povezani VS
- Poznamo kazalec na prvi in zadnji element
Razred Verižni seznam
class VerSez:
# lastnost prvi - referenca na prvi element (Vozel) seznama
# konstruktor
# metode:
# vstaviPrvega ... vstavi nov podatek kot prvi vozel v verigi
# nastaviPrvega ... spremeni ver. seznam tako, da je sedaj
tak z novim prvim vozlom
# vrniPrviVozel ... vrni referenco na prvi vozel VS
# zbrišiPrvega ... odstrani prvi vozel iz verige – VS dobi
novega prvega (ali pa bo prazen)
# vrniPrvoVrednost ... vrni podatek v prvem vozlu VS
# izpisi ... pregledno izpiši VS
# jePrazen ... True/False
# lastnost prvi - referenca na prvi element (Vozel) seznama
# konstruktor
# metode:
# vstaviPrvega ... vstavi nov podatek kot prvi vozel v verigi
# nastaviPrvega ... spremeni ver. seznam tako, da je sedaj
tak z novim prvim vozlom
# vrniPrviVozel ... vrni referenco na prvi vozel VS
# zbrišiPrvega ... odstrani prvi vozel iz verige – VS dobi
novega prvega (ali pa bo prazen)
# vrniPrvoVrednost ... vrni podatek v prvem vozlu VS
# izpisi ... pregledno izpiši VS
# jePrazen ... True/False
Enojno povezani verižni seznam – funkcije
- poišči element
- preštej
- dodaj za element
- dodaj spredaj
- dodaj zadaj
- briši
Izpiši
- izpiši podatek, na katerega kaže kazalec na začetek seznama
- prestavi kazalec na naslednjega
Izpiši
izpiši ()
def izpiši(self) :
'''izpise vsebino verižnega seznama a'''
pom = self.prvi # dobimo kazalec na prvi vozel verige
while pom != None :
print(pom.vrniPodatek(), sep = ' -> ')
pom = pom.vrniNaslednjega()
print('|||')
Vozel in Verižni seznam
VerSez - konstruktor
def __init__(self, t = None) :
if t == None :
self.prvi = None # prazen v. sez.
return
# vstavimo vse elemente iz t v ver. seznam
self.prvi = Vozel(t[0]) # imamo prvega v verigi
konec = self.prvi # hkrati je zanekrat tudi zadnji
for i in range(1, len(t)) :
# vstavljamo na konec
novV = Vozel(t[i])
konec.nastaviNasled(novV)
konec = novV
if t == None :
self.prvi = None # prazen v. sez.
return
# vstavimo vse elemente iz t v ver. seznam
self.prvi = Vozel(t[0]) # imamo prvega v verigi
konec = self.prvi # hkrati je zanekrat tudi zadnji
for i in range(1, len(t)) :
# vstavljamo na konec
novV = Vozel(t[i])
konec.nastaviNasled(novV)
konec = novV
vstaviPrvega(x)
def vstaviPrvega(self, x) :
v = Vozel(x, self.prvi)
# referenca vozla v pokaže na dosedaj prvega v v.s.
self.prvi = v; # novi prvi element
v = Vozel(x, self.prvi)
# referenca vozla v pokaže na dosedaj prvega v v.s.
self.prvi = v; # novi prvi element
vstaviPrvega
- Ali dela prav na vsakem verižnem seznamu?
- Kaj pa, če je VS prazen?
vstaviPrvega(x)
nastaviPrvega
metoda nastaviPrvega
nastaviPrvega
def nastaviPrvega(self, v) :
'''spremeni VS tako,da je sedaj v njem
veriga z začetkom na katerega kaže v
'''
self.prvi = v; # novi prvi element
Prazen
metoda prazen
Je prazen?
- Pogledamo, če kazalec na prvega kaže v prazno
def prazen(self) :
return self.prvi == None
return self.prvi == None
Vrni prvi vozel
vrniPrviVozel
vrniPrviVozel
- Referenca na prvi element VS
def vrniPrviVozel(self) :
return self.prvi
return self.prvi
Vrni prvo vrednost
metoda vrniPrvoVrednost
Vrednost prvega
- Vrnemo podatek iz vozla, na katerega kaže prvi
def vrniPrvoVrednost(self) :
if self.jePrazen() : # ali self.prvi == None
raise Exception('vrniPrvoVrednost : seznam je prazen')
# seznam ni prazen
return self.prvi.vrniPodatek()
if self.jePrazen() : # ali self.prvi == None
raise Exception('vrniPrvoVrednost : seznam je prazen')
# seznam ni prazen
return self.prvi.vrniPodatek()
Zbriši prvega
metoda zbrisiPrvega
zbrisiPrvega()
- Če je seznam prazen - izjema
- Prvi naj pokaže tam, kamor kaže naslednji prvega!
- Preverimo: kaj, če je v seznamu le en element – bomo dobili prazen seznam?
def zbrisiPrvega(self) :
if self.jePrazen() :
raise Exception('zbrisiPrvega : seznam je prazen')
# seznam ni prazen
# prvi pokaže tja, kamor kaže naslednik
self.prvi = self.prvi.vrniNasled()
# ali self.nastaviPrvega(self.prvi.vrniNasled())
# ali
# zac = self.vrniPrviVozel()
# nas = zac.vrniNasled()
# self.nastaviPrvega(nas)
if self.jePrazen() :
raise Exception('zbrisiPrvega : seznam je prazen')
# seznam ni prazen
# prvi pokaže tja, kamor kaže naslednik
self.prvi = self.prvi.vrniNasled()
# ali self.nastaviPrvega(self.prvi.vrniNasled())
# ali
# zac = self.vrniPrviVozel()
# nas = zac.vrniNasled()
# self.nastaviPrvega(nas)
- Več različnih PS
- Seznami – enostavni VS
- Enojno povezan z začetkom in koncem
- Dvojno povezani VS
- Dvojno povezani VS
- Razred Verižni seznam
- Enojno povezani verižni seznam – funkcije
- Izpiši
- Izpiši
- izpiši ()
- Vozel in Verižni seznam
- VerSez - konstruktor
- vstaviPrvega(x)
- vstaviPrvega
- vstaviPrvega(x)
- nastaviPrvega
- nastaviPrvega
- Prazen
- Je prazen?
- Vrni prvi vozel
- vrniPrviVozel
- Vrni prvo vrednost
- Vrednost prvega
- Zbriši prvega
- zbrisiPrvega()
