Izpitno vprašanje RAČ2PRA 8600

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Vprašanje

Napiši objektno metodo public void urejenoVstavi(int elt); ki v nepadajoče urejen seznam vstavi nov element na pravo mesto, tako da ostane seznam še vedno urejen.


Odgovor

Gre za to, da

  • najprej poiščemo vozel ZA katerega spada ta novi element
    • pri iskanju uporabimo dejstvo, da imamo opraviti z nepadajoče urejenim seznamom
  • naredimo nov vozel, ki vsebuje ta novi element
  • novi vozel povežemo v verižni (linearni) seznam
    • naslednik novega vozla je vozel, ki je naslednik poiskanega vozla
    • novi naslednik poiskanega vozla (torej tisti vozel, za katerim vstavljamo) tega novega vozla je novi vozel

  1. public void urejenoVstavi(int elt){
  2. // če je seznam prazen, vstavimo vanj vozel s podatkom elt
  3. if(this.prazen()) this.vstavi_prvega(new Vozel(null,elt));
  4. else{
  5. Vozel t = this.vrniPrviVozel();
  6. /*
  7. Primer, ko ima 1. vozel seznama večji podatek, kot je elt, obravnavamo posebej.
  8. To pa zato, ker če do tega pride moramo, da obdržimo urejenost seznama, pred
  9. 1. vozel vrniti vozel s podatkom elt, kar pa nam spremeni celoten objekt seznam.
  10. */
  11. if(t.vrniPodatek() > elt){
  12. //novi 1. vozel ima sedaj referenco na stari prvi vozel(t) in podatek elt
  13. this.nastaviPrvega(new Vozel(t,elt));
  14. }
  15. //dokler ne pridemo do konca seznama preverjamo
  16. while(t.vrniNasled() != null){
  17. //ce naslednjik ni vecji, se s kazalcem premaknemo naprej
  18. if(t.vrniNasled().vrniPodatek() <= elt) t = t.vrniNasled();
  19. //če je naslednjik večji, med njega in med kazalec vrinemo vozel s podatkom elt
  20. else{
  21. Vozel podatek = new Vozel(t.vrniNasled(),elt);
  22. t.nastaviNasled(podatek);
  23. t = podatek.vrniNasled();
  24. }
  25. }
  26. //ko se zanka izteče vemo, da smo prisli na konec seznama
  27. // ce ima zadnji vozel manjsi podatek, za njim dodamo se nov vozel s podatkom elt
  28. if(t.vrniPodatek() <= elt) t.nastaviNasled(new Vozel(null,elt));
  29. }
  30. }
Osebna orodja