D (1092) : DS循环链表—约瑟夫环(Ver. I - A)

Description

N个人坐成一个圆环（编号为1 - N），从第S个人开始报数，数到K的人出列，后面的人重新从1开始报数。依次输出出列人的编号。 例如：N = 3，K = 2，S = 1。
2号先出列，然后是1号，最后剩下的是3号。
要求使用循环链表实现。

Input

第一行输入t，表示有t个测试用例；

第二行起，每行输入一组数据，包括3个数N、K、S，表示有N个人，从第S个人开始，数到K出列。

(2 <= N <= 10^6，1 <= K <= 10, 1 <= S <= N)

Output

出列的人的编号

Sample

Input

2
13 3 1
3 2 1

Output

3 6 9 12 2 7 11 4 10 5 1 8 13 
2 1 3 

AC代码：

#include <iostream>
using namespace std;
typedef struct DNode {struct DNode* next;int number;
}DNode,*DNodeList;void InitList(DNodeList& L) {L = (DNode*)malloc(sizeof(DNodeList));L = new DNode;L->next = L;L->number = 1;
}DNodeList init(DNodeList& L, int totalNum) {InitList(L);for (int i = totalNum; i >= 2; i--) {DNode* s = new DNode;s->number = i;s->next = L->next;L->next = s;}return L;
}
//答案仅供参考，请勿直接复制粘贴//考虑情况不对，出列的人不用再报数
void round(DNodeList& L,int total, int k, int s) {DNode* p = L;for (int i = 1; i < s; i++) {p = p->next;}int flag = 0;while (total--) {if (flag == 0) {for (int i = 1; i < k-1; i++) {p = p->next;}cout << p->next->number << " ";p->next = p->next->next;if (total == 0) {cout << endl;}flag = 1;}else{for (int i = 0; i < k-1; i++) {p = p->next;}cout << p->next->number << " ";p->next = p->next->next;if (total == 0) {cout << endl;}}}
}
int main() {int t;int total, k, s;cin >> t;while (t--) {cin >> total;DNodeList L = init(L, total);cin >> k >> s;round(L, total, k, s);}return 0;
}