ListNode IntList

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Potrebna mi je pomoc oko jednog zadatka: Ostalo mi je da zavrsim sledece metode: reverseI, reverseR. Zadatak bi glasio ovako nekako: Reverses the list. The method must be implemented iteratively. The actual iteration should be performed in the ListNode class. With this method, no new nodes are created and the values of the nodes can not be overwritten.

class IntList {     private class ListNode {         int elem;         ListNode next = null;         ListNode(int elem, ListNode next) {             this.elem = elem;             this.next = next;         }         ListNode reverseI() {             if (next == null) return this;             /* TODO */            return null;         }         ListNode reverseR() {             /* TODO */             return null;         }     }     private ListNode head = null;     public void reverseI() {         /* TODO: */     }     public void reverseR() {         /* TODO:  */     } } public class Main {     // just for testing ...     public static void main(String[] args) {         IntList l1 = new IntList();         l1.add(8);         l1.add(3);         l1.add(123);         System.out.println(l1);     } }

Nedovrsene metode su obelezene sa: "TODO"
Hvala unapred.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Koja bi bila razlika između reverseI i reverseR?

Inače, obrnuta lista se pravi vrlo jednostavno, u jednom prolazu kroz listu. Napraviš samo pomoćni pokazivač tmpHead, i iz liste skidaš element (čvor) sa glave (removeFromHead) i dodaješ taj element na glavu (addToHead) pomoćne pomoćne liste. To odradiš za svaki element početne liste, a zatim kao head liste upišeš tmpHead. Takođe, pomoću steka je moguće obrnuti redosled elemenata liste. Prvo sve elemsnte baciš na stek, a onda ih pokupiš u obrnutom redosledu.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

reverseR treba biti rekurzivna (Recursion) metoda reverseI obicna (Iteration)

Mene inace buni sto moram da implementiram obe klase.

Ja bih to uradio ovako, pomocu samo jedne metode, ali nije tako postavljen zadatak.

public void reverseI() {         /* TODO */         if (head == null || head.next == null)             return;         ListNode Second = head.next;         ListNode Third = Second.next;         Second.next = head;         head.next = null;         if (Third == null)             return;         ListNode CurrentNode = Third;         ListNode PreviousNode = Second;         while (CurrentNode != null) {             ListNode NextNode = CurrentNode.next;             CurrentNode.next = PreviousNode;             PreviousNode = CurrentNode;             CurrentNode = NextNode;         }         head  = PreviousNode;     }

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Napisano: 23 Maj 2015 15:00

Obe klase? Ili obe metode? Dakle, problem je rekurzivna implementacija? Rekurzija je možda i jednostavnija od iterativne. Head trenutne liste ulančaš na kraj liste koju vrati rekurzivni poziv funkcije reverseR za ostatak liste i to je to.

Dopuna: 23 Maj 2015 15:12

Svakako, nejasan si sada. U prvom postu piše da je potrebna isključivo iterativna implementacija, a sada bi ti i rekurzivnu da implementiraš. Ok je ukoliko hoćeš da provežbaš, ali je zadatak postavljen baš tako - kroz iterativnu implementaciju.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Potrebno je implementirati metode reverseR i reverseI u ListNode i u IntList klasi (znaci ukupno 4). ListNode je klasa unutar IntList klase. U prvom postu sam napisao samo deo zadatka, da bih video samo kako to ide. Inace, vise ni ja nista ne razumem.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Vidi, metode za reverse u klasi ListNode treba da vrše svu obradu, i kao rezultat treba da vrate pokazivač na početak odnosno na prvi element (head) obrnute liste. U istoimenim metodama klase IntList samo pozivaš prethodno pomenute metode i njihov rezultat upisuješ u head.

Što se tiče iterativne implementacije, ovo deluje ok. Da li radi kako treba?? Što se tiče rekurzivne implementacije, pokušaj da je odradiš na način koji sam opisao iznad.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Ne razumem, unutar ListNode nemam head. Kako objekad da obrne samog sebe? Ne vredi, radio sam zadatak preko 2 sata i nisam ga zavrsio.

• 1Ovo se svidja korisniku: Nikola04
  
  Registruj se da bi pohvalio/la poruku!

Ne obrće objekat sam sebe, već obrće redosled svojih sledbenika (a svaki ListNode ima listu sledbenika!!), odnosno prelančava ih, i na kraju vraća pokazivač na prvi u listi. Pod pretpostavkom da je tvoj kod za reverseI (uz sitne izmene) tačan, ovako bi otprilike trebalo da izgleda rešenje:
class IntList {     private class ListNode    {         int elem;         ListNode next = null;              //...           ListNode reverseI()       {          ListNote tmpHead = this;                       if (tmpHead.next == null)             return tmpHead;                    ListNode Second = tmpHead.next;          ListNode Third = Second.next;            Second.next = tmpHead;          tmpHead.next = null;              if (Third == null)             return tmpHead;              ListNode CurrentNode = Third;          ListNode PreviousNode = Second;              while (CurrentNode != null)          {             ListNode NextNode = CurrentNode.next;             CurrentNode.next = PreviousNode;             PreviousNode = CurrentNode;             CurrentNode = NextNode;          }          tmpHead  = PreviousNode;                      return tmpHead;                  }     }       private ListNode head = null;        //...       public void reverseI()    {       head = head.reverseI();     } }   public class Main {     // just for testing ...     public static void main(String[] args) {           IntList l1 = new IntList();         l1.add(8);         l1.add(3);         l1.add(123);           System.out.println(l1);     } }

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Dakle, da li je ovo rešenje odgovarajuće??

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Da, malo sam metodu doradio ali odgovara, hvala. Ostala je samo reverseR(), trenutno radim na njoj.