Мне нужна помощь в устранении проблемы с сортировкой списка приоритетов + очередь в Java - PullRequest
Новая
       47

Мне нужна помощь в устранении проблемы с сортировкой списка приоритетов + очередь в Java

0 голосов
/ 26 сентября 2010

Здравствуйте. Я пытаюсь реализовать приоритетную очередь в Java с нуля с помощью связанного списка, но у меня возникают проблемы при сортировке элементов при вставке.Здесь моя программа до сих пор, любая помощь будет высоко ценится.

import java.util.Scanner;

public class T0 {

    public static void main(String args[]) {
        Scanner keyboard = new Scanner(System.in);

        PQ myList = new PQ();

        myList.addSort("Z");
        myList.addSort("B");
        myList.addSort("C");
        myList.addSort("B");
        myList.addSort("Z");

        System.out.println(myList.view(0));
        System.out.println(myList.view(1));
        System.out.println(myList.view(2));
        System.out.println(myList.view(3));
        System.out.println(myList.view(4));
    }
}


class PQ {

    Node tail = new Node(null, null);
    int elementCount = 0;

    Node lastAdded = tail;

        public void add(String word) {
        Node added = new Node(word, lastAdded);
        lastAdded=added;
        elementCount++;
    }

    public void addSort(String word){
                Node temp = new Node(null, null);
        for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) >1; n++){
            temp=lastAdded.next();
        }
        Node added = new Node(word, lastAdded.next());
        lastAdded.changeNext(added);
        elementCount++;
    }

    public String view(int i){
        Node temp = lastAdded;

        for(int n = elementCount; n > i; n--){
            temp=temp.next();
        }
        return temp.toString();

    }
    public String toString() {
        return lastAdded.toString();
    }



    class Node {

        String name;
        Node nextNode;

        public Node(String s, Node n) {
            name = s;
            nextNode = n;
        }
        public void changeNext(Node n){
            nextNode=n;
        }
        public Node next() {
            return nextNode;
        }

        public String toString() {
            return name;
        }
    }
}

В настоящее время выводит: 

   run:
Z
B
C
B
Z
BUILD SUCCESSFUL (total time: 1 second)

Обновление: изменен addSort на: 

    public void addSort(String word){
            Node temp = lastAdded;
for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) > 0; n++){
    temp=lastAdded.next();
}
    Node added = new Node(word, lastAdded.next());
    lastAdded.changeNext(added);
    elementCount++;
    lastAdded=temp;
}

Это исключение нулевого указателя в 

System.out.println(myList.view(0));

Ответы [ 2 ]

1 голос
/ 26 сентября 2010

В цикле 

    for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) >1; n++){
        temp=lastAdded.next();
    }

вы всегда сравниваете новое слово с одним и тем же элементом, вместо того, чтобы перебирать список (1a) (и вы продолжаете присваивать temp одно и то же значение внутри цикла (1b) ). [Обновить] И вы сравниваете вывод compareTo с 1 вместо 0 (2) . Таким образом - в зависимости от реализации compareTo - результат может всегда быть ложным. (AFAIK это не относится к String.compareTo конкретно, поскольку он может возвращать значения больше 1 - но это не гарантируется в целом.) [/ Update]

И затем, независимо от результата ваших проверок, вы всегда добавляете новый элемент после последнего добавленного элемента (3) .

Однако, поскольку вы не настраиваете lastAdded (4) , он будет продолжать указывать на один и тот же элемент (tail), поэтому в действительности tail всегда будет первый элемент в вашем списке, а не последний .

Обновление 2: в обновленном addSort, вы исправили проблемы (2) и (4) выше, но (1a-b) и (3) все еще там.

Отчасти проблема заключается в том, что для работы односвязного списка вам необходимо постоянно указывать ссылку на заголовок , иначе вы не сможете просмотреть его! Вы как бы пытаетесь использовать lastAdded для этой цели, но это просто смешивание двух разных вещей, что вызывает дальнейшую путаницу. Обратите внимание, что на самом деле вам не нужна ссылка на последний добавленный узел - эта информация бесполезна, когда вы собираетесь вставить следующий элемент в список. Я рекомендую добавить выделенную ссылку head на картинку и соответственно изменить код (и удалить lastAdded, если вы не уверены, что он понадобится вам позже). Обратите внимание, что это не устраняет необходимость в (4) - даже если у вас есть только ссылка head, вам все равно нужно изменить ее (хотя и не всегда - только при вставке в начале списка).

0 голосов
/ 26 сентября 2010

В методе addSort вы присваиваете Node temp (как кажется,) месту, куда хотите вставить узел, - но затем вы не используете эту ссылку снова после цикла for.

...