我目前正在制作一个项目，该项目需要使用双向链表来存储高分。问题是排序算法不起作用。
P.S。我被迫创建自己的课程DoublyLinkedList，而不使用默认的课程。这是练习的项目要求。 =）
public class Scoreboard{
private int numberOfEntries = 0;
private DoublyLinkedList board;
public Scoreboard(int size){
this.board = new DoublyLinkedList();
}
public void add(GameEntry entry){
board.addFirst(entry);
numberOfEntries++;
}
public void remove(GameEntry entry){
board.removeLast();
numberOfEntries--;
}
public int getNumberOfEntries(){
return this.numberOfEntries;
}
public Node getHighest(){
Node nodeHighest = null;
int highest = Integer.MIN_VALUE;
Node head = this.board.getHeader();
int l = 0;
for (Node temp = head; l < getNumberOfEntries(); temp = temp.getNext(), l++){
int score = temp.getElement().getScore();
if (score > highest){
highest = temp.getElement().getScore();
nodeHighest = temp;
}
}
return nodeHighest;
}
public void sort() {
// from unsorted to descending na sorted board
// loop ang entire board , get ang minimum
Node head = this.board.getHeader();
DoublyLinkedList new_board = new DoublyLinkedList();
int newNumberOfEntries = this.numberOfEntries;
while(getNumberOfEntries() > 0){
GameEntry toAdd = getHighest().getElement();
Node toDelete = getHighest();
new_board.addFirst(toAdd);
this.board.deleteNode(toDelete);
this.numberOfEntries--;
// ibutang sa new_board, either addFirst or addLast
}
this.board = new_board;
this.numberOfEntries = newNumberOfEntries;
}
public void display(){
board.toString();
}
public static void main(String[] args) {
GameEntry mojeb = new GameEntry("Mojeb", 10);
GameEntry aljun = new GameEntry("Aljun", 5);
GameEntry alson = new GameEntry("Alson", 20);
GameEntry racman = new GameEntry("Racman", 30);
GameEntry hussien = new GameEntry("Hussien", 25);
GameEntry ram = new GameEntry("Ram", 36);
GameEntry suarto = new GameEntry("Suarto", 60);
GameEntry punggy = new GameEntry("Punggy", 40);
GameEntry alnoor = new GameEntry("Alnoor", 45);
GameEntry yusoph = new GameEntry("Yusoph", 50);
Scoreboard scoreboard = new Scoreboard(10);
scoreboard.add(mojeb);
scoreboard.add(aljun);
scoreboard.add(alson);
scoreboard.add(racman);
scoreboard.add(hussien);
scoreboard.add(ram);
scoreboard.add(suarto);
scoreboard.add(punggy);
scoreboard.add(alnoor);
scoreboard.add(yusoph);
scoreboard.display();
System.out.println(scoreboard.getNumberOfEntries());
scoreboard.sort();
scoreboard.display();
System.out.println();
}
}
deleteNode中存在问题：this.board.deleteNode(toDelete);我不确定为什么，我试图分析deleteNode函数，但我认为它没有错。下面是可疑链接列表类的代码。
public class DoublyLinkedList{
private int size = 0;
private Node header = null;
private Node trailer = null;
public DoublyLinkedList() {
header = new Node(null, null, null);
trailer = new Node(null, header, null);
header.setNext(trailer);
}
//getter methods for attributes
public Node getHeader(){
return this.header;
}
public Node getTrailer(){
return this.trailer;
}
public int getSize(){
return this.size;
}
//setter methods for attributes
public void setHeader(Node header){
this.header = header;
}
public void setTrailer(Node trailer){
this.trailer = trailer;
}
public void setSize(int size){
this.size = size;
}
//methods
public int size() {
return size;
}
public boolean isEmpty(){
return this.size == 0;
}
public GameEntry first(){
if (isEmpty()){
return null;
}
return this.header.getNext().getElement();
}
public GameEntry last(){
if (isEmpty()) {
return null;
}
return this.trailer.getPrev().getElement();
}
// public void addFirst(GameEntry e){
// addBetween(e, header, header.getNext());
// }
public void addFirst(GameEntry e) {
Node temp = new Node(e, header, null);
if(header != null ) {
header = temp;
}
header = temp;
if(trailer == null) {
trailer = temp;
}
size++;
}
// public void addLast(GameEntry e){
// addBetween(e, trailer.getPrev(), trailer);
// }
public void addLast(GameEntry e) {
Node temp = new Node(e, null, trailer);
if(trailer != null) {
trailer = temp;
}
trailer = temp;
if(header == null) { header = temp;}
size++;
}
public GameEntry removeFirst() {
if (isEmpty()) {
return null;
}
return deleteNode(header.getNext());
}
public GameEntry removeLast(){
if (isEmpty()) {
return null;
}
return deleteNode(trailer.getPrev());
}
// private void addBetween(GameEntry e, Node predecessor, Node successor){
// Node newest = new Node (e, predecessor, successor);
// predecessor.setNext(newest);
// successor.setPrev(newest);
// size++;
// }
public GameEntry deleteNode(Node toRemove){
Node predecessor = toRemove.getPrev();
Node successor = toRemove.getNext();
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
return toRemove.getElement();
}
public String toString() {
String s =" ";
Node temp = header;
for(int i=0; i < size; i++){
System.out.println(temp + "\n");
temp = temp.getNext();
}
return s;
}
// public static void main(String[] args) {
// DoublyLinkedList l = new DoublyLinkedList();
// GameEntry e = new GameEntry("ab", 2);
// l.addLast(e);
// l.addFirst(e);
// System.out.println(l.getHeader());
// }
public static void main(String a[]){
DoublyLinkedList dll = new DoublyLinkedList();
GameEntry e = new GameEntry ("ab", 2);
dll.addFirst(e);
dll.addLast(e);
System.out.println(dll.getHeader());
}
}
GameEntry类
public class GameEntry {
private String name;
private int score;
public GameEntry() {
}
public GameEntry(String name, int score) {
setName(name);
setScore(score);
}
public GameEntry(String name) {
setName(name);
}
public String getName() {
return this.name;
}
public void setName(String name) {
this.name = name;
}
public int getScore() {
return this.score;
}
public void setScore(int score) {
this.score = score;
}
public String toString() {
return "("+ this.name + ", " + this.score + ")";
}
}
节点类：
public class Node{
private GameEntry element = null;
public Node next = null;
public Node prev = null;
public Node(){
//default constructor
}
public Node(GameEntry element, Node next, Node prev){
this.element = element;
this.next = next;
this.prev = prev;
}
//getter methods for attributes
public GameEntry getElement(){
return this.element;
}
public Node getNext(){
return this.next;
}
public Node getPrev(){
return this.prev;
}
//setter methods for attributes
public void setElement(GameEntry element){
this.element = element;
}
public void setNext(Node next){
this.next = next;
}
public void setPrev(Node prev){
this.prev = prev;
}
// for displaying purposes
public String toString() {
return this.element.toString();
}
}
您能帮我找出为什么抛出NullPointerException以及如何将其修复到Node successor = toRemove.getNext();行吗？
public GameEntry deleteNode(Node toRemove){
Node predecessor = toRemove.getPrev();
Node successor = toRemove.getNext();
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
return toRemove.getElement();
}
实施您自己的双向链表是浪费时间。标准Java java.util.LinkedList已经提供了这种类型的列表：
java.util.LinkedList：List和Deque接口的双链接列表实现。
使用此类，您还可以使用标准的排序方法java.util.LinkedList。