如何在鏈表中按順序插入節點

今天是我在班上學習計算機編程的第三年。我很高興地說，在這幾個月中我已經能夠取得好成績。如果沒有本網站的幫助，通過查看其他問題並調整相似的答案以幫助我完成任務和診斷測試，我不會做到這一點。如何在鏈表中按順序插入節點

現在我有另一個問題，我覺得它是一個巨大的問題。今天，我已經得到了另一位教授的任務（在兩週內完成），涉及員工，雙鏈表和測試，這次我們被允許使用一些快捷方式，但由於大多數方法已經寫入，我們被假定使用這些，因爲它們都不完整，我們應該完成它們。

我遇到了關於方法addInOrder的問題。該算法被設計爲採取一個對象，並將其作爲另一個節點插入其中。雖然我已經重寫了它，以便它可以在最後添加節點（如果對象比其他對象大，或者列表本身爲空），我無法如何添加某些條件以便它可以被添加在列表的中間/開始處。

我調試了它，發現它與我在addInOrder方法中寫下的內容有關，因爲我測試了用於測試的其他方法，並且它們確實沒有錯誤地工作。

如何重寫包含這些條件的方法？

操作系統：Windows 7工作臺的：Eclipse

的類只有2個節點：頭，尾。它還使用一個稱爲Employee的導入類（我已經完成了，沒有錯誤）。

public void addInOrder(Employee employee) { 
    Node Previous = null; 
    Node position = head; 
    while(position != null){ 
     if(position.getEmployee().compareTo(employee) > 0){ 
      this.setHead(new Node(employee,position.getPrevious(), position)); 
      return; 
     } 
     Previous = position; 
     position = position.getNext(); 
    } 
    if(isEmpty() == true || head == null || Previous.getNext() == null) 
     this.add(employee); 


}

編輯：這實際上是AddInOrder方法。

public void testAddInOrder() { 
    EmployeeList list = new EmployeeList(); 
    list.addInOrder(new Employee("d", 12.5)); 
    list.addInOrder(new Employee("e", 13.5)); 
    list.addInOrder(new Employee("a", 12.5)); 
    list.addInOrder(new Employee("g", 13.5)); 
    list.addInOrder(new Employee("c", 13)); 
    list.addInOrder(new Employee("a", 12.5)); 
    list.addInOrder(new Employee("b", 13.5)); 
    list.addInOrder(new Employee("d", 12.8)); 
    list.addInOrder(new Employee("b", 13)); 
    //A12.5 B13 B13 B13.5 C13 D12.5 D12.8 E13.5 G13.5 
    assertEquals("a",list.get(0).getName()); 
    assertEquals("a",list.get(1).getName()); 
    assertEquals("b",list.get(2).getName()); 
    assertEquals("b",list.get(3).getName()); 
    assertEquals("c",list.get(4).getName()); 
    assertEquals("d",list.get(5).getName()); 
    assertEquals("d",list.get(6).getName()); 
    assertEquals("e",list.get(7).getName()); 
    assertEquals("g",list.get(8).getName()); 
    assertEquals(12.5, list.get(0).getSalaryRate(), 0.01); 
    assertEquals(12.5, list.get(1).getSalaryRate(), 0.01); 
    assertEquals(13, list.get(2).getSalaryRate(), 0.01); 
    assertEquals(13.5, list.get(3).getSalaryRate(), 0.01); 
    assertEquals(13, list.get(4).getSalaryRate(), 0.01); 
    assertEquals(12.5, list.get(5).getSalaryRate(), 0.01); 
    assertEquals(12.8, list.get(6).getSalaryRate(), 0.01); 
    assertEquals(13.5, list.get(7).getSalaryRate(), 0.01); 
    assertEquals(13.5, list.get(8).getSalaryRate(), 0.01); 
}

這是伴隨它的測試。

來源

2014-01-26 user3101890

public void addInOrder(Employee employee){ 

if (head==null){//if your list is empty just insert it in the beginning 
head=new Node(employee); 
return; 
}//end if(head==null) 


if (head.getNext()==null)//if we have one node only{ 
if(position.getEmployee().compareTo(employee) > 0){//if it should be replaced than put it in the beginning 
Node node=new Node(employee); 
node.setNext(head); 
head=node; 
node.getNext().setPrevious(node); 
return; 
    } 
else{ 
//add it to the end,i am assuming you know how to do that,if not than comment on my answer. 
return; 
     } 
} 
else{ 
Node position=head; 
while(position!=null){ 
if(position.getEmployee().compareTo(employee) > 0){ 
Node node=new Node(employee);   //you should add the node before position 
node.setNext(position);     //so set the node's next to position 
node.setPrevious(position.getPrevious());//set the node's previous to position's previous 
position.getPrevious.setNext(node);  //set the next of position's previous to node 
return;//and exit 
      } 
position=position.getNext();//else continue looping through the list 
     } 
//if we looped through the whole array and we haven't inserted the node so we didn't    exit the method,than add it to the end. 
Node n=new Node(employee); 

position.setNext(new Node(n); 
n.setPrevious(position); 
    } 


}

來源

2014-01-26 07:52:42

下面介紹如何考慮寫這個：假設你有一個按順序排列的列表。如果您知道這是真的，您可以輕鬆地添加一個項目順序通過列表，直到插入的項目大於前一個項目，並且小於或等於下一個項目。在這一點上，只需將前一個指向to_insert並將to_insert指向下一個即可，而且你很棒。如果你這樣做，你的名單保持秩序。要處理初始插入，您可以簡單地先在該循環外部使用該案例：如果要插入的項目在第一個項目之前排序，請在第一個項目之前插入並返回。

您還知道，沒有項目的列表是按順序排列的，所以您始終可以按照排序順序的列表開始。所以這不應該很難做 - 只要寫我上面描述的方法。由於這是一項家庭作業，我不會評論你的代碼，但如果你提出關於它的具體問題，我可能會提供一個提示。

來源

2014-01-26 06:25:41

我能想到的方式---->在insert add語句中遍歷列表並找到最佳位置。喜歡的東西

while (tempptr->next != NULL && tempptr->data >= nodelist->data)
if true----> insert in that position

來源

2014-01-26 07:03:21

如何在鏈表中按順序插入節點

回答

相關問題