Izpitno vprašanje RAČ2PRA 6100

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka NusaSkala.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.


Vprašanje

Dan je nepadajoče urejen sklad. S pomočjo osnovnih operacij izbriši vse podvojene elemente v skladu.


Odgovor

Naš program vsebuje dve metodi, testno, v kateri bomo podali sklad s poljubnimi elementi in iz katere bomo tudi poklicali našo drugo metodo, ki pa bo odstranjevala podvojene elemente iz sklada.

Elementi v skladu bodo urejeni nepadajoče. Če v sklad ne bomo podali nobenega elementa, bo metoda vrnila prazen sklad. Vsak element posebej bomo preložili iz prvotnega v pomožni sklad in ga hkrati primerjali z "novim" vrhnjim elementom v prvotnem skladu. Če se bo izkazalo, da sta trenutna elementa enaka, bomo enega odstranili in nadaljevali s pregledovanjem. Hkrati bomo elemente iz prvotnega sklada odstranjevali. Na koncu bomo imeli v pomožnem skladu same nepodvojene elemente, vendar v nasprotnem vrstnem redu, kot so bili v prvotnem skladu. Zato bomo na zadnjem koraku vse elemente "premetali" nazaj v naš prvotni sklad, da bodo urejeni tako kot na začetku.

V konkretnem, spodnjem primeru:

- se naš prvotni sklad imenuje "s"

- pomožni sklad je seveda "pomozni"

- v spremenljivko E bomo shranili tip, torej Integer, če bomo želeli v skladu hraniti cela števila, oziroma Double za realna števila.

  1.  
  2. public class Sklad_6100 {
  3. //metoda, ki bo odstranjevala podvojene elemente iz sklada:
  4. public static Sklad<E> odstrani_podvojene(Sklad<E> s) throws Exception{
  5. //pomožna sklada:
  6. Sklad<E> pomozni = new Sklad<E>();
  7. //če v skladu ni nobenega elementa, vrnemo prazen sklad:
  8. if(s.prazen()) return s;
  9. /*najprej damo v pomožni sklad vrhnji element sklada s, ker bodo težave kasneje,
  10. če bo le-ta prazen:*/
  11. else {
  12. pomozni.vstavi(s.vrh());
  13. s.odstrani();
  14. //dokler s ni prazen, prelagamo elemente v pomožnega in jih primerjamo med seboj:
  15. while(!s.prazen()){
  16. if(s.vrh() != pomozni.vrh()){
  17. pomozni.vstavi(s.vrh());
  18. s.odstrani();
  19. }
  20. else s.odstrani();
  21. }
  22. /*Poskrbimo, da bodo elementi v istem relativnem vrstnem redu, kot so bili v
  23. prvotnem skladu:*/
  24. while(!pomozni.prazen()){
  25. s.vstavi(pomozni.vrh());
  26. pomozni.odstrani();
  27. }
  28. return s;
  29. }
  30. }
  31.  
  32. // Testna metoda:
  33. public static void main(String[] args) throws Exception{
  34. //definiramo sklad s:
  35. Sklad<E> s = new Sklad<E>();
  36. //v skladu morajo biti elementi urejeni nepadajoče:
  37. s.vstavi(1);
  38. s.vstavi(2);
  39. s.vstavi(3);
  40. s.vstavi(3);
  41. s.vstavi(5);
  42. s.vstavi(6);
  43. System.out.println("Podan je sklad: " + s);
  44. System.out.println("Nov sklad brez podvojenih elementov: " + odstrani_podvojene(s));
  45. }}
  46.  
  47. /*V ukazni vrstici:
  48. * > java Sklad_6100
  49. * Podan je sklad: -:- 6 -:- 5 -:- 3 -:- 3 -:- 2 -:- 1
  50. * Nov sklad brez podvojenih elementov: -:- 6 -:- 5 -:- 3 -:- 2 -:- 1
  51. */
Osebna orodja