這個是?約瑟夫循環問題!
我用的單循環鏈表做的:(VC++6.0測試通過)
#include?<stdio.h>#include?<stdlib.h>
#define?_SIZE?sizeof(Node)
typedef?struct?List
{
int?Number;
struct?List?*Next;
}Node,?*pNode;
int?iNode=0;//節點個數
pNode?CreatList(pNode?head,?int?iNum);
int?process(pNode?head,?int?k);
void?main(void)
{
pNode?head?=?NULL;
int?iNum?=?10;
int?k?=?0;
//建立帶頭結點的空鏈表
head?=?(pNode)malloc(_SIZE);
head->Number?=?10;//頭節點表示最後壹個人
head->Next?=?head;
iNode++;
printf("Please?input?k:");
scanf("%d",&k);
head?=?CreatList(?head,?iNum?);
printf("The?result?is?No.%d\n",process(?head,?k?));
}
pNode?CreatList(pNode?head,?int?iNum)
{
int?ident?=?1;
pNode?add?=?NULL,?temp?=?head;
//建立剩下iNum-1個人的鏈表,依次編號1至iNum-1
while?(?ident?<?iNum?)
{
add?=?(pNode)malloc(_SIZE);
add->Number?=?ident++;
add->Next?=?temp->Next;
temp->Next?=?add;
temp?=?add;
iNode++;
}
return?head;
}
int?process(pNode?head,?int?k)
{
int?iCount?=?1;
//curr指向要刪除的節點,temp指向curr的前壹節點
pNode?temp?=?head,?curr?=?head->Next;
//剩余節點個數為1時結束循環
while?(?iNode?!=?1?)
{//只剩下壹個節點時結束循環
if?(iCount?==?k?)
{
iCount?=?1;
//刪除節點
temp->Next?=?curr->Next;
iNode--;
}
else
{
iCount++;
temp?=?temp->Next;
}
curr?=?temp->Next;
}
return?curr->Number;
}?
測試結果