前面文章写了关于Josephus问题解决的一种方法http://blog.itpub.net/29876893/viewspace-1815055/，但是由于前面的程序有两处错误已改正（红色字体），由于本人写文章时太粗心！导致运行结果错误，下面修正：（原文已经修正，下面指出已对自己粗心的教训）
我认为该问题难点在于构造单向循环链表和对链表结点的删除（如何判断删除间隔），下面给出另一种构造单向循环链表的方法：
关于构造单向循环链表，画出图后，会变的简单些，下面简单给出上面的构造循环单链表的示意图（图画的不是太美观~_~）：
点击(此处)折叠或打开
-
...
-
...
-
Note *InitNote(Note *first, int n) {
-
-
Note *head, *p;
-
head = first;
-
-
p = NULL;
-
-
cout << "同学开始座次：" << endl;
-
-
for (int i = 1; i <= n; i++) { //利用尾插法，构造链表
-
-
p = new Note;
-
head->next = p;
-
p->data = i;
-
cout << p->data << "--> ";
-
head = p;
-
}
-
-
p->next = first->next; //形成换
-
return first; //返回头结点
-
}
-
-
void Search(Note *q, int m) {
-
-
...
-
-
for (int i = 1; q != q->next; q = q->next, i++) {
-
-
if (i == m) { //当i = m时，执行其中的语句，并初始化i = 1，至于原因，读者画图便可知
-
-
....
-
-
}
-
}
-
...
-
}
-
int main() {
-
...
-
}
-
点击(此处)折叠或打开
-
#include<iostream>
-
//#include<stdlib.h>
-
using namespace std;
-
-
struct Note {
-
-
int data;
-
struct Note *next;
-
-
};
-
-
Note *CreateNote() {
-
-
Note *first;
-
first = new Note; //first = (Note *)malloc(sizeof(Note));
-
//first->data = NULL;
-
first->next = new Note;
-
return first;
-
}
-
-
void InitNote(Note *first, int n) {
-
-
Note *p;
-
p = first;
-
-
cout << "同学开始座次：" << endl;
-
-
for (int i = 1; i <= n; i++) {
-
-
p->next = new Note;
-
p = p->next;
-
p->data = i;
-
cout << p->data << "-->";
-
-
}
-
-
p->next = first->next;
-
-
}
-
-
void Search(Note *first, int m) {
-
-
cout << "依次出列同学：";
-
if (m == 1) {
-
-
cout << "游戏太无聊！";
-
exit(-1);
-
}
-
int i;
-
Note *q;
-
for (i=1,q = first; q != q->next; q = q->next,i++) {
-
-
if (i == m) {
-
-
i = 1;
-
Note *n;
-
n = q->next;
-
cout<<n->data << "-->";
-
q->next = n->next;
-
delete n;
-
-
}
-
}
-
-
cout << q->data;
-
cout << endl;
-
cout << "获胜的是：" << q->data << "号同学" << endl;
-
-
}
-
int main() {
-
-
Note *p;
-
p = CreateNote();
-
InitNote(p, 5);
-
cout << endl;
-
Search(p, 2);
-
}
-
-
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29876893/viewspace-1850077/ ，如需转载，请注明出处，否则将追究法律责任。
请登录后发表评论
登录
全部评论
