嘗試表達
本人試著去表達約瑟夫環問題：一群人圍成一個圈，作這樣的一個游戲，選定一個人作起點以及數數的方向，這個人先數1，到下一個人數2，直到數到游戲規則約定那個數的人，比如是3，數到3的那個人就離開這個游戲；按這樣的規則，剩下一個人，游戲就結束，這個人就為贏家。(讀者可以試著表達，不認同，直接忽略）
抽象分析
這個人就是一個數據個體，數據結點，數據元素。上面產生的數據結構為：單方向循環的鏈。可以用鏈表實現，也可以用數組來實現。
鏈表到數組的遷移
人（數據元素、
數據結點、數據個體）
結點關系
(結構關系
結點移動)
范型“指針”定義
：能夠定位到下一個結點（變）
“指針“
移到下一個結點
拿到下一個結點的”指針“即可，一般都有作“移動”變量，移動變量變，就相當於移動。
刪除結點
數組
連續的數組元素（基本數據類型，機構體）
數組元素裡面保存有下個結點元素的數組元素下標position。
arrayname固定的，只要給出position，就可以算是定位到數組元素
≈poisiton
[]
move =array[move]
元素內容 = -1
（數組的大小固定）
鏈表
離散的鏈表結點（結構體）
結構體裡面保存有下一個結點的指針 node* next
poiter直接定位到結點，在結合常員變量，就可以拿到數據
=poiter
->
move = move -> next
銷毀
畫圖分析：
代碼實現：
#include<stdio.h>
#include<stdlib.h>
/*Function:遍歷數組實現的約瑟夫環。traverse_joseph_circle_array
*param:int[] array,int tail
*return: void
* 假設是用數組實現的約瑟夫環鏈一定存在。
* */
void traverse_joseph_circle_array (int array[], int tail ){
//數組保存的是下個結點的“指針”，只不過這個指針要通過array才能夠拿到結點的元素，因為array是固定的，只要變換指針就能夠變換結點。
int move= array [tail] ;//從頭開始遍歷
do{
printf ("%d ;",move) ;//數組的元素位置（下標號）就代表這個結點，鏈表是通過結點裡面的元素，
move = array[move];
}while ( move != array [tail]);
printf("\n");
}
/*Function:約瑟夫環問題的數組實現。eliminate_array
*param:int[]array,int tail, int step
*return: void
* */
void eliminate_array1 (int array[], int tail ,int step ){
int move = tail ;
int save_previous = move ;
int count = 0 ;
while(move != array[move]){
save_previous = move ;
move = array [move];
if(++ count == step){ //數數
array[save_previous] = array[move] ;//重構鏈
if( tail == move) tail = save_previous;//銷毀前，判斷要不要更新新約瑟夫環
printf("當前要刪除的結點：%d \n",move);//銷毀前告知用戶
array[move]= -1 ;//銷毀
printf("當前的約瑟夫環為：\n") ;
traverse_joseph_circle_array (array,tail);
count = 0 ;
move = save_previous ;
}
}
}
/*Function:約瑟夫環問題的數組實現。eliminate_array
*param:int[]array,int tail, int step
*return: void
* */
void eliminate_array2 (int array[], int tail ,int step ){
int move = tail ;
int save_previous = move ;
int count = 0 ;
//每執行一此循環，刪除一個結點。
while (move != array[move]){
save_previous = move ;
move = array[move];
// 移動到要刪除的結點
for (count = 0 ; count < step -1 ; count++){
move = array[move] ;
}
//刪除結點，重構約瑟夫環，更新tail
array[save_previous] = array[move] ;//重構鏈
if( tail == move) tail = save_previous;//update tail
printf("當前要刪除的結點：%d \n",move);//銷毀前告知用戶
array[move]= -1 ;//銷毀
printf("當前的約瑟夫環為：\n") ;
traverse_joseph_circle_array (array,tail);
//移動回消除結點的上一個結點，回到初態，即將進行下一輪的游戲。
count = 0 ;
move = save_previous ;
}
}
int main(){
//創建有6個結點的約瑟夫環int array[6];
int array[20];
int length = sizeof(array)/sizeof(int);
int ctl ;
for (ctl = 0 ; ctl < length -1 ;ctl ++){
array[ctl] = ctl + 1;
}
array [length -1] = 0 ;
traverse_joseph_circle_array(array,length-1);
int tail = length -1;
//eliminate_array1(array ,tail ,3) ;
eliminate_array2(array ,tail ,3) ;
return 0 ;
}
結果：
0 ;1 ;2 ;3 ;4 ;5 ;6 ;7 ;8 ;9 ;10 ;11 ;12 ;13 ;14 ;15 ;16 ;17 ;18 ;19 ; 當前要刪除的結點：2 當前的約瑟夫環為： 3 ;4 ;5 ;6 ;7 ;8 ;9 ;10 ;11 ;12 ;13 ;14 ;15 ;16 ;17 ;18 ;19 ; 當前要刪除的結點：5 當前的約瑟夫環為： 6 ;7 ;8 ;9 ;10 ;11 ;12 ;13 ;14 ;15 ;16 ;17 ;18 ;19 ; 當前要刪除的結點：8 當前的約瑟夫環為： 9 ;10 ;11 ;12 ;13 ;14 ;15 ;16 ;17 ;18 ;19 ; 當前要刪除的結點：11 當前的約瑟夫環為： 12 ;13 ;14 ;15 ;16 ;17 ;18 ;19 ; 當前要刪除的結點：14 當前的約瑟夫環為： 15 ;16 ;17 ;18 ;19 ; 當前要刪除的結點：17 當前的約瑟夫環為： 18 ;19 ; 當前要刪除的結點：18 當前的約瑟夫環為： 19 ;
時間復雜度分析：
本人推薦使用第二種算法來作，對於時間復雜度，要通過邏輯思考，要刪除(n-1)個結點，循環執行(n-1)次，內循環執行k=step 次，這個k可能很大；還有在外循環，與內循環無關的，必須執行的某些語句,執行次數為c，表達式為：(n-1)(k+c)=nk +nc -k -c ,表達為：n*k - c0 * n - c1 *k ,大O表達為：O(nk)