❶ java循環單鏈表實現約瑟夫環
看了你的代碼，不是很明白，給你提幾個建議吧：
1、不需要tail節點
2、remove方法應該對刪除節點前面的節點操作，而不是使用數字找
給你我修改的LinkList類，你參考一下：
publicclassLinkList{
privateNodehead;
intcurlen=0;
//創建鏈表
publicvoidcreatelist(intcode)throwsException{
insert(curlen,code);
}
publicvoidinsert(inti,intcode)throwsException{
Nodes=newNode(code);
if(i==0){
s.setNext(head);
head=s;
}
Nodep=head;
intj=0;
while(p!=null&&j<i-1){
p=p.getNext();
j++;
}
if(j>i||p==null){
thrownewException("插入位置不合理");
}
s.setNext(p.getNext());
p.setNext(s);
// tail=s;
// tail.setNext(head);
curlen=curlen+1;
}
publicvoidremove(inti)throwsException{
Nodep=head,q=null;
intj=0;
i=i-1;
while(j<i){
q=p;
p=p.getNext();
j++;
}
if(j>i||p==null)
thrownewException("刪除位置不合法");
if(q==null){
// tail.setNext(p.getNext());
head=head.getNext();
}else
q.setNext(p.getNext());
curlen=curlen-1;
}
/**
*按照節點刪除
*@parami
*@throwsException
*/
publicvoidremove(Nodep)throwsException{
if(p.getNext()==p){
p=null;
head=null;
}
else{
Nodeq=p.getNext();
p.setNext(q.getNext());
}
curlen=curlen-1;
}
publicvoidout(intm)throwsException{
Nodep=head;
if(m==1){
System.out.print("按照順序出列");
return;
}
intcount=1;
intn=m-1;
while(curlen>0){
if(count==n){
System.out.print(p.getNext().getData()+"");
remove(p);
count=1;
}else{
count++;
}
p=p.getNext();
}
}
publicvoiddisplay(){
Nodenode=head;
for(inti=0;i<2*curlen;i++){
System.out.print(node.getData()+"");
node=node.getNext();
}
System.out.println();
}
}
❷ 求解約瑟夫環問題(Java)
package 約瑟夫環;
import java.util.LinkedList;
import java.util.List;
/**
* 約瑟夫環問題的一種描述是：編號為1.2.3…….n的n個人按順時針方向圍坐一圈 ，每人手持一個密碼（正整數），
* 開始任意選一個整數作為報數上限值，從第一個人開始順時針自1開始順序報數，報到m時停止報數。報m的人出列，
* 將他的密碼作為新的m值，從他順時針下一個人開始重新從1開始報數，
* 如此下去直到所有的人全部都出列為止。試設計程序實現，按照出列的順序列印各人的編號。
* @author Administrator
*
*/
public class Question2 {
class person {
int password;
int number;
int state = 1;
public person(int password, int number) {
this.password = password;
this.number = number;
}
public person(int number){
this.number = number;
}
}
public int ListLength(List<person> list) {
int count = 0;
if (list != null) {
for (person p : list) {
if (p.state != 0) {
count++;
}
}
}
return count;
}
public void cacle() {
// 初始化數據
List<person> list = new LinkedList<person>();
list.add(new person(3,1));
list.add(new person(1,2));
list.add(new person(7,3));
list.add(new person(2,4));
list.add(new person(4,5));
list.add(new person(8,6));
list.add(new person(4,7));
int position = -1;//初始位置
int m = 20; //第一次報多少的人出來
int count = 0;//已經報了多少人
while (ListLength(list) != 0) {
position = (position + 1) % list.size();// 位置定位
if (((person) list.get(position)).state != 0) {
count++;
}
if (count == m) {
person p = list.get(position);
System.out.print(p.number+" ");
p.state = 0;
m = p.password;
list.set(position, p);
count = 0;
}
}
}
public static void main(String[] args) {
Question2 q= new Question2();
q.cacle();
}
}
跟這差不多的。
❸ 數據結構— 循環鏈表、雙向(循環)鏈表
鏈表的兩頭連接，形成了一個環狀鏈表，稱為循環鏈表。
約瑟夫環問題，是一個經典的循環鏈表問題，題意是：已知 n 個人（以編號1，2，3，…，n分別表示）圍坐在一張圓桌周圍，從編號為 k 的人開始順時針報數，數到 m 的那個人出列；他的下一個人又從 1 還是順時針開始報數，數到 m 的那個人又出列；依次重復下去，要求找到最後出列的那個人。
例如有 5 個人，要求從編號為 3 的人開始，數到 2 的那個人出列：
出列順序依次為：
編號為 3 的人開始數 1，然後 4 數 2，所以 4 先出列；
4 出列後，從 5 開始數 1，1 數 2，所以 1 出列；
1 出列後，從 2 開始數 1，3 數 2，所以 3 出列；
3 出列後，從 5 開始數 1，2 數 2，所以 2 出列；
最後只剩下 5 自己，所以 5 出列。
循環鏈表和動態鏈表唯一不同在於它的首尾連接，這也註定了在使用循環鏈表時，附帶的最多的操作就是遍歷鏈表。在遍歷的過程中，尤其要注意循環鏈表雖然首尾相連，但並不擾山表示該鏈表沒有第一個節點和最後一個結點。所以，不要隨意改變頭指針的指向。
整個鏈表只能單方向從表頭訪問到表尾，這種結構的鏈表統稱為 「單向鏈表」或「單鏈表」。
如果演算法中需要頻繁地找某結點的前趨結點，單鏈表的解決方式是遍歷整個鏈表，增加演算法的時間復雜度，影響整體效率。
為了快速便捷地解決這類問題，在單向鏈表的基礎上，給各個結點額外配備一個指針變數，用於指向每個結點的直接前趨元素。這樣的鏈表被稱為「雙向鏈表」或者「雙鏈表」。
雙向鏈表中的結點有兩個指針域，一個指向直接前趨，一個指向直接後繼。（鏈表中第一個結點的前趨結點為NULL，最後一個結點的後繼結點為NULL）
結點的具體構成：
雙向鏈表創建的過程中，每一個結點需要初始化數據域和兩個指針域，一個指向直接前趨結點，另一個指向直接後繼結點。
創建一個雙向鏈表line（1，2，3）：
比如在（1，2，3）中插入一個結點 4，變成（1，4，2，3）。
實現效果圖：
在雙向鏈表中插入數據時，首先完成圖中標注為 1 的兩步操作，然後完成標注為 2 的兩步操作；反之，如果先完成 2，就無法通過頭指針訪問結點 2，需要額外增設指針，雖然能實現，但較前一種麻煩。
雙鏈表刪除結點時，直接遍歷鏈表，找到要刪除的結點，然後利用該結點的兩個指針域完成刪除操作。
在（1，4，2，3）中刪除結點 2：
雙向鏈表的查找操作和單鏈表的實現方法完全一樣，從鏈表的頭結點或者首元結點開始遍歷，正氏這里不做過多解釋。
更改鏈表中某結點的數據域的操作是在查找的基礎上完成的。通過遍歷找到存儲有該數據元素的結點後，直接更改其數據域就可以。
其實舉李散就是雙向鏈表和循環鏈表的結合體
例如：約瑟夫環問題其實還可以這樣玩：如果順時針報數，有人出列後，順時針找出出列位置的下一個人，開始反方向（也就是逆時針）報數，有人出列後，逆時針找出出列位置的下一個人，開始順時針報數。依次重復，直至最後一個出列。
有興趣可以自行嘗試，這里就不再分析了，因為本質就是雙向鏈表和循環鏈表。