java链表实现约瑟夫算法

MOST RECENT NEWS - WE MOMENTARILY RENEW

Apr, 2007 12:04

博爱老头 JAVA技术

大 | 中 | 小

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

首先，创建一个链接节点类 LinkedNode.java

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

/**
 * @author    李国庆
 * @company   leo (C) copyright
 * @time      2007-4-12  下午04:14:14
 * @version   1.0.0.0
 * @package   com.leo.note
 * @project   noteDemo
 */
package com.leo.node;

/**
 * @author leo
 * 
 * 链表集合
 * 
 */
public class LinkedList {

private LinkedNode head;

public LinkedList() {
    head.next = head.previous = new LinkedNode("head", null, null);// 头节点
  }

public LinkedList(LinkedNode _head) {
    head = _head;// 头节点
    head.next = head.previous = head;
  }

/**
   * 返回头节点
   *
   * @return
   */
  public LinkedNode getFirst() {// 返回头节点后的第一个节点
    // LinkedNode node = head.next;
    // if (node == head) {
    // return null;
    // }
    // return node;
    return head;
  }

/**
   * 返回最后一个节点
   *
   * @return
   */
  public LinkedNode getLast() {
    LinkedNode node = head.previous;
    if (node == head) {
      return null;
    }
    return node;
  }

/**
   *  将节点加到头节点后
   *
   * @param node
   * @return
   */
  public LinkedNode addFirst(LinkedNode node) {
    node.next = head.next;
    node.previous = head;
    node.previous.next = node;
    node.next.previous = node;
    return node;
  }

/**
   *  将节点加到头节点后
   *
   * @param object
   * @return
   */
  public LinkedNode addFirst(Object object) {
    LinkedNode node = new LinkedNode(object, head.next, head);
    node.previous.next = node;
    node.next.previous = node;
    return node;
  }

/**
   *  节点添加到链表最后
   *
   * @param object
   * @return
   */
  public LinkedNode addLast(Object object) {
    LinkedNode node = new LinkedNode(object, head, head.previous);
    node.previous.next = node;
    node.next.previous = node;
    // head.previous = node;
    return node;
  }

/**
   *  清空列表
   *
   */
  public void clear() {// 清空链表
    // Remove all references in the list.
    LinkedNode node = getLast();
    while (node != null) {
      node.remove();
      node = getLast();
    }
    // Re-initialize.
    head.next = head.previous = head;
  }

/**
   *  返回对象值
   */
  public String toString() {
    LinkedNode node = head;
    StringBuffer buf = new StringBuffer();
    while (node != head) {
      System.out.println("node.toString() in toString is :"
          + node.toString());
      buf.append(node.toString()).append(", ");
      node = node.next;
    }
    return buf.toString();
  }

/**
   * 返回链表的长度
   * 
   * @return
   */
  public int getLength() {
    int _length = 0;
    while (head.next != head)
      _length++;
    return _length;
  }

}

最后一个测试类 Josephus.java

/**
 * @author    李国庆
 * @company   leo (C) copyright
 * @time      2007-4-12  下午04:34:21
 * @version   1.0.0.0
 * @package   com.leo.node
 * @project   nodeDemo
 */
package com.leo.node;

/**
 * @author leo
 * 
 */
public class Josephus {

public LinkedList _list = null;

public int start = 0;

public Josephus(int start) {
    this.start = start;
  }

/**
   * 移除一个子节点
   *
   * @param node
   */
  public void removeOneNode(LinkedNode node) {
    node.remove();
  }

/**
   * 执行踢出
   *
   * @param limit
   */
  public void doLogic(int limit) {
    LinkedNode _node_next_frist = _list.getFirst();
    while (limit > 1) {
      LinkedNode _node_remove = null;
      for (int i = 1; i < start; i++) {
        if (i == 1) {
          _node_remove = _node_next_frist.next;
        } else {
          _node_remove = _node_remove.next;
        }
      }
      _node_next_frist = _node_remove.next;
      System.out.println(String.valueOf(_node_remove.object)
          + " is removed!");
      removeOneNode(_node_remove);
      limit--;
    }
    System.out.println(String.valueOf(_node_next_frist.object)
        + " is the last element!");
  }

/**
   * 
   * 
   * @param person
   */
  public void addNode(String person) {
    _list.addLast(person);
  }

/**
   * 添加到链表
   * 
   * @param person
   */
  public void addNode(String[] person) {
    _list = new LinkedList(new LinkedNode(person[0], null, null));
    for (int i = 1; i < person.length; i++)
      _list.addLast(person[i]);
  }

/**
   * 
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    
    int _persion = 4;//被踢出人的位置
    String[] _personList = { "老二", "张三", "李四", "王五", "赵六",
        "钱七", "孙八", "刘九", "周十", "老大" };//所有人的列队
    
    Josephus jp = new Josephus(_persion);
    jp.addNode(_personList);// 添加数组到链表中
    jp.doLogic(_personList.length);// 执行算法
  }
}

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工程)：

下载文件

这个文件只能在登入之后下载。请先注册或登入

作者：博爱老头@博爱老头的草屋
地址：http://www.icnote.com/post/30/
版权所有。转载时必须以链接形式注明作者和原始出处及本声明！

最新日志		随机日志		综合排行
	零零碎碎的记录超可爱小MM[... 同一首歌〈健康〉深呼吸... 再现“神龙号”... 校准linux... 现代版愚公移... 中俄正讨论太空... 提供一个ESS... 冬天来了。。		周末的钓鱼活动项目进度计划和... 牛人绘出3D立... linux[F... 3Com撤回安... 为自己加油 java读写e... 体验腾讯QQ ... 陈冠希向所有受... ISBN ch...		java m... JSTL详解终于在fc6下... eXtreme... DES加密、解... IDC see... eclipse... 重拾blog乐... 测试Issue... 放假早起，听到...

Tags: java技术 , 算法

自己整理的一些表单验证的通用方法(javascript)

fc6安装mysql-Administrator系列产品

7 条评论 to “java链表实现约瑟夫算法”

&^& 2008/11/17 09:43

我添加的是数组名__personlist
String[] _personlist={"qq","ww","ee","rr","tt","yy","uu","ii","pp","aa"};

&^& 2008/11/14 16:55

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)

博爱老头回复于 2008/11/14 19:02

你添加的对象是什么？这里应该是一个LinkedNode实例。

&^& 2008/11/14 10:31

jp.doLogic(_personlist.length); 是剔除最后队列中最后一个我执行了以后经过那个while(limit>1)之后总是剔除最后一个

博爱老头回复于 2008/11/14 13:23

我的程序测试过了的，你再检查检查吧。

&^& 2008/11/13 17:14

你的那个int _persion=4 是定义开始第一个人的位置吗？然后删除的位置是第几个人，在数组中又是哪个位置？

博爱老头回复于 2008/11/13 23:02

不是，是第几个人被踢出去。

&^& 2008/11/12 14:18

虽没怎么看懂我按照你上面的写了但结果不是这样的我是这样写的数组
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

博爱老头回复于 2008/11/12 15:10