用c++链表写一个总人数为7,间隔数为3的约瑟夫环的全部代码
时间: 2024-03-09 11:45:34 浏览: 36
好的,下面是使用C++链表实现总人数为7,间隔数为3的约瑟夫环的完整代码:
```c++
#include <iostream>
using namespace std;
// 链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 创建链表
ListNode* createList(int n) {
ListNode* head = new ListNode(1);
ListNode* cur = head;
for (int i = 2; i <= n; i++) {
cur->next = new ListNode(i);
cur = cur->next;
}
cur->next = head; // 链接成环形链表
return head;
}
// 约瑟夫环
void josephus(ListNode* head, int m) {
ListNode* cur = head;
int count = 0;
while (cur->next != cur) {
count++;
if (count == m) {
ListNode* del = cur->next;
cur->next = del->next;
cout << del->val << " ";
delete del;
count = 0;
} else {
cur = cur->next;
}
}
cout << cur->val << endl;
delete cur;
}
int main() {
int n = 7, m = 3;
ListNode* head = createList(n);
josephus(head, m);
return 0;
}
```
代码说明:
1. 首先定义了一个链表节点结构体`ListNode`,包含了节点的值和指向下一个节点的指针。
2. `createList`函数用于创建一个总人数为n的链表。首先创建第一个节点,然后依次创建剩下的节点并链接成环形链表,最后返回头节点。
3. `josephus`函数用于实现约瑟夫环。使用一个指针`cur`指向当前的节点,使用一个计数器`count`记录当前节点的位置,当`count`等于间隔数`m`时,删除当前节点并输出其值,然后将指针`cur`指向下一个节点;否则,将指针`cur`继续向后移动。当链表中只剩下一个节点时,输出该节点的值。
4. 在`main`函数中,首先定义总人数为7,间隔数为3,然后创建链表。最后调用`josephus`函数实现约瑟夫环。
希望能够帮到你!
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)