寻道

探寻程序之道，软件之道，生存之道，生活之道及生命之道。

BlogJava 首页 新随笔 联系 聚合 管理
  196 Posts :: 1 Stories :: 342 Comments :: 0 Trackbacks
轮圈数数退出问题
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 阅读(147) 评论(0)  编辑  收藏 所属分类: 算法数据结构

标题  
姓名  
主页
验证码 *  
内容(请不要发表任何与政治相关的内容)  
  登录  使用高级评论  新用户注册  返回页首  恢复上次提交      
 
 
相关链接:
网站导航:

sitinspring(http://www.blogjava.net)原创,转载请注明出处.