约瑟夫环问题

直接上C++代码：

这里有问题的地方就是joseph_circle.cpp实现方法eliminate的循环语句的条件，如果把p->next != p改为p->next != nullptr就会出现循环已经删除了最后一个还继续循环，还继续删除，然后抛出空指针异常。

joseph_circle.h

 1 #ifndef __YueHeFuHuan__joseph_circle__
 2 #define __YueHeFuHuan__joseph_circle__
 3  4 #include <stdio.h>
 5 #include <iostream>
 6 using namespace std;
 7 struct node{
 8 int payload;
 9 node* next;
10 node(int value){
11 payload = value;
12 }//通过构造器传值更好，更直观。 13 };
14 15 class joseph_circle{
16 public:
17  joseph_circle();
18 node* tail;
19 void add(int n);
20 void output();
21 void eliminate(int step);
22 };
23 24 25 #endif /* defined(__YueHeFuHuan__joseph_circle__) */

joseph_circle.cpp

 1 #include "joseph_circle.h"  2  3 joseph_circle::joseph_circle(){
 4 tail = nullptr;
 5 }
 6 void joseph_circle::add(int value){
 7 if (tail == nullptr) {
 8 tail = new node(value);
 9 tail->next = tail;
10 }else{
11 node* next_node = tail->next;
12 tail->next = new node(value);
13 tail = tail->next;
14 tail -> next = next_node;
15 16  }
17 }
18 void joseph_circle::output(){
19 if (tail == nullptr) {
20 cout << "链表为空！" << endl;
21 }else{
22 node* p = tail->next;
23 while (true) {
24 cout << "payload:" << p->payload << endl;
25 if (p == tail) {
26 break;
27  }
28 p = p->next;
29  }
30  }
31 }
32 void joseph_circle::eliminate(int step){
33 if (tail == nullptr) {
34 cout << "链表为空！" << endl;
35 }else{
36 node* p = tail;
37 node* delete_p;
38 //事实证明，当delete一个指针之后，其指针指向不为空 39 while (p != nullptr && p->next != p) {
40 //根据步长找到目标元素 41 for (int i=0; i<step-1; i++) {
42 p = p->next;
43  }
44 delete_p = p->next;
45 cout << "deleting: " << delete_p->payload << endl;
46 p->next = delete_p->next;
47 if (delete_p == tail) {
48 tail = p;
49  }
50 delete delete_p;
51 52  }
53  }
54 }