春风博客

春天里，百花香...

导航

<2008年7月>
日一二三四五六
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

统计

公告

MAIL: junglesong@gmail.com
MSN: junglesong_5@hotmail.com

Locations of visitors to this page

常用链接

留言簿(11)

随笔分类(224)

随笔档案(126)

个人软件下载

我的其它博客

我的邻居们

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

轮圈数数退出问题

package com.sitinspring.roundtable;

/** *//**
 * 循环链表节点类
 * @author: sitinspring(junglesong@gmail.com)
 * @date: 2008-7-1-下午10:42:49
 * @param <T>
 */
class Node{
    protected String name;
    protected boolean isQuited;
    protected Node next;
}

/** *//**
 * 循环链表类，用于解决轮圈数数退出问题的建模
 * @author: sitinspring(junglesong@gmail.com)
 * @date: 2008-7-1-下午10:42:37
 * @param <T>
 */
public class CircleChainList{
    // 头节点
    private Node first;
    
    // 人个数
    private int length;
    
    /**
     * 轮圈退出
     * @param interval 间隔或起始数
     */
    public void wheelOut(int interval){
        // 总节点数
        int n=length;
        
        // 当前轮到的下标
        int currentIndex=interval;
        
        // 当前节点
        Node currentNode=first;
        
        // 轮圈退出直到剩下最后一个人
        while(n>1){ 
            // 经过一个未推出节点即下标减一
            if(currentNode.isQuited==false){                  
                currentIndex--;                
            }  
            
            // 走向下一个节点
            currentNode=currentNode.next;
            
            // 当下标为0及当前节点未退出时让其退出
            if(currentIndex==0 && currentNode.isQuited==false){
                currentNode.isQuited=true; 
                System.out.println(currentNode.name+"退出");
                n--;    
                currentIndex=interval;   
            }
        }
        
        // 找出最后一个幸存者
        currentNode=first;
        while(true){
            if(currentNode.isQuited==false){
                System.out.println(currentNode.name+"是最后的幸存者");
                break;
            }
            else{
                currentNode=currentNode.next;
            }
        }
    }
    
    /**
     * 显示链表元素
     *
     */
    public void display(){
        System.out.print("链表元素有");
        Node curr=first;
        int n=length;
        
        while(n>0){
            System.out.print(curr.name+"-("+curr.isQuited+") ");
            curr=curr.next;
            n--;
        }
        System.out.println();
    }
    
    /**
     * 添加一个数组组成环形链表
     * @param arr
     */
    public void addArray(String[] arr){
        length=arr.length;
        for(String t:arr){
            addTail(t);
        }
        
        
        Node curr=first;
        
        while(curr.next!=null){
            curr=curr.next;
        }
        // 将最后一个节点的指针指向头节点形成环形链表
        curr.next=first;
    }
    
    /**
     * 在链表尾部添加节点
     * @param t
     */
    public void addTail(String t){
        Node newNode=new Node();
        newNode.name=t;
        
        if(first==null){                        
            first=newNode;
        }
        else{
            Node curr=first;
            
            while(curr.next!=null){
                curr=curr.next;
            }
            
            curr.next=newNode;
        }
    }
    
    public static void main(String[] args){
        CircleChainList ls=new CircleChainList();
        
        String[] arr={"1","2","3","4","5","6","7","8"};
        ls.addArray(arr);
        ls.wheelOut(2);
    }
}

posted on 2008-07-05 09:14 sitinspring 阅读(428) 评论(0)  编辑  收藏 所属分类: 算法数据结构


只有注册用户登录后才能发表评论。
网站导航:
 
sitinspring(http://www.blogjava.net)原创,转载请注明出处.