春風博客

          春天里,百花香...

          導航

          <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 閱讀(438) 評論(0)  編輯  收藏 所屬分類: 算法數據結構

          sitinspring(http://www.aygfsteel.com)原創,轉載請注明出處.
          主站蜘蛛池模板: 平乡县| 崇明县| 吴桥县| 常熟市| 莎车县| 溧水县| 孝昌县| 金川县| 临潭县| 万年县| 深圳市| 扶余县| 水富县| 昭觉县| 百色市| 双桥区| 兖州市| 遂宁市| 治县。| 铜山县| 行唐县| 海南省| 罗田县| 盱眙县| 玛沁县| 茶陵县| 南汇区| 天水市| 沂水县| 姚安县| 高邮市| 高安市| 永登县| 乌拉特前旗| 方山县| 新乡市| 北川| 朝阳区| 阿拉善左旗| 科尔| 邮箱|