DoublyLinkedList使用尾遞歸 - InsertItem

我目前正在嘗試創建使用尾遞歸的DoublyLinked列表。DoublyLinkedList使用尾遞歸 - InsertItem

我有我的addItem充分工作。我的插入項成功插入並在指定的索引項。但是，它會刪除所有項目，並且不會移動所有數據。我的代碼在試圖在索引1處添加時也崩潰了。我已經註釋掉了我試圖使其工作的代碼。

這裏是我的節點類：

public class DLLNode 
{ 
    private DLLNode previous; 
    public DLLNode next; 
    private String value; 

    public DLLNode(String value) 
    { 
     this.value = value; 
     this.previous = previous; 
     this.next = next; 
    } 

    public DLLNode(String value, DLLNode next, DLLNode previous) 
    { 
     this.value = value; 
     this.next = next; 
     this.previous = previous; 
    } 

    public String GetDataItem() 
    { 
    return value; 
    } 

    public void setDataItem() 
    { 
     this.value = value; 
    } 

    public DLLNode GetPreviousNode() 
    { 
    return previous; 
    } 

    public void setPrevious(DLLNode previous) 
    { 
     this.previous = previous; 
    } 

    public DLLNode GetNextNode() 
    { 
    return next; 
    } 

    public void setNextNode(DLLNode next) 
    { 
     this.next = next; 
    } 

    public void addItem(String value) { 
    if(this.next == null) { 
      DLLNode newNode = new DLLNode(value); 
      this.next = newNode; 
    } else { 
      this.next.addItem(value); 
    } 
} 


    public void InsertItemHelper(String value, int indexToInsert, int current, DLLNode currNode) 
    { 
     /*if (indexToInsert == 1) 
     { 
      DLLNode newNode = new DLLNode(value); 
      currNode.setNextNode(newNode); 
     }*/ 
     if (current == indexToInsert-2) 
     { 
      DLLNode newNode = new DLLNode(value); 
      currNode.setNextNode(currNode.GetNextNode().GetNextNode()); 
      newNode.setNextNode(currNode.GetNextNode()); 
      currNode.setNextNode(newNode); 
      newNode.setPrevious(currNode); 
     } 
     else 
     { 
      InsertItemHelper(value, indexToInsert, current+1, currNode.GetNextNode()); 
     } 
    } 

    public void DeleteItemHelper(int indexToDelete, int current, DLLNode currNode) 
    { 
     if (current == indexToDelete-2) 
     { 
      currNode.setNextNode(currNode.GetNextNode().GetNextNode()); 
     } 
     else 
     { 
      DeleteItemHelper(indexToDelete, current+1, currNode.GetNextNode()); 
     } 
    } 



}

這裏是我的DoublyLinkedList類。任何幫助和提示非常感謝。

public class DoublyLinkedList 
{ 
    private int noOfItems; 
    private DLLNode head; 
    private DLLNode tail; 
    // Default constructor 
    public DoublyLinkedList() 
    { 
    head = null; 
    tail = null; 
    this.noOfItems = 0; 

    } 


    public int GetNoOfItems() 
    { 
    return noOfItems; 
    } 

    /* Returns the String value held at index (base zero) or null if the index 
    * is out of bounds */ 
    public String GetItemByIndex(int index) 
    { 
    return null; 
    } 


    public DLLNode GetNodeByIndex(int index) 
    { 
    return null; 
    } 


    public void AddItem(String value) 
    { 
     if (head == null) 
     { 
      DLLNode newNode = new DLLNode(value); 
      head = newNode; 
      noOfItems++; 
     } 
     else 
     { 
     head.addItem(value); 
     noOfItems++; 
     } 
     } 



    public void InsertItem(int index, String value) 
    { 
     if (index > noOfItems) 
     { 
      AddItem(value); 
     } 
     else { 
     head.InsertItemHelper(value, index, 0, head); 
     noOfItems++; 
     } 


    } 


    public void DeleteItem(int index) 
    { 

      if (index ==0) 
      { 
       System.out.println("Out of Bounds"); 
      } 
      if (index > noOfItems) 
      { 
      System.out.println("Out of Bounds"); 
      } 
      if (head == null) 
      { 
       System.out.println("No Item to remove"); 
      } 
      else if (index == 1) 
      { 
       head = head.GetNextNode(); 
       noOfItems--; 
      } 
      else 
      { 
       head.DeleteItemHelper(index, 0, head); 
       noOfItems--; 
      } 

    } 

    public int getNoOfItems() 
    { 
     return this.noOfItems; 
    } 

    public boolean isEmpty() 
    { 
     return (head == null); 
    } 


}

來源

2016-12-13 benjano

「使用尾遞歸」尾遞歸是什麼？ – byxor

在我的DLLNode類中 - 我用於添加，刪除和插入的所有方法都需要使用尾遞歸。所以他們每個人都把自己稱爲職能的最後階段。 – benjano

你應該從小處開始。與其試圖一次實施所有3種方法，一次只做一項。如果您在使用_specific_時遇到問題，那麼尋求幫助會更容易。 – byxor

想想是怎麼回事：

currNode.setNextNode(currNode.GetNextNode().GetNextNode()); 
newNode.setNextNode(currNode.GetNextNode()); 
currNode.setNextNode(newNode); 
newNode.setPrevious(currNode);

您的片段分析

讓A:= currnode; B:=currnode.getNextNode(); C:=currnode.getNextNode();

因此，我們必須像一個 - 「乙 - > C

currNode.setNextNode(currNode.GetNextNode().GetNextNode());

A - >Ç

newNode.setNextNode(currNode.GetNextNode());

newNode - 「ç

currNode.setNextNode(newNode);

A - > newNode - 從newNode>Ç

newNode.setPrevious(currNode);

組反向鏈接到甲

什麼，你可能想要做

newNode.setNextNode(currNode.getNextNode());

newNode - >乙

現在我們可以從currNode鏈接更改爲newNode

currNode.setNextNode(newNode);

A - > newNode

所以，現在你應該有像A - > newNode - > B沒有n因此永遠碰觸C.

所以現在你可以修復反向鏈接，你就完成了。的B

currNode.getNextNode().setPrevious(newNode);

一套反向鏈接到newNode

newNode.setPrevious(currNode);

一套反向從newNode到currNode

P.S：我沒有測試這一點。我沒有看自己的if條件，我沒有考慮你的箱等等。我仍然希望能夠告訴你一個錯誤是從哪裏來的，並指出你在正確的方向。。

pps：遵守standard java naming conventions是一種很好的做法 - 方法名應該以小寫字母開頭。

來源

2016-12-13 15:57:17 dingalapadum

真棒謝謝！立即就能發揮作用。 – benjano

@benjano你可能想接受這個答案，所以其他人不費心再次回答 - 只是說;） – dingalapadum

哎呀抱歉！以爲我已經接受了答案！ – benjano

DoublyLinkedList使用尾遞歸 - InsertItem

回答

相關問題