Question

关于 joseph环 的问题

问题描述：
编号是1，2，……，n的n个人按照顺时针方向围坐一圈，一开始任选一个正整数作为报数上限（开始）值m(m＜n)，从第s(s＜n)个人开始沿顺时针方向顺序报数，报到m时停止报数，报m的人出列，然后在从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
实现要求：
⑴ 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
输入数据：建立输入处理输入数据，输入m、n、s的初值和每个人的编号，建立单循环链表。
输出形式：建立一个输出函数，将正确的序列输出。
⑵ 利用顺序表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
输入数据：建立输入处理输入数据，输入m、n、s的初值和每个人的编号，建立单循环链表。
输出形式：建立一个输出函数，将正确的序列输出。
测试数据：
m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

Answer 1

#include<stdio.h>
#include<stdlib.h>
typedef struct data{ //定义一个结构体“data”
int num; //用于存放人的序号
int val; //用于存放密码
}typedata;
typedef struct node{ //定义一个结构体（结点），其中包含一个数据域和一个指针域
typedata data; //结构体的嵌套
struct node *next;
}listnode;
typedef listnode *linklist;
linklist head;

void main()// 进入主函数
{
int n,i,b,m,j;
linklist head=(listnode *)malloc(sizeof(listnode)); //申请一个空间（头结点 head）
listnode *p,*q; //定义两个可以指向结点的指针
printf("输入总人数：");
scanf("%d",&n);
q=head; //用指针q指向头结点

for(j=1;j<=n;j++) //本次循环主要是将每一个人的数据（包括序号、密码）存入循环链表中
{
printf("请输入第%d号同学的密码:\n",j);
scanf("%d",&b);
printf("\n");
q->next=(listnode *)malloc(sizeof(listnode));
//将头结点的next域指向刚生成的一个结点
q=q->next;
q->data.val=b; //输入密码
q->data.num=j; //输入序号
q->next=head->next; }
//将尾结点的next域指向第一个结点，构成循环链表
printf("请任意输入一个数m：");
scanf("%d",&m);
if(m<=0) printf("输入错误");
do{

i=1;
while(i!=m){ //将q指针指向所要输出的结点的前一结点
q=q->next;
i++;
}
p=q->next; //p指向输出结点
q->next=p->next; //将输出结点的前结点的next域指向输出结点的后结点
printf("num:%d\tval:%d\n",p->data.num,p->data.val); //输出
m=p->data.val; //取得输出结点的密码
free(p);
}while(q->next!=q); //只剩最后一个结点时结束
printf("num:%d\tval:%d\n",q->data.num,q->data.val); //输出最后一个结点
free(q); //释放最后一个结点
free(head); //释放头结点
printf("约瑟夫环结束，欢迎下次光临~·~\n");
}
//程序结束