#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
//解决约瑟夫问题
int yue (int m, int n) {
//head指向不带头节点的循环单链表
LinkList head = NULL, cur, p, q;
int i, j;
//生成第一个节点
head = (LinkList) malloc (sizeof(LNode));
head->data = 1;
head->next = head;
//使用尾插法按顺序生成节点
p = head;
for (i=1; i<=m; i++) {
if (i==1) /* 首结点 */
p->data = i; /* 向已存在的首结点写入编号 */
else {
q = (LinkList) malloc (sizeof(LNode)); /* 生成新结点 */
if(!q) /* 内存分配失败 */
exit (OVERFLOW);
q->data = i; /* 为第i个人编号 */
p->next = q; /* 将q链接到p之后，即表尾 */
q->next = head; /* 将q链接到首结点之前 */
p = p->next; /* p指向表尾 */
}
}
//约瑟夫开始
cur = head;
printf ("出列顺序：");
//循环m-1次
for(i = 1; i < m; i++) {
//每次循环开始计数
for (j=1; j cur = cur->next;
q = cur->next; /* q指向p的后继结点，q即报到k之人 */
cur->next = q->next; /* p的后继结点跨过q，指向q的后继结点 */
printf("%d\t", q->data);
if (q == head) /* q是首结点 */
head = q->next; /* 移动首结点 */
free (q); /* 删除q结点 */
cur = cur->next; /* p指向下一个结点 */
j--; /* 人数减一 */
}
putchar ('\n');
//返回最后剩下的节点数据域，即为最后剩下的人
return cur->data;
}
int main (void) {
printf ("最后剩下的人：%d\n", yue (8, 3)); //8个人，报3者出列
//运行结束后，需要销毁链表，此处略
getch (); /* 屏幕暂留 */
return 0 ;
}
