Izpitno vprašanje RAČ2PRA 7600

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka Maša Glavan.

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

Predstavitev vrste s pomočjo tabele.

Odgovor

Pri implementaciji vrste s tabelo imamo problem drsenja vrste. To pomeni, da imamo lahko, po nekaj korakih vstavljanja in odstranjevanja elementov, skoraj prazno vrsto, vanjo pa ne moremo več vstavljati, ker smo z kazalcem prišli že do konca tabele.

To je tabela dane dolžine, skupaj s kazalcema začetek in konec, ki kažeta na prvi in zadnji element v vrsti. Ko iz vrste vzamemo element povečamo začetek za ena, ko dodamo nov element, povečamo konec za ena. Če začetek in konec prestopita mejo tabele, ju postavimo nazaj na začetek tabele. Zato indekse štejemo po modulu dolžine tabele in da se izognemo težavam je najpametneje pustiti en prostor med koncem in začetkom vedno prazen.

PROBLEM DRSENJA VRSTE:

krožna tabela odpravimo problem drsenja operacije po modulu dolžine tabele.Če se odločimo da prostor v celoti izkoristimo teŽko ločimo med prazno in polno vrsto. To dosežemo tako da se odpovemo enemu mestu v tabeli.Naj bo začetek indeks zadnjega praznega mesta pred začetkom vrste .Vrsta je polna ko velja (zadnji + 1 ) mod n = = prvi. Podobno je v vrsti en sam element ko je prvi = zadnji. Kjer je n velikost tabele.

  1.  
  2. public class Vrsta extends Object{
  3. // predstavitev vrste s krozno tabelo
  4. // v vrsti hranimo cela števila
  5. protected int prvi; // indeks prvega elementa v tabeli + 1
  6. protected int zadnji; // indeks zadnjega elementa v tabeli
  7. protected int[] elti; // elementi tabele
  8. protected int vel_tab = 20; // osnovna velikost tabele
  9. // kostruktorji (pripravi)
  10. public Vrsta(){
  11. prvi = 0;
  12. zadnji = 0; // enega vmes spustimo - da razlikujemo med prazno in polno vrsto
  13. elti = new int[vel_tab];
  14. }
  15. public boolean vstavi(int x){
  16. // true - vstavljanje je uspelo
  17. // false - vrsta je polna, ne naredimo nic
  18. int i = (zadnji + 1) % vel_tab; // indeks za vstavljanje
  19. if (prvi == i) // vrsta je polna
  20. return false;
  21. zadnji = i;
  22. elti[zadnji] = x;
  23. return true;
  24. }
  25. public void odstrani(){
  26. // ce je vrsta prazna - ne naredimo nic
  27. if (prvi != zadnji) // vrsta ni prazna
  28. prvi = (prvi + 1) % vel_tab;
  29. }
  30. public int zacetek(){
  31. // ce je vrsta prazna vrnemo Integer.MIN_VALUE
  32. if (prvi != zadnji){ // vrsta ni prazna
  33. int kje = (prvi + 1) % vel_tab;
  34. return elti[kje];
  35. }
  36. return Integer.MIN_VALUE;
  37. }
  38. public boolean prazna(){
  39. return prvi == zadnji;
  40. }
  41. public String toString(){
  42. String rez = "";
  43. int kje = prvi;
  44. while (kje != zadnji){ // dokler ne bo konec vrste
  45. kje = (kje + 1) % vel_tab;
  46. rez = rez + " " + elti[kje];
  47. }
  48. return rez;
  49. }
  50. public void izpis(){
  51. // prvi je element na zacetku
  52. System.out.println("Vrsta: " + this);
  53. }
  54. }

Glej tudi:

vrsta

tabela

Osebna orodja