基于优先级的LinkedList插入问题

This is the basic class: Issue(priority, description) I have a linked list implementation as follows:

这是基本类:问题(优先级,描述)我有一个链表实现如下:

public class IssueQueue {
    public Issue issue;
    public IssueQueue next;

    private static int count = 0;

    public IssueQueue() {
    }

    public IssueQueue(Issue i) {
      issue = i;
      next = null;
    }

  public int getCount() {
      return count;
  }

  public void Add(Issue newIssue) {
      IssueQueue tempQ = this;
      IssueQueue newIssueQ = new IssueQueue(newIssue);
      if (count == 0) {
          issue = newIssue;
      } else if (issue.getPriority() > newIssue.getPriority()) {
          while (tempQ.next != null
                  && tempQ.issue.getPriority() >   newIssue.getPriority()) {
              tempQ = tempQ.next;
          }

        newIssueQ.next = tempQ.next;
        tempQ.next = newIssueQ;
    } else if (issue.getPriority() <= newIssue.getPriority()) {
        newIssueQ.issue = issue;
        newIssueQ.next = next;
        issue = newIssue;
        next = newIssueQ;

    }
    count++;
}

public void print() {
    IssueQueue tempQ = this;
    if (next == null) {
        System.out.println(issue);
    } else {
        do {
            System.out.println(tempQ.issue);
            tempQ = tempQ.next;
        } while (tempQ.next != null);
        System.out.println(tempQ.issue);
    }
    System.out.println("--------------------");
  }
}

The problem is, on doing the following: iq.Add(new Issue(10, "Issue 1")); iq.print();

问题在于,执行以下操作:iq.Add(new Issue(10,“Issue 1”)); iq.print();

    iq.Add(new Issue(4, "Issue 2"));
    iq.print();

    iq.Add(new Issue(20, "Issue 3"));
    iq.print();

    iq.Add(new Issue(2, "Issue 4"));
    iq.print();

    iq.Add(new Issue(12, "Issue 5"));
    iq.print();

The output is correct till 4th insertion:

输出正确,直到第4次插入:

Issue[Priority: 20, Description: Issue 3]
Issue[Priority: 10, Description: Issue 1]
Issue[Priority: 4, Description: Issue 2]
Issue[Priority: 2, Description: Issue 4]

But on 5th Insertion it becomes:

但在第5次插入时,它变为:

Issue[Priority: 20, Description: Issue 3]
Issue[Priority: 10, Description: Issue 1]
Issue[Priority: 12, Description: Issue 5]
Issue[Priority: 4, Description: Issue 2]
Issue[Priority: 2, Description: Issue 4]

Where is my code wrong?

4 个解决方案

#1

Why didn't you use Collections.sort() with your own priority-based compareTo() ?

为什么不使用Collections.sort()和您自己的基于优先级的compareTo()?

You're essentially asking us to step your code with a debugger. But this looks weird

您实际上是在要求我们使用调试器来执行代码。但这看起来很奇怪

 newIssueQ.next = tempQ.next;
 tempQ.next = newIssueQ;

Look you're not even checking against all priorities. I understand this traverses the list but... try stepping in a debugger and you will see.

看起来你甚至没有检查所有优先事项。我理解这遍历了列表,但是...尝试踩到调试器,你会看到。

else if (issue.getPriority() > newIssue.getPriority()) {
          while (tempQ.next != null
                  && tempQ.issue.getPriority() >   newIssue.getPriority()) {
              tempQ = tempQ.next;
          }

#2

You should separate the queue from the control logic. Then you won't get confused from the fact you need to think inside out. I'm sure then you'll easily get the bug.

您应该将队列与控制逻辑分开。那么你不会因为你需要从内到外思考而感到困惑。我相信你很容易得到这个bug。

If you can't follow your code in mind -> refactor.

如果你不能记住你的代码 - >重构。

#3

I would suggest you to write

我建议你写

 PriorityQueue<Issue> issues =  new PriorityQueue<Issue>();

And implement Class Issue with Comparable.

并使用Comparable实现Class Issue。

#4

According to this code you are inserting the new issue after an issue with a lower priority.

根据此代码,您将在优先级较低的问题之后插入新问题。

while (tempQ.next != null
              && tempQ.issue.getPriority() >   newIssue.getPriority()) {
    tempQ = tempQ.next;
}

newIssueQ.next = tempQ.next;
tempQ.next = newIssueQ;

#1