Geek Answers Handbook

The problem of sorting the list of links

YES, this is a homework project. That being said, I'm looking to learn from my mistakes, and not just to have someone do it for me.

My project is a list of word frequencies - I accept a text file (or website URL) and count: - The number of unique words and
- How many times they appear.

All methods are provided for me, except for one: a method insert(E word)where the argument is a word of a general type. The word is stored in Node (a linked list project), which also has the value "count", which is a number representing the number of times the word is displayed in the read text.

What this method should do is the following:

  • If the argument is already in the list, increase the number of this element. I have done this part.
  • If the argument is not found in the list, add it to the list. I also did this part.
  • sort the list in descending order of account value. that is, the highest → lowest indicator 3.5. If two elements have the same count value, they are sorted by the dictionary order of their word.

I am VERY unfamiliar with linked lists, so I come across a lot NullPointerExceptions. This is my current insertion method:

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

My 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;
}

and last but not least, the part I'm struggling with is the sorting method:

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;
                }
            }
        }
    }

Here is the result of my insert method when called by the classes / methods I specified:

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() - ? , , .

?

+4
2

. , 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 , , , , .

+1

, :

-, Comparable. , , Node, Comparable. , java compareTo, , , , " , , ". ** (1): , , , compareTo, Collections.sort( LinkedList), .

, countSort() . , , , Node , , Node. , , . , :

( - null), // .
{
      if (count ),
      else, Node.// .
}

0
source

More articles:


All Articles