4

このラボの割り当てに数時間取り組んでいますが、このコードが機能しない理由がわかりません。int removeEvery(T 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削除すると、要素が indexに移動します。したがって、その 2 番目の要素を削除するには、 ではなく、再度呼び出す必要があります。j-thremove(j)j+1-thjremove(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()

あなたが説明しているこの問題は、反復可能なコレクションを通過し、通過するときに要素を削除するためにJDKのデータ構造を使用する場合のIterator.remove()の有用性を示しています。

于 2013-03-06T08:58:23.530 に答える
1

リンクされたリストには特別なものがあります。 current.getNextNode で次の要素にアクセスできますが、要素インデックスを使用して削除します。実装の残りの部分で、このインデックスがどのように管理されているかを確認する必要があります。最初の要素のインデックスは 0 または 1 ですか (ループは 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

iノードを削除した後、@ Vakimshaarが提案したように、このインデックスのノードが削除され、同じインデックスに新しいノードがあるため、をデクリメントする必要があります。それに加えて、削除したばかりのノードを指しているため、参照を更新する必要もあります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 に答える