链表故障

Question

我正在尝试创建一个链接的最后一个类，该类将存储数据以及数据出现的频率。

例如，如果有人将整数5添加到链表中12次，当询问5的频率（带getFrequencyOf(5)）时，结果应该是12。

不幸的是，添加到我的链表的第一个数字返回的频率比应有的频率低一。我的代码发布在下面。关于如何继续解决此问题的任何想法将不胜感激。

package main;
//    //Implement using a linked list
public class FrequencyBag<T>
{
    // TO DO: Instance Variables
    private Node firstNode;
    private int numOfItems;
    private class Node{
        //Node Instance Variables
        private T data;
        private int frequency;
        private Node next;
        private Node(T Data, Node nextNode){
            data= Data;
            next=nextNode;
            frequency=1;
        }
        private void addF(){
            frequency++;
        }
        private int getF(){
            return frequency;
        }
    }

    /**
     * Constructor
     * Constructs an empty frequency bag.
     */
    public FrequencyBag()
    {
        firstNode=null;
        numOfItems =0;
    }
    /**
     * Adds new entry into this frequency bag.
     * @param aData the data to be added into this frequency bag.
     */
    public void add(T aData)
    {
        if(firstNode!=null){
            boolean found =false;
            Node currNode=firstNode;
            while(currNode.next !=null){
                if(currNode.data.equals(aData)){
                    currNode.addF();
                    found=true;
                    break;
                }
                currNode= currNode.next;
            }
            if(!found){
                Node tempNode=firstNode;
                firstNode= new Node(aData,tempNode);
            }
        }
        else{
            firstNode= new Node(aData,null);
        }
        numOfItems++; 
    }
    /**
     * Gets the number of occurrences of aData in this frequency bag.
     * @param aData the data to be checked for its number of occurrences.
     * @return the number of occurrences of aData in this frequency bag.
     */
    public int getFrequencyOf(T aData)
    {
        Node currNode= firstNode;
        while(currNode!=null){
            if(currNode.data.equals(aData)){
                return currNode.getF();
            }
            currNode= currNode.next;
        }
        return 0;
    }
    /**
     * Gets the maximum number of occurrences in this frequency bag.
     * @return the maximum number of occurrences of an entry in this
     * frequency bag.
     */
    public int getMaxFrequency()
    {
        if(firstNode!=null){
            Node currNode= firstNode;
            Node maxNode= firstNode;
            while(currNode!=null){
                if(currNode.getF()>=maxNode.getF()){
                    maxNode=currNode;
                }
                currNode=currNode.next;
            }
            return maxNode.getF();
        }
        else{
            return 0;
        }
    }
    /**
     * Gets the probability of aData
     * @param aData the specific data to get its probability.
     * @return the probability of aData
     */
    public double getProbabilityOf(T aData)
    {
        if(firstNode!=null){
            boolean flag=true;
            double dataF=0;
            double prob=0;
            Node currNode= firstNode;
            while(currNode!=null){
                if(currNode.data.equals(aData)){
                    dataF=(double)currNode.getF();
                    flag=false;
                    break;
                }
                currNode= currNode.next;
            }   
            if(!flag){
                prob= dataF/(double)numOfItems;
            }
            return prob;
        }
        else{
            return 0;
        }
    }
    /**
     * Empty this bag.
     */
    public void clear()
    {
        firstNode=null;
        numOfItems=0;
    }
    /**
     * Gets the number of entries in this bag.
     * @return the number of entries in this bag.
     */
    public int size()
    {
        return numOfItems;
    }
}

Answer 1

你在add中的逻辑是错误的。当您只执行add一次（即在第二个add操作中）时，您跳过第一个节点而不对其进行测试，因为此时firstNode.next null。

让你的while (currNode.next != null)成为while (currNode != null)。请参阅下面的正确版本（仅适用于该特定问题：我没有测试所有预期的行为，因为我没有您的规范）。

请注意，代码可以按所示缩短（之后还会缩短更多）。开始编写单元测试，你既可以更快地找到这样的错误，又可以更有信心地重构，以使你的代码更短、更易于理解。

纠正：

public void add(T aData)
{       
    if(firstNode!=null){
        boolean found =false;
        Node currNode=firstNode;
        while(currNode != null){
            if(currNode.data.equals(aData)){
                currNode.addF();
                found=true;
                break;
            }
            currNode= currNode.next;
        }
        if(!found){
            Node tempNode=firstNode;
            firstNode= new Node(aData,tempNode);
        }
    }
    else {
        firstNode= new Node(aData,null);
    }
    numOfItems++; 
}

更正和缩短：

public void add(T aData)
{       
    boolean found =false;
    Node currNode=firstNode;
    while(currNode != null){
        if(currNode.data.equals(aData)){
            currNode.addF();
            found=true;
            break;
        }
        currNode= currNode.next;
    }
    if(!found){
        Node tempNode=firstNode;
        firstNode= new Node(aData,tempNode);
    }
    numOfItems++; 
}