java链表实现约瑟夫算法

Share

      在网上闲逛,看到有一道题目如下:
    n个人围成一圈,每人有一个各不相同的编号,选择一个人作为起点,然后顺时针从1到k数数,每数到k的人退出圈子,圈子缩小,然后从下一个人继续从1到k数数,重复上面过程。求最后推出圈子的那个人原来的编号。
     这就是经典的约瑟夫环问题啊,所以,用java链表写了个。shy
     首先,创建一个链接节点类  LinkedNode.java

<br />/**<br /> * @author &nbsp; &nbsp;李国庆<br /> * @company &nbsp; leo (C) copyright<br /> * @time &nbsp; &nbsp; &nbsp;2007-4-12 &nbsp;下午04:29:10<br /> * @version &nbsp; 1.0.0.0<br /> * @package &nbsp; com.leo.node<br /> * @project &nbsp; nodeDemo<br /> */<br />package com.leo.node;<br /><br />/**<br /> * @author leo<br /> * <br /> */<br />public class LinkedNode {<br /><br /> &nbsp;public LinkedNode previous;// 前一节点<br /><br /> &nbsp;public LinkedNode next;// 后一节点<br /> &nbsp;<br /> &nbsp;public int no; //节点序号<br /><br /> &nbsp;public Object object;// 节点中的数据<br /><br /> &nbsp;public LinkedNode(Object object, LinkedNode next,<br /> &nbsp; &nbsp; &nbsp;LinkedNode previous) {<br /> &nbsp; &nbsp;this.object = object;<br /> &nbsp; &nbsp;this.next = next;<br /> &nbsp; &nbsp;this.previous = previous;<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * 从链表中移去<br /> &nbsp; *<br /> &nbsp; */<br /> &nbsp;public void remove() {<br /> &nbsp; &nbsp;previous.next = next;<br /> &nbsp; &nbsp;next.previous = previous;<br /> &nbsp;}<br /><br /> &nbsp;public String toString() {<br /> &nbsp; &nbsp;return object.toString();<br /> &nbsp;}<br /><br />}<br />

   然后 创建环形链表类:LinkedList.java

<br />/**<br /> * @author &nbsp; &nbsp;李国庆<br /> * @company &nbsp; leo (C) copyright<br /> * @time &nbsp; &nbsp; &nbsp;2007-4-12 &nbsp;下午04:14:14<br /> * @version &nbsp; 1.0.0.0<br /> * @package &nbsp; com.leo.note<br /> * @project &nbsp; noteDemo<br /> */<br />package com.leo.node;<br /><br />/**<br /> * @author leo<br /> * <br /> * 链表集合<br /> * <br /> */<br />public class LinkedList {<br /><br /> &nbsp;private LinkedNode head;<br /><br /> &nbsp;public LinkedList() {<br /> &nbsp; &nbsp;head.next = head.previous = new LinkedNode("head", null, null);// 头节点<br /> &nbsp;}<br /><br /> &nbsp;public LinkedList(LinkedNode _head) {<br /> &nbsp; &nbsp;head = _head;// 头节点<br /> &nbsp; &nbsp;head.next = head.previous = head;<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * 返回头节点<br /> &nbsp; *<br /> &nbsp; * @return<br /> &nbsp; */<br /> &nbsp;public LinkedNode getFirst() {// 返回头节点后的第一个节点<br /> &nbsp; &nbsp;// LinkedNode node = head.next;<br /> &nbsp; &nbsp;// if (node == head) {<br /> &nbsp; &nbsp;// return null;<br /> &nbsp; &nbsp;// }<br /> &nbsp; &nbsp;// return node;<br /> &nbsp; &nbsp;return head;<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * 返回最后一个节点<br /> &nbsp; *<br /> &nbsp; * @return<br /> &nbsp; */<br /> &nbsp;public LinkedNode getLast() {<br /> &nbsp; &nbsp;LinkedNode node = head.previous;<br /> &nbsp; &nbsp;if (node == head) {<br /> &nbsp; &nbsp; &nbsp;return null;<br /> &nbsp; &nbsp;}<br /> &nbsp; &nbsp;return node;<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * &nbsp;将节点加到头节点后<br /> &nbsp; *<br /> &nbsp; * @param node<br /> &nbsp; * @return<br /> &nbsp; */<br /> &nbsp;public LinkedNode addFirst(LinkedNode node) {<br /> &nbsp; &nbsp;node.next = head.next;<br /> &nbsp; &nbsp;node.previous = head;<br /> &nbsp; &nbsp;node.previous.next = node;<br /> &nbsp; &nbsp;node.next.previous = node;<br /> &nbsp; &nbsp;return node;<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * &nbsp;将节点加到头节点后<br /> &nbsp; *<br /> &nbsp; * @param object<br /> &nbsp; * @return<br /> &nbsp; */<br /> &nbsp;public LinkedNode addFirst(Object object) {<br /> &nbsp; &nbsp;LinkedNode node = new LinkedNode(object, head.next, head);<br /> &nbsp; &nbsp;node.previous.next = node;<br /> &nbsp; &nbsp;node.next.previous = node;<br /> &nbsp; &nbsp;return node;<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * &nbsp;节点添加到链表最后<br /> &nbsp; *<br /> &nbsp; * @param object<br /> &nbsp; * @return<br /> &nbsp; */<br /> &nbsp;public LinkedNode addLast(Object object) {<br /> &nbsp; &nbsp;LinkedNode node = new LinkedNode(object, head, head.previous);<br /> &nbsp; &nbsp;node.previous.next = node;<br /> &nbsp; &nbsp;node.next.previous = node;<br /> &nbsp; &nbsp;// head.previous = node;<br /> &nbsp; &nbsp;return node;<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * &nbsp;清空列表<br /> &nbsp; *<br /> &nbsp; */<br /> &nbsp;public void clear() {// 清空链表<br /> &nbsp; &nbsp;// Remove all references in the list.<br /> &nbsp; &nbsp;LinkedNode node = getLast();<br /> &nbsp; &nbsp;while (node != null) {<br /> &nbsp; &nbsp; &nbsp;node.remove();<br /> &nbsp; &nbsp; &nbsp;node = getLast();<br /> &nbsp; &nbsp;}<br /> &nbsp; &nbsp;// Re-initialize.<br /> &nbsp; &nbsp;head.next = head.previous = head;<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * &nbsp;返回对象值<br /> &nbsp; */<br /> &nbsp;public String toString() {<br /> &nbsp; &nbsp;LinkedNode node = head;<br /> &nbsp; &nbsp;StringBuffer buf = new StringBuffer();<br /> &nbsp; &nbsp;while (node != head) {<br /> &nbsp; &nbsp; &nbsp;System.out.println("node.toString() in toString is :"<br /> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+ node.toString());<br /> &nbsp; &nbsp; &nbsp;buf.append(node.toString()).append(", ");<br /> &nbsp; &nbsp; &nbsp;node = node.next;<br /> &nbsp; &nbsp;}<br /> &nbsp; &nbsp;return buf.toString();<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * 返回链表的长度<br /> &nbsp; * <br /> &nbsp; * @return<br /> &nbsp; */<br /> &nbsp;public int getLength() {<br /> &nbsp; &nbsp;int _length = 0;<br /> &nbsp; &nbsp;while (head.next != head)<br /> &nbsp; &nbsp; &nbsp;_length++;<br /> &nbsp; &nbsp;return _length;<br /> &nbsp;}<br /><br />}<br />

  最后一个测试类  Josephus.java

<br />/**<br /> * @author &nbsp; &nbsp;李国庆<br /> * @company &nbsp; leo (C) copyright<br /> * @time &nbsp; &nbsp; &nbsp;2007-4-12 &nbsp;下午04:34:21<br /> * @version &nbsp; 1.0.0.0<br /> * @package &nbsp; com.leo.node<br /> * @project &nbsp; nodeDemo<br /> */<br />package com.leo.node;<br /><br />/**<br /> * @author leo<br /> * <br /> */<br />public class Josephus {<br /><br /> &nbsp;public LinkedList _list = null;<br /><br /> &nbsp;public int start = 0;<br /><br /> &nbsp;public Josephus(int start) {<br /> &nbsp; &nbsp;this.start = start;<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * 移除一个子节点<br /> &nbsp; *<br /> &nbsp; * @param node<br /> &nbsp; */<br /> &nbsp;public void removeOneNode(LinkedNode node) {<br /> &nbsp; &nbsp;node.remove();<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * 执行踢出<br /> &nbsp; *<br /> &nbsp; * @param limit<br /> &nbsp; */<br /> &nbsp;public void doLogic(int limit) {<br /> &nbsp; &nbsp;LinkedNode _node_next_frist = _list.getFirst();<br /> &nbsp; &nbsp;while (limit > 1) {<br /> &nbsp; &nbsp; &nbsp;LinkedNode _node_remove = null;<br /> &nbsp; &nbsp; &nbsp;for (int i = 1; i < start; i++) {<br /> &nbsp; &nbsp; &nbsp; &nbsp;if (i == 1) {<br /> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;_node_remove = _node_next_frist.next;<br /> &nbsp; &nbsp; &nbsp; &nbsp;} else {<br /> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;_node_remove = _node_remove.next;<br /> &nbsp; &nbsp; &nbsp; &nbsp;}<br /> &nbsp; &nbsp; &nbsp;}<br /> &nbsp; &nbsp; &nbsp;_node_next_frist = _node_remove.next;<br /> &nbsp; &nbsp; &nbsp;System.out.println(String.valueOf(_node_remove.object)<br /> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+ " is removed!");<br /> &nbsp; &nbsp; &nbsp;removeOneNode(_node_remove);<br /> &nbsp; &nbsp; &nbsp;limit--;<br /> &nbsp; &nbsp;}<br /> &nbsp; &nbsp;System.out.println(String.valueOf(_node_next_frist.object)<br /> &nbsp; &nbsp; &nbsp; &nbsp;+ " is the last element!");<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * <br /> &nbsp; * <br /> &nbsp; * @param person<br /> &nbsp; */<br /> &nbsp;public void addNode(String person) {<br /> &nbsp; &nbsp;_list.addLast(person);<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * 添加到链表<br /> &nbsp; * <br /> &nbsp; * @param person<br /> &nbsp; */<br /> &nbsp;public void addNode(String[] person) {<br /> &nbsp; &nbsp;_list = new LinkedList(new LinkedNode(person[0], null, null));<br /> &nbsp; &nbsp;for (int i = 1; i < person.length; i++)<br /> &nbsp; &nbsp; &nbsp;_list.addLast(person<i>);<br /> &nbsp;}<br /><br /> &nbsp;/**<br /> &nbsp; * <br /> &nbsp; * @param args<br /> &nbsp; */<br /> &nbsp;public static void main(String[] args) {<br /> &nbsp; &nbsp;// TODO Auto-generated method stub<br /> &nbsp; &nbsp;<br /> &nbsp; &nbsp;int _persion = 4;//被踢出人的位置<br /> &nbsp; &nbsp;String[] _personList = { "老二", "张三", "李四", "王五", "赵六",<br /> &nbsp; &nbsp; &nbsp; &nbsp;"钱七", "孙八", "刘九", "周十", "老大" };//所有人的列队<br /> &nbsp; &nbsp;<br /> &nbsp; &nbsp;Josephus jp = new Josephus(_persion);<br /> &nbsp; &nbsp;jp.addNode(_personList);// 添加数组到链表中<br /> &nbsp; &nbsp;jp.doLogic(_personList.length);// 执行算法<br /> &nbsp;}<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!

呵呵。。大家多提意见!smile

SRC下载(eclipse工程):
[sfile]http://www.icnote.com/attachment/200704/nodedemo.rar[/sfile]