链表排序问题

Question

是的，这是一个家庭作业项目。 也就是说，我希望从中吸取教训，而不仅仅是让别人替我完成。

我的项目是一个词频列表 - 我接受一个文本文件（或网站URL）并计算:
-唯一单词的数量, 以及
-它们出现的次数。

所有方法都已经提供给我了，除了一个：insert(E word) 方法，其中参数是泛型类型的单词。 该单词存储在一个节点中 (链表项目)，该节点还有一个'count'值，该值表示该单词在所读取的文本中出现的次数。

这个方法需要做的事情如下：

1. 如果参数已经在列表中，则增加该元素的计数。 我已经完成了这部分
2. 如果在列表中找不到该参数，则将其附加到列表中。 我也已经完成了这部分。
3. 对列表按递减计数值排序。即：最高->最低计数 3.5 如果两个元素具有相同的计数值，则按其单词的字典顺序进行排序

我对链表非常不熟悉，因此遇到了很多NullPointerExceptions。

public void insert(E word){
    if(word.equals("")){
        return;
    }

    if(first == null){//if list is null (no elements)
        /*Node item = new Node(word);
        first = item;*/
        first = new Node(word);
    }

    else{//first != null

        Node itemToAdd = new Node(word);

        boolean inList = false;

        for(Node x = first; x != null; x=x.next){
            if (x.key.equals(word)){// if word is found in list
                x.count++;//incr
                inList = true;//found in list

                break;//get out of for
            }//end IF
            if(x.next == null && inList == false){//if end of list && not found
                x.next = itemToAdd;//add to end of list
                break;
            }//end IF
        }//end FOR

        //EVERYTHING ABOVE THIS LINE WORKS. 
        if (!isSorted()){
            countSort();
        }

    }//end ELSE
}//end method

我的isSorted()方法：

public boolean isSorted(){
    for(Node copy = first; copy.next != null; copy = copy.next){
        if (copy.count < copy.next.count){
            return false;
        }
    }
    return true;
}

最后但并非不重要的部分，我正在苦苦挣扎的是排序方法：

public void countSort(){

        for (Node x = first, p = x.next; p != null; x=x.next, p=p.next){
            // x will start at the first Node, P will always be 1 node ahead of X.

            if(x == first && (x.count < p.count)){
                Node oldfirst = first; 
                x.next = p.next;
                first = p;
                first.next = oldfirst;
                break;
            }

            if (x.count < p.count){
                //copy.next == x.
                Node oldfirst = first;
                oldfirst.next = first.next; 
                x.next = p.next;
                first = p;
                first.next = oldfirst;
                break;
            }

            if (x.count == p.count){
                if(x.toString().charAt(0) < p.toString().charAt(0)){
                    //[x]->[p]->[q]

                    Node oldfirst = first;
                    x.next = p.next;
                    first = p;
                    first.next = oldfirst;
                    break;
                }
            }
        }
    }

当被赋予给我的类/方法调用时，以下是我的插入方法的输出：

Elapsed time:0.084
(the,60)
(of,49)
(a,39)
(is,46)
(to,36)
(and,31)
(can,9)
(in,19)
(more,7)
(thing,7)
(violent,3)
(things,3)
(from,9)
(collected,1)
(quotes,1)
(albert,1)
(einstein,2)
(any,2)
(intelligent,1)
(fool,1)
(make,1)
(bigger,1)
(complex,1)
(it,11)
(takes,1)
(touch,1)
(genius,1)
(lot,1)
(courage,1)
(move,1)
(opposite,1)
(direction,1)
(imagination,1)
(important,5)
(than,3)
(knowledge,3)
(gravitation,1)
(not,17)
(responsible,1)
(for,14)
(people,2)
(falling,1)
(love,2)
(i,13)
(want,1)
(know,3)
(god,4)
(s,8)
(thoughts,2)
(rest,2)
(are,11)
(details,2)
(hardest,1)
(world,7)
(understand,3)
(income,1)
(tax,1)
(reality,3)
(merely,1)
(an,7)
(illusion,2)
(albeit,1)
(very,3)
(persistent,2)
(one,12)
(only,7)
(real,1)
(valuable,1)
(intuition,1)
(person,1)
(starts,1)
(live,2)
(when,3)
(he,11)
(outside,1)
(himself,4)
(am,1)
(convinced,1)
(that,14)
(does,5)
(play,2)
(dice,1)
(subtle,1)
(but,8)
(malicious,1)
(weakness,2)
(attitude,1)
(becomes,1)
(character,1)
(never,3)
(think,1)
(future,2)
(comes,1)
(soon,1)
(enough,1)
(eternal,1)
(mystery,1)
(its,4)
(comprehensibility,1)
(sometimes,1)

