问题描述
约瑟夫环(约瑟夫问题)是一个数学的应用问题：已知n个人(以编号1，2，3...n分别表示)按顺时针方向围坐在一张圆桌周围，每个人持有一个密码(正整数)。一开始任选一个整数作为报数上限值m，从第一个人开始顺时针自1报数，报到m时停止报数，报m的那个人出列，他的密码作为新的m值，从他在顺时针方向上的下一个人又开始重新从1报数，报到m的那个人出列又出列；依此规律重复下去，直到圆桌周围的人全部出列。
输入格式
第一行一个数n，表示圆桌上做的人数；
第二行是n个整数，表示圆桌上座客持有的密码：
第三行是一个整数，表示初始m值；
输出格式
桌上座客的出队顺序
样例输入
7
3 1 7 2 4 8 4
20
样例输出
6 1 4 7 2 3 5
解题思路
本题只需要注意链表循环时，要跳过链表的头结点。
代码实现
#include
#include
typedef struct Node {
int data;
int index;
struct Node *next;
} Node, *LinkList;
void initLink(LinkList *link);
void create(LinkList link, int size);
int main(int argc, char *argv[]) {
int m = 0, n = 0, count = 1, sum = 0;
// 指针p指向报数时的位置，指针q指向报数时的上一位
Node *p, *q;
scanf("%d", &n);
LinkList link;
initLink(&link);
create(link, n);
scanf("%d", &m);
p = link->next;
while (sum != n) {
if (count == m) {
printf("%d\t", p->index);
m = p->data;
q->next = p->next;
free(p);
p = q->next;
count = 0;
sum++;
} else {
q = p;
p = p->next;
}
// 当指针p指向链表的头指针时，指针向后移动一位
if (p->index == -1) {
q = p;
p = p->next;
}
count++;
}
return 0;
}
void initLink(LinkList *link) {
*link = (LinkList)malloc(sizeof(Node));
(*link)->next = NULL;
(*link)->index = -1;
}
void create(LinkList link, int size) {
int i;
Node *node, *q;
q = link;
for (i = 0; i < size; i++) {
node = (Node *)malloc(sizeof(Node));
scanf("%d", &node->data);
node->index = i + 1;
link->next = node;
link = node;
}
link->next = q;
}