*Implementacija s povezanim seznamom

Vaja

Ustvari nov pythonov program in v njem uvozi modul povezaniSeznam.py (glej spodaj). V programu napiši in preizkusi funkcijo Poisci(povSeznam, element), ki vrne indeks prvega vozlišča, ki vsebuje podani element. »Prvo vozlišče« pomeni vozlišče z najmanjšim položajem, ne z najmanjšim indeksom. Če elementa v seznamu ni, naj funkcija vrne vrednost −1.

import povezaniSeznam as sez # Vrne indeks prvega vozlišča, ki vsebuje # podani element. def Poisci(povSeznam, element): pass # Preizkusimo funkcijo. ps = sez.Ustvari() print('Povezani seznam za zaporedje KARTA') sez.DodajNaZacetek(ps, 'T') sez.DodajNaKonec(ps, 'A') sez.DodajNaZacetek(ps, 'R') sez.DodajNaZacetek(ps, 'A') sez.DodajNaZacetek(ps, 'K') sez.IzpisiVse(ps) indeks = Poisci(ps, 'A') if indeks >= 0: print('Indeks prvega vozlišča z elementom A: ' + str(indeks)) else: print('Vozlišče z elementom A ne obstaja.') print('') print('Izločimo prvo vozlišče z elementom A ...') sez.Izloci(ps, indeks) sez.IzpisiVse(ps) indeks = Poisci(ps, 'A') if indeks >= 0: print('Indeks prvega vozlišča z elementom A: ' + str(indeks)) else: print('Vozlišče z elementom A ne obstaja.') print('') print('Izločimo še edino vozlišče z elementom A ...') sez.Izloci(ps, indeks) sez.IzpisiVse(ps) indeks = Poisci(ps, 'A') if indeks >= 0: print('Indeks prvega vozlišča z elementom A: ' + str(indeks)) else: print('Vozlišče z elementom A ne obstaja.')

Izvedi Počisti Namig Rešitev

Vaja

Pomanjkljivost naše predstavitve povezanega seznama je v tem, da pri izločanju elementov v tabeli vozlišč nastajajo luknje (izločena vozlišča), ki jih nikoli ne zapolnimo, saj nova vozlišča vedno dodajamo na konec tabele vozlišč. Na ta način bi nam lahko dolgoročno zmanjkalo pomnilniškega prostora, četudi bi seznam vseboval razmeroma malo elementov. Napiši in preizkusi modul varcenPovezaniSeznam.py, ki povezani seznam implementira tako, da novo vozlišče vedno zapolni eno od lukenj, na konec tabele pa se doda, samo če tabela vozlišč ne vsebuje nobene luknje.