1

I am required to write a method that returns a number - the amount of times an element is found in a linked list. So far I have;

package Question4;

import net.datastructures.Node;

public class SLinkedListExtended<E> extends SLinkedList<E> {
    // returns the number of occurrences of the given element in the list
    public int count(E elem) {

        Node<E> cursor = tail;
    int counter = 0;

    if ((cursor != null) && (!(cursor.getElement().equals(elem)))) { //tail isnt null and element is not equal to elem 

        cursor = cursor.getNext(); //go to next node

    } else if ((cursor != null) && (cursor.getElement().equals(elem))){ //cursor isn't null and element equals elem

        counter++; //increment counter
    }
    else { 
        return counter; //return counter 
    }
    return counter;
}


public static void main(String[] args) {

    SLinkedListExtended<String> x = new SLinkedListExtended<String>();

    x.insertAtTail("abc");
    x.insertAtTail("def");
    x.insertAtTail("def");
    x.insertAtTail("xyz");
    System.out.println(x.count("def")); // should print "2"
    x.insertAtTail(null);
    x.insertAtTail("def");
    x.insertAtTail(null);
    System.out.println(x.count("def")); // should print "3"
    System.out.println(x.count(null)); // should print "2"
}
}

I have extended to a class which compiles correctly, so I know the problem is in my method. I can't figure out what to do, my code returns 0, which is probably the counter integer remaining at 0 and not going through the loop statement. Any ideas are appreciated.

Edit. SLinkedList code:

import net.datastructures.Node;

public class SLinkedList<E> {
protected Node<E> head; // head node of the list
protected Node<E> tail; // tail node of the list (if needed)
protected long size; // number of nodes in the list (if needed)

// default constructor that creates an empty list
public SLinkedList() {
    head = null;
    tail = null;
    size = 0;
}

// update and search methods
public void insertAtHead(E element) {
    head = new Node<E>(element, head);
    size++;
    if (size == 1) {
        tail = head;
    }
}

public void insertAtTail(E element) {
    Node<E> newNode = new Node<E>(element, null);
    if (head != null) {
        tail.setNext(newNode);
    } else {
        head = newNode;
    }
    tail = newNode;
    size++;
}

public static void main(String[] args) { // test
    SLinkedList<String> list = new SLinkedList<String>();

    list.insertAtHead("lol");

}

}

4

4 回答 4

0

One of the fundamental things that you were missing was a loop. Since you are essentially searching for something, you want to loop through the entire list. Once you run into an element that matches the one that you are searching for, you want to increment the count by 1. Once you have finished looping through the entire list, you want to return that count. So this is my solution. I keep it simple so you could understand:

import java.util.LinkedList;

public class Duplicates<E> extends LinkedList<E> {

    public static void main(String[] args) {
        Duplicates<String> duplicates = new Duplicates<String>();
        duplicates.add("abc");
        duplicates.add("def");
        duplicates.add("def");
        duplicates.add("xyz");
        System.out.println(duplicates.duplicateCount("def"));
        duplicates.add(null);
        duplicates.add("def");
        duplicates.add(null);
        System.out.println(duplicates.duplicateCount("def"));
        System.out.println(duplicates.duplicateCount(null));
    }

    public int duplicateCount(E element) {
        int count = 0;
        for (E e : this) {
            if (e == element) {
                count++;
            }
        }
        return count;
    }
}

Output:

2
3
2
于 2013-02-24T01:04:22.890 回答
0

The code in count is not in a loop, so it'll just return after the first element.

Try this:

public int count(E elem) {
    Node<E> cursor = tail;
    int counter = 0;
    while (true)
    {
        if ((cursor != null) && (!(cursor.getElement().equals(elem)))) { //tail isnt null and element is not equal to elem 
            cursor = cursor.getNext(); //go to next node
        } else if ((cursor != null) && (cursor.getElement().equals(elem))){ //cursor isn't null and element equals elem
            counter++; //increment counter
        }
        else { 
            return counter; //return counter 
        }
    }
}

Also, note that cursor.getElement().equals(elem) will return a NullPointerException when cursor.getElement() is null. The easiest way to deal with this is probably to write a separate equals method:

boolean equals(E e1, E e2)
{
  if (e1 == null)
    return e2 == null;
  if (e2 == null)
    return false;
  return e1.equals(e2);
}

Also, presumably Node<E> cursor = tail; makes it point to the end of the list and presumably you want Node<E> cursor = head; instead.

于 2013-02-24T00:58:20.930 回答
0

也许您应该使用 while 循环而不是 if 子句

**while** ((cursor != null) && (!(cursor.getElement().equals(elem)))) {
于 2013-02-24T01:00:07.040 回答
0

我建议你将 Martin 的答案（告诉你如何计算元素）与这个结合起来，告诉你如何使用 foreach - 你只需要制作你的SLinkedListExtended工具Iterable，这应该是下面的东西（你可以这样做on SLinkedList，但我假设您被告知不要更改该代码）：

public class SLinkedListExtended<E> extends SLinkedList<E> implements Iterable<E> () {

    public Iterator<E> iterator() {
        final Node<E> itHead = head;
        return new Iterator<E>() {

            Node<E> current = itHead;
            long position = 0;

            public boolean hasNext() {
                return current != null && position < size;
            }

            public E next() {
                current = current.getNext();
                ++position;
                return current.getElement();
            }

            public void remove() {
                throw new UnsupportedOperationException("Not supported yet.");
            }

        };
    }

};

我不能保证所有细节，但这应该涵盖大部分。您也可以考虑使用equals而不是==，但不要忘记检查元素是否为空。

next应该只调用 if hasNextis true，所以如果它抛出异常不是问题（但它应该是 aNoSuchElementException以符合合同）。

实现Iterable使您的类与 Collections 库兼容，因此支持 foreach，但您可以通过调用iterator,hasNext和您next自己来使用它进行原始迭代。

于 2013-02-24T22:48:58.953 回答