Question

数据结构（c语言版）--约瑟夫环

【实验内容与要求】
问题描述：编号是1,2,…,n(n>0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。
基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。
【测试数据】
n为7，m的初值为20，密码：3、1、7、2、4、8、4，正确的结果应为：6、1、4、7、2、3、5。

一定要数据结构的形式哦~~符合要求的话追加分数~~

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");
}
//程序结束。

Answer 2

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>

struct people //定义结点的结构体
{
int num; //某人在队列中的序号
int code; //某人持有的密码
struct people *next; // 指向下一个结点的指针
}*head; //链表的头指针

void main()
{
int m, n; //m，n分别是随机生成的密码的上限和定义的人数
void ListInit(int m, int n);
void ListKill(int m, int n);
void PrintCode(int n); //函数的声明
srand( (unsigned) time(NULL) ); //初始化随机数发生器
printf("请输入人数 n:");
scanf("%d",&n);
printf("\n请输入密码的上限 m:");
scanf("%d",&m);
ListInit(m, n); //产生一个有n个结点的循环链表
printf("\n随机产生的密码是：\n");
PrintCode(n); //输出各个结点的随机密码
printf("\n\n离开的顺序是：\n");
ListKill(m, n); //按约瑟夫环的规则将各个结点从链表中分离出来，并输出序号
printf("\n按任意键退出");
getch(); //使屏幕停留，以便观察结果
}

void ListInit(int m, int n) //链表初始化函数
{
int i;
struct people *p, *q;
q=(struct people *)malloc( sizeof(struct people) ); //分配内存空间，并将地址返回给指针q
q->num=1; //第一个结点
q->code=rand()%m+1; //随机生成密码
head=q; //头指针指向第一个结点
for(i=1; i<n; i++) //循环生成n个结点
{
p=(struct people *)malloc( sizeof(struct people) ); //分配内存空间
q->next = p; //连成链表
q=p; //指针下移
q->num = i+1; //获得结点序号
q->code = rand()%m+1; //随机生成密码
}
q->next = head; //头尾结点相连，形成循环链表
}

void ListKill(int m, int n) //去除结点的函数
{
int i=0, j=0, code;
struct people *p1, *p2;
p1=head; //从第一个结点开始
code = p1->code; //以第一个人的密码为第一个开始报的数
while(1)
{
for(i=1; i<code; i++) //开始报数，报到code值时退出
{
p2=p1;
p1=p1->next;
}
code=p1->code; //以报出code值人人手中的密码为新密码
p2->next = p1->next; //将代表报出code值的人的结点从链表中去除
printf("%3d ",p1->num); //输出出去的人的序号
j++; //出去的人数加一
if( (j%20) == 0 ) printf("\n"); //控制输出屏幕的宽度
free(p1); //释放从链表出去的结点的内存空间
p1=p2->next; //从下一个结点开始数
if(j==n-1) break; //只剩一个结点时退出循环
}
printf("%3d",p2->num); //输出最后一个结点的序号
}

void PrintCode(int n) //打印链表每个结点的随机密码
{
int i=0, j=0;
struct people *p; //定义指向结构体的指针
p=head; //获得链表的头地址
for(i=0; i<n; i++) //顺序输出结点的密码
{
printf("%3d ",p->code);
p=p->next; //指针下移
j++;
if(j==20) //输出屏幕的控制
{
printf("\n");
j=0;
}
}
}