Naloga/Programiranje/Objektno programiranje/Razred Imenik/Rešitev z urejenim seznamom (Java)

Iz MaFiRaWiki

Sledeča implementacija ni optimalna. Uporaba na lastno odgovornost!

  1. public class Imenik<Kljuc extends Comparable<? super Kljuc>, Vrednost> {
  2. // komponente
  3. Element<Kljuc,Vrednost> glava;
  4. Imenik<Kljuc,Vrednost> rep;
  5. boolean prazen;
  6.  
  7. public Imenik() {
  8. prazen = true;
  9. glava = null;
  10. rep = null;
  11. }
  12.  
  13. public Vrednost najdi(Kljuc x) {
  14. // poisci vrednost, ki pripada kljucu x
  15. Imenik<Kljuc,Vrednost> temp = this;
  16. while(!temp.prazen){
  17. if (temp.glava.kljuc.equals(x)){
  18. return glava.vrednost;
  19. }
  20. temp = temp.rep;
  21. }
  22. return null;
  23. }
  24.  
  25. public void vstavi(Kljuc x, Vrednost y) {
  26. if (this.prazen) {
  27. this.prazen = false; // ni vec prazen
  28. this.glava = new Element<Kljuc,Vrednost>(x,y); // dobil je glavo
  29. this.rep = new Imenik<Kljuc,Vrednost>(); // in prazen rep
  30. }
  31. else {
  32. if (x.compareTo(this.glava.kljuc) > 0) {
  33. // x vstavimo v rep
  34. this.rep.vstavi(x,y);
  35. }
  36. else {
  37. // vrednost pri x nastavimo na y
  38. // ce x obstaja, prepisemo obstojeco vrednost
  39. if(this.glava.kljuc.equals(x)){
  40. this.glava.vrednost = y;
  41. }else{
  42. Imenik<Kljuc,Vrednost> nov = new Imenik<Kljuc,Vrednost>();
  43. nov.prazen = false;
  44. nov.glava = this.glava;
  45. nov.rep = this.rep;
  46. this.glava = new Element<Kljuc,Vrednost>(x,y);
  47. this.rep = nov;
  48. }
  49. }
  50. }
  51. }
  52.  
  53. public void zbrisi(Kljuc x) {
  54. // zbrisi kljuc x in pripadajoco vrednost,
  55. // ce x ne obstaja, ne naredi nicesar
  56. Imenik<Kljuc,Vrednost> temp = this;
  57. while(!temp.prazen){
  58. if (temp.glava.kljuc.equals(x)){
  59. //sledeci if stavek je namenjem brisanju zadnjega elementa imenika
  60. if (temp.rep.prazen){
  61. temp.glava = null;
  62. temp.rep = null;
  63. temp.prazen = true;
  64. return;
  65. }
  66. temp.glava = temp.rep.glava;
  67. temp.rep = temp.rep.rep;
  68. return;
  69. }
  70. temp = temp.rep;
  71. }
  72. }
  73. public String toString(){
  74. String r = "[";
  75. // v r dodajamo (predstavitve) elementov seznama
  76. Imenik<Kljuc,Vrednost> s = this;
  77. while (!s.prazen) {
  78. r = r + s.glava; // v niz r dodaj predstavitev glave
  79. if (!s.rep.prazen) { r = r + ", "; }
  80. s = s.rep; // pomakni se naprej v seznamu
  81. }
  82. r = r + "]";
  83. return r;
  84. }
  85. }

Pri tem je razred Element sledeč:

  1. public class Element<Kljuc extends Comparable, Vrednost> {
  2. Kljuc kljuc;
  3. Vrednost vrednost;
  4. public Element(Kljuc x, Vrednost y){
  5. kljuc = x;
  6. vrednost = y;
  7. }
  8. public String toString(){
  9. return "" + kljuc + " - " + vrednost;
  10. }
  11. }

Preizkusna aplikacija:

  1. import java.io.*;
  2.  
  3. public class Test {
  4. public static void main(String[] args) throws IOException{
  5. Imenik<String,Double> test = new Imenik<String,Double>();
  6. //Vstavljamo lahko samo objekte, zato vnost 41850868 (kar je integer oz. double) ni dovoljen.
  7. //Integersko stevilo bi torej vnesli z "new Integer(12)"
  8. test.vstavi("Miha",new Double(41850868));
  9. test.vstavi("Ana", new Double(40788365));
  10. test.vstavi("Robert", new Double(41899433));
  11. System.out.println(test);
  12. test.zbrisi("Robert");
  13. System.out.println(test);
  14. }
  15. }
Osebna orodja