Izpitno vprašanje RAČ2PRA 7800

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.


Vsebina

Vprašanje

Predstavitev vrste z uporabo linearnega seznama.

Odgovor

Metode ki jih ima vrsta

  1. public class Vrsta {
  2. // kostruktorji
  3. public Vrsta(); // Privzeti konstruktor. Ustvari vrsto s prostorom za 101 element.
  4. public Vrsta(T[] t); // konstruktor ki ustvari vrsto iz tabele
  5. public void vstavi(T x); // vstavi podatek pod v vrsto
  6. public void odstrani(); // odstrani podatek iz vrste
  7. public boolean prazna(); // pove ce je vrsta prazna
  8. public T zacetek(); // vrne element na zacetku vrste
  9. public void izpis(); // izpise vrsto na zaslon
  10. public String toString(); // izpise vrsto v niz in ga vrne
  11. }

Metode razreda LinSez skoraj dobesedno ustrezajo metodam razreda Vrsta. Edina težava, ki se pojavi, je konstruktor, ki napravi vrsto iz tabele števil. "Prevod imen" sem torej zapisala takole:

  1. public class VrstaLS {
  2. LinSez ss; // vrsta je linearen seznam
  3. // kostruktorji
  4. public VrstaLS() { ss = new LinSez(); } // nova prazna vrsta
  5. // nova vrsta, podana vsebina
  6. public VrstaLS(T[] t) {
  7. ss = new LinSez();
  8. for (int ii= 0; ii < vsebina.length; ii++)
  9. ss.vstaviPrvega(vsebina[ii]);
  10. } // VrstaLS
  11. // metode
  12. public void vstavi(T p) { ss.vstaviPrvega(p); } // vstavi podatek
  13. public void odstrani() { ss.zbrisiPrvega(); } // odstrani podatek iz vrste
  14. public boolean prazen() { return ss.prazen(); } // ali je vrsta prazna?
  15. public T zacetek() { return ss.vrniPrvoVrednost(); } //prvi element vrste
  16. public void izpis() { ss.izpisi(); } // izpiše vrsto
  17. public String toString() { return ss.toString(); } // vrne vrsto kot niz
  18. }

Rešitev

  1. public class ResitevLS {
  2.  
  3. public static VrstaLS odstraniNaj(VrstaLS v) {
  4. if (v.prazna()) return new VrstaLS(); // nova prazna vrsta
  5. T najvecji = v.zacetek(); // (doslej) največji
  6. T pozicija = 0; // trenutna pozicija v vrsti, zacetek == 0
  7. T pozicijaMax = 0; // pozicija največjega
  8.  
  9. VrstaLS vmesna = new VrstaLS(100); // nova vmesna vrsta
  10. VrstaLS rezultat = new VrstaLS(100); // vrsta rezultat
  11.  
  12. // Zapeljemo se po v, najdemo pravega! največjega in skopiramo vse v vmesna
  13. while (!v.prazna()) {
  14. if(v.zacetek() > najvecji) {
  15. najvecji = v.zacetek();
  16. pozicijaMax = pozicija;
  17. }
  18. vmesnia.vstavi(v.zacetek());
  19. v.odstrani();
  20. pozicija++;
  21. }
  22. // vse skopiramo nazaj v v, vse brez največjega v rezultat
  23. while (!vmesna.prazna()) {
  24. v.vstavi(vmesna.zacetek());
  25. pozicija--;
  26. if(pozicija != pozicijaMax) rezultat.vstavi(vmesna.zacetek());
  27. vmesna.odstrani();
  28. }
  29. return rezultat;
  30. }
  31.  
  32. }

Glej tudi

Vrsta

Linearni seznam

Osebna orodja