前面解决Josephus问题时（http://blog.itpub.net/29876893/viewspace-1815055/，http://blog.itpub.net/29876893/viewspace-1850077/)，都是找到该同学后，把该同学从环中除去，然后剩下的同学再组成一个新的环，终止条件是p != p->next。下面我们换种方式考虑该问题，可不可以找到该同学后，标识该同学，然后一直循环该环，直到把所有的人都标识，终止循环的条件是标识位等于环中的人数（flag=length），最后"标识"的同学就是获胜者。我把这种方法叫做，“单向循环链表标识法”，下面给出代码：

点击(此处)折叠或打开

#include<iostream>
using namespace std;
typedef struct Note{
char ch;
struct Note *next;
}*node;
int length;
int flag;
void initNote(node first) {
first = new Note;
first->next = NULL;
}
void createNote(node first) {
node p, q;
p = first;
cout << "请依次输入学生的编号：" << endl;
for (char ch; cin >> ch, ch !='#';) {
q = new Note;
p->next = q;
q->ch = ch;
cout << q->ch << " ";
p = q;
length++;
}
p->next=first->next;
}
void searchNote(node first,int n) {
cout << "出队的顺序依次是：" << endl;
while (true) { //死循环，为了找出所有标识结点
for (int i = 1; i <=n; i++) {
first = first->next;
if (first->ch == NULL){ //只要循环到ch为空的结点，i减1，并且继续执行for循环
i--;
continue;
}
}
flag++; //只要结点的first->ch=NULL,则标识就增加1
cout << first->ch << " ";
if (flag == length) { //已经找到了所有的标识结点，退出死循环
break;
}
first->ch = NULL;//把标识结点的数据域置为空
}
cout << endl;
cout << "获胜的同学是：" << endl;
cout << first->ch; //打印出获胜者
}
void deleteNote(node q) {
node p = q;
for (; p != q; p = p->next) {
node no = p;
delete no;
}
cout << "环已销毁！！！" << endl;
}
int main() {
Note note;
initNote(&note);
createNote(&note);
cout << endl;
searchNote(&note,4);
cout << endl;
deleteNote(&note);
}

运行结果：

形成环这里不必多说，关键在于void searchNote(node first,int n)，思路就是找到同学后，把该同学贴上标签，然后继续循环该环，当找到已经被贴上标签的同学，就跳过该同学，当找到所有的同学后，那么剩下的同学就是获胜者，当然别忘了，游戏结束后，不能让同学还是手拉手围成一个环，那就是void deleteNote(node q)的功能啦，把该环"销毁"了。上面的解题思路，我想很多朋友会想到，可不可以用数组解决该问题，当然可以啦！关键是清晰的画出程序流程图解，程序写起来会变的相对容易些。

ITPub博客

Josephus问题解决方法三（单向循环链表标识法）

最新文章