*Implementacija s povezanim seznamom

# Ta modul vsebuje osnovne operacije za delo # s povezanim seznamom. # Ustvari in vrne prazen povezani seznam. def Ustvari(): return [[0, 0, 0]] # Vrne število elementov (vozlišč) pov. seznama. def SteviloElementov(povSeznam): return povSeznam[0][0] # Vrne indeks začetnega vozlišča pov. seznama. def IndeksZacetnega(povSeznam): return povSeznam[0][1] # Vrne indeks naslednika danega vozlišča. def IndeksNaslednika(povSeznam, indeks): return povSeznam[indeks][1] # Vrne indeks končnega vozlišča pov. seznama. def IndeksKoncnega(povSeznam): return povSeznam[0][2] # Vrne indeks predhodnika vozlišča # na podanem indeksu. def IndeksPredhodnika(povSeznam, indeks): return povSeznam[indeks][2] # Vrne element, ki ga hrani vozlišče # s podanim indeksom. def Element(povSeznam, indeks): return povSeznam[indeks][0] # Doda podani element na konec pov. seznama. def DodajNaKonec(povSeznam, element): # Ugotovimo indeks trenutnega končnega # vozlišča seznama. Po dodajanju bo to # vozlišče postalo prejšnje končno vozlišče. iPrejKoncnega = povSeznam[0][2] # Vozlišče dodamo na konec tabele. Dodano # vozlišče nima naslednika, njegov predhodnik # pa postane prejšnje končno vozlišče. iDodanega = len(povSeznam) povSeznam.append([element, 0, iPrejKoncnega]) # Dodano vozlišče postane naslednik prejšnjega # končnega vozlišča. povSeznam[iPrejKoncnega][1] = iDodanega # Dodano vozlišče postane tudi novo končno # vozlišče seznama. povSeznam[0][2] = iDodanega # Število elementov se poveča za 1. povSeznam[0][0] += 1 # Ustvari novo vozlišče s podanim elementom # in ga v seznam poveže tako, da vozlišče na # podanem indeksu postane njegov naslednik. def Vstavi(povSeznam, indeks, element): # Ugotovimo indeks naslednika in predhodnika # vozlišča, ki ga bomo dodali. iNasled = indeks iPredhod = povSeznam[indeks][2] # Vozlišče dodamo na konec tabele. iDodanega = len(povSeznam) povSeznam.append([element, iNasled, iPredhod]) # Vozlišče povežemo z njegovim predhodnikom # in naslednikom. povSeznam[iPredhod][1] = iDodanega povSeznam[iNasled][2] = iDodanega # Število elementov se poveča za 1. povSeznam[0][0] += 1 # Doda novo vozlišče s podanim elementom na # začetek povezanega seznama. def DodajNaZacetek(povSeznam, element): iZacetnega = IndeksZacetnega(povSeznam) Vstavi(povSeznam, iZacetnega, element) # Iz seznama izloči vozlišče s podanim indeksom. def Izloci(povSeznam, indeks): # Ugotovimo indeks naslednika in predhodnika # vozlišča, ki ga želimo odstraniti. iNasled = povSeznam[indeks][1] iPredhod = povSeznam[indeks][2] # "Obvozimo" vozlišče. povSeznam[iPredhod][1] = iNasled povSeznam[iNasled][2] = iPredhod # Število elementov se zmanjša za 1. povSeznam[0][0] -= 1 # Iz seznama izloči začetno vozlišče. def IzlociZacetnega(povSeznam): Izloci(povSeznam, IndeksZacetnega(povSeznam)) # Iz seznama izloči končno vozlišče. def IzlociKoncnega(povSeznam): Izloci(povSeznam, IndeksKoncnega(povSeznam)) # Pomožna funkcija, ki vrne tabelo z elementi # povezanega seznama, v kateri so elementi # zapisani po naraščajočih položajih. def Zaporedje(povSeznam): indeks = IndeksZacetnega(povSeznam) elementi = [] while indeks != 0: elementi.append(Element(povSeznam, indeks)) indeks = IndeksNaslednika(povSeznam, indeks) return elementi # Pomožna funkcija, ki vrne tabelo z elementi # povezanega seznama, v kateri so elementi # zapisani po padajočih položajih. def ZaporedjeNazaj(povSeznam): indeks = IndeksKoncnega(povSeznam) elementi = [] while indeks != 0: elementi.append(Element(povSeznam, indeks)) indeks = IndeksPredhodnika(povSeznam, indeks) return elementi # Pomožna funkcija, ki izpiše zgradbo podanega # povezanega seznama in zaporedje, ki ga seznam # predstavlja. Zaporedje se izpiše v obeh smereh # (od začetnega do končnega in od končnega do # začetnega elementa). def IzpisiVse(povSeznam): print(povSeznam) opis = 'Zaporedje od začetka do konca: ' print(opis + str(Zaporedje(povSeznam))) opis = 'Zaporedje od konca do začetka: ' print(opis + str(ZaporedjeNazaj(povSeznam))) # Ta funkcija se izvede, če datoteko poženemo # kot samostojen program. def main(): print('Ustvarimo novo zaporedje ...') # trenutno zaporedje bo: <> ps = Ustvari() IzpisiVse(ps) print('') print('Dodamo A na konec ...') # trenutno zaporedje bo: <'A'> DodajNaKonec(ps, 'A') IzpisiVse(ps) print('') print('Dodamo Z na začetek ...') # trenutno zaporedje bo: <'Z', 'A'> DodajNaZacetek(ps, 'Z') IzpisiVse(ps) print('') print('Dodamo M na začetek ...') # trenutno zaporedje bo: <'M', 'Z', 'A'> DodajNaZacetek(ps, 'M') IzpisiVse(ps) print('') print('Vstavimo I pred Z ...') # indeks vozlišča 'M' indeks = IndeksZacetnega(ps) # indeks vozlišča 'Z' indeks = IndeksNaslednika(ps, indeks) # trenutno zaporedje bo: <'M', 'I', 'Z', 'A'> Vstavi(ps, indeks, 'I') IzpisiVse(ps) print('') print('Vstavimo N pred A ...') # indeks vozlišča 'A' indeks = IndeksKoncnega(ps) # trenutno zaporedje bo: # <'M', 'I', 'Z', 'N', 'A'> Vstavi(ps, indeks, 'N') IzpisiVse(ps) print('') print('Izločimo N ...') # indeks vozlišča 'A' indeks = IndeksKoncnega(ps) # indeks vozlišča 'N' indeks = IndeksPredhodnika(ps, indeks) # trenutno zaporedje bo: <'M', 'I', 'Z', 'A'> Izloci(ps, indeks) IzpisiVse(ps) print('') print('Izločimo Z ...') # indeks vozlišča 'A' indeks = IndeksKoncnega(ps) # indeks vozlišča 'Z' indeks = IndeksPredhodnika(ps, indeks) # trenutno zaporedje bo: <'M', 'I', 'A'> Izloci(ps, indeks) IzpisiVse(ps) print('') print('Izločimo začetni element ...') # trenutno zaporedje bo: <'I', 'A'> IzlociZacetnega(ps) IzpisiVse(ps) print('') print('Izločimo končni element ...') # trenutno zaporedje bo: <'I'> IzlociKoncnega(ps) IzpisiVse(ps) print('') print('Izločimo začetni element ...') # trenutno zaporedje bo: <> IzlociZacetnega(ps) IzpisiVse(ps) if __name__ == '__main__': main()

Izvedi Počisti