在网上闲逛，看到有一道题目如下：
n个人围成一圈，每人有一个各不相同的编号，选择一个人作为起点，然后顺时针从1到k数数，每数到k的人退出圈子，圈子缩小，然后从下一个人继续从1到k数数，重复上面过程。求最后推出圈子的那个人原来的编号。
这就是经典的约瑟夫环问题啊，所以，用java链表写了个。
首先，创建一个链接节点类 LinkedNode.java
<br />/**<br /> * @author 李国庆<br /> * @company leo (C) copyright<br /> * @time 2007-4-12 下午04:29:10<br /> * @version 1.0.0.0<br /> * @package com.leo.node<br /> * @project nodeDemo<br /> */<br />package com.leo.node;<br /><br />/**<br /> * @author leo<br /> * <br /> */<br />public class LinkedNode {<br /><br /> public LinkedNode previous;// 前一节点<br /><br /> public LinkedNode next;// 后一节点<br /> <br /> public int no; //节点序号<br /><br /> public Object object;// 节点中的数据<br /><br /> public LinkedNode(Object object, LinkedNode next,<br /> LinkedNode previous) {<br /> this.object = object;<br /> this.next = next;<br /> this.previous = previous;<br /> }<br /><br /> /**<br /> * 从链表中移去<br /> *<br /> */<br /> public void remove() {<br /> previous.next = next;<br /> next.previous = previous;<br /> }<br /><br /> public String toString() {<br /> return object.toString();<br /> }<br /><br />}<br />
然后 创建环形链表类：LinkedList.java
<br />/**<br /> * @author 李国庆<br /> * @company leo (C) copyright<br /> * @time 2007-4-12 下午04:14:14<br /> * @version 1.0.0.0<br /> * @package com.leo.note<br /> * @project noteDemo<br /> */<br />package com.leo.node;<br /><br />/**<br /> * @author leo<br /> * <br /> * 链表集合<br /> * <br /> */<br />public class LinkedList {<br /><br /> private LinkedNode head;<br /><br /> public LinkedList() {<br /> head.next = head.previous = new LinkedNode("head", null, null);// 头节点<br /> }<br /><br /> public LinkedList(LinkedNode _head) {<br /> head = _head;// 头节点<br /> head.next = head.previous = head;<br /> }<br /><br /> /**<br /> * 返回头节点<br /> *<br /> * @return<br /> */<br /> public LinkedNode getFirst() {// 返回头节点后的第一个节点<br /> // LinkedNode node = head.next;<br /> // if (node == head) {<br /> // return null;<br /> // }<br /> // return node;<br /> return head;<br /> }<br /><br /> /**<br /> * 返回最后一个节点<br /> *<br /> * @return<br /> */<br /> public LinkedNode getLast() {<br /> LinkedNode node = head.previous;<br /> if (node == head) {<br /> return null;<br /> }<br /> return node;<br /> }<br /><br /> /**<br /> * 将节点加到头节点后<br /> *<br /> * @param node<br /> * @return<br /> */<br /> public LinkedNode addFirst(LinkedNode node) {<br /> node.next = head.next;<br /> node.previous = head;<br /> node.previous.next = node;<br /> node.next.previous = node;<br /> return node;<br /> }<br /><br /> /**<br /> * 将节点加到头节点后<br /> *<br /> * @param object<br /> * @return<br /> */<br /> public LinkedNode addFirst(Object object) {<br /> LinkedNode node = new LinkedNode(object, head.next, head);<br /> node.previous.next = node;<br /> node.next.previous = node;<br /> return node;<br /> }<br /><br /> /**<br /> * 节点添加到链表最后<br /> *<br /> * @param object<br /> * @return<br /> */<br /> public LinkedNode addLast(Object object) {<br /> LinkedNode node = new LinkedNode(object, head, head.previous);<br /> node.previous.next = node;<br /> node.next.previous = node;<br /> // head.previous = node;<br /> return node;<br /> }<br /><br /> /**<br /> * 清空列表<br /> *<br /> */<br /> public void clear() {// 清空链表<br /> // Remove all references in the list.<br /> LinkedNode node = getLast();<br /> while (node != null) {<br /> node.remove();<br /> node = getLast();<br /> }<br /> // Re-initialize.<br /> head.next = head.previous = head;<br /> }<br /><br /> /**<br /> * 返回对象值<br /> */<br /> public String toString() {<br /> LinkedNode node = head;<br /> StringBuffer buf = new StringBuffer();<br /> while (node != head) {<br /> System.out.println("node.toString() in toString is :"<br /> + node.toString());<br /> buf.append(node.toString()).append(", ");<br /> node = node.next;<br /> }<br /> return buf.toString();<br /> }<br /><br /> /**<br /> * 返回链表的长度<br /> * <br /> * @return<br /> */<br /> public int getLength() {<br /> int _length = 0;<br /> while (head.next != head)<br /> _length++;<br /> return _length;<br /> }<br /><br />}<br />
最后一个测试类 Josephus.java
<br />/**<br /> * @author 李国庆<br /> * @company leo (C) copyright<br /> * @time 2007-4-12 下午04:34:21<br /> * @version 1.0.0.0<br /> * @package com.leo.node<br /> * @project nodeDemo<br /> */<br />package com.leo.node;<br /><br />/**<br /> * @author leo<br /> * <br /> */<br />public class Josephus {<br /><br /> public LinkedList _list = null;<br /><br /> public int start = 0;<br /><br /> public Josephus(int start) {<br /> this.start = start;<br /> }<br /><br /> /**<br /> * 移除一个子节点<br /> *<br /> * @param node<br /> */<br /> public void removeOneNode(LinkedNode node) {<br /> node.remove();<br /> }<br /><br /> /**<br /> * 执行踢出<br /> *<br /> * @param limit<br /> */<br /> public void doLogic(int limit) {<br /> LinkedNode _node_next_frist = _list.getFirst();<br /> while (limit > 1) {<br /> LinkedNode _node_remove = null;<br /> for (int i = 1; i < start; i++) {<br /> if (i == 1) {<br /> _node_remove = _node_next_frist.next;<br /> } else {<br /> _node_remove = _node_remove.next;<br /> }<br /> }<br /> _node_next_frist = _node_remove.next;<br /> System.out.println(String.valueOf(_node_remove.object)<br /> + " is removed!");<br /> removeOneNode(_node_remove);<br /> limit--;<br /> }<br /> System.out.println(String.valueOf(_node_next_frist.object)<br /> + " is the last element!");<br /> }<br /><br /> /**<br /> * <br /> * <br /> * @param person<br /> */<br /> public void addNode(String person) {<br /> _list.addLast(person);<br /> }<br /><br /> /**<br /> * 添加到链表<br /> * <br /> * @param person<br /> */<br /> public void addNode(String[] person) {<br /> _list = new LinkedList(new LinkedNode(person[0], null, null));<br /> for (int i = 1; i < person.length; i++)<br /> _list.addLast(person<i>);<br /> }<br /><br /> /**<br /> * <br /> * @param args<br /> */<br /> public static void main(String[] args) {<br /> // TODO Auto-generated method stub<br /> <br /> int _persion = 4;//被踢出人的位置<br /> String[] _personList = { "老二", "张三", "李四", "王五", "赵六",<br /> "钱七", "孙八", "刘九", "周十", "老大" };//所有人的列队<br /> <br /> Josephus jp = new Josephus(_persion);<br /> jp.addNode(_personList);// 添加数组到链表中<br /> jp.doLogic(_personList.length);// 执行算法<br /> }<br />}<br /><br />
ok，输出结果如下：
王五 is removed!
刘九 is removed!
张三 is removed!
孙八 is removed!
李四 is removed!
老大 is removed!
周十 is removed!
老二 is removed!
钱七 is removed!
赵六 is the last element!
呵呵。。大家多提意见！
SRC下载(eclipse工程)：
[sfile]http://www.icnote.com/attachment/200704/nodedemo.rar[/sfile]
![[music] 听歌时间-残酷月光-林宥嘉](/wp-content/themes/textdash/img/thumb-medium.png)
我添加的是数组名__personlist
String[] _personlist={"qq","ww","ee","rr","tt","yy","uu","ii","pp","aa"};
LinkedList.addLast(object object)怎么理解 我的程序说这里有错误
Exception in thread "main" java.lang.NullPointerException
at Josephus.LinkedList.addLast(LinkedList.java:76)
at Josephus.Josephus.addNode(Josephus.java:69)
at Josephus.Josephus.main(Josephus.java:81)
你添加的对象是什么？这里应该是一个LinkedNode实例。
jp.doLogic(_personlist.length); 是剔除最后队列中最后一个 我执行了以后 经过那个while(limit>1)之后 总是剔除最后一个
我的程序测试过了的，你再检查检查吧。
你的那个int _persion=4 是定义开始第一个人的位置吗？然后删除的位置是第几个人，在数组中又是哪个位置？
不是，是第几个人被踢出去。
虽没怎么看懂 我按照你上面的写了 但结果不是这样的 我是这样写的数组
int _persion=4;
String[] _personlist={"qq","ww","ee","rr","tt","yy","uu","ii","pp","aa"};
结果是
aa is removed
qq is removed
aa is removed
the last removed is aa
没有看懂你的意思
假如转过了一圈 转到第一个位置的后面去了 以前的第一个数的位置会移动吗 我看了几遍了 还是看不懂
移动只是个说法，关键是指针的变换。
不错!学习了