約瑟夫環(huán)(約瑟夫環(huán)問題)

引言

黑鏡3：急轉(zhuǎn)直下

約瑟夫問題是循環(huán)鏈表的一個典型應(yīng)用，其描述如下：m個人圍成了一圈，從其中任意一個人開始，按順時針順序使所有人一次從1開始報數(shù)，報道n的人出列；然后使n之后的人接著從1開始報數(shù)，再次使報到n的人出列。。。。。。如此下去，求出列的順序及最后留下來的人的編碼。

舉個栗子

為了更清晰的描述問題，可以將m與n設(shè)定為具體數(shù)字，如m=8，n=3，即8個人圍著坐成一圈。

給這8個人編號，使編號為1的人開始從1開始報數(shù)，報到3的人出列；

編號為4的人接著從1開始報數(shù)，報到3出列。。。

如此重復(fù)，知道最后只剩下一個人。額，有點不太好想，那我們來畫圖看看吧。

01.png

02.png

03.png

04.png

05.png

06.png

07.png

08.png

09.png

來，我們來把步驟總結(jié)一下

第一輪：從1到3，第三個人出列 第二輪：第4個人從1開始報數(shù)，第6個人報到3，則第6個人出列 第三輪：第7個人從1開始報數(shù)，第1個人報到3，則第1個人出列 第四輪：第2個人從1開始報數(shù)，第5個人報到3，則第5個人出列 第五輪：第7個人從1開始報數(shù)，第2個人報到3，則第2個人出列 第六輪：第4個人從1開始報數(shù)，第8個人報到3，則第8個人出列 第七輪：第4個人從1開始報數(shù)，這個時候只剩下4和7，第4個人又報到3，則第4個人出列。 最后，只剩下第7個人，此時，報數(shù)終止。

看圖發(fā)現(xiàn)

當(dāng)數(shù)據(jù)量較小時，通過作圖很容易就能找到出局順序；

但是當(dāng)數(shù)據(jù)量較大時，人工計算幾乎是不可能的。

要解決這樣的問題，需要借助一定的編程算法，而循環(huán)鏈表就正好可以用來解決此問題。

首先用這些數(shù)據(jù)創(chuàng)建一個循環(huán)鏈表；

然后設(shè)置限定條件；

并循環(huán)遍歷鏈表；

當(dāng)遍歷到要出局的元素時，就將其刪除；

這樣循環(huán)操作指導(dǎo)鏈表中只剩下一個結(jié)點。

代碼實現(xiàn)

clist.h （頭文件）

#ifndef _CLIST_H_#define _CLIST_H_struct Node;typedef struct Head *pHead;//定義頭結(jié)點類型為pHeadtypedef struct Node * pNode;//數(shù)據(jù)結(jié)點類型//定義頭結(jié)點 struct Head{ int length; pNode next;//指向下一個結(jié)點的指針 }; //定義數(shù)據(jù)結(jié)點 struct Node { int data; pNode next; //指向后繼結(jié)點的指針 }; pHead ClistCreate(); //聲明創(chuàng)建循環(huán)鏈表的方法 int getLength(pHead ph); //獲取循環(huán)鏈表的長度 int IsEmpty(pHead ph); //判斷鏈表是否為空 int ClistInrt(pHead ph,int pos,int val); //在鏈表的pos位置插入元素 val void print(pHead ph); //打印循環(huán)鏈表中的元素 #endif

clist.c（文件）

#include "clist.h" #include <stdio.h> #include <stdlib.h> pHead ClistCreate(){ //創(chuàng)建循環(huán)鏈表 pHead ph=(pHead)malloc(sizeof(struct Head));//為頭結(jié)點分配空間 if(ph==NULL){ printf("分配頭結(jié)點失敗");//為了方便運行結(jié)果查看，不設(shè)置return返回值 } //創(chuàng)建好頭結(jié)點后，初始化頭結(jié)點中的數(shù)據(jù) ph->length=0; ph->next=NULL; return ph;//帶頭結(jié)點返回 } int IsEmpty(pHead ph)//判斷鏈表是否為空 { if(ph=NULL) printf(“傳入的循環(huán)鏈表有誤”); if(ph->length==0){ return 1; //說明為空 } el{ return 0;//說明不為空 } } //在鏈表的pos位置插入元素val int ClistInrt(pHead ph,int pos,int val){ if(ph==NULL||pos<0||pos>ph->length){ printf(“插入元素時，參數(shù)傳入有誤! ”); } pNode pval=val;//將值val保存到此結(jié)點中 //判斷在哪個位置插入元素，先判斷鏈表是否為空 if(IsEmpty(ph)){ //如果鏈表為空 ph->next=pval;//直接將結(jié)點插入到頭結(jié)點后 pval->next=pval;//將第一個結(jié)點指向他自己 } el{ //循環(huán)鏈表不為空，則分為在頭部插入（即在頭結(jié)點后）和普通位置插入 pNode pRear=ph->next; if(pos==0)//在第一個位置（頭結(jié)點后）插入 { //在0號位置插入，需要先找到尾節(jié)點 while(pRear->next!=ph->next) //循環(huán)結(jié)束的條件 { pRear=pRear->next;//pCur指針向后移動 } //while循環(huán)結(jié)束后，pRear指向尾節(jié)點 //然后插入元素 pval->next=ph->next; ph->next=pval; pRear->next=pval;//這3個步驟順序不能更改 } el{ //如果不是0號位置插入，這和單鏈表無區(qū)別 pNode pCur=ph->next; for(int i=1;i<pos;i++){ //遍歷鏈表找到要插入的位置 pCur=pCur->next;//pCur指針往后移 } //循環(huán)結(jié)束，此時pCur指向的是要插入的位置 pval->next=pCur->next;//指針斷開再連接的過程 pCur->prev=pval; } } ph->length++; return 1; } //打印循環(huán)鏈表中的元素 void print(pHead ph){ if(ph==NULL||ph->length==0){ printf("參數(shù)傳入有誤！"); } pNode pTmp=ph->next; for(int i=0;i<ph->length;i++){ printf("%d",pTmp->data); pTmp=pTmp->next; } printf(" "); }

