Question

数据结构课设(joseph环)用C语言求解

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

Answer 1

1.用循环.
# include "stdio.h"
# define SIZE 100
main()
{
int m,n,i;
int array[SIZE];
printf("约瑟夫环求解,当前设置最大人数为%d.\n",SIZE);
printf("报数上限:\n");
scanf("%d",&m);
printf("总人数为:\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("第%d人的密码为:",i+1);
scanf("%d",&array[i]);
}
joseph(array,m,n);
}
int joseph(a,m,n)
int a[],m,n;
{
int b[SIZE]; /*计录编号数组.*/
int i; /*计数器.*/
int flag=0;
int code; /*删取人的号码.*/
int sum=n; /*现存人数.*/
int point=0; /*当前报数人的位置.*/
int num=m;
for(i=0;i<n;i++) /*计录数组.*/
{
b[i]=i+1;
}
while(sum!=0) /*当人数不为零时继续循环.*/
{
for(i=1;i<=num;i++) /*进行报数.*/
{

if(point>=sum) /*当前报数位置超过最后一人时从第一人报起.*/
{point=1;}
else point++;

}
num=a[point-1]; /*取密码.*/
code=b[point-1]; /*取号码.*/
for(i=point;i<=sum;i++) /*删去退出的人.*/
{
a[i-1]=a[i];
b[i-1]=b[i];

}
sum--; /*现存总人数.*/
flag++; /*退出的人数.*/
point--;
printf("已退出%d人,退出的人的编号为%d.\n",flag,code);
}

}

2.用链表.

# include "stdio.h"
# include "alloc.h"
# define LEN sizeof(struct player)
struct player
{
int num; /*编号*/
int secret; /*密码*/
struct player *next;
};
int n; /*总人数*/
main()
{
int m;
void create();
void delete();
struct player *head;
head=(struct player *)malloc(LEN);
printf("请输入第一次的密码:\n");
scanf("%d",&m);
create(head);
delete(head,m);

}
void create(struct player *head)
{
struct player *p1,*p2,*p;
p1=p2=head;
printf("请输入编号,密码,当编号为零时输入结束.\n");
printf("总人数为:\n");
scanf("%d",&n);
do
{
p=p2;
p2=p1;
printf("编号:");
scanf("%d",&p2->num);
printf("密码:");
scanf("%d",&p2->secret);
p1=(struct player *)malloc(LEN);
p2->next=p1;
}while(p2->num!=0);
p->next=head;
free(p1);
}
void delete(struct player *head,int m)
{
int i;
struct player *p,*q;
int sum;
p=head;
sum=m;
while(n!=0)
{
for(i=1;i<sum;i++)
{ q=p;
p=p->next;
}
printf("%d,",p->num);
sum=p->secret;
q->next=p->next;
p=p->next;
n=n-1;
}
}