V-Seznam

Iz MaFiRaWiki


Vsebina

Kaj je VSeznam?

VSeznam je enojno povezan seznam, katerega elementi so tabele.

Lastnosti VSeznama

Nekaj glavnih operacij VSeznama in njihove časovne zahtevnosti :

  • iskanje k-tega elementa po vrsti v VSeznamu
    Časovna zahtevnost: v povrečju O(1), v najslabšem primeru O(log2(n))
  • dodajanje elementa na začetek VSeznama
    Časovna zahtevnost: O(1)
  • brisanje prvega elementa (oz. nov VSeznam, ki se začne pri drugem elementu prvotnega VSeznama)
    Časovna zahtevnost: O(1)
  • dolžina VSeznama
    Časovna zahtevnost: O(log2(n))

Kako je VSeznam implementiran (struktura)

VSeznam je seznam, ki ga sestavljajo elementi (tipa int) posameznih, med seboj povezanih vozlov. (v svoji implementaciji sem vozle VSeznama poimenovala Tabela). Seznam je enojno povezan, njegovi elementi so torej Tabele. Elementi shranjeni v teh posameznih Tabelah so seveda poljubni, medtem ko je velikost tabel (tabela je spremenljivka objekta Tabela, kjer hranimo podatke) točno določena. Časovne zahtevnosti za iskanje k-tega elementa po vrsti in računanje dolžine VSeznama namreč izhajajo iz dejstva, da se dolžine Tabel manjšajo geometrično. To pomeni, da če je prva Tabela dolžine n, je potem naslednja Tabela le še dolžine n/2.(v resnici gledamo dolžino table znotraj Tabel, kjer hranimo podatke). Naslednjica te Tabele je tako le še dolzine (n/2)/2, torej n/4 itd.

Splošna implementacija

Pomagamo si z dodatnimi kazalci. Kot že vemo, se pri enojno povezanem seznamu v vsakem njegovem elementu (oz. vozlu) nahaja kazalec na naslednji element. Tako se posamezni elementi povezujejo v celoto, na katere prvi element kaže kazalec našega seznama. Pri VSeznamu pa bi želeli spreminjati njegove vozle (Tabele). To storimo tako, da Tabele opremimo z dodatnim kazalcem, ki kaže na prvi elemnt v tabeli (spremenljivka dane Tabele), od koder naprej želimo nadaljnje elemente vključiti v VSeznam. Tako lahko le s premikanjem tega kazalca v posamezni Tabeli odstanjujemo/dodajamo nove elemente.

Primer VSeznama

Slika:slikaVSeznam2.jpg

Osnove moje implementacije

  • Vozli oz. elementi VSeznama (razred Tabela)

Vozle VSeznama sem poimenovala Tabela. Vsebujejo naslednje spremenljivke:

  • private int[] tab - tabela, ki hrani števila
  • private Tabela naslednjaTabela - kaže na naslednjo Tabelo
  • private int zacetek - pove, kje se v dani tabeli tab začne del VSeznama (vijolične puščice na slikah)

Opomba: Elemente v Tabelah štejemo od 1 naprej.

Primer m-te Tabele VSeznama
Slika:primerVSeznam.jpg
Opomba1: Tabele indeksiramo od 1 naprej, torej je prva tabela tista, na katero kaže VSeznam.

Opomba2: Elementi v m-ti Tabeli se štejejo od vijolične puščice naprej, vključno z elementom na katerega kaže vijolična puščica. "Naprej" je na mojih slikah definiran kot od zgoraj navzdol.

  • Razred VSeznam

Razred VSeznam vsebuje spremenljivko:

  • private Tabela prva - objekt tipa Tabela

Primer VSeznama:
Slika:slikaVSeznam2.jpg

Operacije

  • Dodajanje elementa na začetek VSeznama

Pri dodajanju elementa na začetek VSeznama ločimo dve možnosti. Če je v prvi Tabeli (oz. vozlu) še prostor, potem element dodamo v tabelo Tabele na mesto, ki je pred mestom prvega elementa v tej Tabeli. Lahko pa se zgodi, da je naša prva Tabela že zapolnjena. V tem primeru ustvarimo Tabelo, ki je dvakrat večja od naše trenutne prve Tabele. V novo tabelo vstavimo element, ki ga želimo dodati na prvo mesto. Nato pa prevežemo Tabele tako, da je sedaj nova Tabela prva tabela VSeznama in kaže na našo prejšnjo prvo Tabelo. Dosegli smo, da je element, ki ga vstavljamo sedaj na prvem mestu VSeznama in vsebuje vse nadaljnje elemente prvotnega VSeznama v enakem vrstnem redu.

  • Primer

Imejmo prikazani VSeznam {-3,6,7,2,1}.
Slika:primer.jpg
Želimo dodati element 13 na zacetek našega VSeznama. Iz slike lahko vidimo, da je v prvi Tabeli še eno nezasedeno mesto, in sicer mesto, kjer je element 5. (VSeznam je implementiran tako, da postavi element na mesto ne glede ali je na mestu tabele že kakšen element, zato nam element 5 ne povzroča težav). Vstavimo element 13 na mesto, kjer je element 5 in prestavimo naso puščico (v implementaciji kazalec) eno mesto navzgor. Tako smo dobili VSeznam {13,-3,6,7,2,1}.
Slika:vstaviNaZacetek1.jpg
Vstavimo sedaj v VSeznam {13,-3,6,7,2,1} še element 9 na prvo mesto. Sedaj bo potrebno ustvariti novo Tabelo in ustrezno prevezati prvo in novo Tabelo, kot opisano zgoraj:
Slika:vstaviNaZacetek2.jpg

  • Brisanje prvega elementa (oz. VSeznam, ki se začne pri drugem elementu prvotnega VSeznama)

