Izpitno vprašanje DIRI2005 5200

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)

Vprašanje

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


Odgovor in primer programčka sta pripravljena s pomočjo predstavitve Sklada v Javini knjižnici; s pomočjo razreda Stack.


Podatkovna struktura Sklad je v Javini knjižnici predstavljena z razredom Stack. Osnovne operacije s katerimi upravljamo s skladom so predstavljene z metodami razreda Stack. Razred - class Stack vsebuje metode, s pomočjo katerih upravljamo s skladom. S pomočjo metod razreda Stack vstavljamo elemente v sklad, odstranjujemo elemente iz sklada, preverjamo ali je sklad prazen, preverjamo kateri element je na vrhu sklada.

Metode razreda Stack delujejo tako kot je za podatkovno strukturo Sklad značilno. Upoštevana je osnovna lastnost sklada - element, ki je bil zadnji vstavljen v sklad kot prvi prihaja iz sklada. Podatkovna struktura Sklad je v Javini knjižnici torej predstavljena z razredom Stack, ki v celoti upošteva osnovno pravilo sklada, pravilo LIFO. LIFO - last in first out, zadnji noter prvi ven, tako se obnaša Sklad, tako se obnaša Sklad predstavljen v razredu Stack.


Metode razreda Stack, s katerimi so predstavljene osnovne operacije nad skladom:

  • metoda push() - vstavi(), z metodo push vstavljamo elemente v sklad,
  • metoda pop() - odstrani(), z metodo pop odstranjujemo elemente iz sklada. Metoda pop odstrani vrhnji element iz sklada in ga hkrati vrne kot rezultat,
  • metoda peek() - vrh(), z metodo peek ugotavljamo kateri element je na vrhu sklada,
  • metoda empty() - prazen(), z metodo empty ugotavljamo ali je sklad prazen.


Konstruktor razreda Stack, s katerim pripravimo konkreten sklad;

  • konstruktor Stack().

Konkreten sklad pripravimo s pomočjo konstruktorja Stack() iz razreda Stack. Pri pripravi konkretnega sklada napovemo kakšen sklad bomo pripravili, kakšne vrste elemente oziroma kakšne vrste podatkov bomo vstavljali v naš konkreten sklad. Ali bo to sklad celih števil, ali bo to sklad znakov,...

Zgled: priprava sklada celih števil

  • Stack<Integer> sklad = new Stack<Integer>()

Odgovor

V podanem primeru programčka pripravimo sklad števil. V sklad vstavimo 20 naključnih števil. Za izpis elementov sklada v takšnem vrstnem redu kot so bili vstavljeni si pripravimo pomožen sklad.

Odstraniti želimo n-ti element z vrha sklada.

Algoritem 1: Pomagamo si s pripravo pomožnega sklada in prelaganjem elemementov v pomožen sklad. Dokler sklad ni prazen prelagamo elemente v pomožen sklad, le n_tega ne preložimo, le odstranimo ga iz osnovnega sklada. Elemente iz pomožnega sklada še preložimo v osnovni sklad. Algoritem ohrani osnovni sklad, a brez n-tega elementa. Predpostavimo, da vemo koliko elementov je v skladu, torej ne odstranjujemo elementa, ki ga v skladu ni. V primeru, da bi želeli odstranit element, ki ga v skladu ni ne naredimo ničesar. Algoritem je predstavljen z metodo odstrani_n_ti().

Algoritem 2: Podoben kot algoritem 1, a z nekoliko manj prelaganj. Pomagamo si s pripravo pomožnega sklada in prelaganjem elemementov v pomožen sklad. Elemente prelagamo v pomožen sklad, dokler ne pridemo do n-tega. N_tega ne preložimo, le odstranimo ga iz osnovnega sklada. Elemente iz pomožnega sklada sedaj le še preložimo v osnovni sklad. Algoritem ohrani osnovni sklad, a brez n-tega elementa. Predpostavimo, da vemo koliko elementov je v skladu, torej ne odstranjujemo elementa, ki ga v skladu ni. V primeru, da bi želeli odstranit element, ki ga v skladu ni ne naredimo ničesar.

