Vrsta

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Vsebina

Predstavitev vrste

Vrsta je FIFO podatkovna struktura, kar pomeni, da gre tisti element, ki gre prvi v vrsto, tudi prvi iz nje (First In First Out). Za vrsto je tudi značilno, da elemente vstavljamo na enem koncu (na koncu vrste), jemljemo pa jih iz drugega konca (na začetku vrste).

Osnovne operacije v vrsti so: pripravi prazno vrsto, je vrsta prazna, začetek vrste, briši element z vrste, dodaj element na konec vrste.


Formalni opis podatkovne strukture vrsta

Structure VRSTA

declare
pripravi: 0 --> vrsta;
prazna: vrsta --> {true, false};
zacetek: vrsta --> podatek;
odstrani: vrsta --> vrsta;
dodaj: (vrsta, podatek) --> vrsta;
where
prazna(pripravi) ::=true;
prazna(vstavi(v,p)) ::= false;
odstrani(pripravi) ::= NAPAKA;
odstrani(vstavi(v,p)) ::=
if(prazna(v)) then pripravi
else vstavi(odstrani(v),p);
zacetek(pripravi) ::= NAPAKA;
zacetek(vstavi(v,p)) ::=
if(prazna(v)) then p
else zacetek(v);
end

Formalna predstavitev vrste je razdeljena na declare (deklerativni) in na where del. V prvem delu navedemo (dekleriramo) kaj želimo s to podatkovno strukturo delati (metode), v drugem pa navedemo pravila po katerih se morajo metode iz prvega dela ravnati.

Zgled



Grafična predstavitev Vrste in operacij nad njo: Primer grafične predstavitve Vrste, katere elementi so cela števila.


}
7 6 5 4 3 2 1



Operacija pripravi (na začetku nimamo nič, operacija pripravi prazno Vrsto V, v katero potem lahko vstavljamo elemente)



Operacija vstavi (operacija vstavi podatek p v Vrsto V in vrne novo Vrsto) V = vstavi(vstavi(vstavi(V , 7) , 6) , 5)


7 6 5


Operacija začetek (operacija vrne podatek v Vrsti V in sicer tistega, ki je na začetku Vrste)


7 6 5

....vrne podatek 7


Operacija odstrani (operacija izbriše prvi element Vrste V, se pravi tistega, ki je na začetku Vrste in vrne novo Vrsto V).

Morda najzahtevnejši aksiom (glej Formalen opis vrste) definira operacijo odstrani v Vrsti. Operacija odstrani nad Vrsto V, ki si ji nazadnje dodal podatek p, bo vrnila prazno Vrsto, če je bila Vrsta V že prazna in v skupni Vrsti tako en sam podatek. Če pa Vrsta V ni prazna, bo rezultat skupna Vrsta podatka p in odstrani(V).

V primeru, da smo Vrsto dobili z V = vstavi(vstavi(vstavi(V , 7) , 6) , 5), operacija odstrani po predpisu teče takole:

odstrani(vstavi(vstavi(vstavi(V , 7) , 6) , 5)) = vstavi(odstrani(vstavi(vstavi(V , 7) , 6)) , 5) = vstavi(vstavi(odstrani(vstavi(V , 7)) , 6) , 5) =


7 6 5

....vrne novo Vrsto katere prvi element je sedaj podatek 6 (FIFO - podatek 7 je prvi "prišel" v Vrsto in prvi "odšel" iz Vrste)

= vstavi(vstavi(V , 6) , 5)

6 5


Operacija prazna (operacija ugotovi ali je Vrsta parazna in če je vrne true, če ni pa false)

....vrne true - Vrsta je prazna


7 6

....vrne false - Vrsta ni prazna

Implementacija

  • 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.
  • Implementacija s krožno tabelo:
  • Pri implementaciji s krožno tabelo, odpravimo problem drsenja. Pojavi pa se nov problem in sicer, da težko ločimo med prazno in polno vrsto, če želimo v celoti izkoistiti prostor v tabeli. Problem rešimo 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.

Zgled:

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



  • Vrsto z linearnim seznamom implementiramo tako, da podamo referenco na prvi in na zadnji element vrste.

