Izpitno vprašanje RAČ2PRA 5200

Iz MaFiRaWiki

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

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

S pomočjo osnovnih operacij nad skladom iz danega sklada odstrani n-ti element.

Ideja

Imamo dan sklad in iz njega želimo odstraniti n-ti element. Sklad ostane isti kot prej le da manjka en element.

Naredimo pomožni sklad v katerega bomo prelagali elemente iz prvotnega sklada. Pogledamo vrhnji element v prvotnem skladu, če je to element (n-ti), ki ga iščemo ga odstranimo, sicer ga preložimo v pomožni sklad. Ponavljamo toliko časa, dokler sklad ni prazen. Na koncu preložimo vse elemente iz pomožnega sklada nazaj v prvotni sklad.

primer:

Imamo dan sklad naslednjih števil. Radi bi odstranili tretji element.

Pomožen sklad, v katere smo shranjevali vsa števila, razen tretjega, ki smo ga odstranili:


Končen sklad ( pomožen sklad smo prestavili nazaj v prvoten sklad ), sklad ostane isti kot prej, le da manjka en element.

Odgovor

  1.  
  2. public class OdstraniNti{
  3. public static Sklad<Integer> odstraniNti(Sklad<Integer> s, int n)
  4. throws Exception{
  5. // ustvarimo pomožen sklad
  6. Sklad<Integer> pom = new Sklad<Integer>();
  7. int i = 0;
  8. // če je sklad s prazen, javi napako
  9. if(s.prazen()){
  10. throw new Exception("Sklad je prazen.");
  11. }
  12. // v skladu s je en element
  13. if(i == n-1){
  14. s.odstrani();//ki ga odstranimo
  15. return s;
  16. }
  17.  
  18. // sklad je poln
  19. while(!s.prazen()){
  20. if(i != n-1){ // iščemo željeni element
  21. // vstavljamo ga v pomožen sklad
  22. pom.vstavi(s.vrh());
  23. s.odstrani();// in ga odstranimo iz sklada s
  24. }
  25. //smo ga našli
  26. else{
  27. s.odstrani();// in ga ostranili
  28. }
  29. i++;
  30. }
  31. // iz pomožnga sklada preložimo nazaj v sklad s
  32. while(!pom.prazen()){
  33. s.vstavi(pom.vrh());
  34. pom.odstrani();
  35. }
  36. return s;
  37. }
  38. // primer za preizkus delovanja programa
  39. public static void main(String[] args) throws Exception{
  40. Sklad<Integer> pom = new Sklad<Integer>();
  41. pom.vstavi(1);
  42. pom.vstavi(7);
  43. pom.vstavi(2);
  44. pom.vstavi(6);
  45. pom.vstavi(8);
  46.  
  47. System.out.println(pom);
  48. odstraniNti(pom,3);
  49. System.out.println(pom);
  50. }
  51. }
  52.  
Osebna orodja