kodovi/liste/Palindrom.java

   1 /**
   2  * Demonstracija upotrebe dvostruko povezane liste za odredjivanje svih
   3  * palindroma u listi znakova.
   4  *
   5  */
   6 public class Palindrom {
   7
   8         static void interaktivniTest() {
   9                 DPLista lista = new DPLista();
  10                 System.out.println("Unesite rec znak po znak, zavrsite unos tackom:");
  11                 char ulaz = Svetovid.in.readChar();
  12                 while (ulaz != '.') {
  13                         lista.ubaciNaKraj(ulaz);
  14                         ulaz = Svetovid.in.readChar();
  15                 }
  16                 System.out.println("Uneta rec je:" + lista);
  17         }
  18
  19         static void testRec(String rec) {
  20                 System.out.println("= Rec:");
  21                 System.out.println(rec);
  22                 DPLista lista = new DPLista();
  23                 lista.ubaciString(rec);
  24                 System.out.println("= Palindromi:");
  25                 lista.stampajSvePalindrome();
  26         }
  27
  28         public static void main(String[] args) {
  29                 // interaktivniTest();
  30                 testRec("abakus");
  31                 testRec("anavolimilovana");
  32                 testRec("nekoliko brodskih kapaka");
  33                 testRec("");
  34                 testRec(" ");
  35         }
  36
  37 }
  38
  39 /**
  40  * Dvostruko povezana lista znakova koja omogucava provere palindroma
  41  * u okviru liste. Lista ima pokazivace na prvi i poslednji element.
  42  */
  43 class DPLista {
  44
  45         /**
  46          * Klasa predstavlja jedan element dvostruko povezane liste sa pokazivacima
  47          * na prethodni i sledeci, kao i poljem info koje sadrzi znak.
  48          */
  49         class Znak {
  50                 char info;
  51                 Znak sledeci;
  52                 Znak prethodni;
  53
  54                 public Znak(char c) {
  55                         this.info = c;
  56                         this.sledeci = null;
  57                         this.prethodni = null;
  58                 }
  59
  60                 public String toString() {
  61                         return info + "";
  62                 }
  63         }
  64
  65         Znak prvi;
  66         Znak poslednji;
  67
  68         /** Kreira novu praznu dvostruko povezanu listu znakova */
  69         public DPLista() {
  70                 prvi = null;
  71                 poslednji = null;
  72         }
  73
  74         public String toString() {
  75                 String rez = "";
  76                 Znak tekuci = prvi;
  77                 while (tekuci != null) {
  78                         rez += tekuci.info;
  79                         tekuci = tekuci.sledeci;
  80                 }
  81                 return rez;
  82         }
  83
  84         public void ubaciNaKraj(char c) {
  85                 Znak novi = new Znak(c);
  86                 if (poslednji == null) {
  87                         prvi = novi;
  88                         poslednji = novi;
  89                 } else {
  90                         novi.prethodni = poslednji;
  91                         poslednji.sledeci = novi;
  92                         poslednji = novi;
  93                 }
  94         }
  95
  96         public void ubaciString(String rec) {
  97                 for (int i = 0; i < rec.length(); i++) {
  98                         ubaciNaKraj(rec.charAt(i));
  99                 }
 100         }
 101
 102         /**
 103          * pomocni metod za nalazenje podreci oznacene sa dva pokazivaca. ne vrsi
 104          * nikakve provere o validnosti datih argumenata.
 105          */
 106         public String podRec(Znak pocetak, Znak kraj) {
 107                 String rez = "";
 108                 Znak tekuci = pocetak;
 109                 while (tekuci != kraj) {
 110                         rez += tekuci.info;
 111                         tekuci = tekuci.sledeci;
 112                 }
 113                 rez += tekuci.info;
 114                 return rez;
 115         }
 116
 117         /**
 118          * Proverava da li je rec koja pocinje od pokazivaca pocetak do pokazivaca
 119          * kraj predstavlja palindrom. Ne vrsi se nikakva provera validnosti prosledjenih
 120          * pokazivaca, tako da metod moze da baci izuzetak u slucaju null pointera, kao i
 121          * da radi beskonacno dugo u nekim slucajevima.
 122          */
 123         public boolean jePalindrom(Znak pocetak, Znak kraj) {
 124                 while ((pocetak != kraj) && (pocetak.sledeci != kraj)) {
 125                         if (pocetak.info != kraj.info) {
 126                                 return false;
 127                         } else {
 128                                 pocetak = pocetak.sledeci;
 129                                 kraj = kraj.prethodni;
 130                         }
 131                 }
 132                 return pocetak.info == kraj.info;
 133         }
 134
 135         /**
 136          * Stampa sve podreci ove reci koje su palindromi na ekran.
 137          */
 138         public void stampajSvePalindrome() {
 139                 Znak pocetak = prvi;
 140                 while (pocetak != null) {
 141                         Znak kraj = poslednji;
 142                         while (kraj != pocetak) {
 143                                 if (jePalindrom(pocetak, kraj)) {
 144                                         System.out.println(podRec(pocetak, kraj));
 145                                 }
 146                                 kraj = kraj.prethodni;
 147                         }
 148                         pocetak = pocetak.sledeci;
 149                 }
 150         }
 151 }