Izpitno vprašanje RAČ2PRA 7100

Iz MaFiRaWiki

Vsebina

Vprašanje

Odstrani podatek iz enojno povezanega linearnega seznama.

Odgovor

Vprašanje je slabo definirano, saj ne pove, kateri podatek želimo odstraniti. Zato sta tako rešitev, ki je bila prvotno objavljena in odgovor, ki je na pogovorni strani, v bistvu OK, a rešujeta različna problema:

  • prvi algoritem odstrani n-ti podatek LS
  • drugi algoritem predpostavlja, da v LS hranimo cela števla in odstrani prvi vozel, ki ima podatek enak parametru metode.

Odgovor 1 (odstrani n-tega)

Metoda iz linearnega seznama odstrani podatek, ki je na n-tem mestu. To naredimo tako, da gremo s števcem po linearnem seznamu, do mesta n-1, nato pa kazalec nastavimo na naslednika od n, to je na mesto n+1.

Začetni linearni seznam

Ko izbrišemo podatek, ki je na 5. mestu, to naredimo tako, da kazalec pokaže iz 4 na 6 (iz vozla z vsebino v4 na vozel z vsebino v5):

Metoda deluje tudi za robne primere (če odstranjujemo prvi vozel ali odstranjujemo zadnji vozel). Samo vozle moramo šteti od 0 naprej (npr. če hočeš odstraniti drugi vozel, je n = 1).

  1. public void odstraniPodatek(LinSez<Integer> s, int n) throws Exception
  2. //odstranimo n-ti vozel
  3. //Če ni n-vozlov, bo vrniNasled() vrgla izjemo, ki jo bo metoda posredovala naprej!
  4. Vozel<Integer> pomozni = s.vrniPrviVozel();
  5. int stevec = 0;
  6. while(stevec < n-1){
  7. pomozni = pomozni.vrniNasled();
  8. stevec = stevec + 1;
  9. }
  10. pomozni.nastaviNasled(pomozni.vrniNasled().vrniNasled());
  11. }

Odgovor 2

Linearni seznam je množica elementov, kjer vsak element vsebuje kazalec na element. Če je seznam prazen ne naredimo nič. Če pa želimo odstraniti podatek b iz linearnega seznama, mora kazalec predhodnika pokazati tja kamor kaže b. Za vozlišče, na katerega ne kaže več noben kazalec poskrbi Java (garbage collector).

Ideja za program:

Najprej pogledamo, če je seznam prazen, da ne bi brez smiselno nadaljevali. Ustvarimo vozel »p«, ki si zapomni prvi vozel. Ustvarimo pomožen vozel »kje«, ki ga nastavimo na začetek in se bomo z njih sprehodili po seznamu in preverili, kje je iskani podatek. Preverimo, če je iskani podatek na začetku seznama in če je naslednjega nastavimo kot prvega. Za nadaljevanje potrebujemo še en pomožen vozel »pom« in ga nastavimo na null. Naredimo zanko, ki bo tekla do konca seznama (dokler pomožni vozel »kje« ne bo pokazal na null). Potem moramo »kje« spraviti v »pom« in »kje« naj vrne naslednjega. V zanki preverimo, če se iskani podatek ujema s podatkom v vozlu »kje« in če se, »pom« pokaže na naslednjega od »kje«, če ne se zanka izvaja naprej. Program se konča, če je seznam prazen, ko »zbrišemo« dani podatek ali pa, ko pridemo čez cel seznam.

Program:

  1.  
  2. public satic void zbrisi1(int x)
  3. {
  4. if(prazen()) throw new NullPointerException("zbrisi (prazen)"); // če je prazen
  5. else
  6. {
  7. Vozel p = vrniPrviVozel(); // prvi vozel
  8. Vozel kje = p ; // pomozni vozel kje nastavimo na p
  9. if(kje.vrniPodatek() == x) // ce najdemo podatek na začetku
  10. {
  11. vstaviPrvega(kje.vrniNasled()); // pomoznega »kje« nastavimo na naslednjega
  12. return;
  13. }
  14. Vozel pom = null; // pomozni kaze na null
  15. while(kje != null) // dokler kje ne pokaze na null
  16. {
  17. if(kje.vrniPodatek() == x) // ce najdemo podatek
  18. {
  19. pom.nastaviNasled(kje.vrniNasled()); // pomoznega nastavimo na naslednjega
  20. return;
  21. }
  22. pom = kje;
  23. kje = kje.vrniNasled(); // vrne naslednjega
  24. }
  25. }
  26. }
  27.  
Osebna orodja