Zgled:

  1. public class VrstaLS extends Object {
  2. //predstavitev vrste z lin. seznamom
  3. //v vrsti hranimo cela števila
  4. private Vozel prvi;
  5. private Vozel zadnji;
  6. //kostruktorji (pripravi)
  7. public VrstaLS() {
  8. prvi = null;
  9. zadnji = null;
  10. }
  11. public void vstavi(int n) {
  12. Vozel v = new Vozel(n);//naredimo nov objekt
  13. if (prvi == null) { //če je vrsta prazna
  14. zadnji = v;
  15. prvi = v;
  16. }
  17. else {
  18. zadnji.nastaviNasled(v);
  19. v.nastaviNasled(null);
  20. zadnji = v;
  21. }
  22. }
  23. public void odstrani() { // vrsta ni prazna
  24. prvi = prvi.vrniNasled(); // prvi pokaže tja kamor kaže naslednik
  25. }
  26.  
  27. public boolean prazna() { // prazna vrsta
  28. return prvi == null;
  29. }
  30.  
  31. public int zacetek() { // vrnemo prvi element vrste
  32. return prvi.vrniPodatek();
  33. }
  34. public void izpis() { // izpis vrste
  35. Vozel kje = prvi;
  36.  
  37. while (kje != null) {
  38. System.out.print(kje.vrniPodatek() + " ");
  39. kje = kje.vrniNasled();
  40. }
  41. System.out.println();
  42. }
  43. }

Zgled uporabe

Naloga: Sestavi metodo, ki vrsto pozitivnih celih števil razdeli na vrsto sodih in vrsto lihih števil. Uporabi le osnovne operacije nad vrsto!

Ideja: Sprehodimo se čez elemente vrste in sproti preverjamo ali je element sod ali lih in ga na podlagi tega premestimo iz vrste ali pa ga pustimo v prvotni vrsti.

Rešitev:

  1. public static Vrsta<Integer> razdeliSodoLiho(Vrsta<Integer> v){
  2. /* vrne vrsto z lihimi stevili (v istem relativnem vrstnem redu kot v vrsti v),
  3. v vrsti v pa pusti le soda stevila
  4. Ce je vrsta v prazna, naj vrne prazno vrsto!
  5. V vrsti ni vec kot 100 stevil.
  6. Ce vrsta v vsebuje (zacetek vrste v je najbolj levi) "12, 23, 5, 46, 3, 12, 5"
  7. dobimo vrsto "23, 5, 3, 5", v vrsti v pa je "12, 46, 12".
  8. da bi ugotovili koliko elementov vsebuje Vrsta v, jih najprej premaknemo v
  9. Vrsto novaVrsta in povecujemo stevec za 1
  10. */
  11. int stevec = 0;
  12. //definiramo novo vrsto
  13. Vrsta<Integer> novaVrsta = new Vrsta<Integer>();
  14. if(v.prazna()) return new Vrsta<Integer>();
  15. else{
  16. while(!v.prazna()){
  17. novaVrsta.vstavi(v.zacetek());
  18. v.odstrani();
  19. stevec++;
  20. }
  21. }
  22. //v imamo stevec spravljeno stevilo elementov, v novaVrsta pa vse elemente Vrste v
  23. //sedaj preverimo kateri elementi so sodi in kateri lihi
  24. for(int i=0; i<stevec; i++){
  25. if(novaVrsta.zacetek()%2 == 0){
  26. //ce je element sod, ga premaknemo v Vrsto v
  27. v.vstavi(novaVrsta.zacetek());
  28. }
  29. else{
  30. //ce je element lih, ga premaknemo na konec vrste novaVrsta
  31. novaVrsta.vstavi(novaVrsta.zacetek());
  32. }
  33. //v obeh primerih nato odstranimo element iz novaVrsta
  34. novaVrsta.odstrani();
  35. }
  36. //kot rezultat vrnemo novaVrsta, ki vsebuje vse lihe elemente Vrste podane kot argument,
  37. //Vrste v
  38. return novaVrsta;
  39. }

Opomba: Za dano rešitev predvidevamo, da imamo že skonstruiran razred Vrsta, ki je generičen.

Ta rešitev je priročna, ker nismo po nepotrebnem ustvarili dveh novih vrst, ampak le eno.

Začetna vrsta izgleda takole: 12, 23, 5, 46, 3, 12, 5. Izvedemo metodo razdeliSodoLiho in dobimo vrsto lihih števil: 23, 5, 3, 5. Po izvajanju metode naša začetna vrsta zgleda takole: 12, 46, 12.



Naloga: S pomočjo osnovnih operacij nad Vrsto sestavi operacijo n - ti, ki vrne podatek o n - tem elementu v Vrsti, če ta obstaja.

