Dvojna vrsta

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Kratek opis podatkovne strukture

Dvojna vrsta je urejen seznam v katerega vstavljamo in jemljemo elemente na začetku in na koncu vrste. Podatki, ki jih uvrščamo v dvojno vrsto, so lahko poljubnega tipa.

Formalen opis

Dvojna vrsta je struktura, ki podpira poleg običajnega vstavljanja in brisanja elementov na začetku vrste, tudi vstavljanje in brisanje elementov na koncu vrste.

Operacije

  • Operacije, ki jih izvajamo nad dvojno vrsto:
    • pripravi(): pripravi prazno dvojno vrsto
    • prazna(): pove ali je vrsta prazna (če je vrste prazna vrne true, sicer false)
    • zacetek(): vrne podatek, ki je na začetku dvojne vrste
    • konec(): vrne podatek, ki je na koncu dvojne vrste
    • vstaviNaZacetek(): vstavi podatek na začetek dvojne vrste in vrne novo dvojno vrsto
    • vstaviNaKonec(): vstavi podatek na konec dvojne vrste in vrne novo dvojno vrsto
    • odstraniZacetek(): izbriše prvi element dvojne vrste in vrne novo dvojno vrsto
    • odstraniKonec(): izbriše zadnji element dvojne vrste in vrne novo dvojno vrsto

Predstavitev delovanja operacij

Elemente dobivamo sproti. Pri vstavljanju v dvojno vrsto jih lahko vstavimo z obeh strani. Nekaj primerov vstavljanja elementov v dvojno vrsto:

Operacije nad dvojno vrsto Vrsta
pripravi DvojnaVrsta() ()
vstaviNaZacetek(3) (3)
vstaviNaKonec(2) (3, 2)
vstaviNaZacetek(4) (4, 3, 2)
vstaviNaKonec(6) (4, 3, 2, 6)
vstaviNaZacetek(1) (1, 4, 3, 2, 6)
vstaviNaZacetek(7) (7, 1, 4, 3, 2, 6)
vstaviNaKonec(8) (7, 1, 4, 3, 2, 6, 8)
odstraniKonec() (7, 1, 4, 3, 2, 6)
odstraniKonec() (7, 1, 4, 3, 2)
odstraniZacetek() (1, 4, 3, 2)
odstraniZacetek() (4, 3, 2)
zacetek() (4)
konec() (2)
odstraniZacetek() (3, 2)
odstraniKonec() (3)
odstraniKonec() ()
odstraniZacetek() napaka

Aksiomi, ki veljajo v dvojni vrsti

  • metoda prazna
  • metoda dobi kot parameter prazno dvojno vrsto
     //opis, kaj naredimo na prazni dvojni vrsti
     prazna(pripravi) := true;
  • metoda dobi kot parameter neprazno dvojno vrsto
    //opis, kaj naj naredimo na neprazni dvojni vrsti
    prazna(vstaviNaZacetek(dvojna_vrsta, podatek)) := false;
  • metoda odstraniZacetek
  • metoda dobi kot parameter prazno dvojno vrsto
   //opis, kaj naj naredimo na prazni dvojni vrsti
   odstraniZacetek(pripravi) := izjema
   vrnemo izjemo, IllegalStateException odstraniZacetek(prazna dvojna vrsta);
  • metoda dobi kot parameter neprazno dvojno vrsto
   //opis, kaj naj naredimo na neprazni dvojni vrsti
   odstraniZacetek(vstaviNaZacetek(dv,p)) := dvojna_vrsta;
  • metoda odstraniKonec
  • metoda dobi kot parameter prazno dvojno vrsto
   //opis, kaj naj naredimo na prazni dvojni vrsti
   odstraniKonec(pripravi) := izjema
   vrnemo izjemo, IllegalStateException odstraniKonec(prazna dvojna vrsta);
  • metoda dobi kot parameter neprazno dvojno vrsto
   //opis, kaj naj naredimo na neprazni dvojni vrsti
   odstraniKonec(vstaviNaKonec(dv,p)) := dvojna_vrsta;


  • metoda zacetek
  • metoda dobi kot parameter prazno dvojno vrsto
   //opis, kaj naj naredimo na prazni dvojni vrsti
   zacetek(pripravi) := izjema
   vrnemo izjemo, IllegalStateException zacetek(prazna dvojna vrsta);
  • metoda dobi kot parameter neprazno dvojno vrsto
   //opis, kaj naj naredimo na neprazni dvojni vrsti
   zacetek(vstaviNaZacetek(dvojna_vrsta,podatek)) := podatek;
  • metoda konec
  • metoda dobi kot parameter prazno dvojno vrsto
   //opis, kaj naj naredimo na prazni dvojni vrsti
   konec(pripravi) := izjema
   vrnemo izjemo, IllegalStateException konec(prazna dvojna vrsta);
  • metoda dobi kot parameter neprazno dvojno vrsto
   //opis, kaj naj naredimo na neprazni dvojni vrsti
   konec(vstaviNaKonec(dvojna_vrsta,podatek)) := podatek;

