josephus.java

约瑟夫环的具体操作

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @(#)Josephus.java
 * 约瑟夫环
 *
 * @author Ning.Pan
 * @version 1.00 2007/10/13
 */

// 定义结点，相当于一个结构体
class Node {
    int _data; // 数据
    Node _next; // 指针

    public Node(int d) {
        _data = d;
    }

    public int data() {
        return _data;
    }
}

// 定义一个链表及其方法
class CirLinkList {
    Node _cur;
    int _size = 0;

    // 初始化一个循环链表
    public CirLinkList(int n) {
        Node tail = new Node(n);
        _cur = tail;
        for (int i = n - 1; i > 0; i --) {
            Node tmp = new Node(i);
            tmp._next = _cur;
            _cur = tmp;
        }
        tail._next = _cur;
        _size += n;
    }

    // 返回链表长度
    public int size() {
        return _size;
    }

    public void step(int n) {
        for (int i = 0; i < n; i++) {
            _cur = _cur._next;
        }
    }

    // 删除链表中下一个结点
    public Node delete() {
        Node temp = _cur._next;
        _cur._next = temp._next;
        _size --;
        return temp;
    }

    // 显示链表信息
    public void display() {
        Node start = _cur, end = _cur;
        while (end._next != start) {
            System.out.print(end._data + " ");
            end = end._next;
        }
        System.out.println(end._data);
    }
}

public class Josephus {
	public static String getString() throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }

    public static void main(String[] args) throws IOException {
        System.out.print("请输入人数:");
        String str = getString();
        int n = Integer.parseInt(str);
        CirLinkList L = new CirLinkList(n);
        System.out.println("初始化链表为 ：");
        L.display();

        System.out.print("输入初始位置:");
        String start_position = getString();
        int start = Integer.parseInt(start_position);
        L.step(start - 1);

        System.out.print("输入步长:");
        String step_length = getString();
        int stp = Integer.parseInt(step_length);

        while (L.size() > 1) {
        	// 移到需要删除对象的前面一个结点
            L.step(stp - 2);
            // 删除当前结点的下一个结点
            Node death = L.delete();
            // 重新设置_cur指针
            L.step(1);
            System.out.println(death.data() + "出局");
        }
        System.out.println();
        System.out.print("最后剩余的人是 : ");
        L.display();
    }
}