双向回环链表的实现.解决方法-Java教程-爱易网页

双向回环链表的实现.解决方法

日期：2014-05-20　浏览次数：20868 次

双向回环链表的实现.
声明一下,这个是看马士兵老师的java视频教程的时候看到的例子,感觉有趣就拿出来大家做做,思路很明确的给了出来,就是让大家实现一下整个类,另外构造一个测试的类给搞出来就over了.

鸡肋型问题.高手不惜的做,因为我就肯花十分.我们新手确实有难度,就是大家锻炼下.

小孩玩游戏,手拉手围成一个圈,然后数数.每次数到3的时候这个小孩退出,下一个从1开始再数.
试问,如果有500个小孩,最后剩下的小孩是原来的第多少个小孩.
要求:面向对象程序设计实现.

简析:
两个类:小孩,圈.
class Kid {
int id;
Kid left;
Kid right;
}

class KidCircle {
int count;
Kid first,last;

KidCircle(int n) {
count = n;
}

void add() {}
void delete() {}
}

------解决方案--------------------
确切的名字叫做：约瑟夫环问题
典型的做法是模拟一个环形数组，即arr[i%N]
另一个做法只需要一个数学公式，一句话就可以得出答案，非常精炼。

确实有兴趣可以讨论下。
------解决方案--------------------
看下人家的解决办法
public class Josephus {

public static void main(String[] args) {
if(args.length<2){
System.out.println("Input N and M.");
return;
}
int n = Integer.parseInt(args[0]);
int m = Integer.parseInt(args[1]);
int point=0,number=1;
List<Integer> list = new ArrayList<Integer>();
for(int i=1;i<=n; i++){
//初始化链表
list.add(i);
}

while(list.size()>1){
if(number%m==0){
list.remove(point);
--point;
}
++point;//指针后移
++number;
if(point>list.size()-1){
//指针越界重新开始
point=0;
}
}

System.out.println(list.get(0));

}
}
------解决方案--------------------

Java code


public class Kie {
    int id;
    Kie left;
    Kie right;
    public Kie()
    {
        
    }
    public Kie(int id)
    {
        this.id=id;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public Kie getLeft() {
        return left;
    }
    public void setLeft(Kie left) {
        this.left = left;
    }
    public Kie getRight() {
        return right;
    }
    public void setRight(Kie right) {
        this.right = right;
    }
    public static void main(String []args)
    {
        Kie head=null;
        Kie last=null;
        Kie newF = null;
        for(int i=1;i<8;i++)
        {
            newF = new Kie(i);
            if(head==null)
            {
                head=newF;
                last = head;
            }else
            {
                last.right=newF;
                last = newF;
            }
        }
        head.left=last;
        last.right=head;
//        Kie k =head;
//        while(k.right!=head)
//        {
//            System.out.println(k.id);
//            k = k.right;
//        }
//        
        Kie node = head;
        while(node.left!=node.right||node.left==node.right&&node.left!=node)
        {
            node.right.right=node.right.right.right;
            node.right.right.left=node.right;
            node=node.right.right;
            //System.out.println(node.id);
        }
        System.out.println(node.id);
    }
}

------解决方案--------------------
你还真拿对象造个环哦......

下面是我做的。
package KidsGame;

import java.util.ArrayList;

public class Kids {
  int nowNumber=0;
public int GetNumber(){
	
	 return nowNumber++;

}
public void CallBack(){
	nowNumber=1;
}
}
----------------------------------分割线---------------------------------

package KidsGame;

import java.util.ArrayList;

免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。

双向回环链表的实现.解决方法

相关资料更多>

推荐阅读更多>