java链表实现约瑟夫算法

| Posted in JAVA技术 @ 2007/04/13 12:04 by 博爱老头

在网上闲逛，看到有一道题目如下：
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/
版权所有。转载时必须以链接形式注明作者和原始出处及本声明！

最新日志		随机日志		综合排行
	钻石壁纸＋一首经典老歌国内3G牌照正式发放扫盲... 用java将本地化语言转换... ThrottleLock ... 新年快乐 [music] Sisse... 可口的三文鱼你不知道的故... [music] 听歌时间-... 平安夜杂记 DOPOD S900 官方...		中国“神龙”空天飞机惊艳亮... 3G和中国电信南非发现天使完整骨骸,距今... 暴雪将于2007年底发布s... java链表实现约瑟夫算法现代版愚公移山美国空袭巴铁是警报，伊朗真... iPhone 3G国内上市... 奥运直播表(完整版) java numberFo...		java msn机器人 JSTL详解终于在fc6下把TL－WN... eXtremeTable的... DES加密、解密字符串算法... IDC sees $49 ... eclipse 安装pyt... 放假早起，听到熟悉经典的音... 测试Issue管理利器JI... Waiting for f...

文章来自: 本站原创

Tags: java技术 , 算法

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

fc6安装mysql-Administrator系列产品

&^& Said,

2008/11/17 09:43

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

&^& Said,

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实例。

&^& Said,

2008/11/14 10:31

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

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

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

&^& Said,

2008/11/13 17:14

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

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

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

&^& Said,

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