Implementacija podatkovne strukture dvojna vrsta

Zapis razreda DvojnaVrsta v programskem jeziku Java s potrebnimi konstruktorji, get/set metodami in metodo toString, ki morajo delovati na način, kot predvideva definicija podatkovne strukture. Glede na to, da obstaja več možnosti predstavitve strukture, se lahko sami odločimo, v kakšni obliki jo bomo predstavili in kakšne vrednosti bomo v njej shranjevali.

Dvojno vrsto implementiramo kot tabelo, v kateri hranimo cela števila. Pomembno je, da je vrsta predstavljena kot krožna tabela, ki nam omogoča na koncu in začetku vrste dostop do elementov po modulu velikosti tabele. V vrsti lahko hranimo en element manj kot je njena velikost, zato da lahko zaradi krožnega delovanja metod ločimo med polno in prazno vrsto.

  1.  
  2.  
  3. public class DvojnaVrsta {
  4.  
  5. // predstavitev dvojne vrste s krožno tabelo
  6. // v vrsti hranimo cela števila
  7. // v primeru napačnih operacij vržemo IllegalStateException
  8.  
  9. protected int prvi; // indeks prvega elementa v tabeli
  10. protected int zadnji; // indeks zadnjega elementa v tabeli - 1
  11. protected int[] elti; // elementi tabele
  12. protected int vel_tab = 300; // osnovna velikost tabele
  13.  
  14. // kostruktorji, ki pripravijo vrsto
  15. public DvojnaVrsta() {
  16. prvi = 0;
  17. zadnji = 0; // enega vmes spustimo - da razlikujemo med prazno in polno vrsto
  18. elti = new int[vel_tab];
  19. }
  20.  
  21. public DvojnaVrsta(int[] t) {
  22. // vrsta narejena iz tabele
  23. this();
  24. if (t.length > vel_tab - 1) {
  25. throw new IllegalStateException("pripravi - prevelika tabela");
  26. }
  27. for (int i = 0; i < t.length; i++)
  28. this.vstaviNaKonec(t[i]);
  29. }
  30.  
  31. // objektna metoda vstaviNaKonec, ki element vstavi na konec dvojne vrste
  32. public void vstaviNaKonec(int x) {
  33. int i = (zadnji + 1) % vel_tab; // indeks za vstavljanje
  34. if (prvi == i) // vrsta je polna
  35. throw new IllegalStateException("vstaviNaKonec(polna vrsta)");
  36. this.zadnji = i;
  37. elti[zadnji] = x;
  38. }
  39.  
  40. // objektna metoda vstaviNaZacetek, ki element vstavi na zacetek dvojne vrste
  41. public void vstaviNaZacetek(int x) {
  42. int i = (prvi - 1); // indeks za vstavljanje
  43. if(i == - 1) i = vel_tab - 1;
  44. if (zadnji == i) // vrsta je polna
  45. throw new IllegalStateException("vstaviNaZacetek(polna vrsta)");
  46. this.prvi = i;
  47. elti[(prvi+1) % vel_tab] = x;// element vstavimo na zacetek vrste
  48. }
  49.  
  50. // objektna metoda odstraniZacetek, ki odstrani prvi element vrste
  51. public void odstraniZacetek() {
  52. if (this.prazna()) // vrsta je prazna
  53. throw new IllegalStateException("odstraniZacetek(prazna vrsta)");
  54. prvi = (prvi + 1) % vel_tab;
  55. }
  56.  
  57. // objektna metoda odstraniKonec, ki odstrani zadnji element vrste
  58. public void odstraniKonec() {
  59. if (this.prazna()) // vrsta je prazna
  60. throw new IllegalStateException("odstraniKonec(prazna vrsta)");
  61. if(zadnji == 0) zadnji = vel_tab - 1; //
  62. else zadnji = zadnji - 1;
  63. }
  64.  
  65. // objektna metoda zacetek, ki vrne prvi element vrste
  66. public int zacetek() {
  67. if (!this.prazna()) { // vrsta ni prazna
  68. int kje = (prvi + 1) % vel_tab;
  69. return elti[kje]; // vrnemo prvi element vrste
  70. }
  71. throw new IllegalStateException("zacetek(prazna vrsta)");
  72. }
  73.  
  74. // objektna metoda konec, ki vrne zadnji element vrste
  75. public int konec() {
  76. if (!this.prazna()) { // vrsta ni prazna
  77. int kje = (zadnji) % vel_tab;
  78. return elti[kje]; // vrnemo zadnji element vrste
  79. }
  80. throw new IllegalStateException("konec(prazna vrsta)");
  81. }
  82.  
  83. // objektna metoda prazna, ki vrne true, ce je vrsta prazna
  84. public boolean prazna() {
  85. return prvi == zadnji;
  86. }
  87.  
  88. public String toString() {
  89. String rez = "#";
  90. int kje = prvi;
  91. while (kje != zadnji) { // dokler ne bo konec vrste
  92. kje = (kje + 1) % vel_tab;
  93. rez = rez + " - " + elti[kje];
  94. }
  95. return rez;
  96. }
  97.  
  98. // objektna metoda izpis, ki izpise vrsto
  99. public void izpis() {
  100. // uporabimo implicitni klic metode toString
  101. System.out.println("DvojnaVrsta: " + this);
  102. } // izpis
  103. } // class

