运行时间足足两分钟
#include<iostream>
#include<vector>
using namespace std;
vector<int>del;//存储被删除节点的val
class Node
{
public:
Node(int x) :val(x), next(NULL) {}//构造函数
bool is_used = false;//标记该点是否被删除
int val = 0;//节点数值
Node* next;
};
Node* head = new Node(-1);
class CircleList
{
public:
void init()//初始化循环链表
{
head->next = head;
int num;
cout << "请输入参与人数" << endl;
cin >> num; lenth = num;
int m;
cout << "请输入喊第几个的人退出" << endl;
cin >> m;
for (int i = 1; i <= num; i++)insert(i);//将1-num插入到链表中
}
void insert(int n)//插入节点
{
Node* temp = head;
while (temp->next != head)
{
temp = temp->next;
}
Node* p = new Node(n);
temp->next = p;
p->next = head;
}
void start()//开始报数
{
int cnt = 0;
for (Node* i =head->next ; lenth > 0; i = i->next)
{
if (i == head)//遇到头节点跳过
{
i = i->next;
}
if (lenth >= m&&!(i->is_used))//如果剩余长度大于m,并且这个数没有被用过,进行报数
{
cnt++;
if (cnt == m)//当报到m,删除该节点
{
i->is_used = true;
lenth--;
del.push_back(i->val);
cnt = 0;
}
}
else//剩余个数不足,直接删除
{
del.push_back(i->val);
lenth--;
}
}
}
void show()//展示删除次序
{
cout << "===============" << endl;
cout << "退出顺序如下" << endl;
for (auto x : del)
{
printf("%d ", x);
}
}
private:
int lenth=0;//链表长度
int m=0;//报到第几个数字被移除
};
int main()
{
CircleList cirlist;//创建对象
cirlist.init();
cirlist.start();
cirlist.show();
return 0;
}
等待很长时间,才会输出一串错误的
头节点开始定义在类list内作为数据成员,但发现报错,就定义在外面
start函数一直循环,不知道问题所在
对于循环链表,head定义在哪里更好,如何正确输出答案
等待很长时间是死循环了
m 是类的成员属性, 不要在init()中再定义m变量
void init()//初始化循环链表
{
head->next = head;
int num;
cout << "请输入参与人数" << endl;
cin >> num; lenth = num;
//int m; 去掉这行
cout << "请输入喊第几个的人退出" << endl;
cin >> m;
for (int i = 1; i <= num; i++)insert(i);//将1-num插入到链表中
}
大概实现是输入人数,从一开始报数,输入报到第几个时,报这个数的人就退出。
比如5个人,从1开始报数,报第二个数的人退出,则退出顺序为2,4,1,5,3
第一轮:
1 2 3 4 5
1 2 1 2 1
第二轮
1 3 5
2 1 2
第三轮:剩余人数不足,直接退出