一、问题描述：约瑟夫问题
一个旅行社要从n个旅客中选出一名旅客，为他提供免费的环球旅行服务。旅行社安排这些旅客围成一个圆圈，从帽子中取出一张纸条，用上面写的正整数m(<n)作为报数值。游戏进行时，从第s个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人被淘汰出列，然后从他顺时针方向上的下一个人开始重新报数，如此下去，直到圆圈中只剩下一个人，这个最后的幸存者就是游戏的胜利者，将得到免费旅行的奖励。其中数据结构采用单循环链表。
二、任务要求
（1）用单循环链表解决约瑟夫问题。
（2）用顺序表解决约瑟夫问题。
以上二选一
三、测试数据
输入说明，输入的第一行表示总的旅客数,输入的第二行表示报数值，输入的第三行表示报数人的起始编号。
输入样例：
9
5
1
输出说明，输出这n个人的淘汰顺序
输出样例：
5
1
7
4
3
6
9
2
8代码：
#include <stdio.h>
#include <stdlib.h> typedef struct node { int data; struct node *next; }NODE; void Create(NODE **head, int n)//二级指针，和主函数的指针同用一个地址 { NODE *p, *s; int i = 1; (*head) = (NODE *)malloc(sizeof(NODE)); (*head)->next = (*head); p = *head; while (i <= n) { s = (NODE *)malloc(sizeof(NODE)); s->data = i;//给链表的每个结点的数据域赋值 p->next = s; s->next = (*head);//循环链表，尾指针的后继结点为头结点 p = s;//p指向尾节点 i++; } } NODE *Find(NODE *head, NODE *p, int n)//查找要删除的结点 { NODE *s; int j; for (j = 1; j <= n ; j++) { if (p->next == head) p->next = head->next;//如果p->next等于啦头结点就把头结点跳过 s = p; p = p->next; } return s; } void Delete(NODE *head, NODE *s) { /*删除的思想是把当前s结点的后继结点的值赋给s结点然后删除s结点的后继，就避免传参数的时候s不是要删除的节点而是要删除结点的前继结点的情况*/ NODE *p; p = s->next;//p是s的后继结点 if (p == head) p = head->next;//直接跳过头结点 s->data = p->data; s->next = p->next; free(p); } int main() { NODE *head, *p, *s; int sum, n, i, j, k = 1; scanf("%d%d%d", &sum, &n, &i); Create(&head, sum);//创建单链表 p = head; for (j = 0; j<i; j++)//找到其实位置p p = p->next; printf("\n"); while (k <= sum)//直到全部结点都走一遍 { s = Find(head, p, n);//找到从p开始数n次后的节点为s printf("%d\n", s->data); Delete(head, s); p = s; k++; } }