今天上数据结构实验课，有道题是约瑟夫环，感觉挺好玩的，就拿出来总结一下（今天的LeetCode那道题真的是太Easy了）。
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
这里是用双向循环链表实现的：
先是类的申明：
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; }
};类的实现：
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;
}
测试：
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会减少一些常见的错误，一些实现敲起来也会简单点（唯一一个一开始就选择正确的点）。
感觉以后要多总结一些一些基本的数据结构，不然做算法题的时候，会很难找到适合的数据结构。
作者：wuxiaobai24
发表日期：9/28/2017
本文首发地址：约瑟夫环
版权声明：CC BY NC SA 4.0
