// 二josephu問題.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<stdio.h>
#include<malloc.h>
typedef struct node 
{
	int data;
	struct node *next;
}lnode;
typedef struct pnode
{
	struct node *h;
    int length;
}tnode;
tnode creat()     //創(chuàng)建循環(huán)單鏈表
{
	tnode l;
	lnode*q,*p,*t;
	int x,y=1;
	printf("請輸入各個(gè)人的密碼以0為結(jié)束標(biāo)志：\n");
	scanf("%d",&x);
	p=(lnode*)malloc(sizeof(lnode));
	p->data=x;
    p->next=NULL;
	t=p;
	scanf("%d",&x);
	while(x!=0)
	{
		q=(lnode*)malloc(sizeof(lnode));
        q->data=x;
		q->next=NULL;
		t->next=q;
		t=q;
        scanf("%d",&x);
		y++;      //記錄鏈表中的結(jié)點(diǎn)個(gè)數(shù)
	}
   t->next=p;         //使尾結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)
   l.h=p;
   l.length=y;
   return(l);
}
void fun(tnode l,int m)
{
	lnode *p,*t,*q;
    int y=0,x=m;    //y用來記錄各人所報(bào)的數(shù)
	p=l.h;
	printf("依次出列的各個(gè)人手持的密碼是：\n");
    while(l.length!=0)
	{	  q=p;
		  y++;
		  p=p->next;
		  while(y<x)
		  {
			y++;
			t=q;      //t指向要刪除結(jié)點(diǎn)的前一結(jié)點(diǎn)
            p=p->next;
			q=q->next;  //q指向要刪除的結(jié)點(diǎn)
		  }		
		x=q->data;
		printf("%d ",q->data);
		t->next=p;
		free(q);
		l.length--;
		y=0;
	}	
}
void putout(tnode l)
{
	int x=0;
	lnode *p;
	p=l.h;
	printf("從1號開始個(gè)人的密碼是：\n");
	while(x!=l.length)
	{
		x++;
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
void main()
{
   int m;
   tnode l;
   printf("建立循環(huán)單鏈表：\n");
   l=creat(); 
   putout(l);
   printf("請輸入初始報(bào)數(shù)的上限值m：\n");
   scanf("%d",&m);
   fun(l,m);
   printf("\n");
}