ok,以上就講循環(huán)鏈表的一些方法都已經(jīng)第一好了，接下來我們來測試一下

Joph.c(測試文件)

#define _CRT_SECURE_NO_WARNINGS #include "clist.h" #include <stdio.h> #include <stdlib.h> int main(){ int m,n; printf("請輸入約瑟夫環(huán)的總?cè)藬?shù)： "); scanf("%d",&m); if(m<=0){ printf(“請輸入正確的數(shù)字！ ”); return 0; } printf("請輸入被提出的報數(shù)： "); scanf("%d",&n); if(n<=0){ printf("請輸入正確的數(shù)字! "); return 0; } //根據(jù)輸入的m創(chuàng)建鏈表 m即鏈表的長度 pHead ph=NULL; ph=ClistCreate(); if(ph==NULL){ printf("創(chuàng)建循環(huán)鏈表失敗！ "); return 0; } //插入元素 for(int i=m;i>0;i--){ ClistInrt(ph,0,i);//使用頭插法從m到1倒序插入 } print(ph); printf("被踢順序： "); //插入元素后，就循環(huán)遍歷鏈表 pNode node=ph->next; //node指針指向第一個結(jié)點 while(node->next!=node){ //循環(huán)結(jié)束條件，結(jié)點指向其自身，此時剩下最后一個結(jié)點 for(int i=1;i<n-1;i++){ //i<n-1,即報數(shù)報到n就重新開始 node=node->next; } //for 循環(huán)條件結(jié)束后，node指針指向待出局的結(jié)點的前驅(qū)結(jié)點 pNode pTmp=node->next;//pTmp指向要出局的結(jié)點 //接下來要先判斷這個結(jié)點是0號位置的結(jié)點還是其他位置的結(jié)點 if(pTmp==ph->next){ //如果此結(jié)點在0號位置 ph->next=pTmp->next;//對頭結(jié)點進行處理 node->next=pTmp->next; printf("%d",tTmp->data); free(pTmp); ph->length--; } el{ //如果此結(jié)點在其他位置 node->next=pTmp->next; printf("%d",pTmp->data); free(pTmp); ph->length--; } node=node->next; } node->next=node;//循環(huán)結(jié)束，只剩下node一個結(jié)點，讓其指向自身 printf(" "); printf("鏈表中最后留下的是"); printf(ph); system("pau"); return 0; }

上方的測試代碼中，創(chuàng)建了一個循環(huán)鏈表，以循環(huán)鏈表為基礎(chǔ)來計算這一圈人的出局序列，并求出最后留下來的人。

解決約瑟夫問題并沒有用到循環(huán)鏈表的全部算法，因此，在本例子中只涉及到了此問題的相關(guān)方法實現(xiàn)。即：

首先創(chuàng)建一個循環(huán)鏈表

兩個變量去設(shè)置這個循環(huán)鏈表的長度即報數(shù)單位

然后開始遍歷

如果報到指定的報數(shù)單位，就將這個報數(shù)的位置的結(jié)點移除，并free

直到鏈表中只剩下一個結(jié)點時，終止循環(huán)

完事~~~

總結(jié)一下啦

我們從第六篇文章到本篇文章講解了最簡單的數(shù)據(jù)結(jié)構(gòu)——線性表，具體包括常用的順序表、單鏈表、雙鏈表、循環(huán)鏈表。

我們通過使用線性表來解決一些簡單的問題，從而為以后的數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)打下結(jié)實的基礎(chǔ)。

下一篇，我們來看一下android中的 LinkedList 的源碼，看看這個LinkedList內(nèi)部是怎樣一個構(gòu)成~~，敬請期待