用链表解决约瑟夫问题时,但间隔为1,从第一个小孩开始数,会bug。如何用c++面对对象思想解决
时间: 2024-03-08 18:49:16 浏览: 14
链表解决约瑟夫问题时,如果间隔为1,从第一个小孩开始数,会出现bug的原因是,每次删除节点时,需要先将当前节点的“前一个节点”的next指针指向当前节点的“后一个节点”,但是第一个节点没有“前一个节点”,需要特殊处理。
可以通过使用带头结点的链表来解决这个问题。具体实现如下:
```c++
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int d) { data = d; next = nullptr; }
};
class Josephus {
private:
Node* head;
int n, m;
public:
Josephus(int n, int m) {
this->n = n;
this->m = m;
head = new Node(0); // 创建头结点
Node* tail = head;
for (int i = 1; i <= n; i++) {
Node* newNode = new Node(i);
tail->next = newNode;
tail = newNode;
}
tail->next = head->next; // 将尾结点的next指针指向头结点,形成循环链表
}
void run() {
Node* cur = head->next; // 从第一个节点开始数
Node* pre = head; // 前一个节点初始化为头结点
while (n > 1) { // 当链表中仅剩一个节点时结束
for (int i = 1; i < m; i++) { // 数m个节点
pre = cur;
cur = cur->next;
}
pre->next = cur->next; // 将当前节点从链表中删除
delete cur;
cur = pre->next; // 继续从下一个节点开始数
n--; // 链表长度减1
}
cout << "最后一个存活的小孩编号是:" << cur->data << endl;
}
};
int main() {
int n = 5, m = 1; // n表示小孩的个数,m表示间隔数
Josephus j(n, m);
j.run();
return 0;
}
```
在这个实现中,我们使用了带头结点的链表,将尾结点的next指针指向头结点,形成循环链表。在删除当前节点时,我们需要将当前节点的“前一个节点”的next指针指向当前节点的“后一个节点”,因此需要记录前一个节点的位置,同时需要注意特殊处理第一个节点的情况。