数据结构学习<一> 链表解决约瑟夫问题

约瑟夫问题百度百科

已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围只剩一个人。

这个问题可以用链表解决,这里直接使用STL的list类解决。
但是由于需要构建一个循环链表,STL中的List并不是循环的,所以将其加以封装一下,代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<list>
#include<iostream>
using namespace std;
//itCur为指向当前元素的迭代器
//当迭代器指向链表最后 _list.end(),将其指向_list.begin()
class Ring
{
public:
Ring(size_t N)
:RingSize(N)
{
int i = 1;
_list.resize(N);
//为_list赋初值,从1开始到N
for (list<int>::iterator It = _list.begin(); It != _list.end(); It++, i++)
{
*It = i;
}
itCur = _list.begin();//赋初值。使迭代器指向第一个元素
}
//环的大小
size_t GetRingSize() { return RingSize; }
//删除从ItCur开始数的第n个元素
void DelElem(size_t n)
{
for (int i = n-1; i > 0; i--)
{
//考虑迭代器指向end()的情况,因为当end()实际上List最后一个元素之后的元素
//此时实际应该是第一个元素
//在迭代器++的前后都要检查
if (itCur == (_list.end()))
{
itCur = _list.begin();
}
itCur++;
if (itCur == (_list.end()))
{
itCur = _list.begin();
}
}
//删除ItCur元素后,迭代器指向空,需要保存之前状态重新赋值并指向下一个
list<int>::iterator temp = itCur;
//考虑ItCur指向end()的情况,因为当end()实际上List最后一个元素之后的元素
//此时实际应该是第一个元素
if (temp == (_list.end()))
{
temp = _list.begin();
}
temp++;
if (temp == (_list.end()))
{
temp = _list.begin();
}
_list.erase(itCur);//删除
itCur = temp;//恢复到删除位置的下一个
RingSize--;//减小环大小
}
private:
list<int> _list;
size_t RingSize;
list<int>::iterator itCur;
};

测试一下

1
2
3
4
5
6
7
8
9
10
int main(void)
{
//环大小为9,每次删除第5个
Ring r(9);
while (r.GetRingSize() > 1)
{
r.DelElem(5);
}
return 0;
}

最后剩下的是8