gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
summary | shortlog | log | commit | commitdiff | tree
raw | patch | inline | side by side (parent: 5dbfd96)
raw | patch | inline | side by side (parent: 5dbfd96)
| author | Doni Pracner <donny@rarogl> | |
| Tue, 24 Mar 2015 18:44:34 +0000 (19:44 +0100) | ||
| committer | Doni Pracner <donny@rarogl> | |
| Tue, 24 Mar 2015 18:44:34 +0000 (19:44 +0100) |
| kodovi/liste/ListePrimeriOperacija.java | [new file with mode: 0644] | patch | blob |
| kodovi/liste/ListeSaDodavanjemNaKraj.java | [new file with mode: 0644] | patch | blob |
diff --git a/kodovi/liste/ListePrimeriOperacija.java b/kodovi/liste/ListePrimeriOperacija.java
--- /dev/null
@@ -0,0 +1,429 @@
+import org.svetovid.io.SvetovidIOException;
+
+/**
+ * Primer razlicitih operacija nad listama. Program je predstavljen kao
+ * interaktivni meni radi boljeg ilustrovanja operacija i njihovog ucinka.
+ */
+public class ListePrimeriOperacija {
+ static ListaBrojevaBr lista;
+
+ public static void main(String[] args) {
+ // inicijalizujemo listu
+ lista = new ListaBrojevaBr();
+
+ char menu = 'a';
+
+ while (menu != 'Q') {
+ System.out.println();
+ System.out.println("Ilustracija rada sa listama brojeva");
+ System.out.println("======================================");
+ System.out.println("s-Stampa");
+ System.out.println("u-Unos liste");
+ System.out.println("k-Stampanje k-tog elementa");
+ System.out.println("d-dodavanje elementa na pocetak");
+ System.out.println("o-dodavanje elementa na k-to mesto");
+ System.out.println("i-Izbacivanje br iz liste");
+ System.out.println("v-Izbacivanje svih br iz liste");
+ System.out.println("e-Izbacivanje k-tog elementa");
+ System.out.println("m-Minimalni broj u listi");
+ System.out.println("p-Pretraga elementa u listi");
+ System.out.println();
+ System.out.println("q-Kraj rada (Quit)");
+ menu = Svetovid.in.readChar();
+ menu = Character.toUpperCase(menu);
+ switch (menu) {
+ case 'S':
+ lista.stampajNaEkran();
+ break;
+ case 'U':
+ unosBrojeva();
+ break;
+ case 'D':
+ int broj = Svetovid.in.readInt("Broj koji dodajete:");
+ lista.dodajNaPocetak(broj);
+ break;
+ case 'O':
+ broj = Svetovid.in.readInt("Broj koji dodajete:");
+ int pos = Svetovid.in.readInt("Pozicija na koju dodajete:");
+ lista.dodaj(broj, pos);
+ break;
+ case 'I':
+ izbacivanjeEl();
+ break;
+ case 'V':
+ izbacivanjeElSvi();
+ break;
+ case 'E':
+ izbacivanjeK();
+ break;
+ case 'K':
+ stampajK(lista);
+ break;
+ case 'M':
+ Svetovid.out.println("Minimum liste je:" + lista.minimum());
+ break;
+ case 'P':
+ pretraga();
+ break;
+ default:
+ break;
+ }
+ if (menu != 'Q') {
+ Svetovid.out.println(" -- enter za povratak u meni --");
+ Svetovid.in.readLine();
+ }
+ }
+ }
+
+ static void unosBrojeva() {
+ System.out.println("unesite n (broj brojeva): ");
+ int n = Svetovid.in.readInt();
+ System.out.println("unesite brojeve");
+ for (int i = 0; i < n; i++) {
+ int br = Svetovid.in.readInt();
+ lista.dodajNaPocetak(br);
+ }
+ }
+
+ static void pretraga() {
+ int broj = Svetovid.in.readInt("Unesite broj koji trazite:");
+ if (lista.uListi(broj)) {
+ Svetovid.out.println("Broj postoji u listi");
+ } else {
+ Svetovid.out.println("Broj ne postoji u listi");
+ }
+ }
+
+ static void stampajK(ListaBrojevaBr lista2) {
+ int broj = Svetovid.in
+ .readInt("Unesite redni broj elementa koji zelite:");
+ try {
+ Svetovid.out.println("Element na mestu " + broj + " je "
+ + lista.element(broj));
+ } catch (Exception e) {
+ Svetovid.out.println("Greska: " + e.getMessage());
+ }
+
+ }
+
+ static void izbacivanjeK() {
+ int broj = Svetovid.in.readInt("Unesite poziciju koju treba izbaciti:");
+ if (lista.izbaciK(broj)) {
+ Svetovid.out.println("Pozicija je izbacena iz liste");
+ } else {
+ Svetovid.out.println("Pozicija ne postoji u listi");
+ }
+ }
+
+ static void izbacivanjeElSvi() {
+ int broj = Svetovid.in.readInt("Unesite broj koji treba izbaciti:");
+
+ Svetovid.out.println("Izbaceno je " + lista.izbaciIzListeSve(broj)
+ + "brojeva");
+
+ }
+
+ static void izbacivanjeEl() {
+ int broj = Svetovid.in.readInt("Unesite broj koji treba izbaciti:");
+ if (lista.izbaciIzListe(broj)) {
+ Svetovid.out.println("Broj je izbacen iz liste");
+ } else {
+ Svetovid.out.println("Broj ne postoji u listi");
+ }
+ }
+
+}
+
+/**
+ * Povezana lista brojeva sa operacijama nad njom i brojace elemenata. Lista u
+ * svakom momentu moze da efikasno vrati broj elemenata u njoj.
+ */
+class ListaBrojevaBr {
+ class Element {
+ int info;
+ Element veza;
+
+ public Element(int br) {
+ this.info = br;
+ this.veza = null;
+ }
+
+ public String toString() {
+ return info + "";
+ }
+ }
+
+ // pokazivac na prvi element liste
+ Element prvi;
+
+ // interni brojac koji pomaze kod nekih operacija
+ int brojElemenata;
+
+ /** Kreira praznu listu brojeva. */
+ public ListaBrojevaBr() {
+ this.prvi = null;
+ this.brojElemenata = 0;
+ }
+
+ /** vraca broj elemenata u listi */
+ public int velicina() {
+ return brojElemenata;
+ }
+
+ /** Vraca da li je lista prazna */
+ public boolean jePrazna() {
+ return prvi == null;
+ }
+
+ public void dodajNaPocetak(int br) {
+ Element novi = new Element(br);
+ novi.veza = prvi;
+ prvi = novi;
+ brojElemenata++;
+ }
+
+ public void stampajNaEkran() {
+ if (prvi == null) {
+ Svetovid.out.println("Lista je prazna");
+ } else {
+ Svetovid.out.println("Sadrzaj liste duzine:"+velicina());
+ Element tekuci = prvi;
+ while (tekuci != null) {
+ System.out.println(tekuci.info);
+ tekuci = tekuci.veza;
+ }
+ System.out.println();
+ }
+ }
+
+ public String toString() {
+ String rez = "Lista: [ ";
+ Element tekuci = prvi;
+ while (tekuci != null) {
+ rez += tekuci.info + " ";
+ tekuci = tekuci.veza;
+ }
+ rez += "]";
+ return rez;
+ }
+
+ /**
+ * Vraca vrednost k-tog elementa. Prvi element liste je na mestu 0, drugi na
+ * mestu 1 i tako dalje. Ne postoje elementi na negativnim pozicijama. U
+ * slucaju nepostojeceg indeksa baca IndexOutOfBounds izuzetak.
+ *
+ * @throws IndexOutOfBoundsException
+ */
+ public int element(int k) {
+ if (k < 0) {
+ throw new IndexOutOfBoundsException(
+ "Ne postoje elementi na negativnim pozicijama!");
+ }
+
+ if (k < brojElemenata) {
+ Element tekuci = prvi;
+ int br = 0;
+ while (br < k) {
+ tekuci = tekuci.veza;
+ br++;
+ }
+ return tekuci.info;
+ } else {
+ throw new IndexOutOfBoundsException("Lista je kraca od "
+ + k);
+ }
+ }
+
+ // alternativna verzija procedure koja bi radila ako nemamo brojElemenata
+ // kao polje
+ public int elementB(int k) {
+ if (k < 0) {
+ throw new IndexOutOfBoundsException(
+ "Ne postoje elementi na negativnim pozicijama!");
+ }
+
+ Element tekuci = prvi;
+ int brojac = 0;
+
+ while (tekuci != null && k > brojac) {
+ tekuci = tekuci.veza;
+ brojac++;
+ }
+
+ if (tekuci != null) {
+ return tekuci.info;
+ } else {
+ throw new IndexOutOfBoundsException("Lista je kraca od "
+ + k);
+ }
+ }
+
+ /** Vraca minimum liste. U slucaju prazne liste vratice maksimalni Integer. */
+ public int minimum() {
+ int min = Integer.MAX_VALUE;
+
+ Element tekuci = prvi;
+ while (tekuci != null) {
+ if (tekuci.info < min) {
+ min = tekuci.info;
+ }
+ tekuci = tekuci.veza;
+ }
+
+ return min;
+ }
+
+ /** Vraca da li broj br postoji u listi. */
+ public boolean uListi(int br) {
+ Element tekuci = prvi;
+ while (tekuci != null && tekuci.info != br) {
+ tekuci = tekuci.veza;
+ }
+
+ // ako smo dosli do kraja liste i nismo ga nasli
+ // tekuci ce biti jednako null
+ return tekuci != null;
+ }
+
+ /**
+ * Dodaje broj 'br' na poziciju 'pos'. Ako je pozicija negativna, broj ce
+ * biti dodat na prvo mesto. Ako je pozicija veza od broja elemenata, broj
+ * ce biti dodat na poslednje mesto.
+ *
+ * @param br
+ * broj koji se dodaje u listu
+ * @param pos
+ * pozicija na koju se broj dodaje
+ */
+ public void dodaj(int br, int pos) {
+ Element novi = new Element(br);
+
+ // proverimo i popravimo pos po potrebi
+ if (pos < 0)
+ pos = 0;
+ if (pos > brojElemenata) {
+ pos = brojElemenata;
+ }
+
+ // dodavanje na pocetak je jednostavno
+ if (pos == 0) {
+ novi.veza = prvi;
+ prvi = novi;
+ brojElemenata++;
+ } else {
+ // inace nam treba prethodni element
+ Element prethodni = prvi;
+ int brojac = 0;
+ while (prethodni != null && brojac < pos - 1) {
+ prethodni = prethodni.veza;
+ brojac++;
+ }
+ novi.veza = prethodni.veza;
+ prethodni.veza = novi;
+ brojElemenata++;
+ }
+ }
+
+ /**
+ * Izbacuje broj 'br' iz liste, naravno ako postoji i vraca da li je
+ * operacija uspesno obavljena.
+ */
+ public boolean izbaciIzListe(int br) {
+ // proverimo da li je prvi element
+ if (prvi != null && prvi.info == br) {
+ prvi = prvi.veza;
+ return true;
+ } else {
+ /* trazimo u ostatku liste */
+ Element tekuci, prethodni;
+ tekuci = prvi;
+ prethodni = null;
+ while (tekuci != null && tekuci.info != br) {
+ /*
+ * dok ne dodjemo do kraja liste ili ne nadjemo broj
+ */
+ prethodni = tekuci;
+ tekuci = tekuci.veza;
+ }
+ if (tekuci != null) {
+ /*
+ * znaci da nismo na kraju liste, odnosno da smo nasli broj,
+ * prevezemo listu oko elementa
+ */
+ prethodni.veza = tekuci.veza;
+ brojElemenata--;
+ return true;
+ } else {
+ return false;
+ }
+ }
+ }
+
+ /**
+ * Izbacuje sve brojeve 'br' iz liste, naravno ako postoje i vraca koliko ih
+ * je bilo.
+ */
+ public int izbaciIzListeSve(int br) {
+ int brojac = 0;
+
+ /* uklanjamo sa pocetka koliko je potrebno */
+ while (prvi != null && prvi.info == br) {
+ prvi = prvi.veza;
+ brojac++;
+ }
+
+ Element tekuci, prethodni;
+ /* trazimo u ostatku liste */
+ if (prvi != null) {
+ tekuci = prvi;
+ while (tekuci.veza != null) {
+ /* idemo korak po korak do poslednjeg elementa liste */
+ prethodni = tekuci;
+ tekuci = tekuci.veza;
+ if (tekuci.info == br) {
+ /* prevezemo listu oko elementa */
+ prethodni.veza = tekuci.veza;
+ brojac++;
+ /*
+ * vracamo se jedan korak da bi u novom krugu proverili i
+ * ovaj element
+ */
+ tekuci = prethodni;
+ }
+ }
+ }
+ brojElemenata -= brojac;
+ return brojac;
+ }
+
+ /**
+ * Izbacuje K-ti element iz liste. Vraca da li je uspesno izbacen. Ako je
+ * lista prekratka vratice false.
+ */
+ public boolean izbaciK(int k) {
+ if (k >= brojElemenata) {
+ return false;
+ }
+ if (k < 0) {
+ return false;
+ }
+ // da li izbacujemo prvog?
+ if (k == 0) {
+ prvi = prvi.veza;
+ } else {
+ // brojimo do elementa pre onog koji izbacujemo
+ Element prethodni = prvi;
+ int brojac = 0;
+
+ while (k - 1 > brojac) {
+ prethodni = prethodni.veza;
+ brojac++;
+ }
+ // prevezemo oko k
+ prethodni.veza = prethodni.veza.veza;
+ }
+ brojElemenata--;
+ return true;
+ }
+
+}
diff --git a/kodovi/liste/ListeSaDodavanjemNaKraj.java b/kodovi/liste/ListeSaDodavanjemNaKraj.java
--- /dev/null
@@ -0,0 +1,104 @@
+public class ListeSaDodavanjemNaKraj {
+
+ public static void main(String[] args) {
+ ListaBrojevaKraj listak = new ListaBrojevaKraj();
+ listak.dodajNaKraj(4);
+ listak.dodajNaKraj(5);
+
+ listak.dodajNaPocetak(3);
+ listak.dodajNaPocetak(2);
+
+ listak.dodajNaKraj(6);
+
+ listak.dodajNaPocetak(1);
+
+ listak.stampajNaEkran();
+ }
+
+}
+
+/**
+ * Lista brojeva sa mogućnošću dodavanja na kraj.
+ */
+class ListaBrojevaKraj {
+
+ /**
+ * Element u klasi ListaBrojeva. Sadrzi informaciju, odnosno broj i
+ * pokazivac na sledeci element u listi.
+ */
+ class Element {
+ int info;
+ Element veza;
+
+ public Element(int br) {
+ this.info = br;
+ this.veza = null;
+ }
+
+ public String toString() {
+ return info + "";
+ }
+ }
+
+ // pokazivac na prvi element liste
+ Element prvi;
+ // pokazivac na poslednji element liste
+ Element poslednji;
+
+ /** Kreira praznu listu brojeva. */
+ public ListaBrojevaKraj() {
+ this.prvi = null;
+ this.poslednji = null;
+ }
+
+ /** Dodaje novi broj na pocetak liste */
+ public void dodajNaPocetak(int br) {
+ Element novi = new Element(br);
+ novi.veza = prvi;
+ prvi = novi;
+ if (poslednji == null){
+ poslednji = novi;
+ }
+ }
+
+ public void dodajNaKraj(int br) {
+ if (poslednji == null) {
+ dodajNaPocetak(br);
+ } else {
+ Element novi = new Element(br);
+ poslednji.veza = novi;
+ poslednji = novi;
+ }
+ }
+
+ /** Vraca da li je lista prazna */
+ public boolean jePrazna() {
+ return prvi == null;
+ }
+
+ public void stampajNaEkran() {
+ if (jePrazna()) {
+ Svetovid.out.println("Lista je prazna");
+ } else {
+ Svetovid.out.println("Sadrzaj liste:");
+ Element tekuci = prvi;
+ while (tekuci != null) {
+ System.out.println(tekuci.info);
+ tekuci = tekuci.veza;
+ }
+ System.out.println();
+ }
+ }
+
+ public String toString() {
+ String rez = "Lista: [ ";
+ Element tekuci = prvi;
+ while (tekuci != null) {
+ rez += tekuci.info + " ";
+ tekuci = tekuci.veza;
+ }
+ rez += "]";
+ return rez;
+ }
+
+}
\ No newline at end of file