Potek naloge: 1.metoda - imamo Vrsto v in število n, ki nam pove mesto podatka katerega element naj metoda vrne. Prva metoda temelji na tem, da se s for zanko sprehodimo po Vrsti v . V sami zanki preverimo še če je Vrsta v prazna in če je končamo (se pravi da ni n - tega elementa katerega iščemo), če ni z operacijo odstrani odstranimo prvi element Vrste v...ponavljamo dokler je števec i manjši od števila n in pri tem vedno odstranimo prvi element Vrste v. Ko pridemo do števila, katerega podatek nas zanima se for zanka konča in z operacijo začetek vrnemo podatek n - tega elementa katerega smo iskali.

2.metoda - metoda deluje s pomočjo pomožne Vrste pomV, ki je na začetku prazna. Imamo Vrsto v in število n, ki nam pove mesto podatka katerega elementa naj metoda vrne. Z while zanko se sprehodimo po Vrsti v in sicer tako dolgo dokler je še kaj elementov v njej, pri tem pa elemente Vrste v prelagamo v pomožno Vrsto pomV. Pri vsakem izvajanju zanke while povečujemo števec i, preverimo če je števec i enak številu n, katerega iščemo in če je shranimo n - ti element v spremenljivko rez, če ni se zanka if ne izvede. Na koncu še iz pomožne Vrste pomV preložimo elemente nazaj v Vrsto v. Metoda vrne rez v katerem je shranjen podatek n - tega elementa, katerega iščemo.

Rešitev:

  1. public class N_ti {
  2.  
  3. //1.metoda - imamo vrsto v in stevilo n , ki nam pove mesto podatka katerega
  4. //element naj metoda vrne
  5. public static int vrni_nti1(VrstaDLS v, int n) {
  6.  
  7. for (int i = 1; i < n; i ++)
  8. if (v.prazna()) //preverimo če je vrsta prazna
  9. return Integer.MAX_VALUE;
  10. else
  11. v.odstrani();//in če ni odstranimo prvi element vrste
  12.  
  13. if (v.prazna())
  14. return Integer.MAX_VALUE;
  15. else
  16. return v.zacetek();
  17. }
  18.  
  19. //2.metoda - metoda deluje s pomocjo pomozne vrste
  20. public static int vrni_nti2(VrstaDLS v, int n) {
  21.  
  22. VrstaDLS pomV = new VrstaDLS(); //pomozna vrsta
  23. int i = 0; //števec
  24. int rez = Integer.MAX_VALUE;
  25.  
  26. while (!v.prazna()) { //dokler je še kaj elementov v vrsti
  27.  
  28. i++;
  29.  
  30. if (i == n)
  31. rez = v.zacetek();
  32. //prelagamo elemente iz vrste v v pomožno vrsto pomV
  33. pomV.vstavi(v.zacetek());
  34. v.odstrani();
  35. }
  36.  
  37. //prestavimo elemente nazaj v vrsto v
  38. while (!pomV.prazna()) {
  39.  
  40. v.vstavi(pomV.zacetek());
  41. pomV.odstrani();
  42.  
  43. }
  44.  
  45. return rez;//vrnemo rezultat v katerem je shranjen podatek n-tega elementa, ki smo ga iskali
  46.  
  47. }
  48. }



Naloga: Odstrani n-ti element iz Vrste

Potek naloge: Metoda deluje s pomočjo pomožne Vrste pomV. Imamo Vrsto v in število n, ki nam pove mesto katerega element naj odstranimo. Z zanko while se sprehodimo po celotni Vrsti v (dokler je še kaj elementov v njej) in pri tem prelagamo elemente v pomožno Vrsto pomV. Pri vsakem izvajanju zanke while povečujemo števec i in preverjamo če je različen od mesta števila, ki ga želimo odstraniti. Kadar je števec i enak n - ju se zanka if ne izvede in element na mestu n odstranimo iz Vrste v. Na koncu elemente v pomožni Vrsti (v njej ni elementa, ki smo ga odstranili) pomV preložimo še nazaj v Vrsto v.

Rešitev:

  1. public class Odstrani_Nti {
  2.  
  3. //metoda, ki odstrani n-ti element iz vrste
  4.  
  5. public static void odstrani_nti(VrstaDLS v, int n) {
  6. VrstaDLS pomV = new VrstaDLS();//naredimo pomožno vrsto
  7. int i = 0;//števec
  8.  
  9. while (!v.prazna()) {//dokler je še kaj elementov v vrsti
  10. i++;
  11.  
  12. if (i != n)
  13. pomV.vstavi(v.zacetek());//prelagamo elemente v pomožno vrsto
  14.  
  15. v.odstrani();//če i = n potem odstranimo n-ti element iz vrste
  16. }
  17.  
  18. while (!pomV.prazna()) {//preložimo elemente iz pomožne vrste nazaj v začetno vrsto
  19.  
  20. v.vstavi(pomV.zacetek());
  21. pomV.odstrani();
  22. }
  23. }
  24. }



