我的漫漫程序之旅

专注于JavaWeb开发
随笔 - 39, 文章 - 310, 评论 - 411, 引用 - 0
数据加载中……

以单向循环链表求解约瑟夫环问题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 -> 



posted on 2007-12-31 09:59 々上善若水々 阅读(7462) 评论(1)  编辑  收藏 所属分类: 数据结构与算法

评论

# re: 以单向循环链表求解约瑟夫环问题Java版  回复  更多评论   

请问结点类里this(0)是什么意思?
谢谢!
2014-02-13 14:04 | nieschumi

只有注册用户登录后才能发表评论。


网站导航: