Naloga/Programiranje/Objektno programiranje/Razred UrejeniSeznam/Rešitev (Java)

Iz MaFiRaWiki

To je samo osnova za pravo rešitev.

  1. public class UrejeniSeznam<T extends Comparable<? super T>> {
  2. boolean prazen; // == true, ce je seznam prazen
  3. T glava;
  4. UrejeniSeznam<T> rep;
  5. // konstruktor
  6. public UrejeniSeznam() {
  7. this.prazen = true;
  8. this.glava = null;
  9. this.rep = null;
  10. }
  11. public String toString() {
  12. String r = "[";
  13. // v r dodajamo (predstavitve) elementov seznama
  14. UrejeniSeznam<T> s = this;
  15. while (!s.prazen) {
  16. r = r + s.glava; // v niz r dodaj predstavitev glave
  17. if (!s.rep.prazen) { r = r + ", "; }
  18. s = s.rep; // pomakni se naprej v seznamu
  19. }
  20. r = r + "]";
  21. return r;
  22. }
  23. // metoda vstavi(x) vstavi element x na pravo mesto v seznam
  24. // this
  25. public void vstavi(T x) {
  26. if (this.prazen) {
  27. this.prazen = false; // ni vec prazen
  28. this.glava = x; // dobil je glavo
  29. this.rep = new UrejeniSeznam<T>(); // in prazen rep
  30. }
  31. else {
  32. if (x.compareTo(this.glava) > 0) {
  33. // x vstavimo v rep
  34. this.rep.vstavi(x);
  35. }
  36. else {
  37. // x postavimo na zacetek seznama;
  38. UrejeniSeznam<T> nov = new UrejeniSeznam<T>();
  39. nov.prazen = false;
  40. nov.glava = this.glava;
  41. nov.rep = this.rep;
  42. this.glava = x;
  43. this.rep = nov;
  44. }
  45. }
  46. }
  47. }

  1. //Sestavi konstruktor public UrejeniSeznam(Seznam<T> s),
  2. //ki sprejme (navaden) seznam iz naloge Naloga/Programiranje/Objektno programiranje/Razred Seznam
  3. //in naredi nov urejeni seznam, ki ima enake elemente kot seznam s.
  4. public UrejeniSeznam(Seznam<T> s){
  5. UrejeniSeznam<T> urejen = new UrejeniSeznam<T>();
  6. while (!s.prazen){
  7. urejen.vstavi(s.glava);
  8. s = s.rep;
  9. }
  10. this.prazen = false;
  11. this.glava = urejen.glava;
  12. this.rep = urejen.rep;
  13. }
  14. //Sestavi konstruktor public UrejeniSeznam(T x, UrejeniSeznam<T> s),
  15. //ki naredi nov urejeni seznam, katerega elementi so x in elementi seznama s.
  16. //Pazi, da konstruktor ne spremeni seznama s!
  17. public UrejeniSeznam(T x, UrejeniSeznam<T> s){
  18. UrejeniSeznam<T> nov = new UrejeniSeznam<T>();
  19. while (!s.prazen){
  20. nov.vstavi(s.glava);
  21. s = s.rep;
  22. }
  23. nov.vstavi(x);
  24. this.prazen = false;
  25. this.glava = nov.glava;
  26. this.rep = nov.rep;
  27. }
  28.  
  29. //metoda vstavi nerekurzivno
  30. public void vstaviNerekurzivno(T x){
  31. UrejeniSeznam<T> s = this;
  32.  
  33. while (!s.prazen && s.glava.compareTo(x) < 0) s = s.rep;
  34. if (s.prazen){
  35. //nov elemnt dodamo na konec, njegov rep pokažemo na praznega
  36. s.prazen = false;
  37. s.glava = x;
  38. s.rep = new UrejeniSeznam<T>();
  39. }
  40.  
  41. else {
  42. UrejeniSeznam<T> t = new UrejeniSeznam<T>();
  43. t.prazen = false;
  44. t.glava = s.glava;
  45. t.rep = s.rep;
  46. s.glava = x;
  47. s.rep = t;
  48. }
  49. }
  50.  
  51. //metodo elementAt(k), ki vrne k-ti element seznama
  52. public UrejeniSeznam<T> elementAt(int k){
  53. for (UrejeniSeznam<T> s = this; !s.prazen; s = s.rep){
  54. //zmanjšamo k
  55. --k;
  56. if (k == 0) return s;
  57. }
  58. return null;
  59. }
  60.  
  61. //metodo sePojavi(x), ki vrne true, če se element x pojavi v seznamu
  62. public boolean sePojavi(T x){
  63. UrejeniSeznam<T> u = this;
  64.  
  65. while (!u.prazen && !u.glava.equals(x)) u = u.rep;
  66.  
  67. if (u.prazen) return false;
  68. else return true;
  69. }
  70.  
  71. //metodo odstrani(x), ki zbriše prvo pojavitev elementa x iz seznama
  72. public void odstrani(T y){
  73. UrejeniSeznam<T> u = this;
  74. while (!u.prazen && !u.glava.equals(y)) u = u.rep;
  75.  
  76. //poseben primer, če brišemo zadnjega,
  77. if (u.rep.prazen){
  78. u.prazen = true;
  79. u.glava = null;
  80. u.rep = null;
  81. }
  82.  
  83. //če ni zadnji, podatek iz naslednjega prepisati sem
  84. else {
  85. u.glava = u.rep.glava;
  86. u.rep = u.rep.rep;
  87. }
  88. }
  89. //metodo odstraniVse(x), ki zbriše vse pojavitve elementa x iz seznama
  90. //odstrani vse, zanko, če je enak, potem ga odstranimo, drugače nadaljujemo naprej
  91. //če smo ga odstranili, še enkrat v zanki preveriti tega
  92. public void odstraniVse(T z){
  93. UrejeniSeznam<T> s = this;
  94. while (!s.prazen)
  95. if (!s.glava.equals(z)) s = s.rep;
  96. else {
  97. s.odstrani(z);
  98. }
  99. }
Osebna orodja