[C语言、C++]数据结构作业：用双向链表和0

[C语言、C++]数据结构作业：用双向链表和0

请使用合适的数据结构实现：使用“折返报数”方式的Joseph问题。
所谓“折返报数”Joseph问题是指：
（1）n（n>1）个人排成一队，从1到n依次编号；从1到m循环报数，报到m（m>1）者退出；
（2）游戏先从编号为1的人（队头）开始依次从前向后报数，当报数到达队尾时，立即改为从后往前报数；
（3）当从后往前报数到达队头时，立即改为从前往后报数；
（4）如此“折返”报数，直到队列中只剩下1人为止，即为胜者；
要求：
（1）从键盘输入n和m；
（2）依次输出游戏过程中退出人的编号；
（3）输出获胜者编号；
例：
输入：n=5；m=3
输出：
3 4 2 5
胜者：1

#include <iostream>
using namespace std;
typedef struct LinkNode {int data;LinkNode* next;LinkNode* pre;
}*LinkList;
void InitLinkList(LinkList& L) {L = NULL;
}
void CreatRear(LinkList& L,int n) {L = NULL;if (n <= 0)return;else {L = new LinkNode;cin >> L->data;L->pre = NULL; L->next = NULL;if (n > 1) {LinkNode* r = L;for (int i = 1; i < n; i++) {LinkNode* s = new LinkNode;cin >> s->data;r->next = s;s->pre = r;r = r->next;}r->next = NULL;}}
}
void Returning_Joseph(int n, int m) {LinkList L; InitLinkList(L);CreatRear(L, n);LinkNode* p = L; int isBack = 0;for (int i = 0; i < n - 1; i++) {int j = 0;while (j < m - 1) {if (isBack == 0) {while (p->next != NULL && j < m - 1) {p = p->next; j++;}if (p->next == NULL)isBack = 1;}if (isBack == 1) {while (p->pre != NULL && j < m - 1) {p = p->pre; j++;}if (p->pre == NULL)isBack = 0;}}cout << p->data << " ";LinkNode* r = p;if (p->next == NULL || p->pre == NULL) {if (p->next == NULL) {p = p->pre;delete(p->next);}else {p = p->next;delete(p->pre);}}else {p->pre->next = p->next;p->next->pre = p->pre;if (isBack == 0)p = p->next;else p = p->pre;r->next = NULL; r->pre = NULL;delete(r);}}cout << endl;cout << p->data << "是胜者"; 
}
int main(){Returning_Joseph(5, 3);
}

此题难点在于在约瑟夫问题的基础上摒弃了环的结构，而是改为“折返”，所以自然想到双向链表(无头),但难点在于，如何让程序知道现在是向前遍历还是向后遍历呢？

这里我们设一个初始值 isBack==0，来判断现在是向前还是向后遍历，如果超过了边界，那么更改isBack的值进入到另一个向前遍历的分支即可，如此循环，即可实现“折返”