我的初始想法是尝试循环运行if(!isSorted()){ countSort();}部分，直到排序完成，但是当我这样做时，似乎会陷入无限循环。我尝试按照我的教授的讲座笔记操作，但不幸的是，他两次发布了上一次讲座的笔记，所以我感到困惑。

我不确定是否值得一提，但他们为我提供了一个带有hasNext()和next()方法的迭代器 - 我该如何使用它？我无法想象如果它没有用处，他们会提供它。

我哪里做错了？

- csh1579

---

你为什么选择链表？ - MaxZoom

@MaxZoom 他说这是作业。 - Deepak

@MaxZoom - 教授让我们使用链表来完成这个项目，因为这是我们目前正在学习的数据结构。 - csh1579

暂时注释掉//if (x.count == p.count){..}块，尝试先按计数排序。同时在插入方法中加入while(!sorted) { }。我理解了你提供的大部分内容，但能否看到完整的实现呢？ - Deepak

Answer 1

你离答案很近。首先，比较项目的函数不完整，因此isSorted()可能会产生错误的结果（如果计数相同但单词顺序错误）。这也用于排序，因此最好提取一个用于比较的方法：

// returns a value < 0 if a < b, a value > 0 if a > b and 0 if a == b
public int compare(Node a, Node b) {
    if (a.count == b.count)
        return a.word.compareTo(b.word);
        // case-insensitive: a.word.toLoweCase().compareTo(b.word.toLowerCase())
    } else {
        return a.count - b.count;
    }
}

或者简单来说，在您的情况下足够：

public boolean correctOrder(Node a, Node b) {
    if (a.count > b.count)
       return true;
    else if (a.count < b.count)
       return false;
    else
       return a.word.compareTo(b.word) <= 0;
}

你似乎选择了冒泡排序，但是你缺少外部部分：

boolean change;
do {
   change = false;
   Node oldX = null;
   // your for:
   for (Node x = first; x.next != null; x = x.next) {
       if (!correctOrder(x, x.next)) {
            // swap x and x.next, if oldX == null then x == first
            change = true;
       }
       oldX = x;
   }
} while (change);

我们可以利用Java本地库实现或更高效的排序算法来提高性能，但是根据这个练习，排序算法的性能还不是问题的关键，首先需要掌握基本概念。

- maraca

---

@csh1579 我添加了一点代码来展示我的意思，这样你就不会得到无限循环了。 - maraca

我了解你的思路，但我们不是需要检查x.next.next是否为空吗（或者我理解错了 :P）？ - csh1579

@csh1579 我一开始也是这么想的，但通常检查条件会是 x != null，因为它将在 x = x.next 之后进行检查，因此对于冒泡排序来说这样是正确的。oldX == null 是唯一的特殊情况。 - maraca

@csh1579 是的，x.next.next 可能是 null，但是当你将 x 与 x.next 交换时，最后一个节点的 next 指向 null，这不会影响你，对吧？ - maraca

我尝试了交换，但它给了我一个NullPointerException。然后我尝试了这个序列：Node p = x.next.next; Node z = x.next; x.next = p; oldX.next = z; z.next = x;（我为方便起见重命名为p和z，不确定是否会出问题），但出现了一个奇怪的问题，即使change = true，它也只添加了每个元素一次。我需要尝试一下或者做些什么，这是奇怪的行为。 - csh1579

Answer 2

通过查看您的代码，我认为有两件事可以做：

首先，您可以利用Comparable类方法。因此，我假设您编写了Node类，因此您可能希望从Comparable类继承。当您从该类继承时，Java将自动为您提供compareTo方法，您所需要做的就是在该方法中指定“我想按照您的计数进行比较，并且我希望它按升序排列。” **编辑（1）：顺便说一句，我之前忘了提到，在实现compareTo方法后，您可以使用Collections.sort（LinkedList list），然后就完成了。

第二个解决方案是，在countSort（）操作期间使用将所有内容添加到另一个列表并进行排序的技术对列表进行排序，然后将所有内容都添加回真正的列表中。我要说的排序技术是，继续向列表的末尾前进，直到找到列表中具有小于当前添加节点计数的节点为止。希望这不会让您感到困惑，但是通过这种方式，您可以实现更清晰的方法和更简单的视图。为了清楚起见，我想重复该过程：

看下一个节点 如果（下一个节点为空），则添加它//您已经到达末尾。 否则{ 如果（计数小于当前计数），则在那里添加它 否则，继续移动到下一个节点。//可以使用while实现。 }

- Kutay Demireren

---

我理解你的第一个解决方案，但我认为在第二个解决方案中可能表达不清。参数中的节点都具有计数为1的值，只出现一次（到目前为止）的节点也将具有值1。没有节点的计数值小于参数。 此外，我应用了一个ListIterator类 - 我的主类声明如下：public class Frequency<E extends Comparable> implements Iterable<E>因此，如果我理解正确：E通用类型扩展可比较，而Frequency实现了Iterable。 - csh1579