Java自创链表实现约瑟夫杀人环

川长思鸟来 2022-04-22 00:02 180阅读 0赞

约瑟夫杀人环想必大家都已经有所了解，一共n个人坐成一圈，从第一个人开始报数（从1开始），若报到m则此人出列，下一个人重新开始报数，一次往复，直至所有人都出列。  
在之前，已经用C语言的链表写过此类方法，但是在Java中怎么实现呢？下面是我的代码  
**自定义结点类**

public class Node {
    	int num;
    	Node next;	
    	public Node() {
    		
    	}	
    	public Node(int num, Node next) {
    		super();
    		this.num = num;
    		this.next = next;
    	}		
    }

**约瑟夫主体**

public class Joeph {
    	Node first;		//头结点
    	Node last;	//尾结点
    	private int size; //链表长度
    	
    	public void add(int num) {	//增加元素
    		Node temp = new Node();
    		if(first == null) {
    			temp.num = num;
    			temp.next = first;
    			first = temp;
    			last = first;
    		}else {
    			temp.num = num;
    			last.next = temp;
    			temp.next = first;
    			last = temp;
    		}
    		size++;
    	}
    
    	public int getSize() {	//获取链表长度
    		return size;
    	}
    	
    	public void remove(int index) {	//删除链表某位置元素
    		Node temp = new Node();
    		temp = first;
    		int i = 1;
    		if(index == 1) {		//判断头元素
    			last.next = first.next;
    			first = last.next;
    		}else {
    			while(i+1 < index) {
    				temp = temp.next;
    				i++;
    			}
    			if(i+1 == index) {
    				System.out.print(temp.next.num + "   ");
    				temp.next = temp.next.next;
    				first = temp.next;
    			}
    		}
    		size--;
    	}
    	
    	public void bianli() {		//遍历链表
    		Node temp = new Node();
    		temp = first;
    		while(temp.next!= first) {
    			System.out.print(temp.num + "	");
    			temp = temp.next;
    		}		
    		System.out.println(temp.num);
    		
    	}
    }

**主函数**

public static void main(String[] args) {
    		Joeph a = new Joeph();
    		int people,password;	//参与人数与密码（报到多少的人出列）
    		Scanner sc = new Scanner(System.in);
    		System.out.println("输入参与游戏人数：");
    		people = sc.nextInt();
    		for(int i = 1; i <= people;i++) {	//向链表中插入元素
    			a.add(i);
    		}
    		System.out.println("输入密码：");
    		password = sc.nextInt();
    		while(a.getSize()!=0) {	//链表长度不为空时一直删除
    			a.remove(password);
    		}
    		System.out.println();
    		System.out.println("最后存活下来的是：" + a.first.num);
    	}
    	/**
    	 * output:
    	 * 输入参与游戏人数：
    	 * 3
    	 * 输入密码
    	 * 3
    	 * 3	1	2
    	 * 最后存活下来的是：2
    	 */