1

我更关心我正在研究的插入方法，一个最多只占用 10 个节点的单链表。我有一个返回分数SinglyLinkedList的getScore()方法。附上相关方法看流程。基本上我想要完成的以及我在插入方法上所做的将节点（有一个分数）插入到正确的排序位置，从左边是最高分，最右边是最低分。如果我有[100]--[80]--[65]另一个分数 67 的节点出现，[100]--[80]--[67]--[65]只要大小小于 10，它就会变成，if (size == 10)那么这意味着列表已满，并且任何其他进入的节点只会将其与最后一个节点进行比较，例如，95 的新节点仅与 65 进行比较，如果它大于 65，则意味着它 95 必须在列表，删除最后一个节点“65”并遍历以找到适合 95 的合适位置。如果另一个节点例如高于 100，例如 200 .. 那么[200]--[100]--[95]--[80]--[67]只要以size < 10其他方式踢出最低分数，那么list 仍将维护 10 个节点。你明白了。

public void insert(Node n) { 
  //insert if node's score is higher than the last node
  int currScore = n.getScore();
  Node pos = head;

  if(pos.getScore() < currScore) {
    addFirst(n);
  }

  if(pos != null) {
    if(getSize() == 10) {
      if(tail.getScore() < currScore) {
        removeLast();
      } else { 
        n = null;
      }
    } else {
      while(getSize() < 10) {
        if((pos.getNext() != null) && (pos.getNext().getScore() > currScore))
          pos.setNext(pos);
      }
      insertAfter(n,pos);
    }
  }
}

public void addFirst(Node v) {
  if(head == null) {
    head = v;
    tail = v;
    size++;
}

public void insertAfter(Node p, Node v) { //insert v after p
  Node t = p.getNext();
  p.setNext(v);
  v.setNext(t);
  size++;
}

public void removeLast() {
  if(head == null) {
    return;
  }
  Node pos = head;
  if(pos.getNext() == null) {
    pos = null;
  }
  Node curr = head.getNext();
  while(curr.getNext() != null) {
    pos = curr;
    curr.setNext(curr);

    if(curr.getNext() == null) {
      curr = null;
    }
  }         
}

public class Node  {
    private String name;
    private int score;
    private Node next;

    public Node() {
        name = "";
        score = 0;
        next = null;
    }

public Node(String name, int score, Node next) {
    this.name = name;
    this.score = score;
    this.next = next;
}
public String getName() {
    return name;
}

public int getScore() {
        return score;
}

public Node getNext() {
        return next;
}
public void setName(String name) {
        this.name = name;
}

public void setScore(int score) {
        this.score = score;
}

public void setNext(Node next) {
    this.next = next;
}
}

public class SinglyLinkedList {
    public Node head;
    public Node tail;
    public int size;
    static final int MAXSIZE = 10;

public SinglyLinkedList() {
    head = null;
    tail = null;
    size = 0;
}
public void addFirst(Node v) {
    if(head == null) {
    head = v;
    tail = v;
    size++;
    }
}
public void addLast(Node v) {
    v.setNext(null);
    tail.setNext(v);
    tail = v;
    size++;
}
public void insertAfter(Node p, Node v) { //insert v after p
    Node t = p.getNext();
    p.setNext(v);
    v.setNext(t);
    size++;
}
public void removeFirst() {
   if(head == null) {
       return;
   }
   Node t = head;
   head.setNext(head);
   t = null;
   size--;
}
public void removeLast() {
    if(head == null) {
        return;
    }
    Node pos = head;
    if(pos.getNext() == null) {
        pos = null;
    }
    Node curr = head.getNext();
    while(curr.getNext() != null) {
        pos = curr;
        curr.setNext(curr);

        if(curr.getNext() == null) {
            curr = null;
        }
    }         
}

public void insert(Node n) { //insert if node's score is higher than the last node
    int currScore = n.getScore();
    Node pos = head;

    if(pos.getScore() < currScore) {
            addFirst(n);
     }

    if(pos != null) {
        if(getSize() == 10) {
            if(tail.getScore() < currScore) {
                removeLast();
            } else { 
                n = null;
            }
        } else {
            while(getSize() <= 10) {
                if(pos.getNext() != null && pos.getNext().getScore() > currScore)
                pos.setNext(pos);
            }
            insertAfter(n,pos);
        }
    }
}
public int getSize() {
    return size;
}
}
4

1 回答 1

0

你的 setNext() 方法在哪里？？你在增加 setNext() 的大小吗？..我认为您的程序将进入无限循环，因为-

 while(getSize() < 10) {
                if(pos.getNext() != null && pos.getNext().getScore() > currScore)
                pos.setNext(pos);
            }

你在哪里做大小++？？

给出你正在使用的所有方法的实现......

于 2013-09-24T05:22:07.107 回答