使用C++分文件如下三个:1,创建链表 2,数小孩 3,小孩离开 来编写链表和结构体解决约瑟夫问题
时间: 2024-03-07 22:48:34 浏览: 65
好的,以下是使用C++分文件编写链表和结构体解决约瑟夫问题的示例代码:
首先是链表的头文件 List.h:
```
#ifndef LIST_H
#define LIST_H
struct Node {
int data;
Node* next;
};
class List {
public:
List();
~List();
void addNode(int data);
void deleteNode(Node* node);
Node* getHead();
private:
Node* head;
Node* tail;
};
#endif
```
接着是链表的实现文件 List.cpp:
```
#include "List.h"
#include <iostream>
List::List() {
head = nullptr;
tail = nullptr;
}
List::~List() {
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
}
void List::addNode(int data) {
Node* node = new Node;
node->data = data;
node->next = nullptr;
if (head == nullptr) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
void List::deleteNode(Node* node) {
if (node == head) {
head = head->next;
} else {
Node* current = head;
while (current->next != node) {
current = current->next;
}
current->next = node->next;
if (node == tail) {
tail = current;
}
}
delete node;
}
Node* List::getHead() {
return head;
}
```
接下来是数小孩的头文件 CountChild.h:
```
#ifndef COUNTCHILD_H
#define COUNTCHILD_H
#include "List.h"
class CountChild {
public:
CountChild(int n, int k, int m);
~CountChild();
void run();
private:
List list;
int k;
int m;
Node* current;
};
#endif
```
数小孩的实现文件 CountChild.cpp:
```
#include "CountChild.h"
#include <iostream>
CountChild::CountChild(int n, int k, int m) {
for (int i = 1; i <= n; i++) {
list.addNode(i);
}
this->k = k;
this->m = m;
}
CountChild::~CountChild() {
}
void CountChild::run() {
current = list.getHead();
for (int i = 1; i < k; i++) {
current = current->next;
}
while (list.getHead() != list.getTail()) {
for (int i = 1; i < m; i++) {
current = current->next;
}
std::cout << current->data << "离开" << std::endl;
Node* next = current->next;
list.deleteNode(current);
current = next;
}
std::cout << current->data << "是最后一个留下的" << std::endl;
}
```
最后是小孩离开的头文件 LeaveChild.h:
```
#ifndef LEAVECHILD_H
#define LEAVECHILD_H
#include "CountChild.h"
class LeaveChild {
public:
LeaveChild(int n, int k, int m);
~LeaveChild();
void run();
private:
CountChild* cc;
};
#endif
```
小孩离开的实现文件 LeaveChild.cpp:
```
#include "LeaveChild.h"
LeaveChild::LeaveChild(int n, int k, int m) {
cc = new CountChild(n, k, m);
}
LeaveChild::~LeaveChild() {
delete cc;
}
void LeaveChild::run() {
cc->run();
}
```
在主程序中,只需要调用LeaveChild的run()函数即可解决约瑟夫问题:
```
#include "LeaveChild.h"
int main() {
int n, k, m;
std::cout << "请输入总人数n:";
std::cin >> n;
std::cout << "请输入起始位置k:";
std::cin >> k;
std::cout << "请输入报数上限m:";
std::cin >> m;
LeaveChild lc(n, k, m);
lc.run();
return 0;
}
```
以上代码实现了一个能够解决约瑟夫问题的程序。在这个程序中,List类表示链表,Node结构体表示链表中的节点。CountChild类表示数小孩的过程,LeaveChild类表示小孩离开的过程。在主程序中,先读入约瑟夫问题的相关参数,然后创建一个包含n个节点的链表。接下来,程序调用CountChild的run()函数,按照约瑟夫问题的规则遍历链表,并删除指定的节点,直到只剩下一个节点为止。最后输出剩下的节点的编号。
阅读全文