转载： 约瑟夫环 循环链表 必备「建议收藏」

http://blog.csdn.net/gggg_ggg/article/details/42965853

1. /********************************************************************  
2. created:2015年1月20日 23:06:46     
3. author: Jackery      
4. purpose: Joseph problem  
5. *********************************************************************/    
6. #include”stdafx.h”  
7. #include<iostream>  
8. using namespace std;  
9.   
10. typedef struct _Node  
11. {  
12.     int data;  
13.     struct _Node*next;  
14. } node_t;  
15.   
16. typedef struct _Linklist  
17. {  
18.     node_t*phead;  
19.     node_t*ptail;  
20.     int len;  
21. }Linklist;  
22. static node_t*GetNode(int i )//新建并初始化节点  
23. {  
24.     node_t*pNode;  
25.     pNode=new node_t;  
26.     if(!pNode)  
27.     {  
28.         cout <<“内存分配失败” <<endl;  
29.         exit(-1);  
30.     }  
31.     pNode->data=i;  
32.     pNode->next=NULL;  
33.     return pNode;  
34.     delete pNode;  
35. }  
36. void init_list(Linklist*plist)//用第一个节点初始化循环单链表  
37. {  
38.     node_t*p;  
39.     p=GetNode(1);  
40.     //printf(“TheNewNodeis:%d\n”,p->data);//****TEST****  
41.     plist->phead=p;  
42.     plist->ptail=p;  
43.     p->next=plist->phead;  
44.     plist->len=1;  
45. }  
46.   
47. //把其余数据添加到循环单链表中  
48. static void Create_List(Linklist*plist,int n)  
49. {  
50.     int i=0;  
51.     node_t*pNew;  
52.     for(i=2;i<=n;i++)  
53.     {  
54.         pNew=GetNode(i);  
55.         /********TEST********  
56.         cout <<“The New Node is:” <<pNew->data << endl;  
57.         ********TEST********/  
58.         plist->ptail->next=pNew;  
59.         plist->ptail=pNew;  
60.         pNew->next=plist->phead;  
61.         plist->len++;  
62.     }  
63. }  
64. //输出链表内容  
65. // void Print_List(Linklist*plist)  
66. // {  
67. //  node_t*pCur=plist->phead;  
68. //  do  
69. //  {  
70. //      cout << “The “<<  pCur->data <<“person.”  <<endl;  
71. //      pCur=pCur->next;  
72. //  }while(pCur!=plist->phead);  
73. //  cout << “The length of the List “<< plist->len<< endl;;  
74. // }  
75.   
76. //Joseph function implement  
77. void joseph(Linklist* plist,int m,int k)  
78. {    
79.     node_t *pPre=plist->ptail;  
80.     node_t *pCur=plist->phead;  
81.     int i,j;  
82. cout << “出队列的顺序依次为： “<< endl;  
83.     while(plist->len != 1)  
84.     {  
85.         i=0;  
86.         j=0;  
87.         while(j<k-1)  
88.         {  
89.             pPre=pPre->next;  
90.             j++;  
91.         }  
92.         while(i< m -1)  
93.         {  
94.             pPre=pPre->next;  
95.             i++;  
96.         }  
97.         pCur=pPre->next;  
98.         int temp=pCur->data;  
99.         cout <<“第 ” << temp << ”  个人 “<< endl ;  
100.         pPre->next=pCur->next;  
101.         free(pCur);  
102.         plist->len–;  
103.     }  
104.     cout <<“第 ” << pPre->data << ” 个人” << endl; ;  
105.     cout << “The last one is:” << pPre->data<< endl;  
106. }  
107. int main(int argc, char * argv[])  
108. {  
109.     int n=0;  
110.     cout <<“约瑟夫环长度为 : “<<endl;;  
111.     cin >> n;  
112.     int m=0;  
113.     cout << “每此数到m个时，此人出列”<<endl;  
114.     int k;  
115.     cin >> k;  
116.     cout << “从第k 个开始数” << endl;  
117.     cin >>m;  
118.     Linklist pList;  
119.     init_list(&pList);  
120.     Create_List(&pList,n);  
121. //  Print_List(&pList);  
122.     joseph(&pList,m,k);  
123.     return 0;  
124. }