Code & Func

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

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

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

先是类的申明：

1
class JCircle;
2

3
class ListNode{
4
  int val;
5
  ListNode *next,*prior;
6
public:
7
  ListNode(int v,ListNode *n = NULL,ListNode *p = NULL)
8
    :val(v),next(n),prior(p){}
9
  friend class JCircle;
10
  int getVal(){ return val; }
11
  ListNode *getNext() { return next; }
12
  ListNode *getPrior() { return prior; }
13
};
14

15
class JCircle{
11 collapsed lines
16
  ListNode *head;
17
  int size;
18
public:
19
  JCircle(int n);
20
  ~JCircle();
21
  void move(int k);  //向前移动k步
22
  int del();      //删除head所指向的ListNode并返回其 val
23
  int count(int k);  //报数
24
  friend ostream &operator<<(ostream& out,JCircle &jc);
25
  bool empty() { return size == 0; }
26
};

类的实现：

1
JCircle::JCircle(int n)
2
  :head(NULL),size(0){
3
  if (n <= 0) return;
4
  size = n;
5
  head = new ListNode(1,NULL,NULL);
6
  head->next = head;
7
  head->prior = head;
8
  ListNode *p = head;
9
  for(int i = 2;i <= n;i++) {
10
    p->next = new ListNode(i,p->next);
11
    p->next->prior = p;
12
    p = p->next;
13
  }
14
  head->prior = p;
15
}
53 collapsed lines
16

17
JCircle::~JCircle(){
18
  ListNode *p;
19
  while(size--){
20
    p = head;
21
    head = head->next;
22
    delete p;
23
  }
24
}
25

26
void JCircle::move(int k){
27
//  cout << "move";
28
  for(int i = 1;i < k;i++)
29
    head = head->next;
30
//  cout << " over\n";
31
}
32

33
int JCircle::del(){
34
  if (size == 2){
35
    ListNode *p = head;
36
    int ret = p->val;
37
    head = head->next;
38
    delete p;
39
    head->next = head->prior = head;
40
    size--;
41
    return ret;
42
  }
43
  size--;
44
  head->next->prior = head->prior;
45
  head->prior->next = head->next;
46
  ListNode *p = head;
47
  int t = p->val;
48
  head = head->next;
49
  delete p;
50
  return t;
51
}
52

53
int JCircle::count(int k){
54
  move(k);
55
//  cout << "count";
56
  return del();
57
}
58

59
ostream &operator<<(ostream& out,JCircle &jc){
60
  ListNode *p = jc.head;
61
  int n = jc.size;
62
  while(n--){
63
    out << p->getVal() << " ";
64
    p = p->getNext();
65
  }
66
  //out << "asdsad\n";
67
  return out;
68
}

测试：

1
int main() {
2

3
  //test
4
  //人数  开始位置  报数
5
  int  n,  k,       m;
6
  while(cin >> n >> k >> m){
7
    JCircle jc(n);
8
    jc.move(k);
9
    //cout << jc << endl;
10
    while(!jc.empty())
11
      cout << jc.count(m) << " ";
12
    cout << endl;
13
  }
14
  return 0;
15
}

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

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

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

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

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