链接列表排序问题

Question

是的，这是一个家庭作业项目。 这就是说，我期待从我的错误中学习，而不是让别人为我做。

我的项目是一个词频表 - 我接受一个文本文件（或网址）和计数：
- 独特的单词数和
- 他们有多少次出现。

为我提供的所有方法除了一个：insert(E word)方法，其中参数是一个泛型类型的单词。 该单词存储在节点（链接列表项目）中，该节点也具有“count”值，该值表示该单词在正在读取的文本中出现的次数。

什么这种方法需要做的是：

1. 如果参数已经在列表中，增加该元素的数量。 我已完成此部分
2. 如果在列表中找不到参数，请将其追加到列表中。 我也做了这部分。
3. sort该列表按降序计数值。即最高 - >最低计数 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()的迭代器 - 我怎样才能使用它？我无法想象他们会提供它，如果它没用。

我哪里错了？

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本机库的实现或更有效的排序算法的帮助，但是从锻炼判断T的性能他排序算法尚未涉及，首先需要掌握基本概念。

Answer 2

随着寻找你的代码，这听起来像对我来说，两件事情可以做：

首先，你可以利用可比类方法。所以，我假设你编写了Node类，因此你可能想从Comparable类继承。当您从类继承，java会自动为您提供compareTo方法，和所有你需要做的是在该法规定，“我想根据自己的计数来比较，我希望它是按升序排列。” **编辑（1）：对了，我忘了提过，但你的教学贯彻compareTo方法后，您可以使用Collections.sort（LinkedList的列表），它会做。

第二个解决方案来考虑的是，你可以用排序将所有到另一个列表的技术的countSort（）操作过程中排序列表和添加后全部回真正的列表。我试图说的排序技术是，继续前进到列表的末尾，直到您在列表中找到一个计数小于当前添加节点计数的节点。希望不要混淆视听，但通过这种方式，您可以实现更清晰的方法和更简单的视图。要清楚我要重复的过程：

看下一
如果（下一个为空），将其添加//你是在年底。
else {
if（count小于当前计数），将其添加
else，继续移动到下一个节点。 //虽然可以用于此。
}