华北水利水电学院约瑟夫环 实验报告
2010～20##学年 第 一 学期 09 级 计算机科学与技术 专业
班级： 2009119 学号： 200911902 姓名： 万婷婷
一、 实验目的
要求设计一个程序模拟约瑟夫环问题过程，求出出列编号序列。
二、实验要求
1）利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
2）建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。
3）建立一个输出函数，将正确的输出序列
4）测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4
三、实验内容
基本算法以及分析：
本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下
typedef struct Node
{
int Index; 在当前环中所处的位置，即编号
int Password; 在当前环中的所带的密码
struct Node *next;
}JosephuNode;
程序有主函数开始，首先，提示输入创建约瑟夫环环数以及每个环上所带的密码。然后,利用单循环链表建立起约瑟夫环，p ->next = head->next;就是将最后一个结点的后继指向头结点的下一个结点， 然后主函数调用Josephu函数，并实现如下功能：
编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。
四、程序源代码
1．约瑟夫环问题
#include<iostream.h>
#include<malloc.h>
#include<stdio.h>
typedef struct LNode
{
int M;//当前出局人的编号
int Password;//当前出局人所带密码
struct LNode *next;
}JosephuNode;
void Josephu(int n,int m)
{
int i,j,password;
JosephuNode *head,*p,*q,*L;
head=p=(JosephuNode *)malloc(sizeof(JosephuNode));
for(i=1;i<=n;i++)
{
q=(JosephuNode *)malloc(sizeof(JosephuNode));
p->next=q;
q->M=i;
printf("请输入第%d号所带密码:", i);
scanf("%d",&password);
q->Password=password;
p=q;
}
p->next=head->next;
free(head);
L=q->next;
printf("出列者的编号顺序是：");
while(p!=L)
{
for(j=1;j<m;j++)
{
p=L;
L=L->next;
}
p->next=L->next;
printf("%d,",L->M);
m=L->Password;
free(L);
L=p->next;
}
printf("%d \n", p->M);
free(L);
}
void main()
{
int n,m;
printf(".............约瑟夫环问题..........\n");
printf("输入的n和m值不小于1：\n");
printf("请输入参加的人数n:");
scanf("%d",&n);
printf("请输入起始报数上限值m:");
scanf("%d",&m);
Josephu(n,m);
}
五、运行结果
六、小结（不少于100字）
通过这次实验，使我更加知道自己的不足和需要加强的地方，指针仍然是自己需要去加强巩固的地方。每次看到自己写的程序和网上的比较发现自己需要完善程序，而不只是编出而已，必须让自己的程序运行结果一目了然。数据结构让我感觉很有意思，让我没有了学习c语言和c++的茫然和烦恼，实验也很贴近每章学习的内容，很有效的巩固了我们的知识。
第二篇：约瑟夫环代码及实验报告
约瑟夫环问题实验报告
一、问题描述
设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。
二、需求分析
1、需要基于线性表的基本操作来实现约瑟夫问题
2、需要利用数组来实现线性表
3、测试用例
输入：10，3
输出：3 6 9 2 7 1 8 5 10 4
三、概要设计
抽象数据类型
为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。 算法的基本思想
利用数组来代表一个环，然后模拟报号出圈的过程，直到所有人都出圈。 程序的流程
程序由三个模块组成：
（1） 输入模块：完成两个正整数的输入，存入变量n和m中。
（2） 计算模块：计算这n个数的输出序列
（3） 输出模块：屏幕上显示这n个数的输出序列。
四、详细设计
程序代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int number;
int psw;
struct node *next;
}Lnode ,*Linklist;
void insert( Linklist * list , Linklist q , int e1 ,int e2 )
{
Linklist p;
p=( Linklist )malloc( sizeof( Lnode ) ); //给链表分配预存空间 p->number=e1;
p->psw=e2;
if(!*list)
{
*list=p; //如果链表为空，则就将 p作为头结点； p->next=NULL;
}
else
{
p->next=q->next; //插入节点 q
q->next=p;
}
}
void creat( Linklist *jsp ,int n )
{
Linklist q=NULL ;
Linklist list=NULL; int i,e; printf( "\n请输入每个人手中的密码：\n " ); for( i=0 ; i<n ;i++ )
{
scanf("%d",&e);
insert( &list ,q ,i+1 ,e );
if( i==0 ) //第一次生成头结点 ，指向p q=list;
else
q=q->next; //q指向下一个节点
}
q->next=list; //形成一个循环链表
*jsp = list;
}
void shuchu( Linklist *jsp , int m )
{
Linklist q,p;
int i;
p=q=*jsp;
while( q->next !=p )
q=q->next; //q 指向 p 的前一个节点
printf( "\n出列的人的顺序编号:\n" );
while( p->next !=p ) // 判断循环结束的标志
{
for( i=0;i<m-1;i++ )
{ //P 指向要删除的节点，q指向p的前一个节点 q=p;
p=p->next;
}
q->next = p->next; //删除 p 指向的节点
printf("%d ",p->number);
m=p->psw; //重新定义一个报数上限
free(p); //释放 节点 p
p=q->next; //指向下一个节点
}
printf( "\n\n最后有一个的序号为 %d \n",p->number ); //读出最后 一个数据
}
int main()
{
Linklist jsp;
int n ,m;
printf( "请输入约瑟夫环问题的人数：\n" );
scanf("%d",&n); //输入约瑟夫环问题的总人数
creat(&jsp , n);
printf("\n请输入初始最大的出列序号\n");
scanf("%d",&m);
shuchu( &jsp , m );
system("pause");
return 0;
}
物理数据类型
队列元素及出列序列都以整型数组方式存储
算法的具体步骤
（1） 将队列里的元素编号
（2） 循环访问数组元素
（3） 第一个元素从1开始报数，报数编号与出列编号相同时出列，并
将该元素置为0
（4） 下一个元素重新从1开始报数，依次循环
输入和输出的格式
输入格式：n，m
输出格式1：在字符界面上输出这n个数的输出序列
输出格式2：将这n个数的输出序列写入到文件中
五、实验心得该实验利用数组实现线性表，算法简便，但产生很多不必要的消耗，下一步可以尝试采用单链表，双链表实现该问题。