算法是编程的灵魂，是编程思想的精华――――Algorithm One Day One
/********************************************************************
created:2015年1月20日 23:06:46
author: Jackery
purpose: Joseph problem
*********************************************************************/
#include"stdafx.h"
#include<iostream>
using namespace std;
typedef struct _Node
{
int data;
struct _Node*next;
} node_t;
typedef struct _Linklist
{
node_t*phead;
node_t*ptail;
int len;
}Linklist;
static node_t*GetNode(int i )//新建并初始化节点
{
node_t*pNode;
pNode=new node_t;
if(!pNode)
{
cout <<"内存分配失败" <<endl;
exit(⑴);
}
pNode->data=i;
pNode->next=NULL;
return pNode;
delete pNode;
}
void init_list(Linklist*plist)//用第1个节点初始化循环单链表
{
node_t*p;
p=GetNode(1);
//printf("TheNewNodeis:%d
",p->data);//****TEST****
plist->phead=p;
plist->ptail=p;
p->next=plist->phead;
plist->len=1;
}
//把其余数据添加到循环单链表中
static void Create_List(Linklist*plist,int n)
{
int i=0;
node_t*pNew;
for(i=2;i<=n;i++)
{
pNew=GetNode(i);
/********TEST********
cout <<"The New Node is:" <<pNew->data << endl;
********TEST********/
plist->ptail->next=pNew;
plist->ptail=pNew;
pNew->next=plist->phead;
plist->len++;
}
}
//输出链表内容
// void Print_List(Linklist*plist)
// {
// node_t*pCur=plist->phead;
// do
// {
// cout << "The "<< pCur->data <<"person." <<endl;
// pCur=pCur->next;
// }while(pCur!=plist->phead);
// cout << "The length of the List "<< plist->len<< endl;;
// }
//Joseph function implement
void joseph(Linklist* plist,int m,int k)
{
node_t *pPre=plist->ptail;
node_t *pCur=plist->phead;
int i,j;
cout << "出队列的顺序顺次为： "<< endl;
while(plist->len != 1)
{
i=0;
j=0;
while(j<k⑴)
{
pPre=pPre->next;
j++;
}
while(i< m ⑴)
{
pPre=pPre->next;
i++;
}
pCur=pPre->next;
int temp=pCur->data;
cout <<"第 " << temp << " 个人 "<< endl ;
pPre->next=pCur->next;
free(pCur);
plist->len--;
}
cout <<"第 " << pPre->data << " 个人" << endl; ;
cout << "The last one is:" << pPre->data<< endl;
}
int main(int argc, char * argv[])
{
int n=0;
cout <<"约瑟夫环长度为 : "<<endl;;
cin >> n;
int m=0;
cout << "每此数到m个时，这人出列"<<endl;
int k;
cin >> k;
cout << "从第k 个开始数" << endl;
cin >>m;
Linklist pList;
init_list(&pList);
Create_List(&pList,n);
// Print_List(&pList);
joseph(&pList,m,k);
return 0;
}