4

我已经在这个实验室任务上工作了几个小时，但不明白为什么这段代码不起作用。问题是添加int removeEvery(T item)删除所有出现的item并将删除的item的数量返回给实现链接列表接口的链接列表类的方法。

这是我的代码：它删除了该项目的一些出现，但不是全部。

public int removeEvery(T item){
int index = 0;
Node currentNode = firstNode;
for(int i = 1; i <= numberOfEntries; i++)
    {
    System.out.println(currentNode.getData());
        if (item.equals(currentNode.getData())){
            index++;
            remove(i);}
        else{
            currentNode = currentNode.getNextNode();}
    } 
        if(index != 0)
        return index;
    return -1;
}

这是 LinkList 类中包含的 remove 方法：

public T remove(int givenPosition)
{
  T result = null;                 // return value

  if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
  {
     assert !isEmpty();
     if (givenPosition == 1)        // case 1: remove first entry
     {
        result = firstNode.getData();     // save entry to be removed 
        firstNode = firstNode.getNextNode();
        if (numberOfEntries == 1)
           lastNode = null; // solitary entry was removed
        }
        else                           // case 2: givenPosition > 1
        {
           Node nodeBefore = getNodeAt(givenPosition - 1);
           Node nodeToRemove = nodeBefore.getNextNode();
           Node nodeAfter = nodeToRemove.getNextNode();
           nodeBefore.setNextNode(nodeAfter);  // disconnect the node to be removed
           result = nodeToRemove.getData();  // save entry to be removed

           if (givenPosition == numberOfEntries)
              lastNode = nodeBefore; // last node was removed
     } // end if

     numberOfEntries--;
  } // end if

  return result;                   // return removed entry, or 
                                  // null if operation fails
} // end remove
4

4 回答 4

1

我认为您遇到的问题来自remove(i).

当你删除i-th元素时，i+1-th元素变成了i-th等等：每个元素都被移动了。因此，如果您需要删除列表中位于 indexj和的 2 个元素，则j+1删除j-th元素调用remove(j)将移动j+1-thindex 处的元素j。因此，删除第二个元素需要remove(j)再次调用，而不是remove(j+1).

所以你需要i在删除后递减。

由于您的remove方法实际上递减numberOfEntries，因此while循环上的条件已正确更新。所以你需要做的就是更换

if (item.equals(currentNode.getData())) {
    index++;
    remove(i);
}
else {
    currentNode = currentNode.getNextNode();
}

经过

if (item.equals(currentNode.getData())) {
    index++;
    remove(i--);
}
// update the current node, whether removing it or not
currentNode = currentNode.getNextNode();

迭代器.remove()

您描述的这个问题显示了Iterator.remove()在使用 JDK 中的数据结构来遍历可迭代集合并在您遍历它时删除元素时的有用性。

于 2013-03-06T08:58:23.530 回答
1

您的链表有一些特别之处，您可以使用 current.getNextNode 访问下一个元素，但您可以使用元素索引删除。你应该看看你的实现的其余部分是如何管理这个索引的。第一个元素的索引是 0 还是 1（您从 1 开始循环）。删除一个元素时，所有元素的索引会发生什么变化。元素知道它们的索引吗？

你可以使用类似的东西

  int deletedNodes = 0;
  int currentIndex = 0; // check if 1 or 0
  currentNode = fist;
  while(currentNode != null){ // I guess lastNode.getNextNode() is null
    if(//should remove){
      remove(currentIndex);
      deletedNodes++
      // probably no need to change the index as all element should have been shifted back one index
    } else {
      currentIndex++; // index changes only if no node was deleted
    }
    currentNode = currentNode.getNextNode(); // will work even if it was deleted
  }
return deletedNodes;
于 2013-03-06T09:20:49.850 回答
0

删除节点后，正如@Vakimshaar 建议的那样，您需要减少 ，i因为该索引处的节点已被删除，并且同一索引处有一个新节点。除此之外，您还需要更新currentNode引用，因为它仍然指向您刚刚删除的节点，但它实际上应该指向已移动到该索引的新节点。

因此，在if (item.equals(currentNode.getData())){块中，您需要执行以下操作：

Node nextNode = currentNode.getNextNode();
index++;
remove(i--);
currentNode = nextNode;

有了这个，您的代码应该正确地删除所有出现。

于 2013-03-06T09:51:14.497 回答
0

这是一个 Java 代码，用于从链表中删除所有出现的项目：

public class LinkedList{
    Node head;
    class Node{
        int data;
        Node next;
        Node(int d){data =d; next = null;}
    }

    public void push(int new_data){
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

    public void insertAfter(Node givenNode, int new_data){
        if(givenNode == null)
            System.out.println("Given node cannot be empty");

        Node new_node = new Node(new_data);
        new_node.next = givenNode.next;
        givenNode.next = new_node;
    }

    public void append(int new_data){
        Node new_node = new Node(new_data);
        if(head == null)
            head = new_node;

        else{
        Node last = head;

        while(last.next != null)
            last = last.next;

        last.next = new_node;
    }
    }

    public void printList(){
        Node temp = head;

        while(temp != null){
            System.out.println(temp.data + " ");
            temp = temp.next;
        }
    }

    void deleteNode(int key){
        // Store head node
        Node temp = head, prev=null;
        // If head node itself holds the key or multiple occurrences of key
        while(temp != null && temp.data == key){
            head = temp.next;
            temp = head;
        }
        // Delete occurrences other than head
        while(temp != null){
            // Search for the key to be deleted, keep track of the
            // previous node as we need to change 'prev.next'
            while(temp != null && temp.data != key){
                prev = temp;
                temp = temp.next;
            }
            // If key was not present in linked list
            if(temp == null) return;
            // Unlink the node from linked list
            prev.next = temp.next;
            //Update Temp for next iteration of outer loop
            temp = prev.next;
        }
    }

     public static void main(String[] args){
         LinkedList llist = new LinkedList();

         llist.push(6);
         llist.append(7);
         llist.append(7);
         llist.append(7);
         llist.append(9);
         llist.push(10);
         llist.deleteNode(7);
         llist.printList();
     }
}

输出 ：

10 6 9

于 2016-04-20T09:50:45.887 回答