Code & Fun

今天上数据结构实验课,有道题是约瑟夫环,感觉挺好玩的,就拿出来总结一下(今天的LeetCode那道题真的是太Easy了)。

约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

这里是用双向循环链表实现的:

先是类的申明:

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
class JCircle;

class ListNode{
int val;
ListNode *next,*prior;
public:
ListNode(int v,ListNode *n = NULL,ListNode *p = NULL)
:val(v),next(n),prior(p){}
friend class JCircle;
int getVal(){ return val; }
ListNode *getNext() { return next; }
ListNode *getPrior() { return prior; }
};

class JCircle{
ListNode *head;
int size;
public:
JCircle(int n);
~JCircle();
void move(int k); //向前移动k步
int del(); //删除head所指向的ListNode并返回其 val
int count(int k); //报数
friend ostream &operator<<(ostream& out,JCircle &jc);
bool empty() { return size == 0; }
};

类的实现:

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
68
JCircle::JCircle(int n)
:head(NULL),size(0){
if (n <= 0) return;
size = n;
head = new ListNode(1,NULL,NULL);
head->next = head;
head->prior = head;
ListNode *p = head;
for(int i = 2;i <= n;i++) {
p->next = new ListNode(i,p->next);
p->next->prior = p;
p = p->next;
}
head->prior = p;
}

JCircle::~JCircle(){
ListNode *p;
while(size--){
p = head;
head = head->next;
delete p;
}
}

void JCircle::move(int k){
// cout << "move";
for(int i = 1;i < k;i++)
head = head->next;
// cout << " over\n";
}

int JCircle::del(){
if (size == 2){
ListNode *p = head;
int ret = p->val;
head = head->next;
delete p;
head->next = head->prior = head;
size--;
return ret;
}
size--;
head->next->prior = head->prior;
head->prior->next = head->next;
ListNode *p = head;
int t = p->val;
head = head->next;
delete p;
return t;
}

int JCircle::count(int k){
move(k);
// cout << "count";
return del();
}

ostream &operator<<(ostream& out,JCircle &jc){
ListNode *p = jc.head;
int n = jc.size;
while(n--){
out << p->getVal() << " ";
p = p->getNext();
}
//out << "asdsad\n";
return out;
}

测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int main() {

//test
//人数 开始位置 报数
int n, k, m;
while(cin >> n >> k >> m){
JCircle jc(n);
jc.move(k);
//cout << jc << endl;
while(!jc.empty())
cout << jc.count(m) << " ";
cout << endl;
}
return 0;
}

想写这个的原因是,我写了很久,事实上回到宿舍写多一遍的时候,我也写了很久(现在是20:16:00),写了一个多小时了,感觉自己还不怎么熟悉一些的基本数据结构(虽然已经在之前的学院上过一次了,恩,相当水的一门课)。

重写一遍的感觉是,该掉的坑,我还是掉下去了,之前写了的一遍的效果就是,我能比较快的爬出来,而且不会纠结于选择双向链表还是单向链表。

写的过程中,也体会了一下双向链表的坑点:

  • size==2时,不能用常规方法delete掉自己。
  • 加入size会减少一些常见的错误,一些实现敲起来也会简单点(唯一一个一开始就选择正确的点)。

感觉以后要多总结一些一些基本的数据结构,不然做算法题的时候,会很难找到适合的数据结构。


本文首发于Code & Fun