Operacija od nas zahteva, da izbrišemo prvi element VSeznama. Spet ločimo dve možnosti glede na to, ali je prvi element v prvi Tabeli edini element v Tabeli, ali nam po izbrisu ostane se kakšen element.

  • Primer

Vzemimo zopet naš VSeznam {-3,6,7,2,1}.
Slika:primer.jpg
Želimo izbrisati prvi element, ki je v našem primeru -3. Element ni na zadnjem mestu Tabele, zato je dovolj, da za izbris le premaknemo kazalec na prvi element v prvi Tabeli za ena naprej, torej na 6: Slika:brisanje_prvi.jpg
Dobili smo VSeznam {6,7,2,1}. Če bi operacijo uporabili šeenkart bi dobili VSeznam {7,2,1}. Ponovno brisaje prvega elementa v tem VSeznamu, pa ne zahteva premikanja kazalca, ampak za izbris le odstranimo prvo Tabelo iz VSeznama in za novo prvo Tabelo nastavimo tisto Tabelo, na katero kaže naša prvotna prva Tabela.
Izbrišimo prvi element VSeznama {7,2,1}:
Slika:brisanje_prvi2.jpg
Dobili smo nov VSeznam {2,1}.

  • Iskanje k-tega elementa po vrsti

K-ti element poiščemo z primerjanjem velikosti Tabel in indeksa k. Začnemo pri prvi Tabeli in primerjamo velikost. Če je k<= velikosti prve Tabele (tukaj je seveda mišljena velikost množice elementov, ki so vključeni v VSeznam. Kot že omenjeno, množice elementov od vijolične puščice dalje),potem se naš k-ti element po velikosti nahaja kar v prvi tabeli. Označimo velikost prve Tabele z m. Torej če je k večji od velikosti prve Tabele, pa se s kazalcem pomaknemo v naslednjo tabelo VSeznama in tam poskušamo poiskati (k-m)-ti element. Nadaljujemo po tem pravilu, dokler ne pridemo do Tabele v katerem se k-ti element res nahaja.

  • Primer:Imamo zopet naš VSeznam {-3,6,7,2,1}. Recimo, da iščemo 5-ti element po vrsti. (elemente štejemo od 1 naprej)

Slika:primer.jpg
Pogledamo torej velikost prve Tabele. Velikost je 3 in je manjša od 5. Torej iščemo (5-3)-ti, torej 2. element v naslednji Tabeli. Zopet pogledamo velikost Tabele. Velikost je 1, mi pa iščemo 2. element. Nadaljujemo in iščemo (2-1) element v tretji Tabeli. To je kar prvi element naše tretje Tabele, in sicer 1. Torej je 5-ti element po vrsti v VSeznamu {-3,6,7,2,1} 1.

  • Dolžina VSeznama

Doližino VSeznama dobimo tako, da seštejemo velikosti vseh Tabel, ki sestavljajo VSeznam. (velikost m-te Tabele je velikost množice elementov m-te Tabele, ki so vključeni v VSeznam. Kot že omenjeno, množice elementov od vijolične puščice dalje v posamezni m-ti Tabeli). Sledimo puščicam od prve do zadnje Tabele in seštejemo elemente.

  • Primer: Naš VSeznam je {-3,6,7,2,1}. Poiščimo njegovo velikost.

Slika:primer.jpg
V prvi Tabeli se nahajajo trije elementi, v drugi in tretji pa eden. Torej je velikost VSeznama

Časovna zahtevnost

VSeznami se torej lahko pohvalijo s časovno zahtevnostjo večine svojih operacij.

  • iskanje k-tega elementa po vrsti
    Konstantni čas izvajanja te operacije izhaja iz same strukture VSeznama. Glede na k (indeks elementa, ki je k-ti po vrsti), opazujemo velikosti Tabel VSeznama in sledimo kazalcem, ki jih povezujejo, dokler ne najdemo Tabele, v kateri se k-ti element po vrsti nahaja. Glede na velikosti Tabel, ki se kot opisano, manjašajo geometrično, je verjetnost, da je k-ti element v prvi Tabeli VSeznama 1/2. Nadaljnje je verjetnost 1/4, da se moramo s kazalcem prestaviti v Tabelo na katero kaže prva Tabela itd. Tako se izkaže, da je pričakovano število kazalcev, katerim moramo slediti 1. Od tod torej izhaja konstanten čas (v povprečju!) za iskanje k-tega elementa po vrsti. V najslabšem primeru pa moramo seveda priti do konca VSeznama in če spet upoštevamo geometričnost, dobimo časovno zahtevnost O(log2(n))

  • dodajanje elementa na začetek VSeznama
    Dodajanje elementa na začetek VSeznama opravimo v konstantnem času.

  • nov VSeznam, kateri se začne pri drugem elementu prvotnega VSeznama (oz. brisanje prvega elementa)
    Enako je seveda pri brisanjem prvega elementa časovna zahtevnost konstantna.

  • dolžina VSeznama
    Spet se moramo sprehoditi do konca VSeznama prek kazalcev, torej iz geometričnosti dobimo časovno zahtevnost O(log2(n))

Glej še

Osebna orodja