单链表实现Farey序列(2)
下面是Farey序列的具体实现
1.构造子先设定了两个节点,即n=1的情况;
2.generate(int n)用于生成序列,每次会遍历当前序列,如果具备插入的点,则插入之,且将added设置为真;
3.如果遍历完后布尔值added为假,则说明序列已构造完成;
4.整型数turn表示每次需要判断插入的次数,它和前一轮得到的链表长度有关;
public class FareyList {
private Node head;
private int size;
public FareyList() {
head = new Node(0, 1);
Node next = new Node(1, 1);
head.setNext(next);
size = 2;
}
public void insertAfter(Node newNode, Node prev) {
newNode.setNext(prev.getNext());
prev.setNext(newNode);
size++;
}
public void generate(int n) {
if (n <= 0)
throw new UnsupportedOperationException();
if (n == 1) {
printList();
return;
}
boolean added = true;
while (added) {
int turn = size - 1;
added = false;
Node node1 = head;
Node node2 = head.getNext();
for (int i = 1; i <= turn; i++) {
if ((node1.getDnval() + node2.getDnval()) <= n) {
Node newNode = new Node(
node1.getUpval() + node2.getUpval(), node1
.getDnval()
+ node2.getDnval());
insertAfter(newNode, node1);
added = true;
}
node1 = node2;
node2 = node2.getNext();
}
}
printList();
}
private void printList() {
Node node = head;
while (node != null) {
System.out.print(node.getUpval() + " ");
node = node.getNext();
}
System.out.println();
node = head;
while (node != null) {
System.out.print(node.getDnval() + " ");
node = node.getNext();
}
System.out.println();
}
public static void main(String[] args) {
new FareyList().generate(8);
}
}
本文出自 “子 孑” 博客，请务必保留此出处http://zhangjunhd.blog.51cto.com/113473/54836
