【資料結構和算法分析】循環連結清單及約瑟夫問題

循環連結清單及約瑟夫問題

循環連結清單：

                循環連結清單可以為單連結清單，也可以為雙連結清單，但我不想把問題搞得那麼複雜，姑且就做單連結清單的循環形式吧。

                我們在實作了連結清單後，必然會提出一個問題：連結清單能不能首尾相連？怎樣實作？

                答案：能。其實實作的方法很簡單，就是将表中最後一個結點的指針域指向頭結點即可（P->next = head;）。這種形成環路的連結清單稱為循環連結清單。

代碼如下：

public class MyCircleList {
	
	Node headNode;
	Node tailNode;
	int length;
	
	public MyCircleList(Node node){
		this.headNode = node;
		this.tailNode = node;
		length = 1;
	}
	/*
	 * 預設在尾結點插入
	 */
	public void insert(Node node){
		insert(node, length);
	}
	/*
	 * @param Node node 插入的結點 , int index 結點插入的位置
	 */
	public void insert(Node node,int index){
		if (index < 0 || index > length) {
			throw new IndexOutOfBoundsException();
		}
		if (index == 0) {
			this.tailNode.next = node;
			node.next = this.headNode;
			headNode = node;
		}else if (index == length) {
			tailNode.next = node;
			tailNode = node;
			node.next = this.headNode;
		}else {
			Node otherNode = this.headNode;
			while (index > 1) {
				otherNode = otherNode.next;
				index--;
			}
			node.next = otherNode.next;
			otherNode.next = node;		
		}
		length++;
	}
	/*
	 * @param int index 删除結點的位置
	 */
	public void delete(int index){
		if (index < 0 || index >= length) {
			throw new IndexOutOfBoundsException();
		}
		if (index == 0 && length == 1) {
			tailNode = headNode = null;
		}else if (index == 0 && length != 1) {
			tailNode.next = headNode.next;
			headNode = headNode.next;
		}else {
			Node otherNode = this.headNode;
			while (index > 1) {
				otherNode = otherNode.next;
				index--;
			}
			otherNode.next = otherNode.next.next;
		}
		length--;
	}
	
	/*
	 * @param int index 檢視  index 處的 data
	 */
    public Object getData(int index){
    	if (index < 0 || index >= length) {
			throw new IndexOutOfBoundsException();
		}
    	Node otherNode = headNode;
    	for (int i = 0; i < index; i++) {
			otherNode = otherNode.next;
		}
    	return otherNode.data;
    }
    /*
     * @param int index 修改的 data 的位置 ,Object data 所需修改的 data
     */
    public void setData(int index,Object data){
    	if (index < 0 || index >= length) {
			throw new IndexOutOfBoundsException();
		}
    	Node otherNode = headNode;
    	for (int i = 0; i < index; i++) {
			otherNode = otherNode.next;
		}
    	otherNode.data = data;
    }
	public void print(){
		Node otherNode = this.headNode;
		for (int i = 0; i < length; i++) {
			System.out.print(otherNode.data+" ");
			otherNode = otherNode.next;
		}
		System.out.println();
	}

	
}

class Node{
	
	/*
	 * 節點類，包括結點的值 data 和指向下一結點的指針 next,單連結清單适用
	 */
	
	Object data;
	Node next;
	
	public Node(){
		data = null;
		next = null;
	}
	
	public Node(Object data){
		this.data = data;
		this.next = null;
	}
	
	public Node(Object data,Node nextnode){
		this.data = data;
		this.next = nextnode;
	}
	
	/*
	 * 判斷有無下一結點
	 * @return boolean 若true，則該結點有下一結點
	 */
	public boolean hasnext(){
		return this.next != null;
	}
	
	
}
           

約瑟夫問題：

約瑟夫問題幾乎是最經典的用來講解循環連結清單的案例了。為什麼呢？我們來看看這個問題的描述就會明白了：

有一隊由n個冒險家組成的探險隊深入到熱帶雨林中，但他們遭遇到了食人族，食人族的遊戲規則是讓他們圍成一圈，然後標明一個數字m，從第1個人開始報數，報到m時，這個人就要被吃掉了，然後從下一個人開始又重新從1報數，重複這個過程，直到剩下最後一個人，這個人是幸運者，可以離開而不被吃掉。那麼問題是，誰是這個幸運者呢？

我們來舉個例子：

假設這個探險隊有6個探險家，食人族標明的數字m是5，那麼在第一輪中，5号會被吃掉，剩下的就是：1, 2, 3, 4, 6總共5個人，然後從6号開始，重新從1開始報5個數：6, 1, 2, 3, 4，是以在第二輪裡面被吃掉的就是4号……一直重複這個過程，按順序應該是：5, 4, 6, 2, 3被吃掉，剩下1号活下來。

解決這個問題并不是隻能用循環連結清單的，但使用循環連結清單應該是最友善的。我寫的代碼如下：

public class Josephus {
	
	public static final int N = 6;    //代表 6 位人數
	public static final int M = 5;    //標明的數字為 5

	public static void main(String[] args){
		
		//初始化循環連結清單，構造出來為 1,2,3,4,5,6的連結清單分别代表六個人
		MyCircleList myCircleList = new MyCircleList(new Node(1));
		for (int i = 2; i <= N; i++) {
			myCircleList.insert(new Node(i));
		}
	
		
		Node pre = null;
		Node p = myCircleList.headNode;
		for (int i = 0; i < N-1; i++) {     //需要周遊的輪次，執行 N-1 次
			for (int j = 1; j < M; j++) {    //每次周遊的報數，數 M-1 人
				pre = p;
				p = p.next;
			}
	                System.out.println("出局的是：" + p.data);   //輸出
 	                pre.next = p.next;          //删除一個結點
                        p = pre.next;	
 		}
 	}
}