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; }