Zgled uporabe

Napisali bomo program, ki iz enojne vrste naredi dvojno vrsto tako, da so na začetku samo sodi elementi dvojne vrste, na koncu pa lihi elementi.

Ideja

Naredimo dvojno vrsto, v katero bomo prelagali elemente iz enojne vrste. In sicer, če je element na začetku vrste sod, ga vstavimo na začetek dvojne vrste, sicer če ni sod, ga vstavimo na konec dvojne vrste in nato še odstranimo iz enojne vrste. Ponavljamo toliko časa, dokler vrsta ni prazna. Na koncu vrnemo dvojno vrsto, ki ima na začetku dvojne vrste same sode elemente, na koncu dvojne vrste pa same lihe elemente.

primer:

Če imamo npr. tako vrsto Vrsta v = {1,2,3,4}. Vidimo, da je začetek vrste v število 1, to število je liho, zato ga vstavimo na konec dvojne vrste in iz enojne vrste v ga odstranimo. Naslednje število je 2, to število je sodo zato ga vstavimo na začetek dvojne vrste, iz enojne ga odstranimo. Število 3 je liho, vstavimo ga na konec dvojne vrste, iz enojne ga odstranimo. Število 4 je sodo, vstavimo ga na začetek dvojne vrste, iz enojne ga odstranimo. Sedaj je vrsta v prazna, končamo s postopkom in vrnemo dvojno vrsto dv = {4,2,1,3}

  1.  
  2. public class SodoLiho {
  3. public static DvojnaVrsta<Integer> razdeliSodoLiho(Vrsta<Integer> v) {
  4. // naredimo novo dvojno vrsto
  5. DvojnaVrsta<Integer> dv = new DvojnaVrsta<Integer>();
  6. // ponavljamo dokler vrsta v ni prazna
  7. while(!v.prazna()) {
  8. // ce je element na zacetku vrste sod, ga vstavimo
  9. // na zacetek dvojne vrste, sicer ga vstavimo
  10. // na konec dvojne vrste
  11. if(v.zacetek() % 2 == 0) {
  12. dv.vstaviNaZacetek(v.zacetek());
  13. v.odstrani();
  14. }
  15. else {
  16. dv.vstaviNaKonec(v.zacetek());
  17. v.odstrani();
  18. }
  19. }
  20. // vrnemo dvojno vrsto
  21. return dv;
  22. }
  23.  
  24. // primer za preizkus delovanja programa
  25. public static void main(String[] args) {
  26. int[] t = {1,2,3,4,5,6,7,8,9,10};
  27. Vrsta<Integer> v = new Vrsta<Integer>(t);
  28. v.izpis();
  29. DvojnaVrsta<Integer> dv = razdeliSodoLiho<Integer>(v);
  30. dv.izpis();
  31. }
  32. }
Osebna orodja