使用連結清單實作環結構以解決約瑟夫環問題

        自從上次面試後，發現自己的基礎很不行，應該說一直不行(因為是電信專業的，隻學過簡單地VB和C，當然這隻是一個借口而已)。總之，決定以後争取每天寫個小程式動動腦筋，東西可能寫的很爛。但是隻要動腦筋的目的達到了，也就沒有什麼好計較了得。  

       今天寫的是一個關于約瑟夫環的問題。關于約瑟夫環，百度複制一下：約瑟夫環是一個數學的應用問題：已知n個人（以編号1，2，3...n分别表示）圍坐在一張圓桌周圍。從編号為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。

      先定義一個節點類Node：

package com.wly.linkedcirclelist;

/**
 * 節點類
 * @author wly
 *
 */
public class Node {

	private int id;
	private Node next;
	
	public Node(int id) {
		super();
		this.id = id;
	}
	
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
}
           

       再定義一個連結清單類Linkedcirclelist：

package com.wly.linkedcirclelist;

/**
 * 單項"環"型連結清單
 * @author wly
 *
 */
public class LinkedCircleList {

	private Node firstNode; //頭節點
	private Node lastNode; //尾節點
	private int size; //這裡置了一個标記size，也可以通過周遊得到長度，但是那樣可能比較耗時，現在這樣做的話，在多線程時可能會出問題。
	
	public LinkedCircleList() {
		size = 0;
	}
	
	/**
	 * 向連結清單的尾部添加節點
	 * @param node
	 */
	public void addNode(Node node) {
		if(isEmpty()) {
			firstNode = node;
			lastNode = node;
		} else {
			//将首尾節點連接配接，是連結清單變成一個"環"結構
			lastNode.setNext(node);
			node.setNext(firstNode);
			lastNode = node;
		}
		size ++;
	}
	
	/**
	 * 删除和目前節點相距n個節點的那個節點
	 * @param node 目前開始報數的節點
	 * @param n 報數步長
	 * @return
	 */
	public Node deleteAfterN(Node node,int n) {
		for(int i=n-2;i>0;i--) {
			node = node.getNext();
		}
		//删除節點
		System.out.println("删除節點:" + node.getNext().getId());
		node.setNext(node.getNext().getNext());
		size --;
		return node.getNext();
	}
	
	
	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return (firstNode == null);
	}
	
	public Node getFirstNode() {
		return firstNode;
	}
}
           

        最後測試一下，建立Test類：

package com.wly.linkedcirclelist;

public class Test {

	public static void main(String[] args) {
		resolve(9, 1, 5);
	}
	
	public static void resolve(int n,int startIndex,int step) {
		
		//1.建立連結清單
		LinkedCircleList linkedList = new LinkedCircleList();
		for(int i=1;i<=n;i++) {
			Node node = new Node(i);
			linkedList.addNode(node);
		}
		//2.循環處理
		Node node = linkedList.getFirstNode();
		while(linkedList.size() > 0) {
			node = linkedList.deleteAfterN(node, step);
		}
	}
}
           

測試結果:

删除節點:5

删除節點:1

删除節點:7

删除節點:4

删除節點:3

删除節點:6

删除節點:9

删除節點:2

删除節點:8

轉帖請保留出處:http://blog.csdn.net/u011638883/article/details/11783793