Nov sklad izpišemo.


Prikaz delovanja algoritma 1 :


Slika:Sklad_52_1.png Slika:Sklad_52_2.png


V programčku je realiziran algoritem 1.

  1. import java.util.* ;
  2. public class Primer5200_1
  3. {
  4. // metoda odstrani_n_ti
  5. public static void odstrani_n_ti (Stack<Integer> sklad, int n_ti)
  6. {
  7. // Priprava pomožnega sklada
  8. Stack<Integer> sklad_pomozen = new Stack<Integer>();
  9. // Algoritem 1
  10. // Predpostavimo, da vemo koliko elementov je v skladu,
  11. // torej ne odstranjujemo elementa, ki ga vskladu ni.
  12. // V primeru, ko bi želeli odstranit element, ki ga v skladu ni ne naredimo nicesar.
  13. // Sklad ostane nespremenjen.
  14. // Algoritem in polnjenje pomožnega sklada
  15. int n ;
  16. n = 1 ;
  17. while (!sklad.empty())
  18. {
  19. if ( n == n_ti )
  20. {
  21. sklad.pop();
  22. }
  23. else
  24. {
  25. sklad_pomozen.push(sklad.pop());
  26. }
  27. n ++ ;
  28. }
  29. while (!sklad_pomozen.empty())
  30. {
  31. sklad.push(sklad_pomozen.pop());
  32. }
  33. }
  34.  
  35. public static void main(String args[])
  36. {
  37. // priprava sklada
  38. Stack<Integer> sklad = new Stack<Integer>();
  39. int element;
  40. int stevec;
  41. int n;
  42. String s_n_ti = args[0];
  43. int n_ti;
  44. n_ti = Integer.parseInt (s_n_ti);
  45. stevec = 1 ;
  46. // polnjenje sklada
  47. while ( stevec <= 20 )
  48. {
  49. element = 1 + (int)(20*Math.random());
  50. sklad.push(element);
  51. stevec ++ ;
  52. }
  53. // Izpis sklada
  54. // priprava obrnjenega sklada
  55. Stack<Integer> sklad_obrnjen = new Stack<Integer>();
  56. // polnjenje obnjenega sklada
  57. while (!sklad.empty())
  58. {
  59. sklad_obrnjen.push(sklad.pop());
  60. }
  61. System.out.println();
  62. System.out.println();
  63. System.out.println("Izpis sklada :");
  64. while (!sklad_obrnjen.empty())
  65. {
  66. System.out.print(sklad_obrnjen.peek() + " ");
  67. sklad.push(sklad_obrnjen.pop());
  68. }
  69.  
  70. // Priprava novega sklada, oziroma odstranjevanje n-tega elementa iz sklada
  71. // Klic metode odstrani_n_ti
  72. odstrani_n_ti (sklad, n_ti);
  73. // Izpis novega sklada, oziroma sklada brez n-tega elementa
  74. System.out.println();
  75. System.out.println();
  76. System.out.println("Izpis sklada brez n-tega elementa :");
  77. // Priprava obrnjenega sklada
  78. while (!sklad.empty())
  79. {
  80. sklad_obrnjen.push(sklad.pop());
  81. }
  82. while (!sklad_obrnjen.empty())
  83. {
  84. System.out.print(sklad_obrnjen.peek() + " ");
  85. sklad.push(sklad_obrnjen.pop());
  86. }
  87. System.out.println();
  88. System.out.println();
  89. }
  90. }

Izpis testnega programčka :

>java Primer5200_1 15
 
Izpis sklada :
9 6 3 14 9 10 2 8 5 18 5 20 1 17 13 12 18 5 3 17
 
Izpis sklada brez n-tega elementa :
9 6 3 14 9 2 8 5 18 5 20 1 17 13 12 18 5 3 17
Osebna orodja