题目：改进的Joseph环。一圈人报数，报数上限依次为3,7,11,19，循环进行，直到所有人出列完毕。
思路：双向循环链表模拟。
代码：
#include <cstdio>
#include <cstdlib> #define N 20 typedef struct node
{
int id;
struct node *next;
struct node *pre;
}Node, *pNode; //双向循环链表的构建
pNode RingConstruct (int n)
{
int i;
pNode head, p, q;
head = (pNode)malloc(sizeof(Node));
head->id = ;
p = head;
for (i = ; i <= n; i++)
{
q = (pNode)malloc(sizeof(Node));
q->id = i;
p->next = q;
q->pre = p;
p = q;
}
p->next = head;
head->pre = p;
return head;
} //传入报数的次数序号，返回此次报数的上限值
int boundMachine (int order)
{
int boundList[] = {, , , };
return boundList[(order - )%];
} //first为每次报数的第一人，bound为此次报数的上限，返回此次报数的应出列者
pNode count (pNode first, int bound)
{
while (--bound)
{
first = first->next;
}
return first;
} //将currentNode从环中删除，并返回被删除节点的下一节点
pNode removeNode (pNode currentNode)
{
pNode first = currentNode->next;
if (first != currentNode)
{
currentNode->pre->next = first;
first->pre = currentNode->pre;
}
printf("%d ", currentNode->id);
free(currentNode);
return first;
} int main (int argc, char *argv)
{
pNode first, toRemove;
int i;
first = RingConstruct(N);
for (i = ; i <= N; i++)
{
toRemove = count(first, boundMachine(i));
first = removeNode(toRemove);
}
return ;
}
当N为20时，出列顺序是：