Приоритет Связанная очередь добавить метод помощи - PullRequest
Новая
       6

Приоритет Связанная очередь добавить метод помощи

0 голосов
/ 08 октября 2018

Я пытаюсь реализовать приоритетную очередь, используя связанные узлы, и у меня все мои методы работают правильно, кроме метода add.Цель метода add - добавить сопоставимый объект в очередь в правильном порядке.Порядок очереди следующий: узлом с наивысшим приоритетом является firstNode.Любая помощь в том, что я делаю не так с моей попыткой, будет очень признательна. 

public void add(T newEntry) {

   if(newEntry == null) {
       return;
   }

   if(isEmpty()) { 
      firstNode = new Node(newEntry);
   } else {
       Node currentNode = firstNode;
       if(newEntry.compareTo(firstNode.data)<0) {
           firstNode = new Node(newEntry, firstNode);
           length++;
           return;
       } else {
           while(currentNode.getNextNode() != null && newEntry.compareTo(currentNode.next.data) > 0) {
                  currentNode = currentNode.next;
                  currentNode.setNextNode(new Node(newEntry, currentNode.getNextNode()));
           }
       }
   }
   length++;
   return;     
}

1 Ответ

0 голосов
/ 08 октября 2018

У вас есть как минимум две проблемы, которые я указал в комментариях к коду: 

public void add(T newEntry) {

   if(newEntry == null) {
       return;
   }

   if(isEmpty()) { 
      firstNode = new Node(newEntry);
   } else {
       Node currentNode = firstNode;
       if(newEntry.compareTo(firstNode.data)<0) {
// Here you're assigning a new value to firstNode, but not linking to the old
// firstNode. So you're losing the entire list.
           firstNode = new Node(newEntry, firstNode);
           length++;
           return;
       } else {
           while(currentNode.getNextNode() != null && newEntry.compareTo(currentNode.next.data) > 0) {
                  currentNode = currentNode.next;
// Here you're adding multiple new nodes to the list.
                  currentNode.setNextNode(new Node(newEntry, currentNode.getNextNode()));
           }
       }
   }
   length++;
   return;     
}

Вы можете упростить это довольно легко: 

public void add(T newEntry) {

   if(newEntry == null) {
       return;
   }
   Node newNode = new Node(newEntry);

   if(isEmpty()) { 
      firstNode = newNode;
   } else if (newNode.data < firstNode.data) {
      // make newNode point to the firstNode,
      // and then re-assign firstNode
      newNode.setNextNode(firstNode);
      firstNode = newNode;
   } else {
       Node currentNode = firstNode;
       Node nextNode = currentNode.getNextNode;
       while (nextNode != null && nextNode.data > newNode.data) {
           currentNode = nextNode;
           nextNode = currentNode.getNextNode;
       }
       // insert newNode between currentNode and nextNode
       newNode.setNextNode(nextNode);
       currentNode.setNextNode = newNode;
   }
   length++;
   return;     
}
...