#include<stdio.h>
	#include<stdlib.h>
	
	//定義單循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)
	typedef struct CNode{
		int data;
		struct CNode *next;
	}CNode;
	typedef CNode *CLinkList;
	
	//初始化一個(gè)指向頭節(jié)點(diǎn)的指針，使頭指針->next=頭指針，頭指針->data不做處理
	void InitList_L(CLinkList *L){
		(*L) = (CLinkList)malloc(sizeof(CNode));
		if(!(*L))
			exit(-2);
		(*L)->next = *L;  
	}
	
	//頭插法建立單循環(huán)鏈表
	int CreateList_HL(CLinkList *L,int s[],int n){ //二級(jí)指針
		int i;
		CLinkList p;
		*L = (CLinkList)malloc(sizeof(CNode));
		if(!(*L))
			exit(-2);
		(*L)->next = *L;			//只有一個(gè)頭節(jié)點(diǎn)head，就讓next指向自己
		for(i=0; i<n; i++){
			p = (CLinkList)malloc(sizeof(CNode));
			if(!p)
				exit(-2);
			p->data = s[i];			//錄入數(shù)據(jù) 
			p->next = (*L)->next;   //將頭指針?biāo)赶虻南乱粋€(gè)結(jié)點(diǎn)的地址，賦給新創(chuàng)建結(jié)點(diǎn)的next 
			(*L)->next = p;		    //將新創(chuàng)建的結(jié)點(diǎn)的地址賦給頭指針的下一個(gè)結(jié)點(diǎn)
		}
		return 1;
	} 
	
	//尾插法建立單循環(huán)鏈表
	int CreateList_TL(CLinkList *L,int s[],int n){
		int i;
		CLinkList p, q;	
		*L = (CLinkList)malloc(sizeof(CNode));
		if(!(*L))
			exit(-2);
		(*L)->next = *L;	//只有一個(gè)頭節(jié)點(diǎn)head，就讓next指向自己
		for(i=0,q=*L; i<n; i++){
			p = (CLinkList)malloc(sizeof(CNode));
			if(!p)
				exit(-2);
			p->data = s[i];	//錄入數(shù)據(jù) 
			q->next = p;
			q = q->next;
		}
		q->next = *L;      //最后一個(gè)結(jié)點(diǎn)指向head
		return 1;
	}
	
	//求單循環(huán)鏈表的長(zhǎng)度
	int ListLength(CLinkList L){
		CLinkList p;				
		int count;
		if(L){
			count = 0;
			p = L;			   //p指向頭結(jié)點(diǎn)  
			while(p->next!=L){ //p沒到表頭
				count++;
				p = p->next;
			}
		}
		return count;
	} 
	
	//得到指向單循環(huán)鏈表第i個(gè)元素的指針
	CLinkList GetElemPtr(CLinkList L, int i){										
		int count;
		CLinkList p;
		if(L&&i>0){
			count = 1;
			p = L->next;
			while(p!=L && count<i){
				count++;
				p = p->next;
			}
			if(p!=L)   //L為頭指針
				return p;
		}
		return NULL;
	}
	
	//單循環(huán)鏈表第i個(gè)位置插入元素e
	int ListInsert(CLinkList L, int i, int e){
		CLinkList p, s;
		int j;
		if(i<1 || i>ListLength(L)+1)	//插入位置不合理
			return 0;
		p = L;
		j = 0; 
		while(j<i-1){  //尋找第i-1個(gè)結(jié)點(diǎn)
			p = p->next;
			++j;
		}
		s = (CLinkList)malloc(sizeof(CNode));
		if(!s)
			exit(-2);
		s->data = e;
		s->next = p->next;
		p->next = s;
		return 1;		
	} 
	
	//單循環(huán)鏈表第i個(gè)位置刪除元素e
	int ListDelete(CLinkList L, int i, int *e){
		CLinkList pre, p; 
		int j;
		if(i<1 || i>ListLength(L))	//刪除位置不合理
			return 0;
		pre = L;
		j = 1; 
		while(pre->next && j<i){  //尋找第i個(gè)結(jié)點(diǎn)，并令pre指向其前驅(qū) 
			pre = pre->next;
			++j;
		}
		p = pre->next;
		pre->next = p->next;
		*e = p->data;
		free(p);
		p=NULL;
		return 1; 
	}
	
	//遍歷單循環(huán)鏈表
	void ListTraverse(CLinkList L){
		CLinkList p;
		p = L->next;	  //p指向頭結(jié)點(diǎn)，正向訪問鏈表
		while(p!=L){
			printf("%d ",p->data);
			p = p->next;
		}
		printf("\n");
	}
	
	//判斷單循環(huán)鏈表是否為空
	int ListEmpty(CLinkList L){
		if(L!=NULL && L->next==L)  //單循環(huán)鏈表存在并且只有頭結(jié)點(diǎn) 
			return 1;
		else
			return 0;
	}
	
	/*
	用單循環(huán)鏈表解決約瑟夫環(huán)問題(帶頭結(jié)點(diǎn))
	這里的單循環(huán)鏈表使用了帶頭結(jié)點(diǎn)的，方便找到表頭的位置，但是由于頭結(jié)點(diǎn)不存儲(chǔ)元素，因此需要跳過頭結(jié)點(diǎn)
	鏈表插入刪除都比較方便，不需要移動(dòng)大量元素，只需要移動(dòng)指針即可，適合這一類問題
	*/
	void Algo(CLinkList L,int k,int m){ //從編號(hào)為k的人開始數(shù)，數(shù)到m的那個(gè)人出隊(duì)列
		int count,i,j;  //count表示每次從1開始數(shù)，i用來找編號(hào)為k的結(jié)點(diǎn)的前驅(qū)
		CLinkList pre,p;
		pre=L;
		count=1,i=1,j=1; 
		/*尋找第k個(gè)結(jié)點(diǎn)，并令pre指向其前驅(qū)*/
		while(i<k){       
			if(pre->next==L) //跳過頭結(jié)點(diǎn)
				pre=pre->next->next;
			else
			    pre = pre->next;
			++i;
		}
		while(L->next!=L){  //如果單循環(huán)鏈表不為空
			if(count==m){
				/*下一個(gè)結(jié)點(diǎn)不是頭結(jié)點(diǎn)，直接刪除*/
				if(pre->next!=L){  
					p=pre->next;
					printf("第%d次出環(huán)的元素是%d\n",j++,p->data);
					pre->next=p->next;
					free(p);
					p=NULL;
					count=1;
				}
				/*下一個(gè)結(jié)點(diǎn)是頭結(jié)點(diǎn)，下下個(gè)結(jié)點(diǎn)不是頭結(jié)點(diǎn)，跳過頭結(jié)點(diǎn)，刪除下下個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)不保存數(shù)據(jù)，因此不參與運(yùn)算）*/
				else if(pre->next->next!=L){ 
					p=pre->next->next;
					printf("第%d次出環(huán)的元素是%d\n",j++,p->data);
					pre->next->next=p->next;
					free(p);
					p=NULL;
					count=1;
				}
				/*下一個(gè)結(jié)點(diǎn)是頭結(jié)點(diǎn)，下下個(gè)結(jié)點(diǎn)也是頭結(jié)點(diǎn)，說明單循環(huán)鏈表已經(jīng)為空了,只剩下頭結(jié)點(diǎn)，因此跳出循環(huán)*/
				else  
					break;
			}
			count++;        //count代表要?jiǎng)h除的結(jié)點(diǎn)數(shù)的數(shù)，始終在pre指向的結(jié)點(diǎn)之前
			if(pre->next==L) //跳過頭結(jié)點(diǎn)
				pre=pre->next->next; //pre指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
			else
				pre = pre->next;     //pre指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
		}
	}

	void main(){
		CLinkList L;
		int n=5,s[5]={1,2,3,4,5}; //假設(shè)5個(gè)人圍坐一圈
		int k=3,m=2;              //第一次從編號(hào)為k的人開始數(shù)，數(shù)到m的那個(gè)人出隊(duì)列
		CreateList_TL(&L,s,n);    //頭插法建立單循環(huán)鏈表
		ListTraverse(L);          //遍歷原始隊(duì)列
		printf("假設(shè)第一次從編號(hào)為%d的人開始數(shù)，數(shù)到%d的那個(gè)人出環(huán)\n",k,m);
		Algo(L,k,m);       //用單循環(huán)鏈表解決約瑟夫環(huán)問題(帶頭結(jié)點(diǎn))
	}

	/*
	用循環(huán)數(shù)組解決約瑟夫環(huán)問題
	解決問題的難點(diǎn)有兩個(gè):
	1、如何求下一個(gè)的人的位置：在循環(huán)數(shù)組中向后移動(dòng)采用：(k+l)%n
	2、此人出圈后對(duì)這個(gè)人的位置如何處理：先將出圈人的位置打印輸出，然后將其位置元素設(shè)置為0，表示它已出圈，以后見到它就直接跳過去
	*/
	void Algo2(int s[],int n,int k0,int m){  //開始一共有n個(gè)人，從第k0個(gè)人開始數(shù)，數(shù)到m的那個(gè)人出隊(duì)列
		int i,j,k=k0-1;     //元素訪問的下標(biāo)為 k，初始時(shí)從第k0個(gè)人開始數(shù)
	    for(i=0;i<n;i++){   //總共循環(huán)n次，每循環(huán)一次，出隊(duì)一個(gè)元素，k在循環(huán)中會(huì)不斷的運(yùn)動(dòng)
	        j=1;            //j表示數(shù)的數(shù)，初始為1
	        while(j<m){     //如果還沒有數(shù)到m
	            while(s[k]==0) //如果s[k]為0，證明它已經(jīng)出圈了，則跳過它
					k=(k+1)%n; 
	            j++;         //數(shù)下一個(gè)數(shù)
	            k=(k+1)%n;   //數(shù)組下標(biāo)向后走一步
	        }
	        while(s[k]==0) //如果數(shù)到m發(fā)現(xiàn)它出圈了，則跳過它，找到第一個(gè)沒出圈的數(shù)
				k=(k+1)%n;
	        printf("第%d次出環(huán)的元素是%d\n",i+1,s[k]); //先將出圈人的位置打印輸出
	        s[k]=0; //然后將其位置元素設(shè)置為0，表示它已經(jīng)出圈
	    }
	}

	void main(){
		int n=5,s[5]={1,2,3,4,5}; //假設(shè)5個(gè)人圍坐一圈
		int k=3,m=2;              //第一次從編號(hào)為k的人開始數(shù)，數(shù)到m的那個(gè)人出隊(duì)列
		printf("假設(shè)第一次從編號(hào)為%d的人開始數(shù)，數(shù)到%d的那個(gè)人出環(huán)\n",k,m);
		Algo2(s,n,k,m);    //用循環(huán)數(shù)組解決約瑟夫環(huán)問題
	}

	/*
	用遞歸解決約瑟夫環(huán)問題
	n指的是總?cè)藬?shù)，m指的是每次最大報(bào)到的數(shù)值，i是第i次，該函數(shù)每次可以求出第i次扔海里的人的編號(hào)
	*/
	int Algo3(int n,int m,int i){
		if(i==1)
			return (n+m-1)%n;
		else
			return (Algo3(n-1,m,i-1)+m)%n;
	}

	void main(){
		int n=5; //假設(shè)5個(gè)人圍坐一圈
		int m=2; //數(shù)到2的那個(gè)人出環(huán)             
		printf("假設(shè)第一次從編號(hào)為1的人開始數(shù)，數(shù)到%d的那個(gè)人出環(huán)\n",m);
		for(int i=1;i<=n;i++)
			printf("第%d次出環(huán)的元素是%d\n",i,Algo3(n,m,i)+1); //因?yàn)榍蟪龅慕Y(jié)果是數(shù)組中的下標(biāo)，最終的編號(hào)還要加1
	}

	/*
	用迭代解決約瑟夫環(huán)問題
	遞推公式：
	f(N,M)=(f(N?1,M)+M)%N
	f(N,M)表示，N個(gè)人報(bào)數(shù)，每報(bào)到M時(shí)殺掉那個(gè)人，最終勝利者的編號(hào)
	f(N?1,M)表示，N-1個(gè)人報(bào)數(shù)，每報(bào)到M時(shí)殺掉那個(gè)人，最終勝利者的編號(hào)
	*/
	int Algo4(int n,int m){
		int i,p=0;
		for(i=2;i<=n;i++){
			p=(p+m)%i;
		}
		return p+1; //因?yàn)榍蟪龅慕Y(jié)果是數(shù)組中的下標(biāo)，最終的編號(hào)還要加1
	}

	void main(){
		int n=5; //假設(shè)5個(gè)人圍坐一圈
		int m=2; //數(shù)到2的那個(gè)人出環(huán)
		printf("假設(shè)第一次從編號(hào)為1的人開始數(shù)，最后出環(huán)的是：%d\n",Algo4(n,m));
	}