ListNode IntList

1

ListNode IntList

offline
  • Niko E
  • Software & Information Engineering
  • Pridružio: 05 Maj 2009
  • Poruke: 135
  • Gde živiš: Wien

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.



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
offline
  • Milan
  • Pridružio: 17 Dec 2007
  • Poruke: 14809
  • Gde živiš: Niš

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.



offline
  • Niko E
  • Software & Information Engineering
  • Pridružio: 05 Maj 2009
  • Poruke: 135
  • Gde živiš: Wien

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;     }

offline
  • Milan
  • Pridružio: 17 Dec 2007
  • Poruke: 14809
  • Gde živiš: Niš

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.

offline
  • Niko E
  • Software & Information Engineering
  • Pridružio: 05 Maj 2009
  • Poruke: 135
  • Gde živiš: Wien

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.

offline
  • Milan
  • Pridružio: 17 Dec 2007
  • Poruke: 14809
  • Gde živiš: Niš

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.

offline
  • Niko E
  • Software & Information Engineering
  • Pridružio: 05 Maj 2009
  • Poruke: 135
  • Gde živiš: Wien

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

offline
  • Milan
  • Pridružio: 17 Dec 2007
  • Poruke: 14809
  • Gde živiš: Niš

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);     } }

offline
  • Milan
  • Pridružio: 17 Dec 2007
  • Poruke: 14809
  • Gde živiš: Niš

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

offline
  • Niko E
  • Software & Information Engineering
  • Pridružio: 05 Maj 2009
  • Poruke: 135
  • Gde živiš: Wien

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

Ko je trenutno na forumu
 

Ukupno su 893 korisnika na forumu :: 49 registrovanih, 8 sakrivenih i 836 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 3466 - dana 01 Jun 2021 17:07

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: Alibaba1981, anta, babaroga, Bane san, bojcistv, CikaKURE, darionis, Dorcolac, dragoljub11987, DrugiREI, FileFinder, FOX, GandorCC, hologram, janbo, Još malo pa deda, Kaplar2, krkalon, Kubovac, kybonacci, mercedesamg, Mi lao shu, MikeHammer, Mikulino, milenko crazy north, milutin134, mnn2, moldway, Nobunaga, powSrb, procesor, raketaš, robert1979, royst33, ruma, sasakrajina, Sirius, slonic_tonic, Srle993, stegonosa, tmanda323, Toper, vathra, voja64, VP6919, vukovi, wolverined4, x9, zuxbg