链表故障

Question

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

例如，如果有人将整数 5 添加到链表 12 次，当询问 [=11=] 的频率（使用 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++; 
}

链表故障

Linked List Malfunctioning

java

linked-list