Naloga: Obrni vrstni red elementov v Vrsti.

Potek naloge: Pri metodi obrni si pomagamo s pomožnim skladom in sicer za sklad velja ("prvi notri zadnji ven"), za Vrsto pa velja ("prvi notri prvi ven"). Imamo pomožni sklad pomS. Z zanko while gremo po celotni Vrsti v, dokler je še kaj elementov v njej in pri tem prelagamo elemente v pomožni sklad pomS. Naprimer če imamo elemente v Vrsti 1 2 3 4 5 in jih prelagamo v sklad - prvi element, ki gre v sklad je 1, drugi je 2 in tako dalje do zadnjega, ki ga preložimo v sklad je element 5. Potem pa iz pomožnega sklada vstavimo elemente nazaj v vrsto in sicer - velja pravilo sklada "prvi notri zadnji ven", se pravi da je prvi element, ki zapusti sklad je 5, potem 4 in zadnji ki zapusti sklad je element 1. Elementi v Vrsti so sedaj v obrnjenem vrstnem redu 5 4 3 2 1.

Rešitev:

  1. public class Obrni {
  2.  
  3. //pri metodi obrni si pomagamo s pomožnim skladom
  4. public static void obrni(VrstaDLS v) {
  5.  
  6. Sklad pomS = new Sklad();//pomozni sklad
  7. while (!v.prazna()) { //prelagamo elemente iz vrste v sklad
  8. pomS.vstavi(v.zacetek());
  9. v.odstrani();
  10. }
  11.  
  12. while (!pomS.prazen()) { //iz sklada prelozimo elemente nazaj v vrsto
  13. v.vstavi(pomS.vrh());
  14. pomS.odstrani();
  15. }
  16. }
  17. }



Naloga: Iz dveh urejenih Vrst naredi urejeno Vrsto (zlivanje).

Potek naloge: Imamo dve vrsti prva in druga, ki sta urejeni od največjega do najmanjšega elementa. Največji elementi so na vrhu. Z zlivanjem zlijemo obe Vrsti v novo Vrsto in sicer s pomočjo tretje Vrste pom, ki je na začetku prazna. Z zanko while gremo po obeh Vrstah in prelagamo elemente - urejeno. Primerjamo prvi element prve Vrste z prvim elementom druge Vrste in večjega vstavimo v tretjo Vrsto pom in to ponavljamo. Ko je katerakoli (prva ali druga) Vrsta prazna (se pravi, da v njej ni več elementov) se zanka while konča. Na koncu še preverimo, če katera od Vrst še vsebuje elemente ter jih preložimo še v tretjo Vrsto pom. Metoda vrne Vrsto pom v kateri so na koncu elementi urejeni od največjega do najmanjšega.

Rešitev:

  1. public class Zlivanje {
  2.  
  3. public static VrstaDLS zlij(VrstaDLS prva, VrstaDLS druga) {
  4.  
  5. //zlivamo dve urejeni vrsti. Najvecji elementi so na vrhu
  6. VrstaDLS pom = new VrstaDLS();
  7.  
  8. while (!prva.prazna() && !druga.prazna()) {//dokler sta obe vrsti neprazni
  9.  
  10. //prelagajmo elemente
  11. if (prva.zacetek() >= druga.zacetek()) {
  12. pom.vstavi(prva.zacetek());
  13. prva.odstrani();
  14. }
  15. else {
  16. pom.vstavi(druga.zacetek());
  17. druga.odstrani();
  18. }
  19. }
  20.  
  21. //ugotovimo, katera vrsta je se neprazna in se z nje prelozimo elemente
  22. if (prva.prazna()) {
  23. while (!druga.prazna()) {
  24. pom.vstavi(druga.zacetek());
  25. druga.odstrani();
  26. }
  27. }
  28.  
  29. if (druga.prazna()) {
  30. while (!prva.prazna()) {
  31. pom.vstavi(prva.zacetek());
  32. prva.odstrani();
  33. }
  34. }
  35.  
  36. return pom;
  37. }
  38. }
  39.  

Glej tudi

Osebna orodja