春风博客

春天里,百花香...

导航

<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 阅读(422) 评论(0)  编辑  收藏 所属分类: 算法数据结构


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


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