以单向循环链表求解约瑟夫环问题Java版

约瑟夫环（Josephus）问题：古代某法官要判决n个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，从第s个人开始数起，每数到第d个犯人，就拉出来处决，然后再数d个，数到的人再处决……直到剩下的最后一个可赦免.
结点类:OneLinkNode:

package com;
/**
 * 结点类
 * @author zdw
 *
 */
public class OneLinkNode
{
    public int data;
    public OneLinkNode next;
    public OneLinkNode(int k)
    {
        data = k;
        next = null;
    }
    
    public OneLinkNode()
    {
        this(0);
    }
}

 链表类OneLink:

package com;

public class OneLink
{
    //头结点
    protected OneLinkNode head;
    //构造一个空的单向链表
    public OneLink()
    {
        head = null;
    }
    //只有一个结点的单向链表
    public OneLink(OneLinkNode h1)
    {
        head = h1;
    }
    //判断链表是否为空
    public boolean isEmpty()
    {
        return head == null;
    }
    //用随机数构造n个数的链表
    public OneLink(int n)
    {
        OneLinkNode rear,q;
        if(n > 0)
        {
            int k = (int) (Math.random()*100);
            head = new OneLinkNode(k);
            rear = head;
            for(int i = 1; i < n ;i++)
            {
                k = (int) (Math.random()*100);
                q = new OneLinkNode(k);
                rear.next = q;
                rear = q;
            }
        }
    }
    
}

 Josephus类:

package com;

public class Josephus2 extends OneLink
{
    Josephus2() // 构造空的单向循环链表
    {
        super();
    }

    Josephus2(int n) // 建立n个结点的单向循环链表
    { // 链表结点值为1到n
        this();
        int i = 1;
        //q新结点,rear尾结点
        OneLinkNode q, rear;
        if (n > 0)
        {
            //先创建只有一个结点的单向循环链表
            head = new OneLinkNode(i);
            //指向自己
            head.next = head;
            rear = head;
            while (i < n)
            {
                i++;
                //新结点
                q = new OneLinkNode(i);
                //新结点的next字段指向head
                q.next = head;
                //这里的near是尾结点(第一次就是head)的next字段指向新结点
                rear.next = q;
                //保存新节点的地址,以便下次循环使用
                rear = q;
            }
        }
    }
    //计数起点s,d要跳过的个数
    public void display(int s, int d) // 解约瑟夫环
    {
        int j = 0;
        OneLinkNode p = head;
        while (j < s - 1) // 指针步进到计数起始点
        {
            j++;
            p = p.next;
        }
        while (p.next != p) // 多于一个结点时循环
        {
            j = 0;
            while (j < d ) // 计数
            {
                j++;
                p = p.next;
            }
            delete(p); // 删除p的后继结点
            p = p.next;
            this.output();
        }
    }

    public void delete(OneLinkNode p) // 删除p的后继结点
    {
        OneLinkNode q = p.next; // q是p的后继结点
        System.out.print("delete:  " + q.data + "  ");
        if (q == head) // 欲删除head指向结点时，
            head = q.next; // 要将head向后移动
        p.next = q.next; // 删除q
    }

    public void output() // 输出单向链表的各个结点值
    {
        OneLinkNode p = head;
        System.out.print(this.getClass().getName() + ":  ");
        do
        {
            System.out.print(p.data + " -> ");
            p = p.next;
        } while (p != head);
        System.out.println();
    }
    //测试
    public static void main(String args[])
    {
        int n = 5, s = 2, d = 1;
        Josephus2 h1 = new Josephus2(n);
        h1.output();
        h1.display(s, d);
    }


}

 测试输出结果没有任何问题:

com.Josephus2:  1 -> 2 -> 3 -> 4 -> 5 -> 
delete:  4  com.Josephus2:  1 -> 2 -> 3 -> 5 -> 
delete:  2  com.Josephus2:  1 -> 3 -> 5 -> 
delete:  1  com.Josephus2:  3 -> 5 -> 
delete:  3  com.Josephus2:  5 -> 

 来源：http://www.blogjava.net/supercrsky/articles/171805.html

其实这个题没多难，但是要是在面试的时候问你，现想就来不及了……

评论

2 楼 aben6448 2010-09-10  

aben6448 写道

楼主的表示循环链表的类-链表类有问题吧,当插入一个节点时，该节点的next应该还是该节点才对，该类中没有体现出来哦

我指的是只插入一个节点的情况，否则就不是循环链表了

1 楼 aben6448 2010-09-10  

楼主的表示循环链表的类-链表类有问题吧,当插入一个节点时，该节点的next应该还是该节点才对，该类中没有体现出来哦